rijndael (Курсовая - Построение и исследование криптосистемы на основе Rijndael)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИМОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ,ЭЛЕКТРОНИКИ И АВТОМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНЫХ МАШИН И СИСТЕМПостроение и исследование криптосистемына основе Rijndael.Ф.И.О. студентаРыжов Алексей ВладимировичГруппаВИ-1-00Москва 2004Содержание1Введение.32 Создание криптосистемы.2.1 Изменения исходного криптоалгоритма.

.2.2 Определения и обозначения. . . . . . . .2.3 Математическая интерпретация. . . . . .2.4 Спецификация алгоритма. . . . . . . . . .2.4.1 Зашифрование. . . . . . . . . . . .2.4.2 Расшифрование. . . . . . . . . . .2.4.3 Процедура развертывания ключа.2.5 Программная реализация. . . . . .

. . . .................................................3334567783 Методы криптоанализа.3.1 Дифференциальный криптоанализ. . . . . . . . . . . .3.1.1 Описание криптоанализа. . . . . . . . . . . . . .3.1.2 Дифференциальный анализ S-блока. . . . . . .3.1.3 Построение дифференциальной характеристики.3.1.4 Извлечение бит подключа последнего раунда. .3.1.5 Восстановление исходного ключа. . . . . . . . .3.1.6 Эффективность криптоанализа. . . .

. . . . . .3.1.7 Программная реализация. . . . . . . . . . . . . .3.2 Линейный криптоанализ. . . . . . . . . . . . . . . . . .3.2.1 Описание криптоанализа. . . . . . . . . . . . . .3.2.2 Линейный анализ S-блока. . . . . . . . . . . . .3.2.3 Построение линейного приближения. . . . . . .3.2.4 Извлечение бит подключа последнего раунда. .3.2.5 Восстановление исходного ключа. . . . . . . . .3.2.6 Эффективность криптоанализа. . . . .

. . . . .3.2.7 Программная реализация. . . . . . . . . . . . . .................................................................................8991011131616161616181821222323........................................................4 Криптосистема как генератор псевдослучайных последовательностей.4.1 Введение. .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.2 Общее описание набора тестов Руководства НИСТ. . . . . . . .4.3 Описание каждого теста и их параметры. . . . . . . . . . . . . .4.3.1 Частотный (Монобитный) тест (Frequency). . . . . . .4.3.2 Частотный тест в подпоследовательностях(Block-Frequency). . . . . . . . . . . . . . . . . . . . .4.3.3 Тест “дырок” (Runs). . . . . .

. . . . . . . . . . . . . . .4.3.4 Тест “блоков” в подпоследовательностях (Long-Run). .4.3.5 Проверка рангов матриц (Rank). . . . . . . . . . . . . .4.3.6 Спектральный тест (FFT). . . . . . . . . . . . . . . . . .4.3.7 Проверка непересекающихся шаблонов(Aperiodic-Template).

. . . . . . . . . . . . . . . . .4.3.8 Проверка пересекающихся шаблонов(Periodic-Template). . . . . . . . . . . . . . . . . . .4.3.9 Универсальный тест Маурера (Universal). . . . . . . .1242425272727272727282828284.3.10 Проверка сжатия при помощи алгоритма Лемпела-Зива(Lempel-Ziv). . . . . . . . . . . . . .

. . . . . . . . . .4.3.11 Проверка линейной сложности (Linear-Complexity).4.3.12 Проверка серий (Serial). . . . . . . . . . . . . . . . . .4.3.13 Проверка аппроксимированной энтропии (Apen). . . . .4.3.14 Проверка кумулятивных сумм (Cusum). . . . . . . . . .4.3.15 Проверка случайных отклонений (Random-Excursion).4.3.16 Проверка случайных отклонений (вариант)(Random-Excursion-V). .

. . . . . . . . . . . . . . . .4.4 Результат тестирования генератора. . . . . . . . . . . . . . . . .5 Вывод.28292929293030303421 Введение.В данной работе мы рассмотрим основной цикл работ по изучению криптосистемы. Он состоит из создания самой криптосистемы (алгоритмов зашифрования и расшифрования сообщений), проведение криптоанализа этойсистемы и изучение статистических свойств ее работы.На первом этапе мы создадим криптосистему на основе криптографического алгоритма Rijndael, принятого в 2001 г. в качестве американскогостандарта криптографической защиты AES.

