Алгебраические неассоциативные структуры и их приложения в криптографии Грибов Алексей Викторович

Содержание к диссертации

Введение

1 Квазигруппы, лупы и Г2-лупы: первичный радикал 11

1.1 Основные понятия и предварительные сведения 11

1.2 Коммутаторы в лупах, коммутант нормальных подлуп 19

1.3 Первичный радикал луп 24

1.4 Первичный радикал Г2-лупы 28

2 Альтернативные кольца: луповые кольца и лупы обратимых элементов 34

2.1 Альтернативные кольца 35

2.2 Альтернативные луповые кольца 37

2.3 Первичный радикал луповых колец 47

2.4 Первичный радикал лупы GLL(2, Л) 53

3 Криптографические схемы над неассоциативными структурами 57

3.1 Построение алгебраической криптосистемы над квазигрупповым кольцом 57

3.2 Гомоморфность криптографической системы над квазигрупповым кольцом 65

3.3 Схема Эль-Гамаля для квазигрупп с перестановочными степенями 68

3.4 Построение MQ - криптосистемы над альтернативной алгеброй 71

3.5 Криптосхемы на основе луп

3.5.1 Криптосхемы на основе луповых действий 74

3.5.2 Протокол выработки общего секретного ключа 78

3.5.3 Схема шифрования на основе покрытий лупы 81

Заключение 84

Приложение

• Коммутаторы в лупах, коммутант нормальных подлуп
• Первичный радикал Г2-лупы
• Первичный радикал луповых колец
• Гомоморфность криптографической системы над квазигрупповым кольцом

Введение к работе

Актуальность темы.

Диссертация относится к структурной теории неассоциативных структур, а именно к теории радикалов луп, луп обратимых элементов альтернативных луповых колец и Г2-луп. Приложения развитой техники использованы для построения криптографических схем.

При рассмотрении алгебраических систем одной из основных задач является построение структурной теории, которая сводит изучение к более простым системам. Одной из конструкций, осуществляющих такое сведение, является радикал. С тех пор, как в 1950-х гг. А.Г. Курош¹ и С. Ами-цур² ввели аксиоматическое понятие радикала для колец и алгебр, теория радикалов распространилась и на другие алгебраические структуры. Понятие радикала в теории групп окончательно сформировалось к началу шестидесятых годов в определении, предложенном А.Г. Курошем³. В это же время А.Г. Курош обратил внимание на аналогию между разрешимыми нормальными подгруппами и нильпотентными идеалами, позволившую К.К. Щукину построить теорию первичного радикала групп.

Описание первичного радикала группы как множества строго энгеле-вых элементов крайне близка к первичному радикалу в теории ассоциативных колец и алгебр. В связи с этим возник естественный вопрос о соотношении между первичным радикалом кольца с единицей и первичным радикалом подгрупп группы его обратимых элементов. Положительный ответ на него был получен А.В. Михалёвым и И.З. Голубчиком в их теореме о первичном радикале линейной группы над ассоциативным кольцом. В дальнейшем структурная теория первичного радикала алгебраических систем активно развивалась в работах^{5 6}.

В теории квазигрупп некоторые понятия, например, нормальность, производная и центр, хорошо сочетаются с обычными теоретико-групповыми определениями. Р. Брак⁷ показал, что обычные теоретико-групповые определения полностью корректны для луп Муфанг. Наиболее полно теория

¹А.Г. Курош, Радикалы колец и алгебр. Матем. сборы. 33, N.1, (1953), 13-26.

²S.A. Amitsur, A general theory of radicals II. Radicals in rings and bicategories. SAmer. J. Math. 76, N.l, (1954), 125-197.

³А.Г. Курош, Радикалы в теории групп. ДАН СССР. 141, N.4, (1961), 789-791.

⁴К.К. Щукин, RI*-разрешимый радикал групп. Матем. сборы. 52, N.4, (1960), 1021-1031.

⁵А.В. Михалев, И.Н. Балаба, С.А. Пихтильков Первичный радикал і\-групп. Фунд.приклад, матем. 12, N.2, (2006), 159-174.

^еА.Ю. Голубков, Первичный радикал групп над ассоциативными кольцами, дис.к.ф.-м.н. (2000)

⁷R. Brack, A survey of binary systems. Berlin: Springer-Verlag, (1958).

квазигрупп изложена в работе В.Д. Белоусова⁸, различные классы и свойства квазигрупп рассмотрены в работах М.М. Глухова⁹ ,Г.Б. Белявской¹⁰ и А.Х. Табарова¹¹.

Теория коммутаторов и нового, с точки зрения теории групп, понятия ассоциатора в значительной степени отличается от теоретико-группового случая. Теория коммутаторов в лупах развивается в работе Дж. Смита¹². В работе Р. Маккензи и Дж. Сноу¹³ теория коммутаторов в лупах рассмотрена с точки зрения коммутаторов конгруэнции лупы как универсальной алгебры. Именно с этой точки зрения П. Войтеховский и Д. Становский смогли вычислить взаимный коммутант нормальных подлуп.

