|
Блочный шифр Rijndael
4. Спецификация Rijndael представляет собой итеративный блочный шифр, имеющий переменную длину блоков и различные длины ключей. Длина ключа и длина блока могут быть независимо друг от друга 128, 192 или 256 бит. Замечание: в данном разделе объясняется структура шифра и он не является руководством для реализации. Об аспектах реализации мы говорим отдельно в соответствующем разделе. 4.1 "Состояние", Ключ шифрования и Число Циклов. Разнообразные преобразования работают с промежуточным результатом, называемым Состоянием (State). Определение: промежуточный результат шифрования назовем Состоянием (State) Состояние можно представить в виде прямоугольного массива байтов. Этот массив имеет 4 строки, а число столбцов обозначено как Nb и равно длине блока, деленной на 32. Ключ шифрования также представлен в виде прямоугольного массива с четырьмя строками. Число столбцов обозначено как Nk и равно длине ключа, деленной на 32. Это показано на рисунке 1. В некоторых случаях ключ шифрования показан как линейный массив 4-байтовых слов. Слова состоят из 4 байтов, которые находятся в одном столбце (при представлении в виде прямоугольного массива).
 Рисунок1. Пример представления Состояния (Nb=6) и Ключа шифрования (Nk=4) Входные данные для шифра ( "открытый текст", если используется режим шифрования ECB) обозначаются как байты состояния в порядке a0,0, a1,0, a3,0, a0,1, a1,1, a3,1 ,a4,1 ... После завершения действия шифра выходные данные получаются из байтов состояния в том же порядке. Число циклов обозначено как Nr и зависит от значений Nb и Nk. Оно приведено в Таблице 1.
 Таблица 1: Число циклов (Nr) как функция от длины ключа и длины блока. 4.2 Цикловое преобразование Цикловое преобразование состоит из четырех различных преобразований. На псевдо-Си это выглядит следующим образом:
Round (State, RoundKey)
{
ByteSub(State); // замена байт
ShiftRow(State); // сдвиг строк
MixColumn(State); // замешивание столбцов
AddRoundKey(State, RoundKey); // добавление циклового ключа
}
Последний цикл шифра немного отличается. Вот как он выглядит:
FinalRound(State, RoundKey)
{
ByteSub(State); // замена байт
ShiftRow(State); // сдвиг строк
AddRoundKey(State, RoundKey); // добавление циклового ключа
}
В приведенной записи, "функции" - Round, ByteSub и т.д. выполняют свои действия над массивами, указатели (т.е. State, RoundKey) на которые им передаются. Как можно заметить, последний цикл отличается от простого цикла только отсутствием замешивания столбцов. Каждое из приведенных преобразований разобрано далее. 4.2.1 Замена байт (ByteSub) Преобразование ByteSub представляет собой нелинейную замену байт, выполняемуюю независимо с каждым байтом состояния. Таблицы замены (или S-блоки) являются инвертируемыми и построены из композиции двух преобразований: 1. Первое - получение обратного элемента относительно умножения в поле GF(28), описанного в разделе 2.1. '00' переходит сам в себя. 2. Применение афинного преобразования (над GF(2)), определнного как:
 Применение описанного S-блока ко всем байтам состояния обозначено как ByteSub(State). Рисунок 2 иллюстрирует применение преобразования ByteSub к состоянию.
 Рисунок 2: ByteSub действует на каждый байт состояния. 4.2.2 Преобразование сдвига строк (ShiftRow). Последние 3 строки состояния циклически сдвигаются на различное число байт. Строка 1 сдвигается на С1 байт, строка 2 - на С2 байт и строка 3 - на С3 байт. Значения сдвигов С1, С2 и С3 зависят от длины блока Nb. Их величины приведены в таблице 2.
Таблица 2: Велична сдвига для разной длины блоков. Операция сдвига последних 3 строк состояния на определенную величину обозначена как ShiftRow(State). Рисунок 3 показывает влияние преобразования на состояние.
 Рисунок 3: ShiftRow действует на строки состояния. 4.2.3 Преобразование замешивания столбцов (MixColumn). В этом преобразовании столбцы состояния рассматриваются как многочлены над GF(28) и умножаются по модулю x4+1 на многочлен c(x), выглядящий следующим образом: c(x)='03' x3 + '01' x2 + '01' x + '02' Как описано в разделе 2.2, это может быть представлено в виде матричного умножения. Пусть b(x)=c(x)a(x),
