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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ) ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНЫХ МАШИН И СИСТЕМ

Построение и исследование криптосистемы на основе Rijndael.

Москва 2004

1. Введение.

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

На первом этапе мы создадим криптосистему на основе криптографического алгоритма 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, чтобы сохранить общность изложения с другими источниками).

Вход и выход нашего алгоритма представляют собой последовательности из 32 бит каждая.

Промежуточное состояние последовательности во время работы алгоритма называется state. В начале работы state=inp, а в конце out=state.

Каждая последовательность разбивается на четыре группы по 8 бит.

Эти группы образуют следующий квадрат:

[Sorry. Ignored \begin{pspicture} ... \end{pspicture}]

2.3 Математическая интерпретация.

Каждая ячейка квадрата (последовательность 8 бит) интерпретируется как запись коэффициентов многочлена с коэффициентами над полем GF(2) (нумерация идет справа налево).

Например, многочлен можно записать в разных формах: в двоичной — 01100101, или в шестнадцатеричной — 65. Далее в работе в основном будет использоваться последняя форма записи.

Поле — это поле многочленов с коэффициентами над полем GF(2) по модулю m(x).

В данном аспекте никаких изменений в нашей криптосистеме сделано не было. Следовательно описание операций сложения и умножения в поле нашей системы совпадает с исходной.

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

Пусть даны два многочлена над полем

Тогда их сумма будет равна

а произведение равно

Заметим, что если многочлен a(x) фиксирован, то умножение можно записать в матричной форме

2.4 Спецификация алгоритма.

Приведем конкретные алгоритмы для зашифрования и расшифрования. Для начала отметим, что для обоих алгоритмов раунд состоит из четырех этапов (преобразований различного характера).

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

Второе преобразование — это циклический сдвиг влево каждой строки на определенное число позиций. В программной реализации за это преобразование отвечает функция ShiftRows().

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

Четвертое преобразование — это сложение по модулю 2 текущего состояния и ключа раунда. В программной реализации за это преобразование отвечает функция AddRoundKey().

2.4.1 Зашифрование.

Полный алгоритм зашифрования описан следующим образом:

state = inp

AddRoundKey(state, w[0..1])

for round = 1 step 1 to Nr–1

SubBytes(state)

ShiftRows(state)

MixColumns(state)

AddRoundKey(state, w[round*Nb..round*Nb+1])

end for

SubBytes(state)

ShiftRows(state)

AddRoundKey(state, w[Nr*Nb..Nr*Nb+1])

out = state

Откуда видно, что последний раунд отличается от всех отсутствием преобразования MixColumns(). Кроме того, можно условно рассматривать первое преобразование AddRoundKey() как 0 раунд.

Преобразование SubBytes().

Упрощение данного преобразования является самым значимым, так как выбор определенного S-блока сильно сказывается на результатах методов криптоанализа.

Во-первых, зададим подстановку , которая действует на полубайте.

Во-вторых, разделим байт s на старшие и младшие полубайты . Нелинейное преобразование SB[s] байта s строится следующим образом

Другими словами, мы заменяем каждую шестнадцатеричную цифру на другую в соответствии с подстановкой .

Итоговое преобразование SubBytes() заменяет каждый байт на .

Преобразование ShiftRows().

Так как у нас всего две строки, то первая строка остается на месте (сдвиг на 0 позиций), а вторая на 1 позицию.

Преобразование MixColumns().

Каждый столбец нашей системы можно представить как полином 1 степени с коэффициентами над полем . Преобразование MixColumns() заменяет каждый столбец на другой по следующему правилу s'(x)=a(x)Äs(x), где a(x)=03x+02:

Преобразование AddRoundKey(). Это преобразование остается без изменений. Оно заключается в том, что каждый столбец складывается с 16-битным словом расширенного ключа

2.4.2 Расшифрование.

Полный алгоритм расшифрования описан следующим образом:

state = inp

AddRoundKey(state, w[Nr*Nb..Nr*Nb+1])

for round = Nr-1 step -1 downto 1

ShiftRows(state)

InvSubBytes(state)

AddRoundKey(state, w[round*Nb..round*Nb+1])

MixColumns(state)

end for

ShiftRows(state)

InvSubBytes(state)

AddRoundKey(state, w[0..1])

out = state

Алгоритм расшифрования полностью повторяет алгоритм зашифрования в обратном порядке, за исключением одного преобразования InvSubBytes(), которое является обратным к SubBytes(). Остальные преобразования по построению оказались совпали со своими обратными.

Преобразование InvSubBytes().

Данное преобразование по построению эквивалентно своему обратному, разница в том, что вместо подстановки используется обратная к ней подстановка .

2.4.3 Процедура развертывания ключа.

В нашей системе ключ имеет длину 32 бита. Так как на каждом раунде применяется свой раундовый ключ, то расширенный ключ строится с помощью процедуры развертывания ключа KeyExpansion() из исходного ключа K.

Алгоритм этой процедуры следующий:

word temp

i = 0

while (i < Nk)

w[i] = word(key[2*i], key[2*i+1])

i = i+1

end while

i = Nk

while (i < Nb * (Nr+1))

temp = w[i-1]

if (i mod Nk = 0)

temp = SubWord(RotWord(temp)) xor Rcon[i/Nk]

end if

w[i] = w[i-Nk] xor temp

i = i + 1

end while

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

Преобразование RotWord().

Это преобразование меняет местами координаты столбца на столбец . Данное преобразование эквивалентно умножению на x:

w'(x)=w(x)Äx

Преобразование SubWord().