Современная прикладная криптография (стр. 7 )

Это может быть представлено в матричном виде следующим образом

Применение этой операции ко всем четырем столбцам состояния обозначено как

Для обращения операции MixColumn необходимо умножить столбец, к которому применялась эта операция, на многочлен обратный к по модулю , т. е. на многочлен ().

Добавление циклового ключа (AddRoundKey).

В данной операции цикловой ключ добавляется к матрице состояния посредством простого поразрядного XOR. Цикловой ключ вырабатывается из ключа шифрования посредством алгоритма выработки ключей (key schedule). Длина циклового ключа должна быть равна длине блокаПреобразование, состоящее в добавлении посредством XOR циклового ключа к матрице состояния (Ошибка! Источник ссылки не найден.), обозначено как AddRoundKey(State, RoundKey).

При добавлении ключа, цикловой ключ складывается посредством операции XOR с матрицей состояния. Эта операция, очевидным образом, обратима.

Алгоритм выработки ключей (Key Schedule)

Цикловые ключи получаются из ключа шифрования с помощью алгоритма выработки ключей. Он состоит из двух частей:

·  расширение ключа (Key Expansion)

·  выбор циклового ключа (Round Key Selection).

Основные принципы алгоритма выглядят следующим образом:

·  общее число бит цикловых ключей равно длине блока, умноженной на число циклов шифрования плюс 1 (например, для длины блока 128 бит и 10 циклов требуется 1408 бит циклового ключа);

·  ключ шифрования расширяется в расширенный ключ (Expanded Key);

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

Расширение ключа (Key Expansion)

Расширенный ключ представляет собой линейный массив 4-байтовых слов и обозначен как .

Первые слов содержат ключ шифрования. Все остальные слова определяются рекурсивно из слов с меньшими индексами. Алгоритм выработки ключей зависит от величины Ниже приведена версия для меньшего или равного 6 и версия для большего 6.

Для имеем:

KeyExpansion(CipherKey, W)

{

for (i = 0; i < Nk; i++) W[i] = CipherKey[i];

for (j = Nk; j < Nb*(Nk+1); j+=Nk)

{

W[j] = W[j-Nk] ^ SubByte( Rotl( W[j-1] ) ) ^ Rcon[j/Nk];

for (i = 1; i < Nk && i+j < Nb*(Nr+1); i++)

W[i+j] = W[i+j-Nk] ^ W[i+j-1];

}

}

Как можно заметить, первые слов заполняются ключом шифрования. Каждое последующее слово W[i] получается посредством XOR предыдущего слова W[i-1] и слова находящегося на позиций левее. Для слов, позиция которых кратна , перед операцией XOR применяется преобразование к W[i-1], а затем еще прибавляется цикловая константа. Преобразование содержит циклический сдвиг байтов в слове, обозначенный как Rotl, затем следует SubByte - замена байт, описанная выше.

Для имеем:

KeyExpansion(CipherKey, W)

{

for (i=0; i<Nk; i++) W[i]=CipherKey[i];

for (j=Nk; j<Nb*(Nk+1); j+=Nk)

{

W[j] = W[j-Nk] ^ SubByte(Rotl(W[j-1])) ^ Rcon[j/Nk];

for (i=1; i<4; i++) W[i+j] = W[i+j-Nk] ^ W[i+j-1];

W[j+4] = W[j+4-Nk] ^ SubByte(W[j+3]);

for (i=5; i<Nk; i++) W[i+j] = W[i+j-Nk] ^ W[i+j-1];

}

}

Отличие по сравнению с ранее рассмотренной схемой состоит в применении SubByte для каждого 4-го байта из

Цикловая константа не зависит от и определяется следующим образом:

Rcon[i] = ( RC[i], '00' , '00' , '00' ), где

RC[0]='01'

RC[i]=xtime(Rcon[i-1])

Выбор циклового ключа

i-й цикловой ключ получается из слов массива циклового ключа от и до как показано на рис. (белым цветом обозначено начальное заполнение; серым цветом обозначены ключи, получаемые только посредством вычислений внутри итерации Б; а черным цветом обозначены ключи, к которым применяется дополнительное преобразование, выполняемое перед итерацией Б).

рис. Расширение ключа и выбор циклового ключа для и

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

Описание алгоритма

