Усовершенствованный стандарт шифрования (AES — Advanced Encryption Standard)

Алгоритм

Алгоритм 10.1 — простой алгоритм для процедуры расширения ключа (версия AES-128).

$$\tt\parindent0pt

KeyExpansion ([$key_{0}$ to $key_{15}$], [$w_{0}$ to $w_{43}$]

\{ 

for (i = 0 to 3) 

$w_{i} \gets  key_{4i} + key_{4i+1} + key_{4i+2} + key_{4i+3}$

\ for (i = 4 to 43) 

\ \{ 

\ \ \ if (i mod 4 $\ne$  0)  $w_{i} \gets  w_{i-1} + w_{i-4}$

\ \ \ else

\ \ \ \{ 

\ \ \ \ \ t $\gets$  SubWord (RotWord ($w_{i-1}$)) $\oplus$  $RCon_{i/4}$

\ \ \ \ \ $w_{i} \gets  t + w_{i-4}$ \ \ \ \ \     // t  is a temporary word

\ \ \ \} 

\ \} 

\}	$$

Пример 10.1

Таблица 10.3 показывает, как вычисляются ключи для каждого раунда. Предполагается, что между Алисой и Бобом согласован ключ шифра на 128 битов — (24 75 A2 B3 34 75 56 88 31 E2 12 00 13 AA 54 87) 16.

В каждом раунде вычисление последних трех слов очень просто. Для вычисления первого слова мы должны сначала вычислить значение временного слова (t). Например, первое t (для раунда 1 ) вычислено как

Пример 10.2

Каждый ключ раунда в AES зависит от предыдущих ключей раунда. Зависимость, однако, нелинейная из-за преобразования SubWord. Сложение констант раунда также гарантирует, что каждый ключ раунда будет отличаться от предыдущего.

Пример 10.3

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

Как показывает таблица 10.4, имеются существенные разности между двумя соответствующими ключами раунда — R означает "раунд", B и D означают разность битов.

Пример 10.4

Понятие слабых ключей, которое мы обсуждали для DES в лекции 8, не применимо к AES. Предположим, что все биты в ключе шифра — нули. Ниже для этого случая показаны слова для некоторых раундов:

Все слова перед раундом и в первом раунде равны между собой. Во втором раунде первое слово соответствует третьему; второе слово соответствует четвертому. Однако после второго раунда совпадений нет; каждое слово различно.

Расширение ключа в AES-192 и AES-256

Алгоритмы расширения ключей в AES-192 и AES-256 — очень похожи на алгоритм расширения ключа в AES-128, со следующими отличиями:

1. В AES-192 слова сгенерированы в группы по шесть вместо четырех.

a. Ключ шифра создает первые шесть слов ( w0 к w5 ).

b. Если $$i\ mod\ 6 \ne 0$$, то $${w_i} \leftarrow {w_{i - 1}} + {w_{i - 6}}$$ ; иначе $${w_i} \leftarrow t + {w_{i - 6}}$$.

1. В AES-256 слова сгенерированы в группы по восемь вместо четырех.

a. Ключ шифра создает первые восемь слов ( w0 до w7 ).

b. Если $$i{\text{ }}\bmod {\text{ }}8 \ne 0 $$, то $${w_i} \leftarrow {w_{i - 1}} + {w_{i - 8}}$$ ; иначе, wi <-t + wi-8.

c. Если i mod 4=0, но $$i{\text{ }}\bmod {\text{ }}8 \ne 0 $$, то wi = Subword (wi-1) + wi-8.

Анализ расширения ключа

Механизм расширения ключа в AES был разработан так, чтобы обеспечить несколько свойств, которые срывают действия криптоаналитика по раскрытию сообщения.

10.2. Шифры

Теперь посмотрим, как AES использует четыре типа преобразований для шифрования и дешифрования. В стандарте алгоритм шифрования упоминается как шифр и алгоритм дешифрования — как обратный шифр.

Как мы упоминали прежде, ADVANCED ENCRYPTION STANDARD — шифр не-Файстеля, а это означает, что каждое преобразование или группа преобразований должны быть обратимыми. Кроме того, шифр и обратный шифр должны использовать эти операции таким способом, чтобы они отменяли друг друга. Ключи раунда должны использоваться в обратном порядке. Ниже приведены два различных проекта, которые могут быть использованы для различных реализаций. Мы обсудим оба проекта для AES-128; для других версий применяются те же самые проекты.

Первоначальный проект

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

Во-первых, в обратном шифре изменяется порядок следования SubBytes (InvSubBytes) и ShiftRows (InvShiftRows). Во-вторых, в обратном шифре изменен порядок выполнения MixColumns и AddRoundKey. Эти изменения в порядке необходимы, чтобы в обратном шифре сделать порядок работы обратных преобразований инверсным по отношению к прямому шифру. Следовательно, алгоритм дешифрования в целом — инверсия алгоритма шифрования. Мы показали только три раунда, но остальные имеют тот же самый вид. Обратите внимание, что ключи раунда используются в измененном порядке. Обратите также внимание, что алгоритмы шифрования и дешифрования в первоначальном проекте не совпадают.

Алгоритм

Код для версии AES-128 этого проекта показан в алгоритме 10.2. Код для обратного шифра оставляем как упражнение.

$$\tt\parindent0pt

Cipher( InBlock[16], OutBlock[16], w[0…43])

\ 

\{ 

BlockToState (InBlock, S)

\ 

S $\gets$  SubBytes (S)

for (round = 1 to 10)

\{ 

S $\gets$  ShiftRows (S)

If (round $\ne$  10)   S $\gets$  MixColumns (S)

S $\gets$  AddRoundKey (S, w[4 x round, 4 x round + 3])

\} 

StateToBlock (S, OutBlock);

\}	$$

Альтернативный проект

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

Пары SubBytes/ShiftRows

SubBytes изменяет содержание каждого байта, не изменяя порядок байтов матрицы состояний; ShiftRows изменяет порядок байтов в матрице состояний, не изменяя содержание байтов. Это подразумевает, что мы можем изменить порядок этих двух преобразований в обратном шифре, не затрагивая обратимость целого алгоритма; рисунок 10.3 иллюстрирует идею. Обратите внимание, что комбинации двух преобразований — в шифре и обратном шифре — инверсны друг другу.

Пара MixColumns/AddRoundKey

Здесь применяются два преобразования, которые имеют различные свойства. Однако эти пары могут стать инверсиями друг друга, если мы умножим матрицу ключей на инверсию матрицы констант, используемой в преобразовании MixColumns. Мы называем новое преобразование InvAddRoundKey. Рисунок 10.4 показывает новую конфигурацию.

Можно доказать, что эти две комбинации теперь инверсны друг другу. В шифре мы обозначим входную матрицу состояний — S и выходную матрицу — T. В обратном шифре входная матрица — T. Ниже показано, что выходная матрица состояний — также S. Обратите внимание, что преобразование MixColumns — фактически произведение матрицы C (матрицы констант на матрицу состояний).

Теперь мы можем показать шифр и обратный шифр для альтернативного проекта. Обратите внимание, что мы все еще должны использовать два преобразования AddRoundKey в дешифровании. Другими словами, мы имеем девять InvAddRoundKey и два AddRoundKey преобразования, как это показано на рис. 10.5.

Изменение алгоритма расширения ключей

Вместо того чтобы использовать преобразование InvRoundKey в обратном шифре, можно изменить алгоритм расширения ключей так, чтобы создавать различное множество ключей раунда для обратного шифра. Однако отметим, что ключ раунда для операций предварительного раунда и последнего раунда должен быть изменен. Ключи раунда от 1 до 9 необходимо умножить на матрицу констант. Этот алгоритм оставим для упражнений.

10.3. Примеры

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

Пример 10.5

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

Таблица 10.5. показывает значения матрицы состояний и ключей раунда для этого примера.

Пример 10.6

Пример показывает матрицы состояний, раунд 7 в примере 10.5.

Пример 10.7

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

Пример 10.8

Давайте проверим лавинный эффект, который мы обсуждали в лекции 8. Изменим только один бит в исходном тексте и сравним результаты. Мы изменили только один бит в последнем байте. Результат показывает эффект рассеивания и перемешивания. Изменение единственного бита в исходном тексте затронуло много бит в зашифрованном тексте.

Пример 10.9

Ниже показан эффект использования ключа шифрования "все нули".

10.4. Анализ AES

Далее дан краткий обзор трех характеристик AES.

Безопасность

AES был разработан после DES. Большинство известных атак на DES было проверено на AES; ни одна из них до сих пор не нарушила безопасность AES.

Атака грубой силы

AES явно более безопасен, чем DES, из-за большего размера ключа ( 128, 192 и 256 битов). Давайте сравним DES с ключом шифра на 56 битов и AES с ключом шифра на 128 битов. Для DES, чтобы найти ключ, мы нуждаемся в 256 испытаний (игнорируя проблему дополнения ключа); для AES — в 2128 испытаниях. Это означает, что если мы можем нарушить DES в t секунд, нам нужно ( $${2^{72}} \times t$$ ) секунд, чтобы нарушить AES. Это почти невозможно. Кроме того, AES обеспечивает две другие версии более длинными ключами шифра. Отсутствие слабых ключей — еще одно преимущество AES перед DES.

Статистические атаки

Сильное рассеивание и перемешивание, обеспеченное комбинацией преобразований SubByte, ShiftRows и MixColumns, удаляют любую частотную закономерность в исходном тексте. Многочисленные испытания не сумели выполнить статистический анализ зашифрованного текста.

Дифференциальные и линейные атаки

AES был разработан после DES. Дифференциальные и линейные атаки криптоанализа были, без сомнения, учтены. Подобные атаки на AES пока не обнаружены.

Реализация

AES может быть реализован в программном обеспечении, аппаратных средствах и программируемом оборудовании. Реализация может применять процесс поиска в таблице или процедуры, в которых использована четкая алгебраическая структура. Преобразование может быть ориентировано или на байт, или на слово. В ориентированной на байт версии алгоритм может использовать процессор на 8 битов; в ориентированной на слово версии — процессор на 32 бита. В любом случае, обработка делается очень быстро.

Простота и стоимость

Алгоритмы, используемые в AES, настолько просты, что могут быть легко реализованы с помощью дешевых процессоров и минимального объема памяти.

10.5. Рекомендованная литература

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

Книги

[Sta06] [Sti06] [Rhe03], [Sal03], [Mao04] и [TW06] рассматривают AES.

Сайты

Нижеследующие сайты дают больше информации о темах, рассмотренных в этой лекции.

10.6. Итоги

10.7. Набор для практики

Обзорные вопросы

Упражнения