Реализация уменьшеной версии бумернг атаки на уменьшеную модель шифра Риендаля

Министерство образования, науки, молодежи и спорта Украины

Харьковский национальный университет радиоэлектроники

Факультет КОМПЬЮТЕРНОЙ ИНЖЕНЕРИИ И УПРАВЛЕНИЯ

 

Кафедра БЕЗОПАСНОСТИ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

КУРСОВАЯ РОБОТА

 

 

пояснительная записка

Рассмотрение бумеранг-атаки на шифр Rijndael

и реализация атаки на шифр baby- Rijndael

(тема курсовой работы)

 

 

 

Студент	БИКС-08-1				Дяденко Р.В.
	(группа)		(подпись)		(фамилия, инициалы)
Руководитель					доцент Руженцев В.И.
			(подпись)		(должность, фамилия, инициалы)
Комиссия
			(подпись)		(должность, фамилия,  инициалы)
			(подпись)		(должность, фамилия,  инициалы)
			(подпись)		(должность, фамилия,  инициалы)

 

 

 

 

 

 

 

 

2011 г.

 

РЕФЕРАТ

Пояснительная записка  к курсовому проекту имеет 24 страницы, 2 таблицы, 13 рисунков, 1 приложение, 8 источников.

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

 

БЛОЧНЫЙ ШИФР, КРИПТОАНАЛИЗ, СЛОЖНОСТЬ ВЫЧЕСЛЕНИЙ, СТАНДАРТБ СИМЕТРИЧНЫЙ ШИФР, ШИФРОТЕКСТ.

 

Оглавление

 

 

ВВЕДЕНИЕ

Началом развития современного этапа развития криптографии следует  считать появление стандарта  шифрования данных (Data Encryption Standard - DES), разработанного в 70-х годах прошедшего столетия специалистами из ИБМ.  На это же время приходится революционный прорыв в классической криптографии, связанный с появлением принципиально новой идеологии криптосистем с открытым ключом, который открыл новые криптографические задачи и позволил найти принципиально новые решения задач классических. Шифр DES на тот период стал триумфом классической криптографии, представивший собой изящное техническое решение по защите информации, обладающее одновременно и высокой эффективностью (шифрование и дешифрование выполняются быстро) и убедительной надежностью (если ключ неизвестен, то нет способа раскрытия шифра).

Более чем 20 лет Стандарт Шифрования Данных (DES) считался американским государственным стандартом шифрования конфиденциальной, но несекретной информации. Став фактически всемирным стандартом, DES был опубликован в 1977 г. как FIPS PUB 46. Каждые пять лет он подвергался экспертизе Национальным Бюро по Стандартам (NBS), впоследствии переименованным в Национальный Институт Стандартов и Технологии (NIST). Первая экспертиза была проведена в 1983 г., и DES был переутверждён, как пригодный стандарт. Вторая экспертиза произошла в 1988 г., и этот стандарт был переиздан как FIPS PUB 46 -1. Третья экспертиза была проведена в 1993 г., в результате которой DES как стандарт опять был переиздан в виде FIPS 46-2. В последней третьей версии FIPS 46-3 тройной DES был предложен как пригодный альтернативный алгоритм, обеспечивающий более высокий уровень защиты [1].

С момента публикации стандарта началось интенсивное  изучение и всесторонние исследование показателей его стойкости многими заинтересованными специалистами. Большое внимания было уделено поиску ²лазеек² (вложенных слабостей), но время показало, что их в шифре нет. Именно на этом шифре практически начала отрабатываться и развиваться современная методология выполнения криптоаналитических атак.

На сегодняшний день DES считается устаревшим шифром. На смену ему пришел шифр Rijndael. В курсовой работе будет разработана мини версия данного шифра и рассмотрены атаки на него.

 

1 Теоретические сведения о блочных шифрах

1.1 Понятие блочного шифрования

