Алгоритмы симметричного шифрования. Часть 3. Алгоритмы Rijndael и RC6

Разбить на страницы

Показывать лекцию целиком

Алгоритм Rijndael

Предварительные математические понятия

Практически все операции Rijndael определяются на уровне байта. Байты можно рассматривать как элементы конечного поля GF (2⁸). Некоторые операции определены в терминах четырехбайтных слов. Введем основные математические понятия, необходимые для обсуждения алгоритма.

Поле GF(2^8)

Элементы конечного поля могут быть представлены несколькими различными способами. Для любой степени простого числа существует единственное конечное поле, поэтому все представления GF (2⁸) являются изоморфными. Несмотря на подобную эквивалентность, представление влияет на сложность реализации. Выберем классическое полиномиальное представление.

Байт b, состоящий из битов b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀, представляется в виде полинома с коэффициентами из {0, 1}:

b₇х⁷ + b₆х⁶ + b₅х⁵ + b₄х⁴ + b₃х³ + b₂х² + 
b₁х¹ + b₀

Пример: байт с шестнадцатеричным значением ' 57 ' (двоичное 01010111 ) соответствует полиному

х⁶ + х⁴ + х² + х + 1

Сложение

В полиномиальном представлении сумма двух элементов является полиномом с коэффициентами, которые равны сумме по модулю 2 (т.е. 1 + 1 = 0 ) коэффициентов слагаемых.

Пример: '57' + '83' = 'DA' или в полиномиальной нотации:

(х⁶ + х⁴ + х² + х + 1) + (х⁷ + х + 1) = 
х⁷ + х⁶ + х⁴ + х²

В бинарной нотации мы имеем: 01010111 + 10000011 = 11011010. Очевидно, что сложение соответствует простому XOR (обозначается как $$\oplus$$ ) на уровне байта.

Выполнены все необходимые условия Абелевой группы: операция сложения (каждой паре элементов сопоставляется третий элемент группы, называемый их суммой), ассоциативность, нулевой элемент (' 00 '), обратный элемент (относительно операции сложения) и коммутативность.

Умножение

В полиномиальном представлении умножение в GF (2⁸) соответствует умножению полиномов по модулю неприводимого двоичного полинома степени 8. Полином является неприводимым, если он не имеет делителей, кроме 1 и самого себя. Для Rijndael такой полином называется m(x) и определяется следующим образом:

m(x) = x⁸ + x⁴ + x³ + x + 1

или ' 11B ' в шестнадцатеричном представлении.

Пример: $$'57' ullet '83' = 'C1'$$

Или

(x⁶ + x⁴ + x² + х + 1) (x⁷ + х + 1) =

= x¹³ + x¹¹ + x⁹ + x⁸ + x⁷ + 
                x⁷ + x⁵ + x³ + x² + x + 
				x⁶ + x⁴ + x² + х + 1 =

= x¹³ + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x³ + 1

(x⁸ + x⁴ + x³ + х + 1) (x⁵ + x³) + x⁷ + x⁶ + 1 = x¹³ + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x³ +1

Следовательно,

x¹³ + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x⁸ + 1 mod (x⁸ + x⁴ + x³ + х + 1) = x⁷ + x⁶ + 1

Ясно, что результат является двоичным полиномом не выше 8 степени. В отличие от сложения, простой операции умножения на уровне байтов не существует.

Умножение, определенное выше, является ассоциативным, и существует единичный элемент (' 01 '). Для любого двоичного полинома b(x) не выше 8-й степени можно использовать расширенный алгоритм Евклида для вычисления полиномов a(x) и c(x) таких, что

b(x) a(x) + m(x) c(x) = 1

Следовательно,

$$a(x) ullet b(x) \mod m(x) = 1$$

или

b^-1(x) = a(x) mod m(x)

Более того, можно показать, что

$$a(x) ullet (b(x) + c(x)) = a(x) ullet b(x) + a(x) ullet c(x)$$

Из всего этого следует, что множество из 256 возможных значений байта образует конечное поле GF (2⁸) c XOR в качестве сложения и умножением, определенным выше.

