<<

стр. 3
(всего 3)

СОДЕРЖАНИЕ


||Dnvs|| = ||Dnvs|| < ||Dn||||vs|| < Cs||Dn||o ||vs|| <
< Cs||Ds||n ||vs|| = cs7s"||vs||, (9)
где Ys = ||Ds||0 < 1. Аналогично,

||D"v"|| > c„7-n||v"||, 0 <7и < 1. (10)
Неравенства (9) и (10) означают, в частности, выполнение усло­вий (5) и (6) гиперболичности линейного расширения в.
Предположим, что подрасслоения Es и Eu не являются непре­рывными.
Лемма 5. Пусть векториальное множество Es разрывно в точке x0 G Мд. Существуют такие Ks > 0, K„ > 0, что для любой окрест­ности UXo найдется сечение v G Lp(E), v = 0, suppv С UXo, для кото­рого справедливы неравенства: ||vs|| < Ks||v"||, ||v"|| > K„||v||.
Доказательство. Разрывность Es в точке x0 означает, что суще­ствует d > 0, что для любого е > 0 в любой окрестности UXo можно выделить два подмножества положительной меры V и V2, такие, что 3?о GEX0 : Vx G V2 3G Ex, где ||?о|| = ||Cx|| = 1 и

||Со - Cx||x < е, (11)

||Cx - h||x >d, Vh GEx. (12)
Если в качестве h взять ?Х, то падучим ||Cu||x > d. Определим сече-v( x)
, , f Cx, x G V2,
v( x) =

Имеем:
i

WW = I / \\v(x)\\pdp = [p(V2)]p,

IKH > d[p(v2)]i = d\\v\\>d\\\vs\\- IKHI > d(ikii - IKH),

122
откуда
|Кц<^+1|Кц.
Таким образом, Ks = ^ ˜t , Ки = d. Лемма доказана.
d
Продолжим доказательство теоремы. Пусть
, , Г Со, x G U V2,
К ' \ 0, x G {xo}U V2
a v(x) — сечение из леммы 2.2. Фиксируем е > 0 и достаточно боль­шое n G N, чтобы | |вп(Со) | |an(x) < е. Окрестность Uxo можно выбрать настолько малой ( Uxo = Uxo (е, n) ), что

