Алгоритм развертки ключа

Алгоритм развертки ключа блочного шифра «Кузнечик» является его изюминкой и представляет собой 8-ми раундовую сеть Фейстеля, реализованную на блоке длиной 256 бит.

Для произвольного с € F<2²⁸ и а — аа2 € F^⁵⁶ определим отображение F (c, а) : F^²⁸ х F^⁵⁶ -" F^⁵⁶ равенством.

где R — раундовос преобразование, определенное в (7.25).

Пусть к € F^⁵⁶ — ключ, представленный в виде конкатенации к = fciHfo, где значения к, /сг € F^²⁸ являются начальными элементами последовательности раундовух ключей к,…, /сщ. Алгоритм развертки ключа определяется равенством.

для всех г — 1,…, 4. Последовательность констант сь…, сз2, используемых в данном равенстве, определяется в [3J.

Равенство (7.26) позволяет получить из одной пары раундовых ключей другую, следующую за ней пару. Сравнивая данное равенство с соотношениями (7.5), легко видеть, что равенство (7.26) есть сеть Фейстеля, раундовыми ключами в которой служат константы ci,. •, С₃2.

Сравнение алгоритма «Кузнечик» с алгоритмом AES

Представляет интерес провести сравнение между новым российским алгоритмом шифрования «Кузнечик» и алгоритмом шифрования Rijndael, принятым в качестве стандарта AES. Такое сравнение корректно, поскольку оба блочных шифра обладают одинаковой длиной блока 128 бит и допускают использование ключей длины 256 бит.

Согласно данному нами описанию, принципиальное различие данных шифров заключается в алгоритме развертки ключа. Алгоритм развертки AES представляет простую собой процедуру, см. стр. 235, в которой раундовые ключи формируются как конкатенации 32-х битных «слов», вырабатываемых при помощи рекуррентной процедуры. Алгоритм «Кузнечик» использует для развертки ключа последовательное применение преобразования F, см. стр. 243, которое представляет собой сеть Фейстеля. При этом каждое применение преобразования F позволяет выработать сразу пару раундовых ключей.

Алгоритмы зашифрования обоих шифров очень похожи и могут быть представлены в виде последовательного применения г раундовых преобразований R (ki, a), i = где г = 14 для алгоритма AES и г = 9 для алгоритма «Кузнечик».

Преобразование R (ki, a) имеет вид.

где X — определенное равенством (7.22) преобразование наложения ключа ki, a S — нелинейная перестановка на множестве F₂²⁸, определенная равенством (7.23). При этом, у каждого шифра используется собственная нелинейная перестановка 7г: F⁸ —> F⁸.

Преобразование L для обоих шифров может быть представлено в виде умножения вектора a ? F₂²⁸ на квадратную матрицу С. Действительно, для алгоритма AES представим вектор а € F₂²⁸ в виде конкатенации а = ai|| • • • ац, где аь…, aie принадлежат полю F₂s, порожденному многочленом д (х) = ж⁸ + х⁴ + х³ + х + 1.

Комбинируя преобразования ShiftRows и MixColumns, мы можем записать матрицу С в виде.

где константы ао,…, аз € F₂" и определены в (7.19). Можно заметить, что последовательность элементов в строках матрицы С совпадает с последовательностью элементов матрицы, введенной нами в равенстве (7.20). При этом позиции, на которых располагаются константы ао,…, аз, переставлены в соответствии с перестановкой ShiftRows, заданной равенством (7.18).

Аналогично, для алгоритма «Кузнечик» запишем вектор а Е F₂²⁸ в виде конкатенации а = ai|| • • • ||ai6, где а,…, aie принадлежат полю F₂s, порожденному многочленом д (х) = ж⁸+а:⁷+ж⁶-|-ж-Ь1. Запишем отображение A (a): F₂²⁸ —> F⁸, определенное равенством (7.24), в общем виде, то есть.

и не будем забывать, что операции сложения и умножения выполняются в поле F₂8. Отображение Л, задающее один такт работы линейного регистра сдвига, принимает вид

Тогда после первого такта работы линейного регистра сдвига его заполнение принимает вид.

после второго.

или, комбинируя слагаемые при ai,…, ai6,.

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

или, комбинируя слагаемые при ai,…, aie,.

где? = Ai₅ + A?₆.

Выполнив 16 тактов работы линейного регистра сдвига, мы получим, что каждая ячейка его заполнения L (a) может быть выражена в виде линейной комбинации элементов ai,…, aie с некоторыми коэффициентами. Эти коэффициенты могут быть представлены как значения некоторых многочленов, принимающих значения на величинах Ai,…, Ai6. Таким образом, мы можем представить линейное преобразование L алгоритма «Кузнечик» в виде умножения матрицы на вектор:

где матрица С принимает вид:

Как видно из полученного представления, алгоритм «Кузнечик» обладает плотной матрицей ?, то есть матрицей, не содержащей большого числа нулей¹¹. Матрица алгоритма AES является разреженной, то есть в основном состоящей из нулей. Повидимому, такое различие в матрицах линейного преобразования и привело к тому, что число раундов алгоритма «Кузнечик» существенно меньше, чем в алгоритме AES.

Упражнение 7.5.2. Воспользовавшись введенным нами ранее понятием сопровождающей матрицы, см. раздел 6.1.1, предъявите алгоритм быстрого вычисления используемой в алгоритме «Кузнечик» матрицы С.

Упражнение 7.5.3. Предложите алгоритм быстрой реализации линейного преобразования L алгоритма «Кузнечик», использующего умножение на матрицу С.