Умножение на х

Если умножить b(x) на полином х, мы будем иметь:

b₇x⁸ + b₆x⁷ + b₅x⁶ + b₄x⁵ + b₃x⁴ + b₂x³ + b₁x² + b₀x

$$x ullet b(x)$$ получается понижением предыдущего результата по модулю m(x). Если b₇ = 0, то данное понижение является тождественной операцией. Если b₇ = 1, m(x) следует вычесть (т.е. XORed). Из этого следует, что умножение на х может быть реализовано на уровне байта как левый сдвиг и последующий побитовый XOR c ' 1B '. Данная операция обозначается как b = xtime (a).

Полиномы с коэффициентами из GF

Полиномы могут быть определены с коэффициентами из GF(2⁸). В этом случае четырехбайтный вектор соответствует полиному степени 4.

Полиномы могут быть сложены простым сложением соответствующих коэффициентов. Как сложение в GF(2⁸) является побитовым XOR, так и сложение двух векторов является простым побитовым XOR.

Умножение представляет собой более сложное действие. Предположим, что мы имеем два полинома в GF(2⁸).

a(x) = a₃x³ + a₂x² + a₁x + a₀
b(x) = b₃x³ + b₂x² + b₁x + b₀

c(x) = a(x) b(x) определяется следующим образом:

$$с(x) = с_{6}x^6 + с_{5}x^5 + с_{4}x^4 + с_{3}x^3 + с_{2}x^2 + с_{1}x + с_{0}\\ с_{0} = a_{0} ullet b_{0}\\ с_{1} = a_{1} ullet b_{0} \oplus a_{0} ullet b_{1}\\ с_{2} = a_{2} ullet b_{0} \oplus a_{1} ullet b_{1} \oplus a_{0} ullet b_{2}\\ с_{3} = a_{3} ullet b_{0} \oplus a_{2} ullet b_{1} \oplus a_{1} ullet b_{2} \oplus a_{0} ullet b_{3}\\ с_{4} = a_{3} ullet b_{1} \oplus a_{2} ullet b_{2} \oplus a_{1} ullet b_{3}\\ с_{5} = a_{3} ullet b_{2} \oplus a_{2} ullet b_{3}\\ с_{6} = a_{3} ullet b_{3}$$

Ясно, что в таком виде с(х) не может быть представлен четырехбайтным вектором. Понижая с(х) по модулю полинома 4-й степени, результат может быть полиномом степени ниже 4. В Rijndael это сделано с помощью полинома

M(x) = x⁴ + 1

так как

x^j mod (x⁴ + 1) = x^{j mod 4}

Модуль, получаемый из а(х) и b(x), обозначаемый $$d(x) = a(x) \otimes b(x)$$, получается следующим образом:

$$d_{0} = a_{0} ullet b_{0} \oplus a_{3} ullet b_{1} \oplus a_{2} ullet b_{2} \oplus a_{1} ullet b_{3}\\ d_{1} = a_{1} ullet b_{0} \oplus a_{0} ullet b_{1} \oplus a_{3} ullet b_{2} \oplus a_{2} ullet b_{3}\\ d_{2} = a_{2} ullet b_{0} \oplus a_{1} ullet b_{1} \oplus a_{0} ullet b_{2} \oplus a_{3} ullet b_{3}\\ d_{3} = a_{3} ullet b_{0} \oplus a_{2} ullet b_{1} \oplus a_{1} ullet b_{2} \oplus a_{0} ullet b_{3}$$

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

Замечание: х⁴ + 1 не является несократимым полиномом в GF (2⁸), следовательно, умножение на фиксированный полином необязательно обратимо. В алгоритме Rijndael выбран фиксированный полином, который имеет обратный.

Умножение на х

При умножении b(x) на полином х будем иметь:

b₃x⁴ + b₂x³ + b₁x² + b₀x

$$x \otimes b(x)$$ получается понижением предыдущего результата по модулю 1 + х⁴.

Это дает

b₂x³ + b₁x² + b₀x + b₃

