Оглавление
Введение 3
Глава 1 Теоретическая часть 9
Глава 2 Решение трех задач о трех конструкциях классических линейных совершенных шифров 15
§2.1 Вариант решения третьей задачи............................ 15
§2.2 Конечные плоскости и решение второй задачи . . . ........ 17
§2.3 Геометрическое решение третьей задачи..................... 21
§2.4 Решение первой задачи..................................... 24
Глава 3 Исследование эндоморфных (/(£)- и 0(Ь)-стойких
шифров с минимальным числом ключей 37
§3.1 Связь О(Ь)-стойких шифров с геометрическими конфигурациями 37
§3.2 Взаимосвязь линейных и циклических и(2)- и 0(2)-стойких
шифров...................................................... 41
§3.3 Взаимосвязь эндоморфных и(2)- и 0(2)-стойких шифров
с минимальным числом ключей в К1Р-системах.................. 47
§3.4 Геометрическая интерпретация 0(£)-стойких шифров
при помощи групп Матьё и почти-полей........................ 59
Глава 4 Исследование неэндоморфных 1/(3)- и О(3)-стойких
шифров с использованием плоскости Мёбиуса 80
§4.1 Построение неэндоморфных шифров через произвольное
упорядочивание блоков Ь — (д, А,<т)-схемы................... 80
§4.2 Построение неэндоморфных шифров через параметризацию
блоков Ь — (д, Л, <т)-схемы эндоморфными шифрами............ 82
§4.3 Увеличение неэндоморфноети шифра через уменьшение
параметра Л Ь— (д, Л, <т)-схемы ............................ 86
Заключение 87
Библиографический список 88
Введение
Одной из приоритетных задач в современном мире является обеспечение информационной безопасности. Одним из методов защиты информации является криптография - источник сложных математических задач. Важным разделом такого метода является теория совершенных шифров, понятие о которых для пассивных атак ввел Клод Шеннон в 40-х годах двадцатого века [1] как шифра, обеспечивающего наилучшую защиту.
Совершенный шифр по Шеннону - это абсолютно стойкий шифр, стойкий к пассивным атакам но шифртексту (то есть к определению зашифрованному тексту соответствующего открытого текста без знания ключа). К. Шеннон применял понятие совершенного шифра только в том случае, если злоумышленник перехватывает только одно сообщение, зашифрованное на данном ключе.
Эндоморфный шифр -это шифр, для которого \Х\ = \У\ = \К\, где X, Y, К - множества открытых текстов, закрытых текстов и ключей соответственно. В теореме Шсшюна, основанной на вероятностном подходе, доказано, что эндоморфными совершенными шифрами являются шифры табличного гам-мирования со случайной равновероятной гаммой, и только они. Такой шифр задаётся уравнением зашифрования
у = х * к,
где у G Y, х G X, к G К, «*» - операция умножения в некоторой квазигруппе. Все предполагаемые открытые тексты, соответствующие данному зашифрованному сообщению, в этом случае являются равновероятными. В шифрах, стойких только с практической точки зрения, (например, используемые в настоящее время шифр DES и его модификации, а также Rijndael=AES и др.) всегда существует такой открытый текст, вероятность которого значительно больше вероятности других открытых текстов; поэтому злоумышленник может правильно расшифровать сообщение. Операция расшифрования - это операция правого деления в квазигруппе: х = у/к.
з
При создании криптографических примитивов и реализации шифрующих алгоритмов предпочтительнее использовать совершенные шифры с лучшими алгебраическими свойствами. Важным свойством шифра является его линейность. В линейном совершенном шифре умножение в квазигруппе имеет дополнительное свойство линейности по х, в том числе правой дистрибутивности, а множества X и У ~ это множества ненулевых векторов в конечномерном пространстве над конечным полем; в случае их одинаковой размерности шифр называется эндоморфным. В билинейном совершенном шифре умножение в квазигруппе обладает свойством линейности еще н по ключу, в том числе двусторонней дистрибутивности. В [2] авторы указывают, что линейные шифры обеспечивают механизм эффективного перевода ключевой последовательности в основной текст с сохранением ее свойств случайности и равновероятности. Поэтому этими авторами предложены три конструкции линейных совершенных шифров и поставлены три задачи об этих конструкциях.
Конструкция 1 задается формулой зашифрования у = хМк, где Мк -ключевая матрица, строки которой - последовательные отрезки линейной рекуррентной последовательности (ЛРП), задаваемой примитивным многочленом; у, х, и к - вектора. Такая матрица является ганкелевой.
Конструкция 2 задается формулой зашифрования у = х • А*, где уу х, к 6 \ {0}, «•» - операция умножения в СВ(д).
Конструкция 3 (задает мультипликативный шифр) - это обобщение конструкции 2 посредством изотопии, задаваемой линейными преобразованиями: у' = х' - А:', где х' = хА. к' = кВ, у' = уС; Л, В> С - невырожденные матрицы над конечным полем, задающие изотопию квазигруппы.
Задача 1. Является ли совершенный билинейный шифр, построенный с помощью конструкции 1, мультипликативным шифром?
Задача 2. Является ли любой совершенный билинейный шифр мультипликативным шифром?
Задача 3. Является ли любой совершенный линейный шифр билинейным шифром?
В 80-90-х годах двадцатого века появилось понятие современных аналогов совершенных шифров, стойких (в отличие от классических совершенных шифров) к активным атакам. Например, уменьшают вероятность подмены или имитации передаваемого по каналу связи зашифрованного сообщения так называемые и(Ь)- и О (Ь)-стойкие шифры, где Ь - параметр стойкости.
Класс классических совершенных шифров и их современных аналогов требует постоянного расширения, поскольку эти шифры могут использоваться как криптографические примитивы в различных приложениях (например, в схемах разделения секрета), и при исследовании встает проблема их конструирования. Подробное изложение теории совершенных шифров дается в [3,4]: описываются различные классы таких шифров, указываются актуальные проблемы, связанные с решением сложных математических задач. В этих книгах широко используются такие структуры как латинские квадраты и прямоугольники, блок-схемы, ортогональные массивы, группы^ квазигруппы, векторные пространства над конечными нолями. Геометрические понятия лучше соотносятся с нашими интуитивными представлениями. С другой стороны они обладают большим набором свойств, поэтому их можно использовать для построения новых примеров совершенных шифров. Например, в [5] подробно рассмотрено построение дезарговых плоскостей над полем из трех элементов и соответствующих эндоморфных 0(2)-стойких шифров с параметрами \Х\ = |У| = З2 и |ЛГ| = |У| = З3. В [6-9] установлена связь эндоморфных [/(З)-стойких шифров в полях характеристики два с эллиптическими кривыми и предложена конструкция для построения такого шифра; найдены некоторые функции зашифрования, действующие на эллиптической кривой, но не удовлетворяющие условию £/(3)-стойкости. В [10] был дан геометрический метод оценки максимально возможного числа п для схемы разделения секрета (3,п) и, как следствие, была доказана теорема о несуществовании эндоморфных £/(3)-стоПких шифров определенного вида. Развиваемые в диссертации методы конечных геометрий показали свою эффективность при решении указанных в [3.4] задач.
5
Объект исследования - конечные геометрии (конечные плоскости, плоскости Мёбиуса), рассматриваемые в приложении к классическим линейным совершенным шифрам и их современным аналогам.
Предмет исследования - комбинаторные конструкции конечных геометрий в задачах построения и изучения свойств классических линейных совершенных шифров и их современных аналогов.
Цель исследования - решение проблем в области конечных геометрий, связанных с развитием теории совершенных шифров.
Поставленная цель достигнута путем решения следующих задач:
1) установление взаимосвязи теории совершенных шифров с теорией конечных плоскостей;
2) приложение геометрического метода: решение трех проблем о трех конструкциях линейных совершенных шифров, поставленных западными криптографами (в том числе классиком криптографии J. Massey) в 1987 году, и уточнение классификации классических линейных совершенных шифров через их геометрическую интерпретацию;
3) развитие геометрического метода с целыо расширения известных классов совершенных шифров, построения новых классов таких шифров и нахождения взаимосвязей между ними.
Методы исследования - методы конечных геометрий, теории конечных плоскостей, плоскостей Мёбиуса и векторных пространств над конечными полями, комбинаторика совершенных шифров.
Научная новизна. Все основные результаты работы являются новыми.
Теоретическая и практическая ценность диссертации заключается в установлении взаимосвязи теории совершенных шифров с теорией конечных плоскостей, в решении геометрическим методом конкретных проблем теории совершенных шифров, в исследовании свойств соответствующих классов конечных геометрий. Полученные результаты и развитые методы могут иметь криптографические приложения, в том числе в смежных с совершенными шифрами областях.
G
Апробация результатов. Основные результаты диссертации докладывались автором на конференциях [11,13,16,18,22,23, 25, 29-31], в том числе на международной научной конференции по проблемам безопасности и противодействию терроризму и общероссийской научной конференции «Математика и безопасность информационных технологий» (Москва, ИПИБ МГУ, 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 таблиц.
Во введении обосновывается актуальность темы диссертации, проводится обзор литературы, определяется объект и предмет исследования, формулируются цель и задачи исследования на основе естественной взаимосвязи совершенных шифров с квазигруппами, а линейных совершенных шифров -с геометрией конечномерных векторных пространств над конечными полями.
- Київ+380960830922