rijndael (1085219)
Текст из файла
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИМОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ,ЭЛЕКТРОНИКИ И АВТОМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНЫХ МАШИН И СИСТЕМПостроение и исследование криптосистемына основе 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().
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