Квазигруппы и латинские квадраты имеют богатую историю применений в криптографии. Достаточно полные обзоры использования квазигрупп в криптографии приведены в работе М.М. Глухова¹⁵, где применение квазигрупп рассмотрено для построения схем шифрования и однонаправленных функций, а также в работе В.А. Щербакова¹⁶. Основные результаты в этих работах получены для симметрической криптографии. Одной из первых работ, где использовались квазигруппы для криптографии с открытым ключом является работа С. Косельны и Г. Мюллена¹⁷.

С алгебраической точки зрения классические задачи в криптографии

рассматривались в конечнопорожденных и коммутативных группах

²⁰. Достаточно полно эти вопросы описаны в пособиях^{21 22}. Следующим

⁸В.Д.Белоусов Основы теории квазигрупп и луп. Москва: Наука, 1967.

⁹М.М. Глухов, Т-разбиения квазигрупп и групп. Дискрет.матем. 4, N.3, (1992), 47-56.

¹⁰Г.Б. Белявская, Ассоциаторы, коммутаторы и линейность квазигрупп. Дискрет.матем. 4, N.7, (1995), 116-125.

^ПА.Х. Табаров, Тождества и линейность квазигрупп, дис. д.ф.-м.н., 2009.

¹²J. Smith, On the nilpotence class of commutative Moufang loops. Math. Proc. Cambridge Philos. Soc. 84, N.3, (1978), 387-404.

¹³R. McKenzie, J. Snow, Congruence modular varieties commutator theory and its uses. Structural theory of automata, semigroups and universal algebras 207, (2005), 273-329.

¹⁴D. Stanovsky,P. Vojtechovsky, Commutator theory for loops. Journal of Algebra 399,(2014), 290-322.

¹⁵M.M. Глухов, О применениях квазигрупп в криптографии. Прикладная дискретная математика, 2, N.2, (2008), 28-32.

¹⁽³V.A. Shcherbacov, Quasigroups in cryptology. Comput. Sci. J. Moldova 17, N.2, (2009), 193-228.

¹⁷С Koscielny and G. L. Mullen, A quasigroup-based public-key cryptosystem,. Int. J. Appl. Math. Сотр. Sci., 9, N.4, (1999), 955-963.

¹⁸W. Diffie, M.E. Hellman, New directions in cryptography,. IEEE Transactions on Information Theory, 22, (1976), 644-654.

¹⁹R.L. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public key crypto systems,. Communications of the ACM, 21, (1978), 120-126.

²⁰T. ElGamal, A public key cryptosystem and a signature, scheme based on discrete logarithms,. IEEE Transactions on Information Theory, 31, (1985), 469-472.

²¹M.M.Глухов, И.А. Круглов, А.Б. Пичкур, А.В. Черемушкин, Введение в теоретико-числовые методы криптографии. Санкт-Петербург: Лань, 2011.

²²А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В.Черемушкин Основы криптографии . Москва:

шагом в развитии можно считать рассмотрение некоммутативных алгебраических структур и изучение в них вычислительно сложных задач. Одной из первых работ в некоммутативной криптографии является статья Н. Вагнера и М. Магийярика²³, где приведена схема, основанная на неразрешимости слова в конечно представленных группах (для данного представления группы G и элемента д Є G определить, выполняется ли условие д = 1.). Достаточно полное описание и изучение аспектов некоммутативной криптографии в группах приведено в монографии В. Шпильрайна, А. Мясникова, А. Ушакова ²⁴. В работах А.В. Михалева, В.Т. Маркова, А.А. Нечаева и др.^{25 26} исследованы некоторые возможности использования неассоциативных структур в криптографии с открытым ключом. В частности, была построена криптосистема над квазигрупповым кольцом, развивающая подход С.К. Россошека . Также можно выделить работу В.А. Романькова²⁸, посвященную алгебраическому анализу существующих подходов в некоммутативной и неассоциативной криптографии.

Гомоморфное шифрование позволяет производить определённые математические действия с зашифрованным текстом и получать зашифрованный результат, который соответствует результату операций, выполняемых с открытым текстом. В 2009 году К. Джантри²⁹. предложил модель, основанную на алгебраических решетках, полногомоморфной алгебраической системы, то есть гомоморфной для операций умножения и сложения (и других операций) одновременно.

Цель работы

Целью диссертационной работы является исследование: строения первичного радикала ряда неассоциативных структур: луп; Г2-луп; луповых колец; связей первичного радикала луп обратимых элементов с первичным радикалом неассоциативных колец; криптографических схем над раз-

Гелиос АРВ, 2011.

²³М. R. Magyarik and N. R. Wagner, A Public Key Crypto system Based on the Word Problem, -Lecture Notes in Computer Science, 196, (1985), 19-36.

²⁴A. Myasnikov, V. Shpilrain, A. Ushakov, Group-based Cryptography,.Birkb&user Basel, Berlin, (2008).