Умножение на х эквивалентно умножению на матрицу, как описано выше со всеми a_i = '00' за исключением а₁ = '01'. Имеем:

Следовательно, умножение на х соответствует циклическому сдвигу байтов внутри вектора.

Обоснование разработки

При разработке алгоритма учитывались следующие три критерия:

противодействие всем известным атакам;

скорость и компактность кода для широкого круга платформ;

простота разработки.

В большинстве алгоритмов шифрования преобразование каждого раунда имеет структуру сети Фейштеля. В этом случае обычно часть битов в каждом промежуточном состоянии просто перемещается без изменения в другую половину. Преобразование раунда алгоритма Rijndael не имеет структуру сети Фейштеля. Вместо этого преобразование каждого раунда состоит из четырех различных преобразований, называемых слоями.

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

Нелинейный слой состоит из параллельного применения S-boxes для оптимизации нелинейных свойств в наихудшем случае.

Слой линейного перемешивания строк гарантирует высокую степень диффузии для нескольких раундов.

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

Дополнительный слой ключа состоит из простого XOR промежуточного состояния с ключом раунда.

Перед первым раундом применяется дополнительное забеливание с использованием ключа. Причина этого состоит в следующем. Любой слой после последнего или до первого добавления ключа может быть просто снят без знания ключа и тем самым не добавляет безопасности в алгоритм (например, начальная и конечная перестановки в DES). Начальное или конечное добавление ключа применяется также в некоторых других алгоритмах, например IDEA, SAFER и Blowfish.

Для того чтобы сделать структуру алгоритма более простой, слой линейного перемешивания последнего раунда отличается от слоя перемешивания других раундов. Можно показать, что это в любом случае не повышает и не понижает безопасность. Это аналогично отсутствию операции swap в последнем раунде DES.

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

Rijndael является блочным алгоритмом шифрования с переменной длиной блока и переменной длиной ключа. Длина блока и длина ключа могут быть независимо установлены в 128, 192 или 256 бит.

Состояние, ключ шифрования и число раундов

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

Состояние можно рассматривать как двумерный массив байтов. Этот массив имеет четыре строки и различное число столбцов, обозначаемое как Nb, равное длине блока, деленной на 32. Ключ также можно рассматривать как двумерный массив с четырьмя строками. Число столбцов ключа шифрования, обозначаемое как Nk, равно длине ключа, деленной на 32.

В некоторых случаях эти блоки также рассматриваются как одномерные массивы четырехбайтных векторов, где каждый вектор состоит из соответствующего столбца. Такие массивы имеют длину 4, 6 или 8 соответственно, и индексы в диапазонах 0 $$\dots$$ 3, 0 $$\dots$$ 5 или 0 $$\dots$$ 7. Четырехбайтные вектора иногда мы будем называть словами.

Если необходимо указать четыре отдельных байта в четырехбайтном векторе, будет использоваться нотация (a, b, c, d), где a, b, c и d являются байтами в позициях 0, 1, 2 и 3, соответственно, в рассматриваемом столбце, векторе или слове.

(рис 6.1) Пример состояния (с Nb = 6) и ключа шифрования (с Nk = 4)

Входы и выходы Rijndael считаются одномерными массивами из 8 байтов, пронумерованными от 0 до 4* Nb - 1. Следовательно, эти блоки имеют длину 16, 24 или 32 байта, и массив индексируется в диапазонах 0 ... 15, 0 ... 23 или 0 ... 31. Ключ считается одномерным массивом 8-битных байтов, пронумерованных от 0 до 4* Nk - 1.

Входные байты алгоритма отображаются в байты состояния в следующем порядке: А_0,0, А_1,0, А_2,0, А_3,0, А_0,1, А_1,1, А_2,1, А_3,1, ... Байты ключа шифрования отображаются в массив в следующем порядке: K_0,0, K_1,0, K_2,0, K_3,0, K_0,1, K_1,1, K_2,1, K_3,1, ... После выполнения операции шифрования выход алгоритма получается из байтов состояния аналогичным образом.

