Конечные геометрии и их связь с совершенными шифрами тема автореферата и диссертации по математике, 01.01.04 ВАК РФ

0134603738

На правах руюписи

Коновалова Светлана Сергеевна

КОНЕЧНЫЕ ГЕОМЕТРИИ И ИХ СВЯЗЬ С СОВЕРШЕННЫМИ ШИФРАМИ Специальность 01.01.04 - геометрия и топология

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

Екатеринбург - 2010

1 О И ЮН 2010

004603730

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Уральский государственный университет путей сообщения».

Научный руководитель: доктор физико-математических наук

Титов Сергей Сергеевич

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

Падучих Дмитрий Викторович

кандидат физико-математических наук Пудовкина Марина Александровна

Ведущая организация: Государственное образовательное учреждение

высшего профессионального образования «Уральский государственный университет им. А.М. Горького»

Защита диссертации состоится 15 июня 2010 г. в 15 часов на заседании диссертационного совета Д 004.006.03 в Институте математики и механики УрО РАН по адресу: 620219, г. Екатеринбург, ул. С. Ковалевской, 16.

С диссертацией можно ознакомиться в научной библиотеке Института математики и механики УрО РАН (г. Екатеринбург, ул. С. Ковалевской, 16).

Автореферат разослан \ Д. мая 2010 г.

Ученый секретарь диссертационного совета, д-р физ.-мат. наук, профессор

В.В. Кабанов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Совершенный шифр по Шеннону - это абсолютно стойкий шифр, стойкий к пассивным атакам по шифртексту. Эндоморфный шифр - это шифр, для которого \Х\=Щ=\К], где X, У, К- множества открытых текстов, закрытых текстов и ключей соответственно. Эндоморфный совершенный шифр задаётся уравнением зашифрования у=х*к, где уеУ, хеХ, кеК, «*» - операция умножения в некоторой квазигруппе. Все предполагаемые открытые тексты, соответствующие зашифрованному сообщению, в этом случае являются равновероятными. Операция расшифрования - это операция правого деления в квазигруппе: х=у/к. В 80-90-е годы 20-го века появилось понятие современных аналогов совершенных шифров, стойких к активным атакам (например, имитации и подмены сообщения). Подробное изложение теории совершенных шифров дается в1'2, где указываются актуальные проблемы, связанные с решением сложных математических задач; развиваемые в диссертации методы конечных геометрий показали свою эффективность при решении таких задач.

Объект исследования - конечные геометрии (конечные плоскости, плоскости Мёбиуса), рассматриваемые в приложении к классическим линейным совершенным шифрам и их современным аналогам.

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

Цель исследования - решение проблем в области конечных геометрий, связанных с развитием теории совершенных шифров.

Поставленная цель достигнута путем решения следующих задач:

1) установление взаимосвязи теории совершенных шифров с теорией конеч-

1 Зубо», А. Ю. Совершенные шифры. - М.: Гелиос АРВ, 2003. - 160 с.

2 Зубов, А. Ю. Крштгографические методы защиты информации. Совершенные шифры : учебное пособие. - М. : Гелиос АРВ, 2005. -192 с.

ных плоскостей;

2) приложение геометрического метода: решение трех проблем о трех конструкциях линейных совершенных шифров, поставленных западными криптографами (в том числе классиком криптографии J. Massey) в 1987 году, и уточнение классификации классических линейных совершенных шифров через их геометрическую интерпретацию;

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

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

Научная новизна. Все основные результаты работы являются новыми.

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

Апробация результатов. Основные результаты диссертации докладывались автором на конференциях [1, 3, 6, 8, 12, 13, 15, 19-21], в том числе на международной научной конференции по проблемам безопасности и противодействию терроризму и общероссийской научной конференции «Математика и безопасность информационных технологий» (Москва, ИПИБ МГУ, 2005,2007-2009 гг.); международной научной «X Белорусской математической конференции» (г. Минск, БГУ, 2008 г.); молодежной школе-конференции «Проблемы теоретической и прикладной математики» (Екатеринбург, ИММ УрО РАН, 2005, 2007, 2010 гг.). А также -на XI международной конференции «РусКрипто» (Москва, 2009 г.); научно-практической конференции студентов, аспирантов и молодых ученых «Безопасность информационного пространства» (Екатеринбург, 2005 г.; Тюмень, 2007 г.);

IX научно-практической конференции молодых специалистов «Автоматизация. Инновация. Качество» (г. Нижний Тагил, 2010 г.); межвузовской научной конференция «СПИСОК» (Екатеринбург, УрГУ, 2009 г.); межвузовской научно-технической конференции «Молодые ученые - транспорту» (Екатеринбург, 2005, 2007,2010 гг.); на научном семинаре кафедры «Прикладная математика» УрГУПС. Всего сделаны доклады на двадцати конференциях различного уровня.

Публикации. Основные результаты диссертации опубликованы в работах [1-24], в том числе [9] - в издании, входящем в перечень рекомендованных ВАК РФ. В публикациях, выполненных совместно с научным руководителем, научному руководителю принадлежат постановка задач и общее руководство исследованиями, а соискателю - получение и оформление результатов.

Структура и объем диссертации. Диссертация состоит из введения, четырёх глав, заключения, списка литературы из 44 наименований. Объем диссертации составляет 93 страницы.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

В первой главе излагается необходимый теоретический материал.

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

При создании криптографических примитивов и реализации шифрующих алгоритмов предпочтительнее использовать совершенные шифры с лучшими алгебраическими свойствами (например, таким как линейность). В линейном совер-

3 Глухо», М. М. О примененное квазигрупп в криптографии / М М. Глухо» // Прикладная дискретная математика. -№ 2(2). - 2008. — С. 2&-33.

