Алгебраические неассоциативные структуры и их приложения в криптографии тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

ФГБОУ ВО МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М. В. ЛОМОНОСОВА

На правах рукописи

Грибов Алексей Викторович

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

Специальность 01.01.00 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

11 авг т

Москва 2015

005561443

Работа выполнена на кафедре высшей алгебры Механико-математического факультета ФГБОУ ВО "Московский государственный университет имени М. В. Ломоносова".

Научный руководитель: Михалёв Александр Васильевич

доктор физико-математических наук, профессор

Официальные оппоненты: Кожухов Игорь Борисович,

доктор физико-математических наук, профессор кафедры высшей математики ФГБОУ ВПО "Национальный исследовательский университет "МИЭТ";

Голубков Артем Юрьевич,

кандидат физико-математических наук, доцент факультета прикладной математики и информатики

ФГБОУ ВПО "Московский государственный технический университет им. Н.Э.Баумана".

Ведущая организация: ФГБОУ ВПО "Тульский государственный

педагогический университет имени Л.Н.Толстого'

Защита диссертации состоится 25 сентября 2015 г. в 16 ч. 45 мин. на заседании диссертационного совета Д 501.001.84 на базе ФГБОУ ВО "Московский государственный университет имени М.В. Ломоносова", по адресу: 119991, Москва, ГСП-1, Ленинские горы, д. 1, ФГБОУ ВО "Московский государственный университет имени М.В. Ломоносова", Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВО "Московский государственный университет имени М.В. Ломоносова" по адресу: Москва, Ломоносовский проспект, д. 27, сектор А, http://mech.math.msu.Su/~ snark/index.cgi, http://istina.msu.ru/dissertations/9607776.

Автореферат разослан 25 августа 2015 г.

Учёный секретарь

диссертационного совета

Д 501.001.84 на базе

ФГБОУ ВО МГУ имени М.В. Ломоносова

доктор физико-математических наук,

профессор Александр Олегович Иванов

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

С алгебраической точки зрения классические задачи в криптографии рассматривались в конечнопорожденных и коммутативных группах18 19 20. Достаточно полно эти вопросы описаны в пособиях21 22. Следующим

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

шагом в развитии можно считать рассмотрение некоммутативных алгебраических структур и изучение в них вычислительно сложных задач. Одной из первых работ в некоммутативной криптографии является статья Н. Вагнера и М. Магийярика23, где приведена схема, основанная на неразрешимости слова в конечно представленных группах (для данного представления группы G и элемента д G G определить, выполняется ли условие д = 1.). Достаточно полное описание и изучение аспектов некоммутативной криптографии в группах приведено в монографии В. Шпильрайна, А. Мясникова, А. Ушакова 24. В работах A.B. Михалева, В.Т. Маркова,

A.A. Нечаева и др.25 26 исследованы некоторые возможности использования неассоциативных структур в криптографии с открытым ключом. В частности, была построена криптосистема над квазигрупповым кольцом, развивающая подход С.К. Россошека27. Также можно выделить работу

B.А. Романькова28, посвященную алгебраическому анализу существующих подходов в некоммутативной и неассоциативной криптографии.

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

Цель работы

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

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

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

24A. Myasnikov, V. Shpilrain, A. Ushakov, Group-based Crypiojmpftji, .Birkhauser Basel, Berlin, (2008).

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

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

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

57-62.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации

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

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

Основное содержание работы

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

В главе 1 в разделе 1.1 определяются основные понятия, терминология, принятая при изложении, и вспомогательные утверждения.

В разделе 1.2 излагается понятие коммутанта нормальных подлуп и приводятся порождающие множества этого коммутатнта. Пусть (L, •) -лупа, тогда можно дополнительно рассматривать операции \, / такие, что х\{х/у)=у\ х-(х\у) = у; (у-х)/х = у; (у/х) ■ х = у. Для каждого х € L определим биективные отображения LX,RX,MX : G —>■ G:

Lx{y) = ХУ> Rx(y) = ух, Mx(y) = у \ х, у € G. Далее определим биективные отображения

Lx,y = LXyLxLy, Rx,y = R~yRxRy, Мхл = М~~}МХМУ.

Следующее утверждение описывает взаимный коммутант нормальных подлуп.

Следствие 1.49. Пусть L - лупа, А, В - нормальные подлупы лупы L, тогда