Блочным шифром называют функцию, которая отображает n-битовые входные блоки открытого текста в n-битовые блоки зашифрованного текста, n называют длинной блока шифра [1]. Блочный шифр можно рассматривать как некоторую параметризированную функцию подстановки элементов большого размера. Параметром функции выступает k-битовый ключ K, который принадлежит пространству ключей. Блочный шифр является симметричным, если ключ зашифрования равен ключу расшифрования. Алгоритм симметричного блочного шифрования (АСБШ) реализует функцию блокового шифра для зашифрования и расшифрования входных блоков.

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

1.2 Структурная организация алгоритмов симметрического блокового шифрования

Анализ структурной  организации алгоритмов блочного шифрования [2-6] и базовых способов их построения показал, что их структурная организация на высоком уровне можно представить в виде соединения двух основных компонент (рис. 1): процедуры обработки данных и процедуры разворачивания ключа. Порядок обработки блока данных и ключа зависит от структуры алгоритма и от вида выполняемой операции – шифрования или расшифрования.

Рисунок 1 – Высокоуровневое представление АСБШ

 

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

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

Исходя из результатов анализа структурных особенностей составляющих процедур рассмотренных АСБШ и их обобщения, представим эти составляющие как совокупность четырех процедур: процедуры обработки данных для операции шифрования, процедуры обработки данных для операции расшифрования, процедуры разворачивания ключа для шифрования, процедуры разворачивания ключа для расшифрования. Эти процедуры, в свою очередь, состоят из составляющих (более простых) элементов: для процедуры обработки данных это этапы начальной модификации данных, основной обработки данных, конечной модификации данных; для процедуры разворачивания ключа – этапы начальной модификации ключа, основной обработки ключа, конечной модификации подключей.

Рассмотрим порядок обработки данных и ключа согласно с предложенной обобщенной структурной организацией АСБШ.

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

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

Можно сделать вывод, что двумя главными процедурами в блочных шифрах является процедура обработки данных и процедура разворачивания ключа. Далее рассмотрим разработанную мини-версию одного из самых распространенных блочных симметричных шифров – шифра Rijndael.

1.3 Описание шифра Rijndael

На вход шифра подается сообщение размером 128 бит в виде матрицы 4 на 4 по 1 байту и складывают с ключом 128 бит. Схематически шифр Rijndael можно отобразить как:

Рисунок 2 – Схематическое  представление шифрования данных шифром Rijndael

 

На первом шаге, как  видим на рис.2, складываем входящие данные с ключом, а потом подаем на 10 циклов, в котором делаем замену байт, сдвиг рядов, перемешивание колонок и прибавление сеансового ключа, но  последний цикл выполняется без перемешивания колонок.

Замена байт происходит по таблице подстановок, согласно стандарту.

Рисунок 3 – Пример работы функции подстановки байт и таблица  подстановки

 

Функция сдвига рядов циклически сдвигает элементы в рядке, во втором рядке сдвигается на один элемент, во втором на два и в третьем на три.

Функция перемешивания  колонок подразумевает собой  умножение всех колонок на матрицу  из стандарта

Рисунок 4 – Пример работы функции перемешивания колонок и матрица, на которую нужно умножать каждую колонку

 

И функция складывания  с сеансовым ключом предполагает сложение по модулю 2 с сеансовым ключом

Рисунок 5 – Складывание  по модулю 2 с сеансовым ключом (справа)

1.4 Описание разработанной уменьшенной версии шифра Rijndael

В стандартной версии Rijndael на вход шифра подается сообщение размером 128 бит, которые складываются с ключом. Далее 128 бит делятся на 4 блока по 32 бита и первые два блока, а затем и следующие два, умножаются на матрицу MDR.

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

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

Таблица 1 – Таблица подстановок для шифрования

x	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
s(x)	10	4	3	11	8	14	2	12	5	7	6	15	0	1	9	13

 

Таблица 2 – Таблица подстановок  для расшифрования

x	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
s(x)	12	13	6	2	1	8	10	9	4	14	0	3	7	15	5	11

 

Рис. 6 – Схема шифрования

 

Программная реализация алгоритма разработанной уменьшенной  модели шифра  представлена в Приложении А.

1.5 Методы криптоанализа блочных шифров

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