Второго октября 2000 года департамент торговли США подвел итоги конкурса по выработке нового стандарта шифрования США. Победителем стал алгоритм «Rijndael», разработанный бельгийскими криптографами. Второго октября 2000 года департамент торговли США подвел итоги конкурса по выработке нового стандарта шифрования США. Победителем стал алгоритм «Rijndael», разработанный бельгийскими криптографами.

Криптоалгоритм ГОСТ , как и большинство шифров «первого поколения», разрабатывавшихся в 70-е годы и в первой половине 80-х, базируется на архитектуре «сбалансированная сеть Фейстеля» Шифр Rijndael имеет архитектуру «квадрат» (Square). Эта архитектура базируется на прямых преобразованиях шифруемого блока, который представляется в форме матрицы байтов. Зашифрование также состоит из серии однотипных шагов, раундов, однако на каждом раунде блок преобразуется как единое целое и не остается неизменных частей блока. Таким образом, за раунд шифруется полный блок, следовательно, для обеспечения сопоставимой сложности и нелинейности преобразования таких шагов требуется вдвое меньше по сравнению с сетью Файстеля.

Каждый раунд заключается в побитовом сложении по модулю 2 текущего состояния шифруемого блока и ключевого элемента раунда, за которым следует сложное нелинейное преобразование блока, сконструированное из трех более простых преобразований. В Rijndael шифруемый блок и его промежуточные состояния в ходе преобразования представляются в виде матрицы байтов 4×n, где n =4, 6, 8 в зависимости от размера блока.

байтовая подстановка - каждый байт преобразуемого блока заменяется новым значением, извлекаемым из общего для всех байтов матрицы вектора замены; побайтовый циклический сдвиг в строках матрицы: первая строка остается неизменной, вторая строка циклически сдвигается влево на один байт, третья и четвертая строка циклически сдвигаются влево соответственно на 2 и 3 байта; матричное умножение - полученная на предыдущем шаге матрица умножается слева на матрицу-циркулянт размера 4x4:

Шифр Rijndael построен на базе прямых преобразований. Как и для всех подобных алгоритмов, обратное преобразование строится из обращений шагов прямого преобразования, применяемых в обратном порядке.

Операция побайтовой замены (S) коммутативна с процедурой побайтового сдвига строк матрицы: Кроме того, согласно правилам матричной алгебры по закону ассоциативности можно также поменять порядок побитового прибавления ключа по модулю два и умножения на матрицу:

Алгоритмическая структура прямого и обратного преобразований идентична

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

Существуют два алгоритма генерации последовательности ключевых элементов - для ключа размером 128/192 бита и для ключа размером 256 бит. Ключ и ключевая последовательность представляются в виде векторов 4-х байтовых слов, и начальный участок последовательности заполняется словами из ключа, точно так же, как в ГОСТе. Последующие слова ключевой последовательности вырабатываются по рекуррентному соотношению группами, кратными размеру ключа.

Первое 4-байтовое слово вырабатывается с использованием сложного нелинейного преобразования, остальные - по простому линейному соотношению: где N k - число 32-битовых слов в ключе (4 или 6) G(w) - нелинейное преобразование 32-битовых слов - включает байтовый сдвиг, побайтовую подстановку по вектору замен и побитовое сложение по модулю 2 с вектором, зависящим от номера вырабатываемой группы элементов: P(i/Nk) - 4-байтовое слово, конструируемое особым образом и не зависящее от ключа. Полученные из описанного выше потока 4-байтовые слова группируются в ключевые элементы необходимого размера, равного размеру шифруемого блока, и используются на раундах шифрования.

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

Операция байтовой замены в алгоритме Rijndael описывается следующим уравнением: Это преобразование начинается с мультипликативной инверсии заменяемого байта в описанном выше конечном поле GF(28), - значение 00 при этом меняется на самого себя, затем результат подвергается аффинному преобразованию. Полиномы этого преобразования выбраны таким образом, чтобы у итогового отображения отсутствовали точки неподвижности (S(X)=X) и «антинеподвижности» (S(X) = ~X). Здесь знаком «~» обозначена операция побитового инвертирования.

При конструировании шифра Rijndael широко использован алгебраический подход. Это касается главным образом двух основных преобразований шифра - байтовой замены и операции перемешивания столбцов матрицы данных посредством ее умножения слева на матрицу М. По оценкам разработчиков шифра Rijndael, уже на четырех раундах шифрования этот алгоритм приобретает достаточную устойчивость к различным видам криптоанализа. Теоретической границей, за которой линейный и дифференциальный виды криптоанализа теряют смысл, является рубеж в 6-8 раундов в зависимости от размера блока. Согласно спецификации, в шифре предусмотрено раундов. Следовательно, шифр Rijndael устойчив к указанным видам криптоанализа с определенным запасом.