|| Ь(ап(х)) ¦ ... ¦ Y(a(x))]-?Vnv(an(x))-
-Ыап(х)) ¦ ... ¦ Y(a(x))]-LPVnu(an(x))\\aHx) < е
и
|| Ь(ап(х)) ¦ ... ¦ 7(a(x))]-il?nU(an(x)) - РЧШ^х) < е.
Тогда
|| Ь(ап(х)) ¦ ... ¦1(o.(x))]-bvnv(on(x))\\aHx) < < || Ыап(х)) ¦ ... ¦ 7(a(x))]-il?"M(a"(x))|U„(x) +е < < ПвЧ&ОПа-м + 2е < 3е.
V2 .
|Р%|| = | J || |7К(х)) • ... • 7(а(х))]-^%(а"(х))|Г^ | < Оф(У2)]* =3e|M|,
откуда

||Dnv|| < 3е||v||. (13)

Используя (9), (10) и лемму 1.6, получаем

||Dnv|| > ||D"v"|| - ||Dnvs|| > c„7-n||v"|| - cs7s"||vs|| >

123
> (cul-n - \\vu\\> (cudn-n - ca(d+ l)7sn) |M|. (14)
Сравним неравенства (13) и (14):
c„d7-n - cs(d +1)7" < 3е. (15)
В последнем неравенстве константы cs, c„ и d не зависят ни от
, n, n
противоречие. Значит, векториальные множества Es и ?" непрерыв­ны и являются подрасслоениями. Теорема доказана.

[1] Антоневич А. В. Линейные функциональные уравнения. Опера­торный подход. Мн.: Университетское, 1988.
[2] Бронштейн И. У. Неавтономные динамические системы. Кишинев: Издательство "Штиинца", 1984.
[3] Нитецки 3. Введение в дифференциальную динамику. М.: Мир, 1975.^304 с.
[4] Abramovich Y. A., Arenson Е. L., Kitover А. К. Banach C(K) — modules and operators preserving disjointness. England, Longman Scientific and Technical, 1992.

УДК 517.98
Топология интегрируемого случая Стеклова на
so(4)
X. Хоршиди
Московский государственный университет им. М. В. Ломоносова
В работе исследуется топология интегрируемой гамильтоновой системы, заданной уравнениями Эйлера для алгебры Ли so(4). Га­мильтониан и интеграл этой системы — квадратичные функции.
В работе [1] доказано что для алгебры Ли so(4) существуют лишь два интегрируемых случая, для которых гамильтониан и дополни­тельный интеграл квадратичны. Эти интегрируемые случаи явля­ются аналогами классических интегрируемых случаев Стеклова и Клебша в динамике твердого тела. Случай Клебша на so(4) иссле­дован в работе [2].
Здесь рассматривается интегрируемый случай уравнений Эйлера на so(4)*, являющийся компактным аналогом классического инте­грируемого случая Стеклова на e(3)*.

124
Построены бифуркационные диаграммы отображения момента, и доказаны следующие утверждения.
Предложение 1. Бифуркационные диаграммы отображения мо­мента, в случае Стеклова на so(4)*, состоят из объединения двух частей параметрической кривой с тремя отрезками. Концевые точки этих отрезков являются пересечениями отрезков либо друг с другом либо с кривой.
Рассматриваемая система зависит от нескольких параметров. При разных значениях параметров получаются качественно различ­ные бифуркационные диаграммы.
Предложение 2. Всего при различных значениях параметров си­стемы может быть 10 видов бифуркационных диаграмм.
[1] Веселое А. П. Об интегрируемости уравнений Эйлера на алгебре so(4). ДАН СССР. - 1983. - 270, №6. - 1298-1300.
[2] Ошемков А. А. Вычисление инвариантов Фоменко для основных ин­тегрируемых случаев динамики твердого тела. — В кн.: Труды семина­ра по векторному и тензорному анализу. Вып. 25, часть 2. — М.: МГУ, 1993. - 23-109.

УДК 123.45
О криптосистемах, использующих группы кос М. В. Шеблаее
Московский государственный университет им. М. В. Ломоносова
Введение. В 2001 году в работе [1] был предложен подход к построению асимметричной криптосистемы, использующей некото­рые задачи комбинаторной теории групп. Авторы рассмотрели за­дачи определения сопряженности и поиска сопрягающего элемента в группе кос Артина Bn как основу для построения односторонней функции, которая легла в основу этой криптосистемы.
В данной статье мы рассмотрим потенциально уязвимые места этой криптосистемы и опишем некоторые классы ключей, примене­ние которых снижает стойкость системы.
Основные понятия и определения.
Определение 1. Группа кос Артина Bn - конечно порожденная группа с множеством порождающих элементов (cti, ..., <rn_i} и мно­жеством определяющих соотношений вида
= °j°"i> I* - j| > 1 (!)
oWi+iCi = o"i+iO"iO"i+i- (2)

125
Гарсайд и Фурстон показали, что любой элемент b группы Bn может быть единственным образом представлен в некотором кано­ническом виде, представление может быть найдено за O(|b|2nlog2 n) шагов, где |b| означает длину слова b в алфавите {а^1}^1 и тем са­мым нашли эффективное решение проблемы эквивалентности слов. Будем говорить, что элементы х и y ЕЕ Bn сопряжены, если суще­ствует такой элемент а ЕЕ Bn, что y = аха_1.
Определение сопряженности Пусть задана пара (х, y) ЕЕ Bn х Bn Требуется определить, являются ли х и y сопряженными или нет.
Поиск сопрягающего элемента Пусть задана пара (х, y) ЕЕ Bn х Bn такая, что х и y сопряжены. Требуется найти а ЕЕ Bn такое, что y = аха-1
На сегодняшний день известные алгоритмы, предназначенные для решения задачи поиска сопрягающего элемента, недалеко ушли от последовательного перебора всех возможных ключей.
Криптографический протокол, использующий задачу по­иска сопрягающего элемента.
Пусть два абонента A и B желают установить защищенный об­мен информацией. Рассмотрим две подгруппы группы Bn, извест­ные обеим сторонам: SA =< s1, s2,..., sk > и SB =< t1,t2, ...,?; >, где si, 1 ^ i ^ k и tj, 1 ^ j ^ l - порождающие элементы, опубли­кованные в открытом доступе. Определим сопрягающую функцию в : B„ х B„ — Bn как в(х, y) = х^ух.
Из определения сопрягающей функции следует мультипликатив-
ность по второму аргументу, т.е. в(х, y1y2) = в(х, У1.)в(х, y2). Эта
функция формирует основу криптосистемы. Рассмотрим функции
71 : Bn х Bn — Bn = v_xu yl 72 : Bn х Bn — Bn, 72k v) =
Заметим, что 71(х,в(у,х)) = 72(y, в(х, y)). Алгоритм:
1) Абонент A выбирает секретное слово а ЕЕ ?д, Боб выбирает слово b ЕЕ SB соответственно.
AB ва, сопряженные порождающим элементам Sb с помощью а: а^^а, а_1?2а, .. ., а^^а
BA ва, сопряженные порождающим элементам Sa с помощью b: b-1S1b, b-1S2b,..., b-1sfcb
4) Абонент A знает слова b_1s1b, b-1s2b,..., b-1skb и а, кроме то­го абонент A знает слово а, поэтому возможно вычисление