[A,B]l = Ng([a,b}L, [b,a,x]L,wUuU2(a)/wVuV2(a) : w € {L,R,M},a 6 A,be B,Ui/vi € B,x € L),

Причем,

1) если L - IP-лупа, mo

[A, B]L = JVp([a, b]L, LUuU2(a)/LVuVi(a) :aeA,beB, щ/vi 6 B);

2) если L - коммутативная лупа, то

[A, B]i = Ng(wUuU2(a)/wVuV2(a) : w e {L,Ai},a € А,щ/у{ € B);

3) если L - группа, mo

[A, B]L =< [a, 6]i : a 6 A,b 6 В > .

где Ng(X) - наименьшая нормальная подлупа, содержащая множество X.

В разделе 1.3 вводится понятие первичного радикала лупы и строго энгелева элемента.

Определение 1.54. Лупа (L, ■) называется первичной, если для любых ее двух нормальных подлуп А, В из равенства [A, B]i — Е следует, что либо А = Е, либо В = Е, где Е - единичная подлупа лупы L.

Определение 1.59. Пусть (L, •) - лупа. Элемент а е L называется строго энгелевым, если в любой последовательности <zo, aj,... элементов лупы L, удовлетворяющей условию ао — а,(ц+1 £ [Ng(a,i),Ng(ai)]L, начиная с некоторого номера все элементы равны 1.

Основным результатом этого раздела является:

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

В разделе 1.4 получено описание первичного радикала fi-лупы. Лупа (L, +) (не обязательно, коммутативная или ассоциативная) называется лупой с операторами или П-лупой, если в L задана помимо сложения

еще система п-арных алгебраических операций О,, причем для всех и £ £1 должно выполняться условие 00... Ош = 0. Идеал Р в П-лупе Ь называется П-первичным, если для любой операции ш Е П и любых идеалов /ь ...,/„ С £ из включения (Д,..., /п)си С Р следует, что С Р для некоторого 3 = 1,2,..., п. Пересечение всех Г2-первичных идеалов П-лупы Ь называется первичным радикалом 0,-гай(Ь) лупы Ь. Обозначим через {а}1, идеал Г2-лупы Ь, порожденный элементом а € Ь. Подмножество М О-лупы Ь называется П-т-системой, если для любой операции и> любых элементов аь ..., а„ 6 М существуют а- € {а;}1", такие что а^ ... а'пш € М. Теперь каждому элементу о € Ь поставим в соответствие подмножество Ма С Ь, которое получается следующим образом: Ма = и»Д-, где

А0 = а,А1 = иделЛ'.Аг Л:.л - = ...а'^^шх},

где и>\ - п-арная операция, 6 а,^,..., а,¿п - всевозможные

наборы по п элементов из А{.

Основной результат:

Теорема 1.72. Пусть а 6 Ь, где Ь ■ 0,-лупа, тогда эквивалентны следующие условия:

1) а е Г1-гай{Ь);

2) любая П-т-система, содержащая элшент а, содержит 0;

3) любая С1-т-система Ма, соответствующая элементу а, содержит

0,

В начале главы 2 излагается описание первичного радикала неассоциативных в-колец и показываются некоторые его свойства (в частности, его совпадение с множеством строго нильпотентных элементов е-кольца).

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

Теорема 2.13. Пусть Я - альтернативное кольцо с единицей, тогда множество обратимых элементов и(Н) является лупой Муфанг.

Также рассмотрены различные свойства первичных альтернативных колец.

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

Определение 2.20. Лупа Ь для которой луповое кольцо КЬ, где К - коммутативное и ассоциативное кольцо с единицей и с/гагК ф 2,

является альтернативным неассоциативным кольцом называется RA-лупой.

Будем называть упорядоченную тройку элементов лупы (а, Ь, с) неассоциативной, если равенство ассоциативности не выполняется для этих элементов (т.е. а(Ьс) ф (аЪ)с). Соответственно, упорядоченная тройка (а, Ь, с) ассоциативна, если а(Ьс) = (ab)c.

Теорема 2.21. Jlyna L является RA-лупой тогда и только тогда, когда выполняются следующие условия:

1. если какие-либо элементы лупы ассоциативны в нектором порядке, то они ассоциативны в любом другом порядке;

2. если элементы a,b,c € L неассоциативны, то а ■ Ъс = ас- b = с - ab;

