на многочлен

а(х) = Озх + агУ? + а\Х +

и деления на

{х) = х+\,

На получение результата (остатка от деления произведения а{х)Ь{х) на ф(д:)) требу, ется 4 такта. Подача на вход устройства при нулевом начальном состоянии последова. тельности 1000 вызывает следующую последовательность переключений регистров:

Каждое состояние приведенной последовательности дает соответствующий столбец матрищ>1 преобразования, обеспечивающего получение того же результата за один такт.

Рис. 2.8.1. Устройство для одновременного умножения и деления многочленов Пусть

Ь{х) = + Ът + 6,х + Ьо-Умножению на х многочлена й(х) с коэффтщентами из GF{2) по модулю многочлена

ф(д:) = д: +1,

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

X ® Ь{х) = biC + b\x + b + Ьг.

2.8.3. Структура шифра

RIJNDAEL - это итерационный блочный щифр, имеющий архитектуру "квадрат" (Р" 2.8.2, а). Рассеивающие и перемещивающие свойства шифра иллюстрирует рис. 2.8.2,

фр имеет переменную длину блоков и различные длины ключей. Длина ключа и дли

блока могут быть равны независимо друг от друга 128, 192 или 256 битам. " Промежуточные результаты преобразований, выполняемых в рамках криптоалгорит

называются состояниями (state). Состояние (рис. 2.8.2) можно представить в вид( пямоугольного массива байтов. Этот массив имеет 4 строки, а число столбцов Л* равнс не блока, деленной на 32.

Р01ЮЧ шифрования также представлен в виде прямоугольного массива с четырьмя (•троками. Число столбцов N равно длине ключа, деленной на 32.

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

Входные данные для шифра обозначаются как байты состояния в порядке яоо, alo го азо, Ооь «1ь «21, Язь 41 ••• После завершения действия шифра выходные данные получаются из байтов состояния в том же порядке.

Число раундов Л,, зависит от значений Nb и Л;, как показано в таблице 2.8.1.

Функция 6 зашифрования

WHDAet

Входной блок

Добавление раундового ключа AddRoundKey

Замена байтов SubBytes

Сдвиг строк ShiftRom

Перемешивание столбцов MixColumns

Добавление раундового ключа AddRoundKey

Замена байтов SubBytes

Сдвиг строк 5/jr/t/?ow5

Перемешивание столбцов MixColumns

Добавление раундового ключа AddRoundKey

Замена байтов SubBytes

Сдвиг строк 5/jlft/?ow5

Добавление раундового ключа AddRoundKey

1-й раунд

9-й раунд

10-й раунд

Выходной блок

Входной блок

MixCoiumns 1-го раунда

ShiftRom 2-го раунда

MixCoiumns 2-го раунда

"С. 2.8.2. Криптоалгоритм RIJNDAEL:

а - схема функции Ек зашифрования при Nk = Мь = 4; 5 - принцип действия

Рис. 2.8.3. Пример представления состояния (Nk = 4) и ключа шифрования (Nk = 4)

Таблица 2.8.1. Число раундов N, как функция от длины ключа Nk и длины блока

Раундовое преобразование. Раунд состоит из четырех различных преобразовани (см. рис. 2.8.2, а). На псевдо-Си это выглядит следующим образом:

=================================================================

Round (State, RoundKey) 1

SubBytes(State); SliiftRows (State) ; MixColumns(State); AddRoundKey(State, RoundKey);

замена байтов

сдвиг строк

перемешивание столбцов

добавление раундового ключа

Последний раунд шифра немного отличается от остальных. Вот как он выгляди

=================================================================

FinalRound(State, RoundKey) I

SubBytes(State); ShiftRows(State); AddRoundKey(State, RoundKey); )

замена байтов сдвиг строк

добавление раундового ключа

В приведенной записи функции {Round, SubBytes и т. д.) выполняют свои действ над массивами, указатели (т. е. State, RoundKey) на которые им передаются.

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

Замена байтов (SubBytes). Преобразование SubBytes представляет собой нели нейную замену байтов, выполняемую независимо над каждым байтом состояния -раблииы замены S-блока являются инвертируемыми и построены из композици1 двух преобразований:

J) получение обратного элемента относительно умножения в поле GF{2\ нулевой эле мент 00 переходит сам в себя;

0 0 0 1 1 1 1

0 0 0 1 1 1

1 0 0 0 1 1 11 0 0 0 1 1110 0 0

0 111110 0 0 0 111110

0 0 0 1 1 1 1 1

Применение описанного S-блока ко всем байтам состояния обозначено как SubByte (State). Рис. 2.8.4 иллюстрирует применение преобразования SubBytes к состоянию.

5-6лок

Рис. 2.8.4. SubBytes действует на каждый байт состояния

Преобразование сдвига строк (ShiftRows). Последние 3 строки состояния цикличе сдвигаются на различное число байт. Строка 1 сдвигается на С1 байт, строка 2 - н J2 байт и строка 3 - на СЗ байт. Значения сдвигов С1, С2 и СЗ зависят от длины блок

К Их

величины приведены в таблице 2.8.3.

Таблица 2.8.3. Величина сдвига для разной длины блоке

Ассемблер в задачах защиты информац i 33 2. ПР?.Т.?.!!?Р?!!.!1!1.?°Р..™?

Операция сдвига последних 3 строк состояния на определенную величину обозначен, KaKShiftRos (State). Рис. 2.8.5 показывает влияние преобразования на состояние.

Рис. 2.8.5. ShiftRows действует на строки состояния

Преобразование перемешивания столбцов (MixCoIumns). В этом преобразовании столбцы состояния рассматриваются как многочлены над GF(2) и умножаются по мол\. лю х" + 1 на многочлен g(x), выглядящий следующим образом:

g{x) = 03 х + 01 х +0\х+ 02. Это может быть представлено в матричном виде следующим образом \Ь, 02 03 01 О Г 01 02 03 01 01 01 02 03 \а. 03 01 01 02 Применение этой операции ко всем четырем столбцам состояния обозначено как MixColumn{State). Рис. 2.8.6 демонстрирует применение преобразования MixColumn к столбцу состояния.

Рис. 2.8.6. MixCoIumns действует на столбцы состояния

Добавление раундового ключа. В данной операции раундовый Jc ксостояншо посредством простого поразрядногаХШ. Py.JSulTA из ключа шифрования посредством алгоритма выработки ключей (key schedule), tv

ового ключа равна длине блока Мь- Преобразование, содержащее добавление по-ецством XOR раундового ключа к состоянию (рис. 2.8.7), обозначено как

JjdRoundKeyiState, RoundKey).

Рос. 2.8.7. При добавлении ключа раундовый ключ складьвается посредством операции XOR с состоянием

Алгоритм выработки ключей (Key Schedule). Раундовые ключи получаются из ключа шифрования посредством алгоритма выработки ключей. Он содержит два компонента: расширение ключа (Key Expansion) и выбор раундового ключа {Round Key Selection). Основополагающие принципы алгоритма выглядят следующим образом:

общее число бит раундовых ключей равно длине блока, умноженной на число раундов плюс 1 (например, для длины блока 128 бит и 10 циклов требуется 1408 бит циклового ключа);

ключ шифрования расширяется в расширенный ключ {Expanded Key);

ш раундовые ключи берутся из расширенного ключа следующим образом: первый раундовый ключ содержит первые jV;, слов, второй - следующие Nh слов и т. д.

Расширение ключа (Key Expansion). Расширенный ключ представляет собой линейный массив 4-байтовых слов и обозначен как

W[Nb{K+l)].

Первые Nk слов содержат ключ шифрования. Все остальные слова определяются рекурсивно из слов с меньшими индексами. Алгоритм выработки ключей зависит от величины Ниже приведена версия для Л, равного или меньшего 6, и версия для Nk, большего 6.

Для TVfc < 6 имеем:

%Expansion(CipherKey,W)

(i = 0; i < Nk; i++) W[i] = CipherKey[i]; (j = Nk; j < NbMNk+1); j+=Nk)

b] = W[i-Nk] SubBytesC Rotl( W[j-1] ) ) Rcon[j/Nk]; J. <i = 1; i < Nk SS i+j < Nb*(Nr+l); i++) Щ] = W[i+j-Nkl W[i+j-l];