шеннам шифре умножение в квазигруппе линейно по х, а X и У - это множества ненулевых векторов в конечномерном пространстве над конечным полем. В билинейном совершенном шифре умножение в квазигруппе обладает свойством линейности еще и по ключу. В 4 предложены три конструкции линейных совершенных шифров и поставлены три задачи об этих конструкциях; в 5 они также приведены как нерешенные, сложные и актуальные.

Конструкция 1 задается формулой зашифрования у=х*к=хМк, где у, х, к — векгора, Мк - ключевая матрица, строки которой - последовательные отрезки линейной рекуррентной последовательности (ЛРП), задаваемой примитивным многочленом; Конструкция 2: у=х-к, где у^е0р(д)\{0}, «-»-операция умножения в СД^). Конструкция 3 (задает мультипликативный шифр)'. у'=х'-к\ где х'=хА, к'=кВ, у'=уО, А, В, С - невырожденные матрицы над конечным полем, задающие изотопию.

Задача 1. Является ли совершенный билинейный шифр, построенный с помощью конструкции 1, мультипликативным шифром?

Задача 2. Является ли любой совершенный билинейный шифр мультипликативным шифром?

Задача 3. Является ли любой совершенный линейный шифр билинейным шифром?

В диссертации одним из вариантов решения задачи 3 является следующая Теорема 2.1. Любая нелинейная по ключу к изотопия мультипликативной группы поля дает пример линейного, но не билинейного совершенного шифра.

Действительно, уравнение зашифрования линейного, но не билинейного совершенного шифра можно представить каку=х*к=х~Лк), теДк) - любая нелинейная биекция по ключу поля СР(д) на себя, «•» - операция умножения в СДд). Так, можно заменить операцию зашифрования операцией расшифрования: у=х/к. Поэтому естественно глубокое изучение свойства линейности и билинейности шифров, что привело к созданию геометрической методики и полному решению всех

4 Massey, J. Non-expanding, key minimal, robustly-perfect, linear and bilinear ciphers / J. Massey, U. Maurer, M. Wang // Proceedings «Advances in Cryptology» of Crypto'87. -1987. - P. 237-247.

! Зубов, А. Ю. Совершенные шифры / А.Ю. Зубов. - M.: Гелкос АРВ, 2003. - 160 с.

трех задач.

Решение задачи 2 основано на наблюдениях 2.1-2.2 (здесь наблюдение -доказанное утверждение, главную роль в котором играет нахождение его формулировки).

Наблюдение 2.1. Набор матриц М* приводит к линейному совершенному шифру тогда и только тогда, когда «ЭДЛ/,. - Л/,- ] * О ЛЮ§Ь1Х ненулевых ключей к'Фк". Наблюдение 2.2 Построение линейного совершенного шифра эквивалентно построению конечной (аффинной) плоскости типа Веблена-Веддербёрна с уравнениями прямых вида у = х *к+( = х

Наблюдение 2.2 в диссертации является основой геометрической методики исследования совершенных шифров, позволившей перенести область исследования совершенных шифров в область теории конечных плоскостей. С помощью теоремы Алберта6 показано, что примером билинейного немультипликативного шифра является шифр, построенный в таком частном случае системы Веблена-Веддербёрна (КЖ-системы), задающей недезарговы плоскости, как полуполя, не сводящиеся к полям7 (например, полуполе Алберта и полупале Д. Кнута), т.е. доказана

Теорема 23 Существуют билинейные немультипликативные совершенные шифры.

В силу дезарговости конечных плоскостей малых порядков имеет место Утверждение 2.1. Все билинейные двумерные и трехмерные совершенные шифры над полем из двух элементов мультипликативны.

Наблюдение 2.2 применено и для решения задачи 3: в диссертации доказана Теорема 2.4. Любая система Холла приводит к двумерному над данным полем линейному, но не билинейному совершенному шифру.

Система Холла7 - это частный случай КЖ-системы, задающей недезаргову конечную плоскость. Уравнение зашифрования в системе Холла: у=х*у=хМк, где х=(х0^1), у=(УйУ]), ключ £=(Аг0,£|) - ненулевые двумерные вектора над конечным полем, Мк - матрица Холла. В этой квазигруппе есть двусторонняя единица При матрица Мк зависит от коэффициентов характеристического многочлена мат-

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

7 Ходд, М. Комбинаторика. - М.: Мир, 1970. - 424 с.

рицы и нелинейна по ключу ввиду деления одного из ее элементов на часть ключа ki.

Доказанная в работе теорема 2.5 является решением задачи 3 в более сильной формулировке: является ли любой совершенный линейный шифр билинейным в соответствующем представлении множества ключей? Теорема 2.5. Линейный совершенный шифр на основе системы Холла не сводится к билинейному шифру никакой изотопией по ключу.

Решение задачи 1. На основе предложенной в диссертации геометрической методики векторное пространство степеней сопровождающей матрицы характеристического многочлена ЛРП изоморфно вложено в векторное пространство всех строк по первой строке матрицы, и таким образом конструктивно доказана Теорема 2.6. Конструкция I задает мультипликативный шифр с уравнением зашифрования вида у = и-k, где и -хМе.

В результате не только дан ответ на вопрос, поставленный в задаче 1, но и явно указан изоморфизм: матрицы В и С, задающие линейную изотопию, равны единичной, яА= М„ где Ме - матрица на основе ЛРП с единичным ключевым вектором е=(1,0,0,...,0). В дополнение к теореме 2.6 замечено, что найденная изотопия приводит конструкцию 1 к мультипликативному шифру не только для примитивного, но и для любого неприводимого характеристического многочлена ЛРП.