В разделе 2.3 исследовано строение первичного радикала лупы обратимых элементов альтернативного кольца. Основной результат:

Теорема 2.38. Если R - альтернативное кольцо с единицей, то для любой подлупы L лупы U (R) выполняется включение L П Z(R, rad R) С radL.

В разделе 2.4 получено описание первичного радикала лупы обратимых элементов альтернативного кольца GLL(2, R) (неассоциативный аналог теоремы A.B. Михалева и И.З. Голубчика). Основным результатом этого раздела является:

Теорема 2.40. Пусть К - комм,утативное и ассоциативное кольцо с единицей, Z(K) - кольцо матриц Цорна и GLL(2, К) - лупа обратимых матриц из Z{K), тогда rad GLL(2,K) = Z(Z(K),rad Z{K)).

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

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

Пусть К - кольцо с единицей (необязательно ассоциативное), Q -- квазигруппа, KQ - луповое кольцо.

Участник А :

1. Конструирует автоморфизмы а 6 AutK,r] е AutQ, такие что |<т| > ¿3) Ы > h, причем выполняются следующие условия на централизаторы |С(ег) \ <сг>| > U и \С(г}) \ (77)1 > i6, где t3,U,t5,t6 - параметры безопастности.

2. Случайно выбирает автоморфизмы т е С (а) \ (и) и и? 6 С(г)) \ {г/).

3. Погиш строит секретный автоморфизм<р £ АгйКО так: для любого

/г € Л'<3 вида /г = а,,^ Н-----Ь аЯпдп, пусть <р(Л) = т(аЯ1)и(д 1) -I-----Ь

т(аЯп)ш(дп).

4. Выбирает элементы а е КС},х € Л'ф и вычисляет (¿>(2:) и Открытым ключом участника А является:

Участник В:

1. Выбирает натуральные числа (г. 3, к, I) и с помощью пар автоморфизмов {а1,г]Э),{ак,т}1) строит сеансовые автоморфизмы </>, х б АиЬКС^.

2. Вычисляет (х(а) • Ф(х), х(</'(а)) • Ф{р(х)) 11 левый аннулятор Апп(хЫа)) -ф{ф))).

3. Записывает исходный текст, который надо передать, в виде тп € КЬ и вычисляет тп ■ |х(^(а)) • .

4. Отправляет для А криптограмму

Получив криптограмму, участник А расшифровывает её:

1. Используя секретный автоморфизм <р, вычисляет <^(х(а) ■ Ф{х)).

2. Расшифровывает посланный текст пользуясь тем, что^, ф и ¡р коммутируют, поскольку сеансовые автоморфизмы ф. х построены на степенях выбранных автоморфизмов <т, 77, а секретный автоморфизм <р построен с помощью элементов из централизаторов для а, г].

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

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

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

Благодарности

Автор выражает глубокую благодарность своему научному руководителю д.ф.-м.н., профессору Александру Васильевичу Михалёву за выбор темы исследования, постановки задач и внимание к работе. Автор благодарен к.ф.-м.н., доценту Виктору Тимофеевичу Маркову за многочисленные советы и обсуждения работы. Автор приносит благодарность профессору Михаилу Михайловичу Глухову за ценные советы. Автор благодарен всему коллективу кафедры высшей алгебры за внимание к работе.

Работы автора по теме диссертации

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

[2] А. В. Грибов, П. А. Золотых, В. Т. Марков, А. В. Михалёв, С. С. Ска-женик. Квазигруппы и кольца в кодировании и построении крипто-схем. Прикладная дискретная математика4, (2012), 31-52. А. В. Грибову принадлежат разделы 1 и 3.

[3] А. В. Грибов, А. В. Михалёв, Первичный радикал для луп и il-луп: I. Фундамент, и прикл. мат. 19, N. 2, (2014), 25-42.

А. В. Грибову принадлежат доказательсва основных результата-тов работы. А. В. Михалёву принадлежит постановка задач и общая редакция работы.

[4] А. В. Грибов, Гомоморфность некоторых криптографических систем на основе неассоциативных структур. Фундамент, и прикл. мат. 20, N. 1, (2015), 55 62.

[5] А. В. Грибов, Первичный радикал для альтернативных колец и луп Фундамент, и прикл. мат. 20, N. 2, (2015), G3-82.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж ¡00 экз. Заказ №¿5"