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

Rijndael. Эквивалентность за- и расшифрования.

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

Шаг	Прямое преобразование	Формальное обращение	Обратное преобразование
1	X = XkR–1	X = XkR+1	X = XkR+1
2	X = S(X)	X = (X)	X = S –1(X)
3	X = (X)	X = S –1(X)	X = (X)
4	X = MX	X = XkR	X = M –1X
5	X = XkR	X = M –1X	X = X(M –1kR)
6	X = S(X)	X = (X)	X = S –1(X)
7	X = (X)	X = S –1(X)	X = (X)
8	X = XkR+1	X = XkR–1	X = XkR–1

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

- обращением операции побитового прибавления ключевого элемента является эта же самая операция;

- обращением операции побайтовой замены является операция того же типа, в которой используется обратный узел замен;

- обращением операции построчного вращения матрицы данных влево является операция вращения строк матрицы вправо на те же самые величины сдвига;

- обращением операции умножения слева на матрицу является умножение слева на обратную ей матрицу.

Далее были выполнены тождественные преобразования последовательности операций из столбца 2, при этом использовались следующие тождества:

1.  Так как побайтовая замена элементов матрицы всегда осуществляется с помощью одного и того же узла замен, а операция построчного вращения матрицы (в любом направлении) лишь переставляет байты матрицы не меняя их значения, две указанные операции коммутативны:

S ^–1((X)) = (S ^–1(X)).

Применив это тождество к содержимому пар строк 2 и 3, а также 6 и 7 второго столбца таблицы, получим соответствующие пары строк в третьем столбце.

2.  В алгебре матриц над конечным полем GF(2⁸) справедлив дистрибутивный закон - произведение некоторой матрицы на сумму двух матриц является суммой произведений этой матрицы на каждую из двух матриц:

M ^–1(Xk_R) = (M ^–1X)(M ^–1k_R).

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

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

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

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