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

Rijndael. Нелинейное преобразование.

Нелинейное преобразование F матрицы данных состоит из трех шагов: замены байтов матрицы на новые значения (S[]), циклического сдвига строк матрицы влево (), умножения матрицы данных слева на постоянную матрицу-циркулянт M:

X' = F(X) = M(S(X)).

Схема преобразования данных показана на рисунке 3, схема соответствующего алгоритма - на рисунке 4.

Рис. 3. Схема нелинейного преобразования блока данных.

Рис. 4. Схема алгоритма нелинейного преобразования.

Все входные (X), выходные (X') и промежуточные (Y, Z) значения преобразования являются матрицами байтов одинакового размера 4n. Функция преобразования последнего раунда F' отличается от регулярной функции преобразования F отсутствием шага умножения матрицы данных слева на постоянную матрицу, схема преобразования блока данных на последнем раунде и схема соответсвующего алгоритма приведены на рисунках 5 и 6 соответственно:

Рис. 5. Схема нелинейного преобразования последнего раунда.

Рис. 6. Схема алгоритма нелинейного преобразования последнего раунда.

Вся нелинейность преобразования сосредоточена в его первом шаге - замене, второй и третий шаги являются линейными. Первый шаг служит для перемешивания информации внутри байтов, второй обепечивает "экспорт" изменений в другие столбцы, третий осуществляет диффузию изменений в одном элементе матрицы на весь соответсвующий столбец. Таким образом, за два раунда достигается диффузия изменений в одном единственном бите на весь блок данных. Ниже каждый из указанных шагов рассмотрен подробно, при этом некоторые преобразования байтов определены в терминах операций в конечном поле GF(2⁸), порожденном неприводимым полиномом m(x) над полем GF(2): m(x) = x⁸+x⁴+x³+x+1. Операция сложения в этом поле является ни чем иным, как побитовым суммированием по модулю 2, умножение в соответствие с определением поля выполняется как обычное умножение полиномов над GF(2) по модулю полинома m(x). При манипулировании с байтами данных как с элементами поля GF(2⁸) каждый бит соответсвует слагаемому вида xⁱ в соответсвии со старшинством бита в байте. Можно сказать, что если байт с целочисленным значением b представлен в виде полинома B(x), то справедливо b = B(2).

Побайтовая замена.

В ходе побайтовой замены каждый байт матрицы данных заменяется на новое значение того же размера, индексируя общий для всех байтов вектор замен S 8-в-8 бит:

y_ij = S[x_ij], 1i4, 1jn,

где n - число столбцов матрицы данных - 4,6 или 8. Единственный узел замен в шифре Rijndael конструируется с помощью следующего алгебраического соотношения:

S[y] = (x⁴+x³+x²+x+1) + y^-1(x⁷+x⁶+x⁵+x⁴+1) mod (x⁸+1).

При этом обращение ненулевых байтов осуществляется в описанном выше конечном поле GF(2⁸), для нулевого байта полагают 0^-1 = 0. Таким образом, байтовая замена определяется как обращение элемента-байта в конечном поле GF(2⁸), доопределенное для нулевого элемента поля, с последующим аффинным преобразованием результата. Коэффициенты этого преобразования выбраны таким образом, чтоб у полученного узла замен отсутсвовали точки неподвижности (S[y] = y), и "антинеподвижности" (S[y] = ~y). Тильдой (знаком "~") обозначена операция побитового дополнения своего аргумента.

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

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

Построчное вращение матрицы.

В ходе данной операции каждая строка матрицы данных, кроме первой, вращается (циклически сдвигается) влево на определенное число позиций, зависящее от номера строки и от размера блока данных:

, 1i4, 1jn.

Первая строка всегда остается на месте: С₁ = 0, для нее приведенная выше формула существенно упрощается: z_1j = y_1j. Ниже в таблице приведены величины сдвига для строк матрицы со второй по четвертую в зависимости от числа столбцов n в матрице:

n	4	6	8
С₂	1	1	1
С₃	2	2	3
С₄	3	3	4

Умножение на постоянную матрицу.

На этом шаге матрица данных слева умножается на постоянную матрицу-циркулянт M:

X = MX,

.

При выполнении матричного умножения операции сложения и умножения элементов обеих матриц выполняются в конечном поле GF(2⁸). Матрица M является циркулянтом: каждая ее строка получается циклическим сдвигом предыдущей строки вправо на один элемент. Элементы матрицы выбраны таким образом, чтобы свести к минимуму трудоемкость операции умножения: в ней присутствуют лишь небольшие по значению числа 01, 02 и 03, половина элементов - единичные, т.е. реального умножения выполнять для них не требуется. Этим самым обеспечивается высокая эффективность возможных реализаций этой операции.

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

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

[Начало осмотра] [Что нового] [Статьи] [Выпуски в "Байтах"] [Что скачать] [Криптоалгоритмы] [Глоссарий] [Ссылки] [Гостевая книга] [Форум] [Напиши мне]