²⁵A.B. Грибов, П.А. Золотых, А.В. Михалёв, Построение алгебраической криптосистемы над квазигрупповым кольцом,.Математические вопросы криптографии, 4, N.4 (2010), 23-33.

^2еС.Ю. Катышев, В.Т. Марков и А.А. Нечаев, Использование неассоциативных группоидов для реализации процедуры открытого распределения ключей,.Дискрет, матем., 26, N.3 (2014), 45-64.

²⁷С.К. Росошек, Криптосистемы групповых колец. Вестник Томского госуниверситета, 6, (2003), 57-62.

²⁸В.А. Романьков, Криптографический анализ некоторых схем шифрования, использующий автоморфизмы. Мат.методы криптографии, 3, N.21 (2013), 35-51.

²⁹С. Gentry, A fully homomorphic encryption scheme,-Stanford University PhD thesis, (2009).

личными неассоциативными структурами; новых примеров гомоморфной криптографии.

Научная новизна

Результаты диссертации являются новыми и получены автором самостоятельно. Основные результаты диссертации состоят в следующем:

1. Развита теория первичного радикала лупы, исследованы его свойства, доказано его совпадение с множеством строго энгелевых элементов лупы.

2. Получено описание Г2-первичного радикала Г2-лупы, как множества ^-строго энгелевых элементов.

3. Установлены связи первичного радикала лупы обратимых элементов альтернативного кольца и первичного радикала кольца.

4. Построены криптографические схемы над различными неассоциативными структурами:

аналог схемы шифрования Эль-Гамаля над ППС-квазигруппой;

схема выработки общего секретного ключа над лупами Пейджа;

схема шифрования с открытым ключом на основе покрытий лупы Муфанг.

5. Рассмотрена схема шифрования с открытым ключом над луповым
кольцом, проанализированы свойства данной схемы, доказана гомо-
морфность данной схемы относительно одной из операций.

Основные методы исследования

В работе применяются методы и результаты теории ассоциативных и неассоциативных колец, теории квазигрупп, теории луповых колец и криптографии с открытым ключом.

Теоретическая и практическая ценность.

Работа имеет как теоретический, так и прикладной характер. Полученные в ней результаты могут быть использованы в различных задачах теории луп. Построенные криптографические схемы могут быть использованы при построении различных систем безопасности.

Апробация диссертации.

Результаты диссертации докладывались на следующих конференциях:

на семинаре "Algebra and Cryptography", Нью-Йорк, США, 2013 г.;

на конференции "New directions in cryptography", Москва, 12 июня 2014.

на конференции "Non-associative algebra and Lie theory", Оахака, Мексика, 26-30 января 2015.

на конференции "Индо - Российская конференция по алгебре, теории чисел, дискретной математике и их приложений", Москва, 15-17 октября 2014.

а также на следующих семинарах кафедры высшей алгебры механико-математического факультета МГУ:

на научно-исследовательском семинаре кафедры высшей алгебры, 2009-2015 гг., неоднократно;

на семинаре "Теория колец", 2009-2015 гг., неоднократно;

Публикации

Основные результаты диссертации опубликованы в работах, список которых приведен в конце автореферата [1] — [5]. Работы [1], [2] - из перечня ВАК.

Структура диссертации Диссертационная работа состоит из четырех глав. Текст диссертации изложен на 93 листах. Список литературы содержит 72 наименования.

Коммутаторы в лупах, коммутант нормальных подлуп

Замечание 1.58. Пусть {РІ],і Є І, - убывающая цепочка нормальных первичных подлуп лупы L. Тогда Г\РІ есть нормальная первичная подлупа. Согласно лемме Цорна, каждая первичная подлупа содержит минимальную первичную подлупу. Поэтому первичный радикал - это пересечение всех минимальных первичных подлуп.

Определение 1.59. Пусть (L, ) - лупа. Элемент а Є L называется строго энгелевым, если в любой последовательности ао, элементов лупы, L, удовлетворяющей условию ао = а}а,і+і Є [Ng(ai)}Ng(ai)}b, начиная с некоторого номера все элементы равны 1.

Данное определение согласуется с определением строго энгелевых элементов для групп (элемент g группы (G, ) называется строго энгелевым,, если в любой последовательности ?о5 элементов группы G, удовлетворяющей условию go = 9i9i+i [[hi9І]І9І] ДЛЯ всех 1{ Є G, начиная с некоторого номера все элементы равны 1). В случае, если G является группой, то множества [[G,g},g] и [Ng(g),Ng(g)}L совпадают [24], поскольку [[G,g],g] = [Ng(g),g] = [Ng(g),Ng(g)}.

Замечание 1.60. Если элемент аг из последовательности для строго энгелевых элементов принадлежит нормальной подлупе А лупы L, то все элементы этой последовательности а,И г г, содержатся в А. Рассмотрим еще одну нормальную подлупу В, пересекающуюся с последовательностю ao,ai,..., т.е. содержаищю начиная, с некоторого аа, все последуюище члены этой последовательности. Тогда все члены последовательности, начиная с at}t = max(r} s), содержатся в А П В.