126
e(b, а) Аналогично абонент B может вычислить в(а, b). 5) Теперь абоненты могут вычислить открытые ключи для ис­пользования: Ka = 71(а, e(b, а)) = а_1b_1аb = [а, b], Kb = 72(b, в(а, b)) = в(а, b)b = a_1b_1ab = [а, bj. Тем самым оба абонента имеют ключ, который может быть использован для установления защищенного соединения.
Для дешифрования сообщений криптоаналитик, располагающий только перехваченной перепиской, должен решить задачу поиска со­прягающего элемента, не имеющей эффективного алгоритма для ре­шения.
Слабые классы ключей.
Утверждение 1. Пусть х,у ЕЕ Bn, X =< х >С Bn - циклическая
Bn х
верки y Ее X может быть решена за время 0(тах(|х|, |y|)2nlog2 n)
х Е Bn
да х = a^1 ... . Заметим, что величина 5_^П=о kn> которую далее будем называть логарифмом этого элемента, является инвариантной для данного слова относительно сопряжения. Кроме того, для какой-
х
ется на показатель этой степени. Логарифм элемента может быть
| х|
?
Тогда для проверки y ЕЕ X нужно найти логарифмы /ж = log х и ly = log y. Есл и log х| log y не выполняется, то y не принадлежит
X. В противном случае потребуется проверить, что х1^ = у. Возве­дение в степень - простая конкатенация п под слов, которая в свою очередь может быть выполнена за logo -г- шагов, проверка равенства выполняется алгоритмом Гарсайда - Фурстона за полиномиальное время.
Утверждение 1 позволяет сделать сразу два вывода:
• Убедиться в том, что что какая-либо из групп Sa или SB, фор­мирующих секрет, является циклической, можно за время, яв­ляющееся полиномом от длины s$ и tj соответственно.

группе - они также могут быть найдены за полиномиальное время.
Рассмотрим гомоморфизм F : Bn — GL(Z[tj,n), задаваемый сле­дующим образом:
Каждому порождающему элементу a j сопоставим матрицу над Z [tj

127





V
1

Можно показать, что при таком определении отображения выпол­няются определяющие соотношения группы кос. Это линейное пред­ставление группы кос получило название представления Бурау.
Известно, что при n ^ 5 данное представление является неточ­ным, т. е. ядро гомоморфизма нетривиально. Пусть Sa и Sb таковы, что KerF П SA = e и KerF П Sb = e Тогда задачу поиска х тако­го, что выражение а = х_1Ьх можно переписать в матричном виде как XA = BX для матриц, являющихся образами соответствующих элементов группы кос.
Заметим, что из определения гомоморфизма следует, что матри­ца X Л B невырождены. Тем самым мы получили систему линей-Z[tj
дена к диагональному виду. Тогда задача превращается в решение методом неопределенных коэффициентов задачи поиска коэффици-n
| х|
F
KerF П Sa = e и KerF П Sb = e. Тогда секретный ключ может быть найден за полиномиальное время.
[1] Anshel I., Anshel М., Fisher В., Goldfield D. New Key Agreement Protocol in Braid Group Cryptography (Lecture Notes in Computer Science, 2020). — Springer Berlin, 2001.











128

<<

стр. 3
(всего 3)

СОДЕРЖАНИЕ