b0 02 03 01 01 a0 b1 01 02 03 01 a1 = b2 01 01 02 03 a2 b3 03 01 01 02 a3 Применение этой операции ко всем четырем столбцам состояния обозначено как MixColumn(State). Рисунок 4 демонстрирует применение MixColumn к состоянию.
 Рисунок 4: MixColumn действует на столбцы состояния. 4.2.4 Добавление циклового ключа В данной операции цикловой ключ добавляется к состоянию посредством простого EXOR. Цикловой ключ вырабатывается из ключа шифрования посредством алгоритма выработки ключей (key schedule). Длина циклового ключа равна длине блока Nb. Преобразование, содержащее добавление посредством EXOR циклового ключа к состоянию, обозначено как AddRoundKey(State, RoundKey). Оно проиллюстрированно на рисунке 5.
 Рисунок 5: При добавлении ключа цикловой ключ складывается посредством EXOR с состоянием. 4.3 Алгоритм выработки ключей (Key Schedule) Цикловые ключи получаются из ключа шифрования посредством алгоритма выработки ключей. Он содержит два компонента: расширение ключа (Key Expansion) и выбор циклового ключа (Round Key Selection). Основополагающие принципы алгоритма выглядят следующим образом: Общее число бит цикловых ключей равно длине блока, умноженной на число циклов плюс 1 (например, для длины блока 128 бит и 10 циклов требуется 1408 бит циклового ключа). Ключ шифрования расширяется в Расширенный Ключ (Expanded Key). Цикловые ключи берутся из Расширенного ключа следующим образом: первый цикловой ключ содержит первые Nb слов, второй - следующие Nb слов и т.д. 4.3.1 Расширение ключа (Key Expansion) Расширенный ключ представляет собой линейный массив 4-ех байтовых слов и обозначен как W[Nb*(Nr+1)]. Первые Nk слов содержат ключ шифрования. Все остальные слова определяются рекурсивно из слов с меньшими индексами. Алгоритм выработки ключей зависит от величины Nk: ниже приведена версия для Nk равного или меньшего 6 и версия для Nk большего 6. Для Nk<6 или Nk=6 мы имеем:
KeyExpansion(CipherKey,W)
{
for (i = 0; i < Nk; i++) W[i] = CipherKey[i];
for (j = Nk; j < Nb*(Nk+1); j+=Nk)
{
W[j] = W[j-Nk] ^ SubByte( Rotl( W[j-1] ) ) ^ Rcon[j/Nk];
for (i = 1; i < Nk && i+j < Nb*(Nr+1); i++)
W[i+j] = W[i+j-Nk] ^ W[i+j-1];
}
}
Как можно заметить, первые Nk слов заполняются ключом шифрования. Каждое последующее слово W[i] получается посредством EXOR предыдущего слова W[i-1] и слова на Nk позиций ранее W[i-Nk]. Для слов, позиция которых кратна Nk, перед EXOR применяется преобразование к W[i-1], а затем еще прибавляется цикловая константа. Преобразование содержит циклический сдвиг байтов в слове, обозначенный как Rotl, затем следует SubByte - применение замены байт. Для Nk>6 мы имеем:
KeyExpansion(CipherKey,W)
{
for (i=0; i < Nk; i++) W[i]=CipherKey[i];
for (j=Nk; j < Nb*(Nk+1); j+=Nk)
{
W[j] = W[j-Nk] ^ SubByte(Rotl(W[j-1])) ^ Rcon[j/Nk];
for (i=1; i < 4; i++) W[i+j] = W[i+j-Nk] ^ W[i+j-1];
W[j+4] = W[j+4-Nk] ^ SubByte(W[j+3]);
for (i=5; i < Nk; i++) W[i+j] = W[i+j-Nk] ^ W[i+j-1];
}
}
Отличие для схемы при Nk>6 состоит в применении SubByte для каждого 4-го байта из Nk. Цикловая константа независит от Nk и определяется следующим образом:
Rcon[i] = ( RC[i], '00' , '00' , '00' ), где 4.3.2 Выбор циклового ключа i-ый цикловой ключ получается из слов массива циклового ключа от W[Nb*i] и доW[Nb(i+1)]. Это показано на рисунке 6.
 Рисунок 6: Расширение ключа и выбор циклового ключа для Nb=6 и Nk=4. Замечание: Алгоритм выработки ключей можно осуществлять и без использования массива W[Nb*(Nr+1)]. Для реализаций, в которых существенно требование к занимаемой памяти, цикловые ключи могут вычисляться на лету посредством использования буфера из Nk слов. 4.4 Шифр Шифр Rijndael состоит из:
На псевдо-Си это выглядит следующим образом:
Rijndael (State, CipherKey)
{
KeyExpansion(CipherKey, ExpandedKey); // Расширение ключа
AddRoundKey(State, ExpandedKey); // Добавление циклового ключа
For ( i=1 ; i < Nr ; i++) Round(State,ExpandedKey+Nb*i); // циклы
FinalRound(State, ExpandedKey+Nb*Nr); // заключительный цикл
}
Если предварительно выполнена процедура расширения ключа, то Rijndael будет выглядеть следующим образом:
Rijndael (State, CipherKey)
{
AddRoundKey(State, ExpandedKey);
For ( i=1 ; i < Nr ; i++) Round(State,ExpandedKey+Nb*i);
FinalRound(State, ExpandedKey+Nb*Nr);
}
Замечание: Расширенный ключ должен всегда получаться из ключа шифрования и никогда не указывается напрямую. Нет никаких ограничений на выбор ключа шифрования. |
Автор проекта: USU Software
Вы можете выкупить этот проект.