В третьей главе с использованием геометрического метода второй главы исследуются такие современные аналоги совершенных шифров, как эндоморфные U(L)- и 0(/,)-стойкие шифры с минимальным числом ключей; приводятся их конструкции для 1=2, L=3; устанавливается взаимосвязь между такими типами шифров.

Классические совершенные шифры связаны с современными их аналогами, т.к. являются и (/(1)-, и 0(1)-стойкими. Так, ЩЦ-стойкий шифр (от слова Unordered) соответствует классическому комбинаторному объекту - перпендикулярному массиву РАш{Ь,\дх). Минимальность числа ключей достигается при ю=1. L - параметр стойкости шифра. {/(2)- и 0(2)-стойкие линейные шифры задаются уравнениями зашифрования у=хМк+€, где ключ - пара (к, €). По аналогии с наблюдением 2.1 в диссертации сформулированы наблюдения 3.1-3.2.

Наблюдение 3.1. Набор матриц Л/* приводит к линейному 0(2)-стойкаму шифру тогда и только тогда, когда ~ * " для любых ненулевых ключей к'Фк". Наблюдение 3.2. Набор матриц Мк приводит к линейному Щ2)<тойкому шифру тогда и только тогда, когда «к^Л/^ ±Мк- для любых ненулевых ключей к'фк"-

Для 0(2)-стойких шифров доказанная в диссертации теорема 3.1 - аналог наблюдения 2.2 (тоща геометрически к- наклон прямой, / -ее начальная ордината). Теорема 3.1. Построение эндаморфного линейного 0(2)-стойкого шифра с минимальным числам ключей равносильно построению конечной аффинной плоскости. Теорема 3.5. Если имеется эндоморфный линейный Щ2)-стойкий шифр, то существует У1У-система с квазигруппой по умножению, которая допускает такую инволюцию ин(-и), что (-х)т=х(-т). И наоборот, если имеется 0(2)-стойкий эндоморфный шифр, соответствующий М¥-системе, то в нем можно выделить 1/(2)-стойкий подшифр, когда квазигруппа по умножению в ЮУ-системе допускает такую инволюцию.

Теорема 3.5 устанавливает взаимосвязь 4(2)- и 0(2)-стойких шифров; указанная инволюция геометрически означает отражение графика функции относительно оси абсцисс. В работе доказаны и важные частные случаи теоремы 3.5.

Для группового шифра с минимальным числом ключей свойство 0(1)-стойкости эквивалентно свойству точно ¿-транзитивности. Классическим примером 0(3)-стойкого шифра является представление его дробно-линейными функциями над полем С/Д^), составляющими точно 3-транзитивную группу РСЬ{2,ц). Не все виды дробно-линейных функций задают шифр, обладающий свойством 0(3)-стойкости; нетривиальность этой задачи подтверждает Утверждение 3.12. Шифр на основе формулы зашифрования у=(х+<1)\ (хМа+Ь), где Ь, аевР(32), аевР*(32), Ша, Ма - матрица Холла, для которой /(х) =х2+2х+2 — характеристический многочлен, не является 0(3)-стойким.

Другим примером точно ¿-транзитивных групп являются группы Матьё8. Группа Матьё Ми задает 0(5)-стойкий шифр, ее подгруппа А/ц - 0(4)-стойкий

* Зубов, А. Ю. Совершенные шифры / А.Ю. Зубов - М.: Гелиос АРВ, 2003. - 160 с.

9

шифр. Больше нетривиальных примеров точно ¿-транзитивных групп с ¿>3 неизвестно (и в предположении правильности классификации простых конечных групп доказано, что их и нет). Анализируя подстановки, порождающие группы Матьё, в Мп найдена подгруппа, изоморфная почти-полю К(9), что дает недезар-гову конечную плоскость и соответствующий 0(2)-сгойкий шифр, а также ее расширение - подгруппа, соответствующая 0(3)-стойкому шифру. Почти-поле К(рО, не сводящееся к полю9,10 — частный случай Fff-системы, все ненулевые элементы в нем образуют группу, р- простое число, г- натуральное число. В диссертации также доказаны:

Утверждение 3.13. В почти-пале К(р2), приводящем к эндоморфному 0(2)-стойкому шифру, при рФ2 выделяется эндаморфный Щ2)-стойкий подшифр. Утверждение 3.14. Совершенный шифр, соответствующий группе ненулевых элементов в почти-поле К(9), является линейным, но не билинейным.

По аналогии с построением О(3)-стойких шифров из 0(2)-стойких в группах Матьё путем добавления инволюции а(х)*= 1/х, дана геометрическая конструкция О(3)-стойкого шифра на основе дробно-линейных функций в почти-полях: Теорема 3.7. Уравнение зашифрования 0(3)-стойкого шифра может быть задано в любом почти-поле К(рг)ь>{<х>} дробно-линейными функциями вида

х, d = co; j

1 f причем ~ - операция деления в поле GF(pr),

y=h(x+d)ok+€, где h(x) = ■ операция «о» - умножение в почти-поле К(рТ).

X

' Zassenhaus, H. Uber endliche Fastkoiper / H. Zassenhaus // Abh. Math. Sem. Hamburg. - 1936. - Р. 187-220.

10 Холл, M. Комбинаторика i M. Холл. - M.: Мир, 1970. - 424 с.

Полученные в главах 2-3 результаты отображены на рис. 1.

Рис. 1. Конечные плоскости и 0(Ь)-стойкие шифры

В четвертой главе рассматривается плоскость Мёбиуса и ее обобщение в виде £-{ц,Х,ст)-схем для построения неэндоморфных ЩЬУ и 0(1)-стойких шифров.

Плоскость Мёбиуса" порядка ц является частным случаем такой известной комбинаторной конструкции как Ь-((л,Х,о)-схема (£, ц, X соответствуют параметрам массивов и при £=3, ц^+1, Х=ц+\. В 12 указано на возможность построения современных аналогов совершенных шифров на основе Ь-(ц,Х,о)-схем. В диссертации для построения неэндоморфных шифров на основе плоскости Мёбиуса доказана

Теорема 3.9. Если множество элементов каждого цикла плоскости Мёбиуса взято за множество открытых текстов массива РАЮ(ЗХ^), то объединение всех таблиц зашифрования для всех циклов является массивом РАШ(3,Х,М)-Доказана и аналогичная теорема для 0(Х)-стойких шифров; предложены

11 Картесиф. Введение в конечные геометрии: Пер. с ант. -М.: Наука. Гл. ред. физ.-маг. лит., 1980. -320 с.

ц Зубов, А. Ю. Совершенные шифры / А.Ю. Зубов - М.: Гелиос АРВ, 2003. - 160 с.

и обоснованы другие геометрические методы построения неэндоморфных шифров.

В заключении сформулированы выносимые на защиту результаты.

Основные результаты диссертации

1) установлена взаимосвязь конечных плоскостей типа Веблена-Ведцербёрна с классическими линейными эндоморфными совершенными шифрами и с линейными <9(2)-стойкими шифрами с минимальным числом ключей;

2) развит геометрический метод и решены три проблемы о трех конструкциях линейных совершенных шифров с использованием недезарговых плоскостей;

3) применены конечные плоскости со специфическими свойствами (системы Холла, почти-поля, не сводящиеся к полям), а также плоскости Мёбиуса к построению линейных совершенных шифров и их современных аналогов, дана геометрическая интерпретация таких шифров;

4) установлена взаимосвязь групп Матьё и почти-полей, не сводящихся к полям, между собой, а также взаимосвязь между линейными 0(2)- и 1/(2)-стойкими шифрами через наличие инволюции.

Автор выражает глубокую признательность своему научному руководителю С.С. Титову, а также заведующему кафедрой «Прикладная математика» УрГУПС С.П. Баутину. За внимание к работе автор выражает благодарность: Ященко В.В. -1-му заместителю директора ИПИБ МГУ; Глухову М.М. - академику Академии криптографии РФ; Харину Ю.С. - чл.-кор. HAH Беларуси; Махнёву A.A. - чл.-кор. РАН; Пудовкиной М.А. - директору ассоциации «РусКрипто»; Аресто-ву В.В. - председателю правления Уральского математического общества.

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

[1] Коновалова, С. С. Три задачи о трех конструкциях совершенных шифров / С.С. Коновалова, С.С. Титов // Проблемы теоретической и прикладной математики : тр. 36-й регион, молодежной конф. - Екатеринбург : УрО РАН, 2005.-С. 37-43.

[2] Коновалова, С. С. О конструкциях эндоморфных совершенных шифров / С.С. Коновалова, С.С. Титов // Проблемы прикладной математики : сб. науч. тр. - Екатеринбург: УрГУПС, 2005-2006. - № 41(124). - Т. 2. - С. 70-106.

[3] Коновалова, С. С. Конструирование эндоморфных циклических £/(2)-стойких шифров / С.С. Коновалова, С.С. Титов // Устойчивость, управление и моделирование динамических систем : сб. науч. тр. межд. конф, - Екатеринбург : УрГУПС, 2006. - № 54(137). - С. 79-80.

[4] Коновалова, С. С. Конструирование эндоморфных циклических С/(2)-стойких шифров / С.С. Коновалова, С.С. Титов И Наука, инновации, образование: актуальные проблемы развития транспортного комплекса России : матер, межд. науч.-техн. конф.. - Екатеринбург: УрГУПС, 2006. - С. 512-513.

[5] Коновалова, С. С. Разностные схемы, проективные плоскости и совершенные шифры / С.С. Коновалова, С.С. Титов // Проблемы теоретической и прикладной математики : тр. 37-й регион, молодежной конф. - Екатеринбург : УрО РАН, 2006. - С. 482-486.

[6] Коновалова, С. С. О конструкциях эндоморфных совершенных шифров / С.С. Коновалова, С.С. Титов // Проблемы безопасности и противодействия терроризму : матер, межд. науч. конф. по проблемам безопасности и противодействия терроризму. - М.: МЦНМО, 2006. - С. 168-180.

[7] Konovalova, S. S. On construction of endomorphic perfect ciphers / S.S. Konovalova, S. S. Titov // Proc. of the Internat. Security and Counteracting Terrorism Conf. - M.: Lomonosov Moscow State University, 2006. - P. 179-191.

[8] Коновалова, С. С. Взаимосвязь между циклическими 0(2)- и £/(2)-стойкими шифрами / С.С. Коновалова, С.С. Титов // Проблемы теоретической и прикладной математики : тр. 38-й регион, молодежной конф. - Екатеринбург : УрО РАН, 2007. - С. 359-363.

[9] Комбинаторные проблемы существования совершенных шифров / С. С. Коновалова [и др.] // Труды Института математики и механики. - Екатеринбург : УрО РАН, 2007. - Т. 13. - № 4. - С. 61-73.

[10] Коновалова, С. С. 0(1)-стойкие шифры на основе групп Матьё и почти-полей

/ С.С. Коновалова, С.С. Титов // Проблемы прикладной математики и механики : сб. науч. тр. - Екатеринбург : УрГУПС, 2007. - Вып. 58(141)/2м. - Т. 2. -С. 125-144.

[11] Коновалова, С. С. Конструирование классических эндоморфных совершенных шифров и их современных аналогов // Тез. докл. студенч. конф. «IT security for new generation». M,: Лаборатория Касперского, 2008. - С. 27-28.

[12] Коновалова, С. С. Изучение свойств системы Холла для построения совершенных шифров // Тр. межд. науч.-пракг. конф. «СВЯЗЬ-ПРОМ». - Екатеринбург : ЗАО «Компания Реал-Медиа», 2008. - С. 419-421.

[13] Коновалова, С. С. Построение 0(L)- и U(L)-стойких шифров в конечных плоскостях / С.С. Коновалова, С.С. Титов // Проблемы безопасности и противодействия терроризму: матер. III межд. науч. конф. по пробл. безопасности и противод. терроризму. - М.: МЦНМО, 2008. - С. 191-209.

[14] Коновалова, С. С. Комбинаторные конструкции совершенных шифров и их современных аналогов / С.С. Коновалова // Наука и технологии : тез. докл. XXVni Российской школы. - Миасс: МСНТ, 2008. - С. 93.

[15] Коновалова, С. С. Конструирование классических эндоморфных совершенных шифров и их современных аналогов / С.С. Коновалова, С.С. Титов // X Белорусская математическая конференция: тез. докл. межд. науч. конф. -Ч. 5. - Мн.: Институт математики HAH Беларуси, 2008. - С. 48-49.

[16] Коновалова, С. С. Изучение свойств системы Холла для построения совершенных шифров / С.С. Коновалова, С.С. Титов // Проблемы прикладной математики и механики : сб. науч. тр. - Екатеринбург : УрГУПС, 2008. - Вып. 65(148)/Зм,-С. 202-211.

[17] Коновалова, С. С. О взаимосвязи между эндоморфными 1/(2)- и 0(2)-стойкими шифрами с минимальным числом ключей в FfF-системах //Безопасность информационного пространства : матер. VII регион, науч.-пракг. конф. студ., аспирантов и молодых ученых. - Екатеринбург: УрГУПС, 2008. - С. 76-77.

[18] Konovalova, S. S. On some combinatorial constructions of the perfect cipher

/ S.S. Konovalova [and other] // Proceedings of the 26th SAMSA conference Maputo-Mozambique, 2008. - P. 33.

[19] Коновалова, С. С. Комбинаторно-геометрический метод исследования совершенных шифров и их современных аналогов / С.С. Коновалова // Научная сессия ТУСУР-2009 : маггер. докл. всерос. науч.-техн. конф. студентов, аспирантов и молодых ученых. - Ч. 3. - Томск: В-Спекгр, 2009. - С. 359-366.

[20] Коновалова, С. С. Исследование исключительных почти-полей и плоскостей Мёбиуса для построения современных аналогов совершенных шифров / С.С. Коновалова // Научн. тр. межд. науч.-пракг. конф. «СВЯЗЬ-ПРОМ». -Екатеринбург: УрТИСИ ГОУ ВПО «СибГУТИ», 2009. - С. 185-187.

[21] Коновалова, С. С. Комбинаторно-геометрический метод исследования взаимосвязей между шифрами / С.С. Коновалова, С.С. Титов // Матер. IV межд. науч. конф. по проблемам безопасности и противодействия терроризму. -Т. 2. - М.: МЦНМО, 2009. - С. 71-86.

[22] Коновалова, С. С. Об отсутствии £ДЗ)-стойкости одного шифра, задаваемого подстановками на множестве из 23 элементов / A.A. Волокитин, С.С. Коновалова, С.С. Титов // Проблемы прикладной математики, механики и информатики : сб. научн. тр. - Екатеринбург : УрГУПС. - 2009. - Вып. 77 (160)-С. 212-215.

[23] {/(З)-стойкие шифры и конечные плоскости / С.С. Коновалова [и др.] //Безопасность информационного пространства : матер. VIII регион, науч.-практ. конф. спуд., аспир. и молодых ученых. - Челябинск : ЮУрГУ, 2009. -С. 221-223.

[24] Коновалова, С. С. О моделировании совершенных нелинейных шифрующих автоматов // Некоторые актуальные проблемы современной математики и математического образования : матер, науч. конф. «Герценовские чтения-2010». - СПб.: БАН, 2010. - С. 150-153.

Бумага офсетная Подписановпечагь04.05.2010 Усл. печ. л. 0,9

_Тираж 100_Формат 60x84 1/16_Заказ 330_

Издательство УрГУПС 620034, г Екатеринбург, ул. Колмогорова, 66

Введение

Глава 1 Теоретическая часть

Глава 2 Решение трех задач о трех конструкциях классических линейных совершенных шифров

§2.1 Вариант решения третьей задачи.

§2.2 Конечные плоскости и решение второй задачи.

§2.3 Геометрическое решение третьей задачи.

§2.4 Решение первой задачи.

Глава 3 Исследование эндоморфных U{L)~ и 0(b)-стойких шифров с минимальным числом ключей

§3.1 Связь O(L)-стойких шифров с геометрическими конфигурациями

§3.2 Взаимосвязь линейных и циклических JJ{2)- и 0(2)-стойких шифров.

§3.3 Взаимосвязь эндоморфных U{2)- и 0(2)-стойких шифров с минимальным числом ключей в УИ^-системах.

§3.4 Геометрическая интерпретация 0(Ь)-стойких шифров при помощи групп Матьё и почти-полей.

Глава 4 Исследование неэндоморфных U(3)- и О(3)-стойких шифров с использованием плоскости Мёбиуса

§4.1 Построение неэндоморфных шифров через произвольное упорядочивание блоков L — Л, сг)-схемы.

§4.2 Построение неэндоморфных шифров через параметризацию блоков L — (ц, Л, сг)-схемы эндоморфными шифрами.

§4.3 Увеличение неэндоморфности шифра через уменьшение параметра Л L — (//, Л, (т)-схемы

Одной из приоритетных задач в современном мире является обеспечение информационной безопасности. Одним из методов защиты информации является криптография - источник сложных математических задач. Важным разделом такого метода является теория совершенных шифров, понятие о которых для пассивных атак ввел Клод Шеннон в 40-х годах двадцатого века [1] как шифра, обеспечивающего наилучшую защиту.

Совершенный шифр по Шеннону -это абсолютно стойкий шифр, стойкий к пассивным атакам по шифртексту (то есть к определению зашифрованному тексту соответствующего открытого текста без знания ключа). К. Шеннон применял понятие совершенного шифра только в том случае, если злоумышленник перехватывает только одно сообщение, зашифрованное на данном ключе.

Эндоморфный шифр - это шифр, для которого \Х\ = \Y\ = \К\, гдеХ, У, К - множества открытых текстов, закрытых текстов и ключей соответственно. В теореме Шеннона, основанной на вероятностном подходе, доказано, что эндоморфными совершенными шифрами являются шифры табличного гам-мирования со случайной равновероятной гаммой, и только они. Такой шифр задаётся уравнением зашифрования у = X * k, где yEY,xEX,k£K, «*» - операция умножения в некоторой квазигруппе. Все предполагаемые открытые тексты, соответствующие данному зашифрованному сообщению, в этом случае являются равновероятными. В шифрах, стойких только с практической точки зрения, (например, используемые в настоящее время шифр DES и его модификации, а также Rijndael=AES и др.) всегда существует такой открытый текст, вероятность которого значительно больше вероятности других открытых текстов; поэтому злоумышленник может правильно расшифровать сообщение. Операция расшифрования - это операция правого деления в квазигруппе: х = у/к.

При создании криптографических примитивов и реализации шифрующих алгоритмов предпочтительнее использовать совершенные шифры с лучшими алгебраическими свойствами. Важным свойством шифра является его линейность. В линейном совершенном шифре умножение в квазигруппе имеет дополнительное свойство линейности по ж, в том числе правой дистрибутивности, а множества X и Y - это множества ненулевых векторов в конечномерном пространстве над конечным полем; в случае их одинаковой размерности шифр называется эндоморфным. В билинейном совершенном шифре умножение в квазигруппе обладает свойством линейности еще и по ключу, в том числе двусторонней дистрибутивности. В [2] авторы указывают, что линейные шифры обеспечивают механизм эффективного перевода ключевой последовательности в основной текст с сохранением ее свойств случайности и равновероятности. Поэтому этими авторами предложены три конструкции линейных совершенных шифров и поставлены три задачи об этих конструкциях.

Конструкция 1 задается формулой зашифрования у = хМ/ь, где М& -ключевая матрица, строки которой - последовательные отрезки линейной рекуррентной последовательности (ЛРП), задаваемой примитивным многочленом; у, ж, и к - вектора. Такая матрица является ганкелевой.

Конструкция 2 задается формулой зашифрования у = х • к, где ?/, ж, к G GF(q) \ {0}, «•» - операция умножения в GF(q).

Конструкция 3 (задает мультипликативный шифр) - это обобщение конструкции 2 посредством изотопии, задаваемой линейными преобразованиями: у' = х' ■ к', где х' = хА, к' = кВ, у' = уС\ А, В, С - невырожденные матрицы над конечным полем, задающие изотопию квазигруппы.

Задача 1. Является ли совершенный билинейный шифр, построенный с помощью конструкции 1, мультипликативным шифром?

Задача 2. Является ли любой совершенный билинейный шифр мультипликативным шифром?

Задача 3. Является ли любой совершенный линейный шифр билинейным шифром?

В 80-90-х годах двадцатого века появилось понятие современных аналогов совершенных шифров, стойких (в отличие от классических совершенных шифров) к активным атакам. Например, уменьшают вероятность подмены или имитации передаваемого по каналу связи зашифрованного сообщения так называемые U(L)~ и O(L)-стойкие шифры, где L - параметр стойкости.

Класс классических совершенных шифров и их современных аналогов требует постоянного расширения, поскольку эти шифры могут использоваться как криптографические примитивы в различных приложениях (например, в схемах разделения секрета), и при исследовании встает проблема их конструирования. Подробное изложение теории совершенных шифров дается в [3,4]: описываются различные классы таких шифров, указываются актуальные проблемы, связанные с решением сложных математических задач. В этих книгах широко используются такие структуры как латинские квадраты и прямоугольники, блок-схемы, ортогональные массивы, группы^ квазигруппы, векторные пространства над конечными полями. Геометрические понятия лучше соотносятся с нашими интуитивными представлениями. С другой стороны они обладают большим набором свойств, поэтому их можно использовать для построения новых примеров совершенных шифров. Например, в [5J подробно рассмотрено построение дезарговых плоскостей над полем из трех элементов и соответствующих эндоморфных 0(2)-стойких шифров с параметрами \Х\ = |У| = З2 и \Х\ = |У| = З3. В [6-9] установлена связь эндоморфных С/(3)-стойких шифров в полях характеристики два с эллиптическими кривыми и предложена конструкция для построения такого шифра; найдены некоторые функции зашифрования, действующие на эллиптической кривой, но не удовлетворяющие условию [/(З)-стойкости. В [10] был дан геометрический метод оценки максимально возможного числа п для схемы разделения секрета (3, п) и, как следствие, была доказана теорема о несуществовании эндоморфных £7(3)-стойких шифров определенного вида. Развиваемые в диссертации методы конечных геометрий показали свою эффективность при решении указанных в [3,4] задач.

Объект исследования - конечные геометрии (конечные плоскости, плоскости Мёбиуса), рассматриваемые в приложении к классическим линейным совершенным шифрам и их современным аналогам.

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

Цель исследования - решение проблем в области конечных геометрий, связанных с развитием теории совершенных шифров.

Поставленная цель достигнута путем решения следующих задач:

1) установление взаимосвязи теории совершенных шифров с теорией конечных плоскостей;

2) приложение геометрического метода: решение трех проблем о трех конструкциях линейных совершенных шифров, поставленных западными криптографами (в том числе классиком криптографии J. Massey) в 1987 году, и уточнение классификации классических линейных совершенных шифров через их геометрическую интерпретацию;

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

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

Научная новизна. Все основные результаты работы являются новыми.

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

Апробация результатов. Основные результаты диссертации докладывались автором на конференциях [11,13,16,18, 22, 23, 25, 29—31J, в том числе на международной научной конференции по проблемам безопасности и противодействию терроризму и общероссийской научной конференции «Математика и безопасность информационных технологий» (Москва, ИПИБ МГУ, 2005, 2007-2009 гг.); международной научной «X Белорусской математической конференции» (г. Минск, БГУ, 2008 г.); молодежной школе-конференции «Проблемы теоретической и прикладной математики» (Екатеринбург, ИММ УрО РАН, 2005, 2007, 2010 гг.). А также - на XI международной конференции «РусКрипто» (Москва, 2009 г.); научно-практической конференции студентов, аспирантов и молодых ученых «Безопасность информационного пространства» (Екатеринбург, 2005 г.; Тюмень, 2007 г.); IX научно-практической конференции молодых специалистов «Автоматизация. Инновация. Качество» (г. Нижний Тагил, 2010 г.); межвузовской научной конференция «СПИСОК» (Екатеринбург, УрГУ, 2009 г.); межвузовской научно-технической конференции «Молодые ученые - транспорту» (Екатеринбург, 2005, 2007, 2010 гг.); на научном семинаре кафедры «Прикладная математика» УрГУПС. Всего сделаны доклады на двадцати конференциях различного уровня.

Публикации. Основные результаты диссертации опубликованы в работах [11-34], в том числе [19] - в издании, входящем в перечень рекомендованных ВАК РФ. В публикациях, выполненных совместно с научным руководителем, руководителю принадлежат постановка задач и общее руководство исследованиями, а соискателю - получение и оформление результатов.

Структура и объем диссертации. Диссертация состоит из введения, четырёх глав, заключения, списка литературы из 44 наименований. Объем диссертации составляет 93 страницы. В работе 13 рисунков, 13 таблиц.

Основные результаты диссертации:

1) установлена взаимосвязь конечных плоскостей типа Веблена-Веддер-бёрна с классическими линейными эндоморфными совершенными шифрами и с линейными 0(2)-стойкими шифрами с минимальным числом ключей;

2) развит геометрический метод и решены три проблемы о трех конструкциях линейных совершенных шифров с использованием недезарговых плоскостей;

3) применены конечные плоскости со специфическими свойствами (системы Холла, почти-поля, не сводящиеся к полям), а также плоскости Мёбиуса к построению линейных совершенных шифров и их современных аналогов, дана геометрическая интерпретация таких шифров;

4) установлена взаимосвязь групп Матьё и почти-полей, не сводящихся к полям, между собой, а также взаимосвязь между линейными 0(2)- и U{2)-стойкими шифрами через наличие инволюции.

Автор выражает глубокую признательность своему научному руководителю С.С. Титову, а также заведующему кафедрой «Прикладная математика» УрГУПС С.П. Баутину. За внимание к работе, полезные обсуждения, поддержку данных исследований, за направляющие дискуссии автор выражает благодарность: Ященко В.В. - 1-му заместителю директора Института проблем информационной безопасности МГУ; Варновскому Н.П. - ведущему сотруднику Института проблем информационной безопасности МГУ; Глухову М.М. -академику Академии криптографии РФ; Харину Ю.С. - чл.-кор. НАН Беларуси; Махнёву А.А. - чл.-кор. РАН; Кабанову В.В. - заместителю директора ИММ УрО РАН; Пудовкиной М.А. и Жукову А.Е. - директорам ассоциации «РусКрипто»; Арестову В.В. - председателю правления Уральского математического общества; Баранскому В.А. - директору Регионального научного центра «Информационная безопасность»; Рожкову А.А. - профессору ЮжноУральского государственного университета, Росошеку С.К. - доценту Томского университета систем управления и радиоэлектроники.

Заключение

1. Шеннон, К. Теория связи в секретных системах // Шеннон К. Работы по теории информации и кибернетике. М. : ИЛ, 1963. - С. 333-369.

2. Massey, J. Non-expanding, key minimal, robustly-perfect, linear and bilinear ciphers / J. Massey, U. Maurer, M. Wang // Proceedings «Advances in Cryp-tology» of Crypto'87. 1987. - P. 237-247.

3. Зубов, А. Ю. Совершенные шифры. — M. : Гелиос АРВ, 2003. 160 с.

4. Зубов, А. Ю. Криптографические методы защиты информации. Совершенные шифры : учебное пособие. М. : Гелиос АРВ, 2005. - 192 с.

5. Реализация конечных плоскостей и семейств ортогональных латинских квадратов / И.А. Вакуленко и др. // Труды IV науч.-технич. конф. «Молодые ученые транспорту». - Екатеринбург : УрГУПС, 2003. - С. 341-358.

6. U(З)-стойкие шифры и эллиптические кривые / Д.С. Гутарин и др. // Тез. докл. X Белорусской мат. конф. Мн. : Институт математики НАН Беларуси, 2008. - Ч. 5. - С. 41-42.

7. Имитостойкие шифры и эллиптические кривые в полях характеристики два / JI.E. Пашнина и др. // Тез. докл. X Белорусской мат. конф. Мн. : Институт математики НАН Беларуси, 2008. - Ч. 5. - С. 60-61.88

8. Титов, С. С. Пороговые схемы разделения секрета и совершенные шифры / С.С. Титов, Н.О. Устьянцева // Проблемы теоретической и прикладной математики: Тр. 39-й Всеросс. молодежной конф. Екатеринбург : УрО РАН, 2008. С. 408-412.

9. Коновалова, С. С. Три задачи о трех конструкциях совершенных шифров / С.С. Коновалова, С.С. Титов // Проблемы теоретической и прикладной математики : тр. 36-й регион, молодежной конф. Екатеринбург : УрО РАН, 2005. - С. 37-43.

10. Коновалова, С. С. О конструкциях эндоморфных совершенных шифров / С.С. Коновалова, С.С. Титов // Проблемы прикладной математики : сб. науч. тр. Екатеринбург : УрГУПС, 2005-2006. - №41(124). - Т. 2. -С. 70-106.

11. Коновалова, С. С. Разностные схемы, проективные плоскости и совершенные шифры / С.С. Коновалова, С.С. Титов // Проблемы теоретической и прикладной математики : тр. 37-й регион, молодежной конф. Екатеринбург : УрО РАН, 2006. - С. 482-486.

12. Konovalova, S. S. On construction of endomorphic perfect ciphers / S.S. Ko-novalova, S. S. Titov // Proc. of the International Security and Counteracting Terrorism Conf. M. : Lomonosov Moscow State University, 2006. - P. 179191.

13. Коновалова, С. С. Взаимосвязь между циклическими 0(2)- и U^-стойкими шифрами / С.С. Коновалова, С.С. Титов // Проблемы теоретической и прикладной математики : тр. 38-й регион, молодежной конф. Екатеринбург : УрО РАН, 2007. - С. 359-363.

14. Комбинаторные проблемы существования совершенных шифров / С.С. Коновалова и др. // Труды Института математики и механики. Екатеринбург : УрО РАН, 2007. - Т. 13. - №4. - С. 61-73.

15. Коновалова, С. С. 0(£)-стойкие шифры на основе групп Матьё и почти-полей / С.С. Коновалова, С.С. Титов // Проблемы прикладной математики и механики : сб. науч. тр. Екатеринбург : УрГУПС, 2007. - Вып. 58(141)/2м. - Т. 2. - С. 125-144.

16. Коновалова, С. С. Конструирование классических эндоморфных совершенных шифров и их современных аналогов // Тез. докл. студенч. конф. «IT security for new generation». M. : Лаборатория Касперского, 2008. -С. 27-28.

17. Коновалова, С. С. Изучение свойств системы Холла для построения совершенных шифров // Тр. межд. науч.-практ. конф. «СВЯЗЬ-ПРОМ». -Екатеринбург : ЗАО «Компания Реал-Медиа», 2008. С. 419-421.

18. Коновалова, С. С. Комбинаторные конструкции совершенных шифров и их современных аналогов / С.С. Коновалова // Наука и технологии : тез. докл. XXVIII Российской школы. Миасс : МСНТ, 2008. - С. 93.90

19. Коновалова, С. С. Изучение свойств системы Холла для построения совершенных шифров / С.С. Коновалова, С.С. Титов // Проблемы прикладной математики и механики : сб. науч. тр. Екатеринбург : УрГУПС, 2008. -Вып. 65(148) / Зм. - С. 202-211.

20. Konovalova, S. S. On some combinatorial constructions of the perfect cipher / S.S. Konovalova and other. // Proceedings of the 26th SAMSA conference. Maputo-Mozambique, 2008. P. 33.

21. Коновалова, С. С. Комбинаторно-геометрический метод исследования взаимосвязей между шифрами / С.С. Коновалова, С.С. Титов // Матер. IVмежд. науч. конф. по проблемам безопасности и противодействия терроризму. Т. 2. - М. : МЦНМО, 2009. - С. 71-86.

22. U(3)-стойкие шифры и конечные плоскости // С.С. Коновалова и др. // Безопасность информационного пространства : матер. VIII регион, науч.-практ. конф. студ., аспир. и молодых ученых. Челябинск : ЮУрГУ, 2009. - С. 221-223.

23. Коновалова, С. С. О моделировании совершенных нелинейных шифрующих автоматов // Некоторые актуальные проблемы современной математики и математического образования : матер, науч. конф. «Герценовские чтения 2010». СПб. : БАН, 2010. - С. 150-153.

24. Глухов, М. М. О применениях квазигрупп в криптографии // Прикладная дискретная математика. №2(2). - 2008. - С. 28-33.

25. Холл, М. Комбинаторика. М. : Мир, 1970. - 424 с.

26. Zassenhaus, Н. Uber endliche Fastkorper // Abh. Math. Sem. Hamburg, 1936. - P. 187-220.

27. Картеси, Ф. Введение в конечные геометрии: Пер. с англ. М. : Наука. Гл. ред. физ.-мат. лит., 1980. - 320 с.

28. Артин, Э. Геометрическая алгебра. М. : Наука, 1969. - 284 с.

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

30. Белоусов, В. Д. Латинские квадраты, квазигруппы и их приложения / В.Д. Белоусов, Г.Б. Белявская. Кишинев : Штиница, 1989. - 80 с.

31. Скорняков, JT. А. Проективные плоскости. М. : УМН, 1951, - Вып. 6(46). -Т. 6. - С. 112-154.

32. Глухов, М. М. Алгебра: учебник / М.М. Глухов, В.П. Елизаров, А.А. Нечаев. М. : Гелиос АРВ, 2003 - Т. 2. - 416 с.

33. Разделение секрета и решетки / А.Е. Аксёнов и др. // Проблемы прикладной математики, механики и информатики: Сб. науч. тр. под общ. ред. C.JL Дерябина, д.ф.-м.н. Екатеринбург: УрГУПС. Вып. 77(160). -2009. - С. 174-195.