Методические указания к лабораторным работам по курсу «Методы и средства защиты компьютерной информации» Волгоград 2008 (стр. 3 из 4)
Рисунок 4. Пример представления состояния (Nb=6) и ключа шифрования (Nk=4)
Входные данные для шифра обозначаются как байты состояния в порядке A0,0, A1,0, A3,0, A0,1, A1,1, A3,1 ,A4,1 ... После завершения действия шифра выходные данные получаются из байтов состояния в том же порядке. Число циклов обозначено как Nr и зависит от значений Nb и Nk. Оно приведено в таблице 4.
| Таблица 4. Число раундов Rijdael как функция от длины блока и длины ключа | |||
| Nr | Nb = 4 | Nb = 6 | Nb = 8 |
| Nk = 4 | 10 | 12 | 14 |
| Nk = 6 | 12 | 12 | 14 |
| Nk = 8 | 14 | 14 | 14 |
Алгоритм шифрования Rijndael состоит из:
1. Начального сложения блока открытого текста с ключом;
2. Nr - 1 раундов основного преобразования;
3. Заключительного раунда.
Преобразование раунда состоит из четырех различных преобразований: табличной подстановки (ByteSub), циклического сдвига строк (ShiftRow), линейного перемешивания столбцов (MixColumn), добавления материала ключа (AddRoundKey). В заключительном раунде из преобразований исключается линейное преобразование столбцов.Преобразование ByteSub является нелинейной байтовой подстановкой, выполняющейся для каждого байта состояния независимо. Таблица подстановки является обратимой и сконструирована в виде композиции двух преобразований:
1.Во-первых, c помощью алгоритма Евклида берется мультипликативная инверсия в GF (28) по модулю полинома m(x) вида m(x) = x8 + x4 + x3 + x + 1. '00' отображается сам в себя (подробнее о полях Галуа и преобразованиях в них см [3]). 2.Затем применяется аффинное (в GF (2)) преобразование, определяемое следующим образом: 
Инверсия ByteSub есть применение байтовой подстановки в соответствии с инверсной таблицей. Это получается инверсией аффинного отображения и мультипликативной инверсией в GF (28).
В преобразовании ShiftRow строки состояния циклически сдвигаются на различные значения. Нулевая строка не сдвигается. Строка 1 сдвигается на С1 байтов, строка 2 на С2 байтов, строка 3 на С3 байтов. Величины С1, С2 и С3 зависят от Nb. Значения приведены в таблице 5.
Инверсией для ShiftRow является циклический сдвиг трех нижних строк соответственно на Nb - С1, Nb - С2 и Nb - С3 байт, чтобы байт в позиции j в строке i перемещался в позицию (j + Nb - Ci) mod Nb.
В преобразовании MixColumn столбцы состояния рассматриваются как полиномы в GF (28) и умножаются по модулю х4 + 1 на фиксированный полином:
c(x) = '03' x3 + '01' x2 + '01' x + '02'. Данный полином является взаимно простым с х4 + 1 и, следовательно, инвертируем. Это может быть записано в виде умножения матрицы. Пусть b(x) = c(x) * a(x).
Инверсия MixColumn является аналогичным MixColumn. Каждый столбец преобразуется умножением его на полином d(x), определяемый следующим образом: ('03' x3 + '01' x2 + '01' x + '02') * d(x) = '01' В результате получаем
d(x) = '0B' x3 + '0D' x2 + '09' x + '0E'Сложение с ключом раунда AddRoundKey выполняется как операция побитового XOR ключа раунда с текущим состоянием. Длина ключа раунда равна длине блока Nb. AddRoundKey является инверсией самого себя.
Ключи раунда получаются из ключа шифрования с помощью преобразования, состоящего из двух компонентов ключа (Key Expansion) и выбор циклового ключа (Round Key Selection). Основополагающие принципы алгоритма выглядят следующим образом:
1. Общее число бит ключей раунда равно длине блока, умноженной на число циклов плюс 1 (например, для длины блока 128 бит и 10 циклов требуется 1408 бит циклового ключа).
2. Ключ шифрования расширяется в Расширенный Ключ (Expanded Key).
3. Цикловые ключи берутся из Расширенного ключа следующим образом: первый цикловой ключ содержит первые Nb слов, второй - следующие Nb слов и т.д.
Expanded Key является линейным массивом четырехбайтных слов и обозначается как W [Nb * (Nr + 1)]. Первые Nk слов состоят из ключа шифрования. Остальные слова определяются рекурсивно. Функция расширения ключа зависит от значения Nk: существует версия функции для Nk, равному или меньшему 6, и версия для Nk больше 6. Для Nk ≤6 мы имеем:
KeyExpansion(byte Key[4*Nk], word W[Nb*(Nr+1)]){ for(i=0;i<Nk;i++) W[i]=(Key[4*i],Key[4*i+1],Key[4*i+2],Key [4*i+3]); for(i=Nk;i<Nb*(Nr+1);i++) { temp=W[i-1]; if (i%Nk==0) temp=ByteSub(RotByte(temp))^Rcon[i/Nk]; W[i]=W[i-Nk]^temp; }}В данном случае ByteSub является функцией, которая возвращает четырехбайтное слово, в котором каждый байт является результатом применения S-box Rijndael к байту в соответствующей позиции во входном слове. Функция RotByte (W) возвращает слово, в котором байты циклически переставлены таким образом, что для входного слова (a, b, c, d) создается выходное слово (b, c, d, a).
Можно заметить, что первые Nk слов заполняются ключом шифрования. Каждое следующее слово W[i] равно XOR предыдущего слова W[i-1] и позиций слова Nk до W[i - Nk]. Для слов в позициях, которые кратны Nk, сначала применяется преобразование XOR к W[i-1] и константой раунда. Данное преобразование состоит из циклического сдвига байтов в слове RotByte, за которым следует применение табличной подстановки для всех четырех байтов в слове (ByteSub).
Для Nk > 6 имеем:
KeyExpansion(byte Key [4*Nk],word W[Nb*(Nr+1)]){ for (i=0;i<Nk;i++) W[i]=(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3]); for (i=Nk;i<Nb*(Nr+1); i++) { temp=W[i-1]; if(i % Nk==0) temp=SubByte(RotByte(temp))^Rcon[i/Nk]; else if (i % Nk==4) temp=SubByte(temp); W[i]=W[i-Nk]^temp; }}Отличие в схеме для Nk
6 состоит в том, что для i-4 кратных Nk, SubByte применяется для W[i-1] перед XOR.Константы раунда не зависят от Nk и определяются следующим образом:
Rcon [i] = (RC [i], '00', '00', '00').RC [i] являются элементами в GF (28) со значением x(i-1) таким, что:
RC [1] = 1 (т.е. '01')RC [i] = x (т.е. '02') • (RC [i-1]) = x(i-1)Ключ раунда i получается из слов буфера ключа раунда W [Nb * i] до W [Nb * (i+1)].
Достоинствами алгоритма Rijndael является хорошее быстродействие, вариативность при выборе длины блока и ключа, возможность распараллеливания процедур шифрации/дешифрации.
Основным недостатком алгоритма является его несимметричность по процедурам шифрации/дешифрации.
Шифр RC6 был также представлен на конкурсе AES группой разработчиков во главе с известным криптографом Рональдом Ривестом. Шифр очень прост, что делает его очень привлекательным для использования в различных прикладных задачах. Он представляет собой сеть Фейштеля из 20 раундов с 4 ветвями смешанного типа – результат образующих функций, вычисленных от четных ветвей, накладывается на нечетные ветви, затем ветви меняются местами. Размер блока – 128 бит. Структура алгоритма приведена на рис.5.
Рисунок 5 – Алгоритм шифрования RC6
Преобразование T представляет собой функцию: T(X)=(X*(2*X+1)) mod 232. Оно используется в качестве нелинейного преобразования с хорошими показателями перемешивания битового значения входной величины. В качестве параметра циклического сдвига на переменное число бит поступает результат умножения, циклически смещенный влево на 5 бит. Таким образом, реально величину переменного сдвига определяют 5 старших бит результата 32-битного умножения – а именно эти биты находятся в центре 64 битного общего (до взятия вычета) произведения, и, следовательно, зависят от всех бит входного параметра X.
Дешифрование алгоритма RC6 производится инвертированием порядка выполняемых в сети Фейштеля действий и заменой операции сложения на вычитание.
Формирование ключей раунда в RC6 происходит следующим образом. Сначала ключ, размер которого может иметь произвольную длину, выравнивается по 32-битной границе нулями. В результате получается массив K из с машинных слов K[0]..K[c-1]. Массив ключей раунда назовем k, всего потребуется 44 элемента. На первом этапе массив k заполняется с использованием специальных констант, полученных из двоичной записи чисел e (основание натурального логарифма) и φ (золотое сечение):
k[i]=B7E1516316 +i*9E3779B916, i=0..43.