Следовательно, если одноразмерный индекс байта в блоке есть n, и двухмерный индекс есть (i,j), то мы имеем:

$$I = n\ mod\ 4\\ J = \lfloor n / 4 \rfloor\\ N = i + 4*j$$

Более того, индекс i является также номером байта в четырехбайтном векторе или слове, j является индексом вектора или слова во вложенном блоке.

Число раундов обозначается Nr и зависит от значений Nb и Nk, что показано в следующей таблице.

Число раундов как функция от длины блока и длины ключа
Nr	Nb = 4	Nb = 6	Nb = 8
Nk = 4	10	12	14
Nk = 6	12	12	14
Nk = 8	14	14	14

Преобразование раунда

Преобразование раунда состоит из четырех различных преобразований. В нотации на псевдо С это можно записать следующим образом:

Round (State, RoundKey)
{ 
   ByteSub (State);
   ShiftRow (State);
   MixColumn (State);
   AddRoundKey (State, RoundKey); 
}

Заключительный раунд алгоритма немного отличается и выглядит следующим образом:

FinalRound (State, RoundKey)
{
   ByteSub (State);
   ShiftRow (State);
   AddRoundKey (State, RoundKey);
}

Как мы видим, заключительный раунд эквивалентен остальным, за исключением того, что отсутствует слой MixColumn.

Преобразование ByteSub

Преобразование ByteSub является нелинейной байтовой подстановкой, выполняющейся для каждого байта состояния независимо. Таблица подстановки является обратимой и сконструирована в виде композиции двух преобразований:

Во-первых, берется мультипликативная инверсия в GF (2⁸) с определенным выше представлением. ' 00 ' отображается сам в себя.

Затем применяется аффинное (в GF (2)) преобразование, определяемое следующим образом:

Применение описанного S-box ко всем байтам состояния обозначается как

ByteSub (State)

На рисунке 6.2 показан результат применения преобразования ByteSub к State.

(рис 6.2) Применение ByteSub для каждого байта в State

Инверсия ByteSub есть применение байтовой подстановки в соответствии с инверсной таблицей. Это получается инверсией аффинного отображения и мультипликативной инверсией в GF (2⁸).

Преобразование ShiftRow

В ShiftRow строки состояния циклически сдвигаются на различные значения. Нулевая строка не сдвигается. Строка 1 сдвигается на С₁ байтов, строка 2 на С₂ байтов, строка 3 на С₃ байтов. Величины С₁, С₂ и С₃ зависят от Nb. Значения приведены в следующей таблице.

Величина сдвига в зависимости от длины блока
Nb	С₁	С₂	С₃
4	1	2	3
6	1	2	3
8	1	3	4

Операция сдвига строк на указанные значения обозначается как

ShiftRow (State)

Инверсией для ShiftRow является циклический сдвиг трех нижних строк соответственно на Nb - С₁, Nb - С₂ и Nb - С₃ байт, чтобы байт в позиции j в строке i перемещался в позицию (j + Nb - C_i) mod Nb.

Преобразование MixColumn

В MixColumn столбцы состояния рассматриваются как полиномы в GF (2⁸) и умножаются по модулю х⁴ + 1 на фиксированный полином:

c(x) = '03' x³ + '01' x² + '01' x + '02'

Данный полином является взаимнопростым с х⁴ + 1 и, следовательно, инвертируем. Как было описано выше, это может быть записано в виде умножения матрицы. Пусть $$b(x) = c(x) \otimes a(x)$$

Применение данной операции ко всем столбцам состояния обозначается как

MixColumn (State)

Инверсия MixColumn является аналогичным MixColumn. Каждый столбец преобразуется умножением его на полином d(x), определяемый следующим образом:

$$('03' x^3 + '01' x^2 + '01' x + '02') \otimes d(x) = '01'$$

В результате получаем

d(x) = '0B' x³ + '0D' x² + '09' x + '0E'

Сложение с ключом раунда

Выполняется операция побитового XOR ключа раунда с текущим состоянием. Длина ключа раунда равна длине блока Nb. Данное преобразование обозначается как

AddRoundKey (State, RoundKey)

