А.Винокуров. Серия "Энциклопедия блочных шифров".

Rijndael. Выработка ключевых элементов.

Размер ключа в шифре Rijndael равен 128, 192 или 256 бит. Размер ключевого элемента, используемого на раунде, совпадает с размером блока и также равен 128, 192 или 256 бит независимо от размера ключа. Число раундов шифрования находится в пределах от 10 до 14. Массив ключевых элементов вырабатывается из ключа шифрования с использованием описанной ниже процедуры "развертывания" ключа.

Как и блок данных, ключ может быть представлен в виде массива байтов:

K = (b₁, b₂, ... , ), n_K - размер ключа в байтах, n_K{16, 24, 32}.

Алгоритм развертывания ключа оперирует 32-битовыми ключевыми словами W_i, интерпретируя их как четырехбайтовые массивы:

W_i = (w_i1, w_i2, w_i3, w_i4), | w_ij | = 8.

Первые q = n_K /4 ключевых слов получаются простым разделением ключа K на 4-байтовые фрагменты аналогично тому, как байтами шифруемого блока заполняются столбцы матрицы данных:

W₀ = (b₁, b₂, b₃, b₄),
W₁ = (b₅, b₆, b₇, b₈),
...................................
.

Необходимое число ключевых элементов на 1 больше числа раундов R, каждый ключевой элемент по размеру равен блоку данных (n_B байт) и содержит q_B = n_B /4 ключевых слов. Таким образом, всего необходимо Q = (R+1)q_B ключевых слов. Первые q ключевых слов составлены из байтов ключа как показано выше, остальные Q - q вырабатываются по следующему алгоритму:

При размере ключа 16 или 24 байта (q{4,6}) используется следующая итерационная формула:

,  i = q..Q-1,

а при размере ключа 32 байта (q = 8) следующая:

,  i = q..Q-1.

В приведенных выше формулах использованы следующие обозначения:

• S(W) - побайтовая замена 32-битового слова, т.е. замена всех четырех входящих в него байтов с использованием штатного узла замен S шифра:
  если W = (w₁, w₂, w₃, w₄),
  то S(W) = (S[w₁], S[w₂], S[w₃], S[w₄]);
• - циклический сдвиг 4-байтового вектора на один элемент влево:
  если W = (w₁, w₂, w₃, w₄),
  то (W) = (w₂, w₃, w₄, w₁);
• P_j - 4-байтовый вектор (массив), задаваемый следующей формулой:
  P_j = (02 ^j-1, 00, 00, 00),
  где возведение в степень выполняется в ранее описанном конечном поле GF(2⁸).

Таким образом, все усложняющее преобразование может быть представлено в следующей форме:

S((W))P_j = (S[w₂]02 ^j-1, S[w₃], S[w₄], S[w₁]).

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

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

Каждые последовательно выработанные q_B ключевых слов, - включая те, что получены непосредственно из ключа, - объединяются в раундовые ключевые элементы:

,
,
................................................
.

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

.

Описанная схема используется для выработки ключевых элементов для зашифрования. При расшифровании необходимо выработать ту же самую последовательность элементов, переставить их в обратном порядке, и все элементы, кроме крайних, умножить слева на матрицу M ^-1, как это указано в соответсвующем разделе.

[Список алгоритмов] [Основные характеристики] [Общая схема] [Нелинейное преобразование] [Расшифрование] [Эквивалентность за- и расшифрования] [Выработка ключевых элементов]
 
[Начало осмотра] [Что нового] [Статьи] [Выпуски в "Байтах"] [Что скачать] [Криптоалгоритмы] [Глоссарий] [Ссылки] [Гостевая книга] [Форум] [Напиши мне]

Подготовлено 08.06.01. (c) 2001 Андрей Винокуров.