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

• Коновалова, Светлана Сергеевна
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Коновалова, Светлана Сергеевна

Введение

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

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Коновалова, Светлана Сергеевна, 2010 год

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.