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

• Автор: Грибов, Алексей Викторович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Москва
• Количество страниц: 93 с.

Содержание
Введение

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

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

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

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

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

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

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

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

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

2.4 Первичный радикал лупы СЬЬ{2, Я)
3 Криптографические схемы над неассоциативными структурами
3.1 Построение алгебраической криптосистемы над квазигрупповым кольцом
3.2 Гомоморфность криптографической системы над квазигрупповым
кольцом
3.3 Схема Эль-Гамаля для квазигрупп с перестановочными степенями
3.4 Построение - криптосистемы над альтернативной алгеброй .
3.5 Криптосхемы на основе луп
3.5.1 Криптосхемы на основе луповых действий
3.5.2 Протокол выработки общего секретного ключа
3.5.3 Схема шифрования па основе покрытий лупы
Заключение
Приложение

Введение
При рассмотрении алгебраических систем одной из основных задач является построение структурной теории, которая сводит изучение к более простым системам. Одной из конструкций, осуществляющих такое сведение, является радикал. С тех пор, как в 1950-х гг. А.Г. Курош [13] и С.Амицур [26] ввели аксиоматическое понятие радикала для колец и алгебр, теория радикалов распространилась и на другие алгебраические структуры. Понятие радикала в теории групп окончательно сформировалось к началу шестидесятых годов в определении, предложенном А. Г. Курошем [14]. В это же время А. Г. Курош обратил внимание на аналогию между разрешимыми нормальными подгруппами и нильпотентными идеалами, позволившую К. К. Щукину [24] построить теорию первичного радикала групп.
Описание первичного радикала группы как множества строго эпгелевых элементов крайне близка к первичному радикалу в теории ассоциативных колец и алгебр. В связи с этим возник естественный вопрос о соотношении между первичным радикалом кольца с единицей и первичным радикалом подгрупп группы его обратимых элементов. Положительный ответ на пего был получен А. В’. Михалёвым и И. 3. Голубчиком в их теореме о первичном радикале линейной группы над ассоциативным кольцом. В дальнейшем структурная теория первичного радикала алгебраических систем активно развивалась в работах [17], [8].
В теории квазигрупп некоторые понятия, например, нормальность, производная и центр, хорошо сочетаются с обычными теоретико-групповыми определениями. Р. Брак [27] показал, что обычные теоретико-групповые определения полностью корректны для луп Муфанг. Наиболее полно теория квазигрупп изложена в работе В.Д. Белоусова [2], различные классы и свойства квазигрупп рассмотрены в работах М.М. Глухова [5], Г.Б. Белявской [3] и А.Х. Табарова [23].
Теория коммутаторов и нового, с точки зрения теории групп, понятия ассоциатора в значительной степени отличается от теоретико-группового случая. Теория коммутаторов в лупах развивается в работе Дж. Смита [61]. В работе Р. Маккензи и Дж. Сноу [48] теория коммутаторов в лупах рассмотрена с точки зрения коммутаторов конгруэнций лупы как универсальной алгебры. Именно с этой точки зрения П. Войтеховский и Д. Стаповский [66] смогли вычислить взаимный коммутант нормальных подлуп.
Квазигруппы и латинские квадраты имеют богатую историю применений в криптографии. Достаточно полные обзоры использования квазигрупп в криптографии приведены в работе М.М. Глухова [6], где применение квазигрупп