Теорема 1.61. Первичный радикал rad{V) лупы (L,-) совпадает с множеством всех строго энгелевых элементов лупы.

Доказательство. Покажем сначала, что если элемент а лупы L не принадлежит первичному радикалу, то он не является сторого энгелевым. Пусть а ( rad(L), т.е. существует нормальная первичная подлупа Л такая, что а ( А. Тогда Ng(a) А Следовательно, образ нормальной подлупы Ng(a) в фактор-лупе L/A не является единицей: Ng(a) 1. Поэтому, согласно определению первичной лупы, [Ng{a),Ng{a)]i/A Ї. Значит [Ng(a)} Ng(a)]L А. Пусть ао = CL-, далее выберем элемент а\ Є [Ng(a)}Ng(a)]L \ А. Элемент а\ не принадлежит первичному радикалу rad(L). Продолжая процесс, построим необры-вающаюся последовательность ао, ai,..., где а Є [Ng(di-i), Ng{ai-i)\i. Таким образом, элемент а не является строго энгелевым.

Пусть теперь элемент а Є L не является строго энгелевым, тогда существует последовательность ао,аі,..., где а Є [Ng(di-i), Ng{ai-i)\i, все элементы которой отличны от единицы. Рассмотрим максимальную нормальную подлупу Р, не содержащую ни одного элемента данной последовательности. Пусть U, V - нормальные подлупы лупы L, строго содержащие подлупу Р. Ввиду максимальности подлупы Р, подлупы U, V пересекаются с данной последовательностью. Значит, начиная с какого-то натурального числа к выполняются условия (ik Є U П V . Таким образом, а& Є [U, V]L И коммутант [U,V]L/P не равен единичной подлупе Е. Тогда L/P - первичная лупа, и, следовательно, Р - первичная нормальная подлупа. Возникает противоречие с определением первичного радикала.

Доказательство. Пусть элемент а принадлежит радикалу лупы L/R, тогда этот элемент содержится в каждой первичной подлупе лупы L/R. Если элемент а лупы L/R отличен от единичного элемента, то элемент а лупы L не содержится в ее радикале R. Следовательно, в лупе L существует такая первичная нормальная подлупа Р, что а ( Р. Но факторлупа P/R является первичной нормальной подлупой лупы L/R, причем а не содержится в P/R. Это противоречит выбору элемента а. Таким образом, элемент а равен единице.

К определению первичного радикала лупы L можно прийти другим путем. Для этого обозначим через p(L) подлупу лупы L, порожденную всеми разрешимыми нормальными подлупами этой лупы. Построим теперь возрастающий ряд таких подлуп пользуясь следующим правилом pk+i(L)/pk(L) = p(L/pk+i(L)) и для предельного а берем Pa{L) = Ui3 aPi3(L). Пусть А - первое натуральное число, при котором рх(Е) = p\+i(L). Подлупу р\(Е) обозначим через rad(L) и назовем верхним радикалом лупы, L.

Теорема 1.63. Первичный радикал rad(L) лупы L совпадает с верхним радикалом rad(L) этой лупы. Доказательство. Лупа L/rad(L) не содержит, согласно теореме 1.62, нетривиальных разрешимых нормальных подлуп. Тогда из построения rad(L) следует, что rad(L) С rad(L). Пусть rad(L) С rad(L), тогда выберем элемент Ъ Є rad(L), но Ъ . rad(L). Ясно, что Ng(b) rad(L), тогда [Ng(b),Ng(b)]L rad(L). Следовательно, в лупе L существует такой элемент Ъ\ Є [Ng(b), Ng(b)]L, что Ъ\ ф rad(L), причем Ъ\ Є rad(L). Повторяя рассуждения для элемента Ъ\, построим необрывающуюся последовательность b = bo,b\,.. . элементов лупы L. Вся эта последовательность содержится Brad(L) и не пересекается с rad(L). Теперь рассмотрим максимальную нормальную подлупу Р, не содержащую ни одного элемента данной последовательности. Пусть U, V - нормальные подлупы лупы L, строго содержащие подлупу Р. Ввиду максимальности подлупы Р, подлупы U, V пересекаются с данной последовательностью. Значит, начиная с какого-то натурального числа к выполняются условия bk Є U П V . Таким образом, bk Є [U, V]L, И коммутант [U,V]L/P образов подлуп U, V в факторлупе L/Р не равен единичной подлупе Е. Тогда L/P - первичная лупа, и, следовательно, Р - первичная нормальная подлупа, причем rad(L) Ри rad(L) С Р. Возникает противоречие с определением первичного радикала.

Понятия операторных групп и Г2-группы используют аналогию между нормальными подгруппами группы и идеалами колец. В работах П. Хиггинса [38], А.Г. Куроша [16], Б. Брауна и Н. Маккоя [47] были отмечены различные свойства Г2-группы.

Р. Брак [27], Б. Браун и Н. Маккой [47] приводили примеры использования конструкций Г2-луп. Определение 1.64. Лупа (L, +) (не обязательно, коммутативная или ассоциативная) называется лупой с операторами или Q-лупой, если в L задана помимо сложения еще система п-арных алгебраических операций Q, причем для всех ш Є Г2 должно выполняться условие 00 ... 0ш = 0. Для удобства будем использовать для лупы (L, +) аддитивную запись; в частности, нулевой элемент этой лупы будет обозначаться символом 0.

При пустой системе операций Q мы получаем понятие лупы. С другой стороны, понятие Г2-лупы превращается в понятие кольца, если аддитивная лупа этой Г2-лупы коммутативна и ассоциативна (т.е. абелева группа), а система операций Q состоит из одного бинарного умножения, связанного со сложением законами дистрибутивности.

Первичный радикал Г2-лупы

Хорошо известна характеризация первичного радикала ассоциативного кольца R как множества всех элементов г Є R таких, что любая т - последовательность, начинающаяся с г, содержит нулевой элемент [43]. В работе М.Рича [56] была получена подобная характеризация неассоциативных s-колец (к s-кольцам, в частности, относятся все альтернативные и йордановы кольца).

Определение 2.1. Кольцо R (необязательно ассоциативное) называется s-колъцом, если для любого идеала А множество As сумм различных произведений элементов 2i,..., as Є А

Первичным радикалом s-кольца R называется пересечение всех его первичных идеалов. Основные свойства первичного радикала rad(R) s-кольца R приведены в работах [55], [63]. (см. [55], [63]). Пусть rad(R) - первичный радикал s-кольца R, тогда выполнены следующие условия: является пересечением всех идеалов Q в R таких, что R/Q не содержит ненулевых нилъпотентных идеалов. Будем обозначать через (а)д главный идеал кольца Л, порожденный элементом а Є R. Определение 2.4. Последовательность элементов { 2о, ai,..., an,...} из s-колъца R называется Р-последовательностью, если ап Є (an-i)sR для всех п. Элемент а Є R называется строго нильпотентным, если любая Р- последовательность, начинающаяся с а, содержит нулевой элемент.

В неассоциативной теории колец важное место занимают функции коммутатора и ассоциатора.

Определение 2.6. Коммутатором элементов а}Ь кольца (Л, ,+) называется элемент [a,b]R = ab — Ьа кольца R. Ассоциатором элементов а}Ь}с кольца R называется элемент [а, 6, с]д = (ab)c — а(Ьс) кольца R. Данные функции аддитивны (линейны для алгебр) по каждой переменной. Например, если а\, а 2, Ъ и с - элементы кольца Л, то [аі + 22, Ь, с]д = [а\, 6, с]д + [а.2, Ь, с]д, а если Л - алгебра над полем F и а Є F, то [ста, 6, с]д = а[а, 6, с]д. Определение 2.7. Кольцо R удовлетворяет левому альтернативному тождеству, если [x,x,y]R = 0 (и правому, если [y,x,x]R = 0 для всеж х}у Є R). Кольцо называется альтернативным, если оно удовлетворяет левому и правому альтернативным тождествам. Полезными являются понятия ядра и центра кольца. Определение 2.8. Ядром кольца (R, , +) называется множество N(R) = {z Є R\ [z, ж, y]R = [ж, z, y]R = [x, у, z]R = 0} для всех z,y Є R. Центром кольца (R, , +) называется множество Z(R) = {z Є R\[z}r]R = 0, [z, x,y]R = [ж, z, y]R = [ж, у, z]R = 0} для всех r,z,y Є Л.