AddRoundKey является инверсией самого себя.

Создание ключей раунда

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

Общее число битов ключа раунда равно длине блока, умноженной на количество раундов плюс 1. Например, для длины блока 128 бит и 10 раундов необходимо 1408 битов ключа раунда.

Ключ шифрования расширяется в ExpandedKey.

Ключи раунда получаются из этого ExpandedKey следующим способом: первый ключ раунда состоит из первых 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 = SubByte (RotByte (temp)) ^ 
             Rcon [i / Nk];
    W [i] = W [i- Nk] ^ temp; 
  }
}

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

Для 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 (2⁸) со значением x^(i-1) таким, что:

$$RC [1] = 1 (т.е. '01')\\ RC [i] = x (т.е. '02') ullet (RC [i-1]) = x(i-1)$$

Выбор ключа раунда

Ключ раунда i получается из слов буфера ключа раунда W [Nb * i] до W [Nb * (i+1)].

Алгоритм шифрования

Алгоритм шифрования Rijndael состоит из

начального сложения с ключом;

Nr - 1 раундов ;

заключительного раунда.

В С-подобном представлении это выглядит так:

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, ExpandedKey)
{
   AddRoundKey (State, ExpandedKey);
   for (i=1; i < Nr; i++)
      Round (State, ExpandedKey + Nb*i);
   FinalRound (State, ExpandedKey + Nb*Nr)
}

Замечание: расширенный ключ всегда получается из ключа шифрования и никогда не специфицируется непосредственно. Тем не менее, на выбор самого ключа шифрования ограничений не существует.

Преимущества алгоритма

Преимущества, относящиеся к аспектам реализации:

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

Rijndael можно реализовать в смарт-карте в виде кода, используя небольшой RAM и имея небольшое число циклов. Выполнена оптимизация размера ROM и скорости выполнения.

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

Алгоритм шифрования не использует арифметические операции, поэтому тип архитектуры процессора не имеет значения.

Простота разработки:

Алгоритм шифрования полностью "самоподдерживаемый". Он не использует других криптографических компонентов, S-box 'ов, взятых из хорошо известных алгоритмов, битов, полученных из специальных таблиц, чисел типа p и тому подобных уловок.

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

Компактная разработка алгоритма не дает возможности спрятать люки.

Переменная длина блока:

Длины блоков от 192 до 256 бит позволяют создавать хэш-функции без коллизий, использующие Rijndael в качестве функции сжатия. Длина блока 128 бит сегодня считается для этой цели недостаточной.

Расширения:

Разработка позволяет специфицировать варианты длины блока и длины ключа в диапазоне от 128 до 256 бит с шагом в 32 бита.

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

Расширения

Различная длина блока и ключа шифрования

Обработка ключа поддерживает длину ключа, которая была бы кратна 4 байтам. Единственным параметром, который необходим для определения другой длины ключа, отличной от 128, 192 или 256 бит, является число раундов алгоритма.

Структура алгоритма допускает произвольную длину блока, кратную 4 байтам, с минимумом в 16 байтов. Добавление ключа и ByteSub и MixColumn преобразования не зависят от длины блока. Единственным преобразованием, которое зависит от длины блока, является ShiftRow. Для каждой длины блока должен быть определен специальный массив С₁, С₂, С₃.

Можно определить расширение Rijndael, которое также поддерживает длины блока и ключа между 128 и 256 битами с приращением в 32 бита. Число раундов определяется так:

Nr = max (Nk, Nb) + 6

Это расширяет правило для количества раундов для альтернативных длин блока и ключа.

Дополнительные значения С₁, С₂ и С₃ определены в следующей таблице.

Величина сдвига в зависимости от длины блока
Nb	С1	С2	С3
5	1	2	3
7	1	2	4

Другие возможности

Обсудим функции, отличные от шифрования, которые могут выполняться алгоритмом Rijndael.

МАС

Rijndael может применяться в качестве алгоритма МАС. Для этого следует использовать блочный алгоритм в режиме СВС-МАС.

Хэш-функция