рассмотрено для построения схем шифрования и однонаправленных функций, а такеже в работе В.А. Щербакова [59]. Основные результаты в этих работах получены для симметрической криптографии. Одной из первых работ, где использовались квазигруппы для криптографии с открытым ключом является работа С.Косельны и Г.Мюллена [41].
С алгебраической точки зрения классические задачи в криптографии рассматривались в конечнопорожденных и коммутативных группах [30], [57], [31]. Достаточно полно эти вопросы описаны в пособиях [7], [1]. Следующим шагом в развитии можно считать рассмотрение некоммутативных алгебраических структур и изучение в них вычислительно сложных задач. Одной из первых работ в некоммутативной криптографии является статья Н.Вагнера и М. Магий-ярика [45], где приведена схема, основанная на неразрешимости слова в конечно представленных группах (для данного представления группы G и элемента g € G определить, выполняется ли условие $ =1.). Достаточно полное описание и изучение аспектов некоммутативной криптографии приведено в монографии
В.Шпильрайна, А.Мясникова, А.Ушакова [50]. В работах A.B. Михалева, В.Т. Маркова, A.A. Нечаева и др. [68], [12] исследованы некоторые возможности использования иеассоциативных структур в криптографии с открытым ключом. В частности, была построена криптосистема над квазигрупповым кольцом, развивающая подход С.К. Россошека [21]. Также можно выделить работу В.А. Ро-манькова [20], посвященную алгебраическому анализу существующих подходов в некоммутативной и неассоциативной криптографии.
Гомоморфное шифрование позволяет производить определённые математические действия с зашифрованным текстом и получать зашифрованный результат, который соответствует результату операций, выполняемых с открытым текстом. В 2009 году К.Джантри [32] предложил модель, основанную на алгебраических решетках, полпогомоморфной алгебраической системы, то есть гомоморфной для операций умножения и сложения (и других операций) одновременно.
Цель работы
Целыо диссертационной работы является исследование: строения первичного радикала ряда неассоциативных структур: луп; fi-луп; луповых колец; связей первичного радикала луп обратимых элементов с первичным радикалом неассо-циативиых колец; криптографических схем над различными неассоциативными структурами; новых примеров гомоморфной криптографии.
Научная новизна
Результаты диссертации являются новыми и получены автором самостоя-

2.1 Альтернативные кольца
В неассоциативной теории колец важное место занимают функции коммутатора и ассоциатора.
Определение 2.6. Коммутатором элементов а,Ь кольца (Я, •,+) называется элемент [а, Ь]ц — аЬ — Ьа кольца Я. Ассоциатором элементов а,Ь,с кольца Я называется элельент [а, Ь, с]д = (аЪ)с — а(Ьс) кольца Я.
Данные функции аддитивны (линейны для алгебр) по каждой переменной. Например, если 01,02, бис - элементы кольца Я, то [а + йг, Ь, с]д = [01, Ь, с]д + [02, с]я, а если Я - алгебра над полем Я и а 6 Я, то [ста, Ь, с]д = а [о, Ь, с]д.
Определение 2.7. Кольцо Я удовлетворяет левому альтернативному тождеству, если [ж, х, ул = 0 (и правому, если [у,х, ж]д = 0 для всех х, у €Е Я).
Кольцо называется альтернативным, если оно удовлетворяет левому и правому альтернативным тождествам.
Полезными являются понятия ядра и центра кольца.
Определение 2.8. Ядром кольца (Я, -,+) называется множество N (Я) =
{г е Я[г,х,уя = [х,г,уц = [х,у,г]д = 0} для есеж г,у е Я.
Центром кольца (Я, •,+) называется множество К{Я) = {г 6 Я|[г, г]д =
0, [2, ж, у]д = [ж, г, у]д = [ж, у, г]д = 0} для есеж г, г, у € Я.
Лемма 2.9 (см. [10]). Пусть Я - кольцо (необязательно ассоциативное), тогда ядро и центр являются подкольцами.
Приведем используемые свойства коммутатора и ассоциатора.
Лемма 2.10 (см. [34]). Пусть Я - альтернативное кольцо, тогда для всех х, у, г € Я выполнены следующие тождества:
(1) [ж, у, г1{ = -[х,г,у]д;
(2) [ж, у, ж]д = 0;
(3) [ух, х, г]н = ж[у, ж, г]д;
^ ((жу)ж)2г = ж(у(ж;г));
(5) {(ху)г)у — х{у(гх));
(6) (ху)(гх) = (ж(уг))ж;
(7) [ж,п]д[ж, у, г]д = 0, для есеж п € АД Я).
(жу)[ж, у, Дд = у(ж[ж, у, г]д);
Лемма 2.11. Пусть Я - альтернативное кольцо, тогда Я является 2-колъцом.
Доказательство. Пусть элементы а, Ъ принадлежат идеалу А кольца Я, ж - произвольный элемент из кольца Я. Тогда (аб)ж = [а, 6,ж]д + а(6ж), где