Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Итак, 128-битовый блок сообщения (исходного или зашифрованного) разбивается на сегменты по 16 байт (один байт состоит из восьми бит, т.е. 128 = 16 х 8).
InputBlock = mo, mi,...,mis-
Аналогичная операция выполняется над блоком ключа.
InputKey = ко, к\,..., к^.
268
Часть III. Основные методы криптографии
Для внутреннего представления данных используется матрица 4x4.
ТТЦ т5 m9 т13
ш2 me тю mi4 ' ^m3 m^ mu mis;
(к,
ki &5 kg ki3
k2 ке кю ki4 ^k3 k7 кц ki5j
Как алгоритм DES (и большинство современных симметричных блочных шифров), алгоритм Rijndael состоит из большого количества повторяющихся преобразований — раундов. В минимальном варианте, когда размеры блока и ключа равны 128 бит, количество раундов равно 10. Для более крупных сообщений и ключей количество раундов может возрастать, как показано в работе [219].
Преобразование, выполняемое внутри раунда, обозначается как
Round (State, RoundKey).
Здесь переменная State представляет собой матрицу, содержащую сообщение раунда, и считается как входом, так и результатом раунда, а переменная RoundKey представляет собой матрицу, содержащую ключ раунда, и создается на основе входного ключа с помощью расписания ключей. Преобразования внутри раунда' должно изменять элементы матрицы State (т.е. изменять состояние). При шифровании (соответственно при расшифровке) матрица State, поступающая на вход первого раунда, совпадает с матрицей InputBlock и содержит исходный текст (соответственно зашифрованный текст). В свою очередь, матрица State, возникающая в результате заключительного раунда, содержит зашифрованный текст (соответственно исходный текст).
Преобразования, выполняемые в ходе промежуточных раундов, разбиваются на четыре операции, которые являются внутренними функциями (они будут описаны позднее). Round (State, RoundKey) {
SubBytes(State),
ShiftRows(5tate),
MixColumns(State),
AddRoundKey (State, RoundKey);
}
InputBlock =
InputKey =
Глава 7. Шифрование — симметричные методы
269
Последний раунд обозначается как
FinalRound(S'ta/e, RoundKey).
Он немного отличается от остальных и совпадает с раундом Round(S'to/e, RoundKey) с удаленной матрицей MixColumns. Этот раунд напоминает заключительный раунд алгоритма DES, в котором выполнялась дополнительная перестановка половин результирующего блока.
Для обеспечения расшифровки преобразования раунда являются обратимыми. Обратные преобразования раунда обозначаются как
Round-1 (State, RoundKey)
и
FinalRound_1(S,tate,/?oi/wfifATey). Далее будет показано, что все четыре внутренние функции являются обратимыми.
7.7.2 Внутренние функции алгоритма Rijndael
Опишем четыре внутренние функции алгоритма Rijndael. Рассмотрим лишь функции, предназначенные для шифрования. Поскольку каждая из них является обратимой, расшифровка в алгоритме Rijndael просто сводится к применению обратных функций в обратном порядке.
Внутренние функции шифра Rijndael определены на конечном поле. Это поле состоит из всех полиномов по модулю неприводимого полинома
f(x) = х8 + х4 + х3 + х + 1
над полем ?2- Иначе говоря, шифр использует поле ?2[х}3а+х*+э?+х+1- Любой элемент этого поля является полиномом над полем F2, степень которого меньше восьми, а операции выполняются по модулю f(x). Назовем это поле "полем Rijndael". Благодаря изоморфизму это поле можно переобозначить как F2s. Оно состоит из 28 = 256 элементов.
На самом деле мы уже изучали поле Rijndael в главе 5 (примеры 5.17, 5.18 и 5.19), где были продемонстрированы следующие операции.
• Отображение между байтом и элементом поля (пример 5.17).
• Сложение двух элементов поля (пример 5.18).
• Умножение двух элементов поля (пример 5.19).
Эти сведения помогут нам изучить внутренние функции шифра Rijndael.
Во-первых, как уже указывалось, блок сообщения (состояние) и блок ключа в шифре Rijndael разбиты на байты. Учитывая взаимно-однозначное отображение, рассмотренное в примере 5.17, эти байты можно рассматривать как элементы поля и обрабатывать внутренними функциями шифра Rijndael.
270
Часть III. Основные методы криптографии
7.7.2.1 Внутренняя функция SubBytes(57a?e)
Эта функция выполняет нелинейную подстановку каждого байта (т.е. числа] х) в переменной State. Любой ненулевой байт х ? (F28)* заменяется с помощью следующего преобразования:
у = АаГ1 + Ъ,
(7.7.1)'
где
А =
А 0 0 0 1 1 1 1 0 0 0 1 10 0 0
1 1 1 1
0 0 0 1
о о
А
1 1 1
ъ =
1
о о о 1 1
ООО 10 0 0 110 0 1110
1 1 1 lj
Если число х является нулевым байтом, результатом преобразования SubBytes является число у = Ь.
Следует отметить, что нелинейность преобразования (7.7.1) обеспечивается исключительно нелинейностью инверсии х~1. Если бы это преобразование применялось непосредственно к элементу х, аффинное уравнение (7.7.1) было бы абсолютно линейным1.
Поскольку матрица А, имеющая размер 8x8, является обратимой (т.е. ее строки линейно независимы в поле F2e), преобразование (7.7.1) также обратимо. Следовательно, функция SubBytes(Stoe) имеет обратную.
7.7.2.2 Внутренняя функция ShiftRows(5'tate)