Rijndael может использоваться в качестве итерационной хэш-функции. При этом Rijndael применяется в качестве функции раунда. Существует одна возможная реализация. Рекомендуется использовать длину блока и ключа, равной 256 битам. Блок сообщения подается на вход в качестве ключа шифрования. Другим входом является переменная, выход алгоритма XORed с данной переменной, и полученное значение является новым значением этой переменной.

Генератор псевдослучайных чисел

Существует много способов, с помощью которых Rijndael можно использовать в качестве генератора псевдослучайных чисел. Рассмотрим один из них, в котором применяются длина блока и длина ключа 256 бит.

Существует три операции:

Reset:

Ключ алгоритма шифрования и состояние устанавливаются в ноль.

Seeding (и reseeding):

"Seed биты" выбираются таким образом, чтобы обеспечивать минимальную энтропию. Они дополняются нулями до тех пор, пока результирующая строка не будет иметь длину, кратную 256 битам.

Вычисляется новый ключ шифрования шифрованием с помощью Rijndael блока битов seed, используя текущий ключ шифрования. Это выполняется рекурсивно до тех пор, пока все блоки seed не будут обработаны.

Состояние изменяется путем применения Rijndael с новым ключом шифрования.

Генератор псевдослучайного числа:

Состояние изменяется путем применения Rijndael с новым ключом шифрования. Первые 128 бит состояния рассматриваются как псевдослучайное число. Данный шаг может быть повторен много раз.

Алгоритм RC6

RC6 является полностью параметризуемым семейством алгоритмов шифрования. RC6 правильнее указывать как RC6-w/r/b, где w - длина слова в битах, r - число раундов, b - длина ключа. Обычно используются значения w = 32 и r = 20.

(рис 6.3) Алгоритм RC6

Алгоритм является сетью Фейштеля с 4 ветвями смешанного типа: два четных подблока используются для одновременного изменения содержимого двух нечетных подблоков. Затем производится обычный для сети Фейштеля сдвиг на одно слово, что меняет четные и нечетные подблоки местами.

f (x) = x (2x + 1)

a + b - сложение целых по модулю 2^w

a - b - вычитание целых по модулю 2^w

$$a \oplus b$$ - XOR w-битных слов

a x b - умножение целых по модулю 2^w

a <<< b - ротация влево на b бит w-битного слова а

a >>> b - ротация вправо на b бит w-битного слова а

S [0, ..., 2r + 3] - w-битные подключи раунда

Страницы:

Алгоритм Rijndael

Предварительные математические понятия

Поле GF(2^8)

b₇х⁷ + b₆х⁶ + b₅х⁵ + b₄х⁴ + b₃х³ + b₂х² + 
b₁х¹ + b₀

Пример: байт с шестнадцатеричным значением ' 57 ' (двоичное 01010111 ) соответствует полиному

х⁶ + х⁴ + х² + х + 1

Сложение

Пример: '57' + '83' = 'DA' или в полиномиальной нотации:

(х⁶ + х⁴ + х² + х + 1) + (х⁷ + х + 1) = 
х⁷ + х⁶ + х⁴ + х²

Умножение

m(x) = x⁸ + x⁴ + x³ + x + 1

или ' 11B ' в шестнадцатеричном представлении.

Пример: $$'57' ullet '83' = 'C1'$$

Или

(x⁶ + x⁴ + x² + х + 1) (x⁷ + х + 1) =

= x¹³ + x¹¹ + x⁹ + x⁸ + x⁷ + 
                x⁷ + x⁵ + x³ + x² + x + 
				x⁶ + x⁴ + x² + х + 1 =

= x¹³ + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x³ + 1

(x⁸ + x⁴ + x³ + х + 1) (x⁵ + x³) + x⁷ + x⁶ + 1 = x¹³ + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x³ +1

Следовательно,

x¹³ + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x⁸ + 1 mod (x⁸ + x⁴ + x³ + х + 1) = x⁷ + x⁶ + 1

b(x) a(x) + m(x) c(x) = 1

Следовательно,

$$a(x) ullet b(x) \mod m(x) = 1$$

