Математические методы защиты информации. Ч. 2 (90

S-блок есть матрица 4 16 с целыми элементами от 0 до 15. Выбор элемента в матрице Si осуществляется следующим образом: пусть

11

Сi Si (Bi ).

вычисляется из начального ключа K . Процесс формирования ключа можно представить с помощью следующего рисунка

(см. рис. 5).

12

ключ K

Функция G

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

Результат этой перестановки делится на две половины C0 и

влево на одну позицию, если i 1, 2, 9, 16.

При других значениях i , M i – циклический сдвиг влево на две позиции.

13

Наконец, две части Ci и Di соединяются вместе и подаются на вход перестановки H, выходом которой и будет 48-битовый подключ i -го раунда.

Заметим, что существуют 64-битовые последовательности, которые не рекомендуется использовать в качестве ключей, например вектор K {0000}3.

Формирование ключа окончено.

Процесс дешифрования

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

а затем над последовательностью битов R16 L16 выполняются действия, которые можно описать схемой

Алгоритм AES

Общие положения

AES представляет собой алгоритм шифрования 128-битных блоков данных ключами по 128, 192 и 256 бит. AES является упрощенной версией алгоритма Rijndael (этот алгоритм был разработан Винсентом Райманом и Йоан Дамен). Алгоритм Rijndael победил в конкурсе о выборе стандарта шифрования США и был видоизменен для большей стандартизации и назван AES. Алгоритм AES в 2002 году был объявлен стандартом шифрования.

3 {x} число в шестнадцатеричной системе счисления.

14

Алгоритм оперирует байтами, которые рассматриваются как элементы конечного поля GF (28 ). Напомним, что элементами по-

ля GF (28 ) можно описать множество многочленов, степень которых меньше 8, так, например, элементу-вектору (10001011) будет

соответствовать многочлен x7 x3 x 1. Поскольку мы работаем в поле, то зададим операции сложения и умножения: сложение – суть операция поразрядного XOR .

Пример: (x7 x 1) (x6 x 1) x7 x6 ■; умножение – это

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

(x) x8 x4 x3 x 1.

Пример:

((x7 x 1) (x6 x4 x2 x 1)) mod( x8 x4 x3 x 1) x7 x6 1. ■

Раундовые преобразования работают с четырехбайтовыми словами. Этому слову можно поставить в соответствие мно-

будет происходить сложение и умножение четырехбайтовых слов

a(x) и b(x), где a(x) a3x3 a2 x2 a1x a0 , b(x) b3 x3 b2 x2 b1x b0 :

сложение a(x) b(x) (a3 b3 )x3 (a2 b2 )x2 (a1 b1)x (a0 b0 )

умножение с(x) a(x) b(x) c6 x6 c5 x5 c4 x4 c3 x3 c2 x2 c1x c0 ,

где с6 a3 b3 с0 a0 b0 с5 a2 b3 b2 a3

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

Предварительная обработка данных

Промежуточные результаты преобразований, выполняемые в рамках алгоритма, называются состояниями (State). Состояние обычно представляют в виде прямоугольного массива байтов (а

15

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

s00 ,s10 , s20 , s30 , s01, s11,

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

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

В зависимости от длины ключа количество раундов (итераций) будет различным (размер ключа 128 бит – 10 раундов; 196 бит – 12 раундов; 256 бит – 14 раундов).

Процесс шифрования

Общая схема шифрования алгоритма AES может быть представлена следующим рисунком (см. рис. 6).

16

ExpandKey

AddRoundKey

round:=1

SubBytes

ShiftRows

Рис. 6. Схема шифрования: round – текущий раунд; Nr – количество раундов; ExpandKey – вычисление ключей для всех раундов; AddRoundKey – сложение раундового ключа с состояниями (State); SubBytes – замены байтов с помощью побайтовой подстановки; ShiftRows – побайтовый циклический сдвиг строк массива State на различное количество байт; MixColunms – перемешивание столбцов из массива State

Опишем каждую процедуру более подробно.

Процедура SubBytes

Рассматриваемое преобразование заключается в замене каждого байта , которая выполняется с помощью S-блоков. В

алгоритме два типа S-блоков. Один тип применяется для шифрования, а другой – для дешифрования. Таблица замены S-блока состоит из двух преобразований входного байта: 1. Вычисляется мультипликативно обратный элемент в поле GF (28 ) и

записывается как новый байт x (x7 , , x0 ). По соглашению элемент {00}переходит сам в себя. 2. Над полем GF(2) применяется преобразование вида

17

Пример. Найдем замену для байтов {01},{02}

Однако чаще пользуются уже готовой таблицей.

Таблица подстановок S процедуры SubBytes

18

Например, байт {xy} {43} заменится на байт {1a}. Описание процедуры SubBytes завершено.

Процедура ShiftRows

Рассматриваемое преобразование заключается в циклическом сдвиге строк состояния (State). Каждая из ее строк сдвигается на свое число позиций. Первая строка остается неизменной. Во второй производится сдвиг на 1 байт, то есть первый байт переносится в конец. В третьей – сдвиг на 2 байта, в четвертой – на 3.

Пример

Описание процедуры ShiftRows завершено.

Процедура MixColunms

В этом преобразовании столбцы состояния (State) рассматриваются как многочлены над GF (28 ) и умножаются по модулю

где c номерстолбцаизState.

d (x) a(x) g(x), где a(x) {ae}x3 {52}x2 {b4}x {e0}.

19

(x7 x5 x3 x2 x) (x6 x4 x) ((x 1) (x7 x5 x4 x2 )) (x (x7 x6 x5 )) (x7 x5 x3 x2 x) (x6 x4 x) (x7 x6 x2 x 1) (x7 x6 x4 x3 x 1) x7 x6 x5 (11100000) {e0}.

Напомним, что произведение многочленов r(x) h(x) берется

по модулю (x) x8 x4 x3 x 1.

d1 a0 g1 a1 g0 a2 g3 g2 a3 {e0} ({b4} {02}) ({52} {03}) {ae} {cb} d2 a0 g2 a1 g1 a2 g0 a3 g3 {e0} {b4} ({02} {52}) ({ae} {03}) {19}

d3 a0 g3 a1 g2 a2 g1 a3 g0 ({e0} {03}) {b4} {52} ({ae} {02}) {9a}.

В результате получили вектор (e0,cb,19,9a) ■ Описание процедуры MixColunms завершено.

Процедура AddRoundKey

ключа. Раундовый ключ вырабатывается из ключа шифрования посредством алгоритма выработки ключей (процедура ExpandKey).

Пример

Описание процедуры AddRoundKey завершено.

20