Лемма 2.9 (см. [10]). Пусть R - кольцо (необязательно ассоциативное), тогда ядро и центр являются подколъцами. Доказательство. Пусть элементы а, Ь принадлежат идеалу А кольца Л, х - произвольный элемент из кольца R. Тогда (ab)x = [a,b,x]R + a(bx)} где [a, 6, x]R = (ab)x — a(bx), однако в альтернативных кольцах выполняется тождество [а,&, ж]д = — [а,ж, &]д (равенство (1) леммы 2.10 ). Значит, (ab)x = — {ах)Ь + а{хЬ) +а{Ьх) и каждое слагаемое принадлежит А2. Аналогично можно показать, что x(ab) Є А2.

Более того верна следующая теорема. Теорема 2.12 (критерий Артина, см. [10]). Кольцо R является альтернативным тогда и только тогда, когда подкольцо, порожденное любыми двумя элементами кольца R, является ассоциативным.

Рассмотрим вопрос об обратимых элементах альтернативного кольца. Элемент х Є R называется обратимым, если существуют элементы у, z, такие что ху = 1 = zx. Обозначим множество обратимых элементов кольца Л через U(R).

Для любого а Є R, используя опять равенства (3), (8) из леммы 2.10, имеем [x l,x,a]R = (xx l)[x l, x,a]R = x l(x[x l,x, a]R) = x l[x lx,x,a]R = 0. По теореме 2.12 Артина, элементы х}х и а порождают ассоциативную подалгебру алгебры R. В частноти, это показывает, что для обратимых элементов из уравнений ах = Ьх,ха = хЪ следует, что а = Ъ. А также получаем, что для любых а, Ъ Є R уравнения ах = b,xa = Ъ имеют единственное решение. Таким образом, подмножество U(R) замкнуто относительно умножения, и, значит, является лупой.