или

b^-1(x) = a(x) mod m(x)

Более того, можно показать, что

$$a(x) ullet (b(x) + c(x)) = a(x) ullet b(x) + a(x) ullet c(x)$$

Умножение на х

Если умножить b(x) на полином х, мы будем иметь:

b₇x⁸ + b₆x⁷ + b₅x⁶ + b₄x⁵ + b₃x⁴ + b₂x³ + b₁x² + b₀x

Полиномы с коэффициентами из GF

Умножение представляет собой более сложное действие. Предположим, что мы имеем два полинома в GF(2⁸).

a(x) = a₃x³ + a₂x² + a₁x + a₀
b(x) = b₃x³ + b₂x² + b₁x + b₀

c(x) = a(x) b(x) определяется следующим образом:

M(x) = x⁴ + 1

так как

x^j mod (x⁴ + 1) = x^{j mod 4}

Модуль, получаемый из а(х) и b(x), обозначаемый $$d(x) = a(x) \otimes b(x)$$, получается следующим образом:

Умножение на х

При умножении b(x) на полином х будем иметь:

b₃x⁴ + b₂x³ + b₁x² + b₀x

$$x \otimes b(x)$$ получается понижением предыдущего результата по модулю 1 + х⁴.

Это дает

b₂x³ + b₁x² + b₀x + b₃

Следовательно, умножение на х соответствует циклическому сдвигу байтов внутри вектора.

Обоснование разработки

При разработке алгоритма учитывались следующие три критерия:

противодействие всем известным атакам;

скорость и компактность кода для широкого круга платформ;

простота разработки.

Слой линейного перемешивания строк гарантирует высокую степень диффузии для нескольких раундов.

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

Дополнительный слой ключа состоит из простого XOR промежуточного состояния с ключом раунда.

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

Состояние, ключ шифрования и число раундов

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

(рис 6.1) Пример состояния (с Nb = 6) и ключа шифрования (с Nk = 4)

Следовательно, если одноразмерный индекс байта в блоке есть n, и двухмерный индекс есть (i,j), то мы имеем:

$$I = n\ mod\ 4\\ J = \lfloor n / 4 \rfloor\\ N = i + 4*j$$

Число раундов обозначается Nr и зависит от значений Nb и Nk, что показано в следующей таблице.

Число раундов как функция от длины блока и длины ключа
Nr	Nb = 4	Nb = 6	Nb = 8
Nk = 4	10	12	14
Nk = 6	12	12	14
Nk = 8	14	14	14

Преобразование раунда

Round (State, RoundKey)
{ 
   ByteSub (State);
   ShiftRow (State);
   MixColumn (State);
   AddRoundKey (State, RoundKey); 
}

Заключительный раунд алгоритма немного отличается и выглядит следующим образом:

FinalRound (State, RoundKey)
{
   ByteSub (State);
   ShiftRow (State);
   AddRoundKey (State, RoundKey);
}

Как мы видим, заключительный раунд эквивалентен остальным, за исключением того, что отсутствует слой MixColumn.

Преобразование ByteSub

Затем применяется аффинное (в GF (2)) преобразование, определяемое следующим образом:

Применение описанного S-box ко всем байтам состояния обозначается как

ByteSub (State)

На рисунке 6.2 показан результат применения преобразования ByteSub к State.

(рис 6.2) Применение ByteSub для каждого байта в State

Преобразование ShiftRow

Величина сдвига в зависимости от длины блока
Nb	С₁	С₂	С₃
4	1	2	3
6	1	2	3
8	1	3	4

Операция сдвига строк на указанные значения обозначается как

ShiftRow (State)

Преобразование MixColumn

c(x) = '03' x³ + '01' x² + '01' x + '02'

Применение данной операции ко всем столбцам состояния обозначается как

MixColumn (State)

$$('03' x^3 + '01' x^2 + '01' x + '02') \otimes d(x) = '01'$$

В результате получаем

d(x) = '0B' x³ + '0D' x² + '09' x + '0E'

Сложение с ключом раунда