В качестве входных данных имеем открытый текст. Выходные данные – зашифрованный текст. Для шифрования открытого текста выполняем следующие действия:

·  разбиваем текст на блоки (текст в блок записывается по столбцам);

·  шифруем каждый блок.

Шифрование блока состоит из следующих этапов:

·  начального добавления циклового ключа;

·  циклов шифрования;

·  заключительного цикла шифрования.

На псевдо-Си это выглядит следующим образом:

Rijndael (State, CipherKey)

{

KeyExpansion(CipherKey, ExpandedKey); // Расширение ключа

AddRoundKey(State, ExpandedKey); // Добавление циклового ключа

For ( i=1 ; i<Nr ; i++) Round(State, ExpandedKey+Nb*i); // циклы

FinalRound(State, ExpandedKey+Nb*Nr); // заключительный цикл

}

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

Rijndael (State, CipherKey)

{

AddRoundKey(State, ExpandedKey);

For ( i=1 ; i<Nr ; i++) Round(State, ExpandedKey+Nb*i);

FinalRound(State, ExpandedKey+Nb*Nr);

}

Расширенный ключ должен всегда получаться из ключа шифрования и никогда не указывается напрямую. На выбор ключа шифрования никаких ограничений не накладывается.

Для расшифровки текста необходимо разбить текст на блоки и к каждому блоку применить обратный алгоритм (см. раздел 0).

Расшифрование

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

InvRound (State, RoundKey)

{

AddRoundKey(State, RoundKey); // добавление циклового ключа

InvMixColumn(State); // перемешивание столбцов

InvShiftRow(State); // сдвиг строк

InvByteSub(State); // замена байтов

}

InvFinalRound(State, RoundKey)

{

AddRoundKey(State, RoundKey); // добавление циклового ключа

InvShiftRow(State); // сдвиг строк

InvByteSub(State); // замена байтов

}

Т. е. необходимо выполнить процедуру InvFinalRound, а затем определенное число раз процедуру InvRound.

Рассмотрим алгебраические свойства обратного преобразования шифра.

Во-первых, порядок операций InvShiftRow и InvByteSub безразличен, т. к. InvShiftRow переставляет байты, но не изменяет их значения, а InvByteSub работает со значениями байтов и не зависит от их позиций.

Во-вторых, последовательность операций:

AddRoundKey(State, RoundKey); // добавление циклового ключа

InvMixColumn(State); // перемешивание столбцов

может быть заменена последовательностью:

InvMixColumn(State); // перемешивание столбцов

AddRoundKey(State, InvRoundKey); // добавление циклового ключа,

где InvRoundKey получен применением InvMixColumn к соответствующему цикловому ключу.

Итак, используя свойства, описанные выше, инверсия двухциклового алгоритма будет следующей:

AddRoundKey(State, ExpandedKey+2*Nb); // добавление циклового ключа

InvByteSub(State); // замена байтов

InvShiftRow(State); // сдвиг строк

InvMixColumn(State); // перемешивание столбцов

AddRoundKey(State, I_ExpandedKey+Nb); // добавление циклового ключа

InvByteSub(State); // замена байтов

InvShiftRow(State); // сдвиг строк

AddRoundKey(State, ExpandedKey); // добавление циклового ключа

Таким образом, получаем обратный шифр, имеющий ту же структуру, как и прямой шифр. Это может быть обобщено на произвольное число циклов. В результате, обратный шифр RIJNDAEL можно записать следующим образом:

I_Rijndael (State, CipherKey)

{

I_KeyExpansion(CipherKey, I_ExpandedKey); // Расширение ключа

AddRoundKey(State, I_ExpandedKey+Nb*Nr); // Добавление циклового ключа

For (i=Nr-1 ; i>0; i--) Round(State, I_ExpandedKey+Nb*i); // циклы

FinalRound(State, I_ExpandedKey); // заключительный цикл

}

А процедуру расширения ключа можно записать так:

I_KeyExpansion(CipherKey, I_Expanded)

{

KeyExpansion(CipherKey, I_ExpandedKey);

for(i=1; I<Nr; i++)

InvMixColumn(I_ExpandedKey+Nb*i);

}

Что касается эффективной реализации обратного алгоритма, то все рекомендации данные ранее для прямого шифра сохраняются в силе.