AES принят на замену морально устаревшему DES — самому распространенному криптоалгоритму в мире.Этим и обусловлен наш выбор основы нашего алгоритма.На втором этапе мы подвергнем нашу систему двум основным методамкриптоанализа — дифференциальному и линейному. Данные два метода относятся к числу универсальных, а также они были применены для анализаразличных версий DES-подобных шифров.На третьем этапе мы рассмотрим работу нашей системы в режиме генератора псевдослучайных последовательностей (ПСП). Для оценки их качествамы выберем один из наиболее известных статистических тестов, применяемых для анализа генераторов, — Руководство по статистическому тестированию генераторов ПСП (Руководство НИСТ).2 Создание криптосистемы.2.1Изменения исходного криптоалгоритма.Спецификация исходного криптоалгоритма Rijndael описана в Федеральномстандарте шифрования США и легко доступна, поэтому останавливаться наподробном описании мы не будем.

Остановимся только на основных его параметрах.Алгоритм Rijndael относится к числу симметричных блочных шифров иимеет архитектуру “квадрат” (4 × 4), размер каждой ячейки 8 бит; размерблока (бит) 128, 192 или 256 (в качестве стандарта принят вариант шифратолько с размером блока 128 бит); pазмер ключа (бит) 128, 192 или 256;число раундов 10, 12 или 14; pазмер ключевого элемента (бит) 128, 192 или256 (равен размеру блока); число ключевых элементов 11, 13 или 15 (на 1больше числа раундов).На его основе мы создадим его упрощенный аналог. Архитектуру квадрата уменьшим до размера 2 × 2. Размер ячейки оставим прежним, но припреобразовании S-блока разделим 8 бит на две независимые группы по 4бита. Соответственно размер блока и ключа уменьшится до 32 бит. Числораундов сократим до 3.Более подробные детали изменений будут рассмотрены в спецификацииалгоритма.2.2 Определения и обозначения.Далее приведены основные определения и обозначения, которые используются в данной работе (они совпадают с обозначениями исходной спецификацииRijndael, чтобы сохранить общность изложения с другими источниками).3ключ шифрования (ключи зашифрования и расшифрования совпадают)Nbчисло столбцов (16-битных слов) (равно 2)Nkчисло 16-битных слов ключа (равно 2)Nrчисло раундов (равно 3)w[i..j]срез массива развернутого ключа (индексация ведется в 16-битных словах)AddRoundKey()функция добавления ключаSubBytes()функция побайтной заменыShiftRows()функция циклического сдвига строкMixColumns()функция линейной замены столбцовInvSubBytes()функцияпобайтнойзамены,обратнаякSubBytes()KeyExpansion() функция выработки расширенного ключа из KRcon[]массив констант, используемых в функции расширения ключа KeyExpansion()RotWord()функция, которая меняет местами старшие и младшие разряды 16-битного словаSubWord()функция побайтной замены в 16-битном слове⊕операция сложения в поле GF(28 ) (операцияИсключающие-ИЛИ)•операция умножения в поле GF(28 )⊗операция умножения двух многочленов (степенькаждого из которых < 2) по модулю x2 + 1Вход и выход нашего алгоритма представляют собой последовательностииз 32 бит каждая.inp0 inp1 inp2 .

. . inp30 inp31Kout0 out1 out2 . . . out30 out31Промежуточное состояние последовательности во время работы алгоритманазывается state. В начале работы state = inp, а в конце out = state.Каждая последовательность разбивается на четыре группы по 8 бит.state = [s0 s1 s2 s3 ]Эти группы образуют следующий квадрат:2.3s0s2s1s3Математическая интерпретация.Каждая ячейка квадрата (последовательность 8 бит) интерпретируется какзапись коэффициентов многочлена с коэффициентами над полем GF(2) (нумерация идет справа налево).si = [b7 b6 b5 b4 b3 b2 b1 b0 ]b7 x7 + b6 x6 + b5 x5 + b4 x4 + b3 x3 + b2 x2 + b1 x1 + b0 x0 =7Pi=04bi xiНапример, многочлен x6 + x5 + x2 + 1 можно записать в разных формах: вдвоичной — 01100101, или в шестнадцатеричной — 65.