AddRoundKey (State, RoundKey)

AddRoundKey является инверсией самого себя.

Создание ключей раунда

Ключ шифрования расширяется в ExpandedKey.

Расширение ключа

Для 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];
    W [i] = W [i- Nk] ^ temp; 
  }
}

Для 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 (2⁸) со значением x^(i-1) таким, что:

$$RC [1] = 1 (т.е. '01')\\ RC [i] = x (т.е. '02') ullet (RC [i-1]) = x(i-1)$$

Выбор ключа раунда

Ключ раунда i получается из слов буфера ключа раунда W [Nb * i] до W [Nb * (i+1)].

Алгоритм шифрования

Алгоритм шифрования Rijndael состоит из

начального сложения с ключом;

Nr - 1 раундов ;

заключительного раунда.

В С-подобном представлении это выглядит так:

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 (State, ExpandedKey)
{
   AddRoundKey (State, ExpandedKey);
   for (i=1; i < Nr; i++)
      Round (State, ExpandedKey + Nb*i);
   FinalRound (State, ExpandedKey + Nb*Nr)
}

Преимущества алгоритма

Преимущества, относящиеся к аспектам реализации:

Простота разработки:

Компактная разработка алгоритма не дает возможности спрятать люки.

Переменная длина блока:

Расширения:

Расширения

Различная длина блока и ключа шифрования

Nr = max (Nk, Nb) + 6

Это расширяет правило для количества раундов для альтернативных длин блока и ключа.

Дополнительные значения С₁, С₂ и С₃ определены в следующей таблице.

Величина сдвига в зависимости от длины блока
Nb	С1	С2	С3
5	1	2	3
7	1	2	4

Другие возможности

Обсудим функции, отличные от шифрования, которые могут выполняться алгоритмом Rijndael.

МАС

Хэш-функция

Генератор псевдослучайных чисел

Существует три операции:

Reset:

Ключ алгоритма шифрования и состояние устанавливаются в ноль.

Seeding (и reseeding):

Состояние изменяется путем применения Rijndael с новым ключом шифрования.

Генератор псевдослучайного числа:

Алгоритм RC6

(рис 6.3) Алгоритм RC6

f (x) = x (2x + 1)

a + b - сложение целых по модулю 2^w

a - b - вычитание целых по модулю 2^w

$$a \oplus b$$ - XOR w-битных слов

a x b - умножение целых по модулю 2^w

a <<< b - ротация влево на b бит w-битного слова а

a >>> b - ротация вправо на b бит w-битного слова а

S [0, ..., 2r + 3] - w-битные подключи раунда

Занятие пройдено

Предыдущее занятие Занятие пройдено Следующее занятие

Вернуться к учебному плану

Алгоритмы симметричного шифрования. Часть 3. Алгоритмы Rijndael и RC6

Алгоритм Rijndael

Предварительные математические понятия

Поле GF(2^8)

Полиномы с коэффициентами из GF

Обоснование разработки

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

Состояние, ключ шифрования и число раундов

Преобразование раунда

Создание ключей раунда

Алгоритм шифрования

Преимущества алгоритма

Расширения

Различная длина блока и ключа шифрования

Другие возможности

МАС

Хэш-функция

Генератор псевдослучайных чисел

Алгоритм RC6

Алгоритм Rijndael

Предварительные математические понятия

Поле GF(2^8)

Полиномы с коэффициентами из GF

Обоснование разработки

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

Состояние, ключ шифрования и число раундов

Преобразование раунда

Создание ключей раунда

Алгоритм шифрования

Преимущества алгоритма

Расширения

Различная длина блока и ключа шифрования

Другие возможности

МАС

Хэш-функция

Генератор псевдослучайных чисел

Алгоритм RC6

Купить дополнительную попытку

Вы действительно хотите купить ещё одну попытку для прохождения тестирования?

Успешно!

Напишите нам, если у вас есть вопросы

Уважаемые пользователи ИНТУИТ!

Уважаемые пользователи ИНТУИТ!

Добро пожаловать на обновлённый сайт НОУ «ИНТУИТ»!