Далее, если х - обратимый элемент и [x,a,b]R = 0, то 0 = [x lx,a,b]R = x[x l,a,b]R + [x,a,b]Rx l = x[x l,a,b]R = 0, значит [x l,a,b]R = 0. Теперь пусть х,у - обратимые элементы n[x,y,xy]R = 0, тогда [x l,y,xy]R = 0 и [x l,y l,xy]R = 0. Таким образом, (xy)(y lx l) = 1. Это показывает, что если ж, у Є U(R), то элемент ху обратим и элемент у 1х 1 является его обратным. Лупа U(R) является лупой Муфанг, так как в альтернативном кольце R выполняется тождество Муфанг (равенство (6) из леммы 2.10).

Рассмотрим некоторые свойства первичных альтернативных колец. Напомним, что альтернативное кольцо (2-кольцо) R называется первичным, если (0)д является первичным идеалом кольца R. Теперь введем следующее определение.

Определение 2.14. Альтернативное кольцо R с ненулевым центром Z(R), не содержащим делителей нуля кольца R, называется кольцом Кэли-Диксона. В качестве примера кольца Кэли-Диксона можно рассмотреть алгебру ок-тонионов О над полем F. Каждый элемент алгебры О является линейной комбинацией базисных элементов Єо,Єі,...,Є7 Є О с коэффициентами из поля F. Причем, для базисных элементов имеется следующая таблица умножения:

Таким образом, относительно этих операций множество KL является неассоциативным кольцом с единицей (неассоциативной /С-алгеброй с элементами лупы в качестве базиса). Удобно отождествить / Є L с элементом 1 / Є KL, а а Є К с элементом а е, где е - единица лупы (тогда К и L будут являться подмножествами в KL).

Положим Н = {1,2}, тогда Н - подлупа лупы L и левыми смежными классами по Н являются следующие подмножества: \Н = {1,2}, 2Н = {1,2}, ЗН = {3,5},4Я = {3,4},5Я = {4,5}. Заметим, что ЗН П АН ф 0. Таким образом, (L, ) не имеет разложения на левые смежные классы.

Пусть (L, ) - лупа Муфанг, Н подлупа лупы L. Тогда KL является левым (правым) if Я-модулем. Причем, KL - свободный левый (правый) модуль, если L имеет разложение на левые (правые) смежные классы по Н. Лемма 2.19. Пусть Н - подлупа лупы My фанг L и а Є КН. Тогда элемент а обратим в КН тогда и только тогда, когда он обратим в KL. Более того, элемент а - правый (или левый) делитель нуля в КН тогда и только тогда, когда он правый (или левый) делитель нуля в KL.

Первичный радикал луповых колец

С. К. Росошек предложил в [21] криптосистему, все вычисления которой производятся в групповом кольце и в группе его автоморфизмов. Построим подобную криптосистему над неассоциативной структурой - квазигрупповым кольцом.

Пусть К - кольцо с единицей (необязательно ассоциативное), Q - квазигруппа. Рассмотрим квазигрупповое кольцо KQ, состоящее из всех формальных сумм вида 2qenCYq q (ск/ Є К), в которых конечное число aq отлично от нуля. Предполагаем, что группы автоморфизмов AutK и AutQ некоммутативны, причём \AutK\ ti, \AutQ\ 2, где t\ и Ї2 - параметры безопасности. Также предполагаем, что в KL достаточно элементов с нулевым левым аннулятором.

Рассмотрим следующую задачу. Пусть R - алгебраическая структура (например, кольцо или квазигруппа), А некоторое подмножество автоморфизмов в AutR, а - случайно выбранный элемент из А. Предположим, что известно некоторое множество пар yLii CxyXi) J, L 1,..., її, где Х{ Є R. Требуется найти автоморфизм а Є А, такой что а {х{) = а{х{) для всех і = 1,... ,п , а также o!{yj) = ot(jjj) для некоторых случайно выбранных у2 Є R,yj = %i,j = 1,... , т, і = 1,.. . , n, причем злоумышленнику не известны значения a(yj),j = 1,.. . ,m. Обозначим эту задачу как Q(A, R).

Заметим, что при отсутствии существенной информации о множествах А и R, задача Qn(A,R) является вычислительно трудной и разрешима полным перебором всех элементов множества А, и для каждого выбранного а Є А проверкой условия а!(хі) = а(х{),і = 1,. .. ,п и производных соотношений из этих условий.

Криптосистема имеет следующий вид: Участник А : 1. Конструирует такой автоморфизм а Є AutK, что \а\ t?,, причём а имеет нетривиальный централизатор С(а) и \С(а) \ (а)\ t , где з, 4 -параметры безопастности. 2. Конструирует такой автоморфизм ту Є AutQ, что \r)\ t$, причём ц имеет нетривиальный централизатор С{г\) и \С{г\) \ {т])\ ta, где 5, 6 - параметры безопастности. 3. Случайно выбирает автоморфизм г Є С (а) \ (а). 4. Случайно выбирает такой ш, что ш Є С(г)) \ (г)). 5. По гиш строит автоморфизм ер Є AutKQ (назовем его секретным автоморфизмом) так: для любого h Є KQ вида