Далее в работе восновном будет использоваться последняя форма записи.Поле GF(28 ) — это поле многочленов с коэффициентами над полем GF(2)по модулю m(x).m(x) = x8 + x4 + x3 + x + 1В данном аспекте никаких изменений в нашей криптосистеме сделаноне было. Следовательно описание операций сложения и умножения в полеGF(28 ) нашей системы совпадает с исходной.Но из-за изменения количества строк и столбцов квадрата, измениласьоперация умножения полиномов с коэффициентами над полем GF(28 ).

Если висходной схеме были многочлены по модулю x4 +1, то в нашем случае модульравен x2 + 1. Выбор такого модуля обусловлен сохранением выражения:xi mod (x2 + 1) = xi mod 2 .Пусть даны два многочлена над полем GF(28 )a(x) = a1 x + a0 , и b(x) = b1 x + b0 .Тогда их сумма будет равнаa(x) + b(x) = (a1 ⊕ b1 )x + (a0 ⊕ b0 ),а произведение равноd(x) = a(x) ⊗ b(x) = d1 x + d0d0 = a0 • b0 ⊕ a1 • b1d1 = a0 • b1 ⊕ a1 • b0Заметим, что если многочлен a(x) фиксирован, то умножение можно записать в матричной форме·¸ ·¸·¸d0a0 a1b0=d1a1 a0b12.4Спецификация алгоритма.Приведем конкретные алгоритмы для зашифрования и расшифрования.

Дляначала отметим, что для обоих алгоритмов раунд состоит из четырех этапов(преобразований различного характера).Первое преобразование — это взаимооднозначная замена одного байта надругой. Это преобразование является нелинейным, в литературе оно носитназвание S-блока. В программной реализации за это преобразование отвечаетфункция SubBytes().Второе преобразование — это циклический сдвиг влево каждой строкина определенное число позиций. В программной реализации за это преобразование отвечает функция ShiftRows().Третье преобразование — это преобразует каждый столбец в другой поопределенному правилу. В программной реализации за это преобразованиеотвечает функция MixColumns().

Второе и третье преобразования вместеобразуют линейное, в литературе оно носит название P-блока.Четвертое преобразование — это сложение по модулю 2 текущего состояния и ключа раунда. В программной реализации за это преобразованиеотвечает функция AddRoundKey().52.4.1 Зашифрование.Полный алгоритм зашифрования описан следующим образом:state = inpAddRoundKey(state, w[0..1])for round = 1 step 1 to Nr–1SubBytes(state)ShiftRows(state)MixColumns(state)AddRoundKey(state, w[round*Nb..round*Nb+1])end forSubBytes(state)ShiftRows(state)AddRoundKey(state, w[Nr*Nb..Nr*Nb+1])out = stateОткуда видно, что последний раунд отличается от всех отсутствием преобразования MixColumns(). Кроме того, можно условно рассматривать первое преобразование AddRoundKey() как 0 раунд.Преобразование SubBytes().

Упрощение данного преобразования является самым значимым, так как выбор определенного S-блока сильно сказывается на результатах методов криптоанализа.Во-первых, зададим подстановку S16 , которая действует на полубайте.0 1 2 3 4 5 6 7 8↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓9 B 8 E A C 6 4 D9 A B C D E F↓ ↓ ↓ ↓ ↓ ↓ ↓F 1 3 5 7 2 0Во-вторых, разделим байт s на старшие sH и младшие полубайты sL .Нелинейное преобразование SB[s] байта s строится следующим образомSB[s] = SB[sH sL ] = [S16 (sH )S16 (sL )].Другими словами, мы заменяем каждую шестнадцатеричную цифру на другую в соответствии с подстановкой S16 .Итоговое преобразование SubBytes() заменяет каждый байт si на SB[si ].Преобразование ShiftRows().