Отметим, что при должных параметрах безопасности з5 4 5 6 автоморфизмов, подходящих для открытого ключа, достаточно много. Сформированный открытый ключ участник А передает участнику В по открытому каналу.

Получив криптограмму, участник А расшифровывает её: 1. Используя секретный автоморфизм р , вычисляет ір[х{а) ф{х)). 2. Расшифровывает посланный текст пользуясь тем, что Хі гр и ср коммутируют, поскольку сеансовые автоморфизмы гр,х построены на степенях выбранных автоморфизмов т, Г], а секретный автоморфизм р) построен с помощью элементов из централизаторов т, Г]. Участник А знает т ср[х(а) Ф(х)) = h и ср(рх(а) Ф(х)) = г - следовательно, для получения сообщения т достаточно решить линейную систему т г = h с коэффициентами из кольца К.

В самом деле, так как т Є С (а) \ (а) и со Є С(г)) \ (г)), то коммутируют между собой попарно автоморфизмы г и т; со и г]. Поэтому коммутируют и сконструированные на их основе автоморфизмы р) и гр, р) и х- Вследствие этого x((f(o )) гр{р){х)) = р)(х{а) Ф(х)) = Q- Кроме того, элемент х( р(а)) Ф( р(х)) выбран с нулевым левым аннулятором. Поэтому система уравнений m q = h с коэффициентами из кольца К имеет единственное решение.

Анализ атак на криптосистему Рассмотрим некоторые атаки на криптосистему. 1. Атака только с криптограммой. Пусть злоумышленник располагает открытым ключом участника А и криптограммой. Перед ним стоит следующая задача: по известным парам (а, ср(а)), (х,ср(х)) найти такой а Є AutKQ, индуцированный автоморфизмами (а , г) ), что ср{а) = а(а), ср{х) = а(х). К тому же необходимо, чтобы а Є С (а) \ (а), а rf Є С(г]) \ (г]).

Наличие у злоумышленника не одной криптограммы, а некоторого множества криптограмм, не позволяет упростить задачу. В этом случае злоумышленник обладает некоторым подмножеством элементов г І Є KQ и соответствующими уравнениями из которых ему необходимо найти сообщение: ті ср(гі) = hi, не зная автоморфизм р .

Попробуем построить автоморфизм а для этого случая. Положим а(а) := ср(а), а(х) := ср{х). Доопределим его на элементах ах и ха: а(ах) = а (а) а(х) := ср(а) ср(х) и а(ха) = а(х) а(а) := ср(х) ср(а). Но значение автоморфизма а на элементе х(а) Ф{%) так же должно совпадать со значением автоморфизма ср на этом же элементе. Данную проблему можно решить перебором образа а с последующей проверкой того, что о Є С (а) \ (и), а т/ Є С(ту) \ (г]). Но это вычислительно не легче перебора всех автоморфизмов, индуцированных парами (а , ту ) Є (С (а) \ ( т)) х (О(ту) \ (ту)), удовлетворяющих начальным условиям а (а) = (р(а) и а:(ж) = (р(х). В итоге получаем задачу Ql(Y, KQ), где У - это множество автоморфизмов KL, полученных с помощью пар

Атака на сеансовые автоморфизмы ф и х Другой способ атаки - найти автоморфизмы ф и %, а затем решить относительно т уравнение т х((/?(а)) ф((р(х)) = h, где h известен из криптограммы. Пусть ф был построен с помощью автоморфизмов ( 7і, туї), а автоморфизм \ с помощью {(Т2-,щ)- Для того чтобы найти ф и %, крип-тоаналитику придется перебрать пары (статуї) Є (( т), (ту)) и (о"2,ту2) Є (( т), (ту)) с последующей проверкой условия х(а)Ф(х) = h\, где h\ известен из криптограммы. Произведение найденных автоморфизмов должно совпадать с произведением искомых на элементах (р(а),(р(х). Следовательно, определенная выше сложность атаки будет равна t\ Ц. При правильном выборе соответствующих параметров безопасности эта задача является вычислительно трудной.

Поясним, почему для построения сеансового автоморфизма рассматривался не один автоморфизм, а выбрано произведениех(а)Ф(х)- В случае единственного автоморфизма открытый ключ участника - это: ( т, ту, ж, (р(х а криптограмма - (ф(х),т ф(ір(х)). В этом случае стали бы возможны следующие атаки:

Эта атака основана на попытке злоумышленника получить х( р(а)) ф((р(х)) Є KL с последующим решением уравненияш-х(( (а)) (( (ж)) относительно т посредством нового сеанса связи с участником В в качестве участника А. Даже если участник В повторяет тот же исходный текст т, то он должен сконструировать новые сеансовые автоморфизмы гр j гр и х Ф Х- Поэтому злоумышленник получит неш-х((/?(а)) ((/?(ж)), а т-Х/((/9(а)) /((/9(ж)). И даже если он решит новое уравнение относительно Xі\p(a))ip ((р(х)), никакой новой информации относительнох((/?(а)) ((/?(ж)) он не получит. Таким образом, злоумышленник может только накапливать значения автоморфизма ср на различных прообразах. Однако при правильно выбранных параметрах безопасности и своевременном обновлении секретного ключа данная атака вычислительно трудна.

Гомоморфность криптографической системы над квазигрупповым кольцом

Работа Диффи и Хеллмана [30] в 1975 году положила начало криптографии с открытым ключом. В данной работе предложен алгоритм выработки общего ключа, и этот алгоритм решал важную проблему криптографии того времени - распределение ключей.

В оригинале проткола использовалась мультипликативная группа G целых чисел по модулю р, где р является простым числом и д - порождающий элемент группы G. 1. Алиса выбирает случайное число а и посылает Бобу да. 2. Боб выбирает случайное число Ь и посылает д Алисе. 3. Алиса вычисляет К А = {дЪ)а = дЬа. Боб вычисляет KB = (ga)b = даЬ Так как ab = Ьа, тогда Алиса и Боб имеют один и тот же элемент группы К = К A = Kg, который называется общим ключом.

Отметим, что в протоколе Диффи-Хеллмана вычисления проходят в коммутативной группе. Следующим этапом развития данного протокола является работа Е. Стикела [62]. Алгебраической структурой в этом протоколе является некоммутативная конечная группа G.

Замечание 3.16. Знания одного из секретных чисел достаточно для получения секретного ключа. Действительно, пусть злоумышленник каким-либо образом получил число т, тогда, сделав следующие вычисления: {а тщ) = bk, b kU2 = cn,((amVi)bk)(bk(v2Cn))= К злоумышленник получает секретный ключ К.

Поэтому стойкость протокола не превышает сложности нахождения одного секретного ключа. Замечание 3.17. Злоумышленник для нахождения ключа может решить задачу дискретного логарифмирования в подгруппе a}b С L или 6,с С L, либо найти элемент лупы, который является общим ключом.

Порядки данных элементов равны {q — 1)/2 Использование неассоциативных структур находит свое оправдание в следующем примере. В работе [50] рассмотрена атака на протокол Стикела в группе обратимых (кхк) - матриц с использованием линейной алгебры. Атака сводится к решению системы уравнений: где a,b,u известные матрицы, а ж,у - неизвестные (к х к) - матрицы над F2 . Для того, чтобы получить линейную систему была использована обратимость искомых матриц. Обозначим за Х\ = х 1 матрицу обратную к х. После некоторых преобразований система примет следующий вид:

Конструкция легко может быть обобщена на произвольную квазигруппу, если умножение на у 1 справа в алгоритме расшифрования заменить на правое деление. Замечание 3.22. Любое [з}г]-покрытие можно представить в виде матрицы a = (ttjj), где dij L,l i s,l j r. Тогда, с практической точки зрения, [з}г]-покрытие удобно задавать случайной (s х г)-матрицей с проверкой необходимых условий. Заключение

В диссертации рассмотрена теория коммутаторов и ассоциаторов квазигрупп и луп. Развита теория первичного радикала лупы, исследованы его свойства, доказано его совпадение с множеством строго энгелевых элементов лупы и с верхним радикалом этой лупы. Получено описание Г2-первичного радикала Г2-лупы, как множества -строго энгелевых элементов. Установлены связи первичного радикала лупы обратимых элементов альтернативного кольца и первичного радикала кольца.

Построены криптографические схемы над различными неассоциативными структурами: - аналог схемы шифрования Эль-Гамаля над ППС-квазигруппой; - схема выработки общего секретного ключа над лупами Пейджа; - схема шифрования с открытым ключом на основе покрытий лупы Му-фанг. Построена также схема шифрования с открытым ключом над луповым кольцом, проанализированы свойства данной схемы, доказана гомоморфность данной схемы относительно одной из операций.

Работа имеет как теоретический, так и прикладной характер. Полученные в ней результаты могут быть использованы в различных задачах теории луп. Построенные криптографические схемы могут быть использованы при построении различных систем безопасности. Приложение

Ниже приведен исходный код в системе GAP [37]. Результатом выполнения являются параметры t\—t для криптосистемы на основе автоморфизмов луповых колец. Данные параметры позволяют определить возможность применения выбранных алгебраических структур на практике.