Шифр AES. 
Криптографические методы защиты информации

История AES. В 1997 г. Национальный институт стандартов и технологий США (NIST) объявил о проведении конкурса по замене стандарта DES. На конкурс могли быть присланы алгоритмы шифрования, разработанные как организациями, так и частными лицами в любой стране. Алгоритм — победитель этого конкурса должен был стать новым стандартом блочного симметричного шифрования США.

В конкурсе, которому было присвоено название AES (Advanced Encryption Standart), приняли участие 15 алгоритмов, из которых были отобраны пять финалистов: MARS, RC6, Rijndael, Serpent и Tvvofish. Основными требованиями, предъявляемыми к шифрам-нретендентам, были практическая стойкость и эффективность реализации.

Анализ алгоритмов-иретендентов проводился как специалистами института NIST, так и различными независимыми экспертами. В результате победителем конкурса AES был выбран алгоритм Rijndael, который по большинству критериев оказался лучше остальных ал горитмов-фи нал истов.

Алгоритм Rijndael («рэндал») получил свое название, но именам авторов — В. Рэймена (Vincent Rijment) и Й. Даймена (Joan Daemon). Алгоритм позволяет шифровать данные блоками длиной 128, 192 и 256 бит, которые представляются в виде двумерных байтовых массивов размером 4×4, 4×6, 4×8. Алгоритм использует ключи грех фиксированных размеров: 128, 192 и 256 бит.

В отличие от Rijndael AES' использует для шифрования только 128-битовые блоки текста (двумерный байтовый массив размером 4X4, рис. 2.37). Запись байтов в массив производится, но столбцам. Каждый элемент представляется двузначным шестнадцатеричным числом.

Рис. 2.37. Представление блока входных данных AES.

Структура алгоритма AES. Алгоритм AES имеет структуру «квадрат», разработанную его создателями. Входные данные представлены в виде квадратной таблицы (массива) байтов. Все операции производятся над отдельными байтами массива, а также над независимыми столбцами и строками.

Для шифрования в каждом раунде алгоритма используются следующие преобразования: SubBytes, Shift Rows, MixColumns, AddRonndKey (рис. 2.38).

Рис. 2.38. Раунд шифрования алгоритма AES.

¹ Зенлин О. С., Иванов М. Л. Стандарт криптографической защиты — AES. Конечные поля. М.: КУДИЦ-ОБРАЗ, 2002; FIPS PUB 197. Federal Information Processing Standards Publication. Advanced Encryption Standard (AES). November 26, 2001. URL: http://csrc.nist.gov/ publications/fips/fips!97/fips-197.pdf.

Операция SubBytes (рис. 2.39) представляет собой табличную замену каждого байга массива данных. Замена производится в соответствии с табл. 2.17.

Байты представляются двухразрядными шестнадцатеричными числами. Первый шестнадцатеричный разряд определяет строку, а второй — столбец таблицы замен (см. табл. 2.17), определяющие новое значение байта.

Рис. 239. Операция SubBytes Таблица замен операции SubBytes

Таблица 2.17

Примеры операции SubBytes: 7С —*? 10, F4 —*• BF.

Операция ShiftRows выполняет циклический сдвиг влево последних трех строк массива данных (рис. 2.40).

Пример операции ShiftRows приведен на рис. 2.41.

Операция MixColumns использует вычисления над полем Галуа GF (2⁸). Элементы конечного поля могут быть представлены различными способа;

Рис. 2.40. Операция ShiftRows

Рис. 2.41. Пример операции ShiftRows.

ми. Для любой степени простого числа существует единственное конечное поле, поэтому все представления GF (2⁸) являются изоморфными. Классическим является полиномиальное представление.

Операция MixColumns производится над каждым из столбцов массива данных (рис. 2.42). Выполняется умножение столбца, который рассматривается как полином в конечном поле Галуа GF (2⁸) на фиксированный полином g (x) = З. г^! + х² + х + 2. Умножение выполняется по модулю х⁴ + 1.

Рис. 2.42. Операция MixColumns.

Элементы а_к столбца рассматриваются как коэффициенты полинома третьей степени, в результате новые значения Ь_к столбца байтов могут быть вычислены по формуле.

или.

где «02», «03» — двухразрядные шестнадцатеричные числа; а_к — коэффициенты из GF (2⁸); операция • — умножение над полем Галуа. Каждый коэффициент а_к может быть представлен восьмиразрядным двоичным числом, которому соответствует полином 7-й степени, коэффициенты которого (0 или 1) определяются значениями соответствующих битов.

Пример 2.7.

Представление числа а_к в виде полинома над GF (2⁸).

13_|6 = 10 011₂, полином над GT (2⁸) — х* + х + 1 (табл. 2.18).

BF_ie = 10 111 111₂, полином над GF ( 2⁸) — x'+x⁵ + xⁱ+x^s + x²+x + 1 (табл. 2.19).

Таблица 2.18

Представление числа 13_1б в GF (2⁸)

Таблица 2.19

Представление числа BF₁₆ в GF (2⁸)

В полиномиальном представлении сумма двух элементов является полиномом с коэффициентами, которые равны сумме по модулю 2 коэффициентов слагаемых (т.е. парные слагаемые сокращаются, поскольку 1 + 1 mod 2 = 0).

В двоичном представлении сложение (+) эквивалентно побитовому XOR. В отличие от сложения простой операции умножения на уровне байтов не существует.

В полиномиальном представлении операция умножения представляется в виде умножения полиномов по модулю т (х) — неприводимого двоичного полинома степени 8. Для Rijndael т (х) = х⁸ + х⁴ + х³ + х + 1. Приведение по модулю аналогично делению на полином т{х).

Пример 2.8

Умножение чисел BF и 13 над GF (2⁸). Представления чисел BF и 13 в виде полиномов приведено в примере 2.7. Сократим одинаковые степени х, повторяющиеся кратное число раз (выделены полужирным написанием):

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

Сократим кратные слагаемые:

Старшая степень х превышает 7, добавим к результату

Сократим кратные слагаемые:

Представим результат в двоичном виде (табл. 2.20).

Таблица 2.20

Перевод полинома х⁷ + х⁶ + х* + х³ + х² + х¹ + 1 из GF ( 2⁸) в двоичный вид.

Получили BF • 13 = 11 011 111₂ = DF_I6.

Умножение чисел над полем Галуа GF (2⁸) можно проводить и в двоичном виде. В этом случае можно умножать аналогично обычному умножению «в столбик», однако к результатам по столбцам применяется не суммирование с переносом в старший разряд, a XOR. Для приведения по модулю т (х) двоичная запись этого полинома 100 011 011 подписывается под результатом, начиная со старшего значащего разряда, затем проводится операция XOR. Такая операция приведения повторяется, пока не останется не более восьми значащих разрядов. На рис. 2.43 приведен пример умножения чисел BF и 13 над GF (2⁸), произведенного в двоичном виде: BF₎₆ = 10 111 111₂, 13_]6= 10 011₂.

11 011 111₂ = DF₁₆, таким образом, получили BF • 13 = DF.

Рис. 2.43. Пример умножения чисел, представленных в двоичном виде,.

над GF (2⁸).

Пример 2.9.

Пример операции MixColumns представлен на рис. 2.44.

Рис. 2.44. Пример операции MixColumns.

Продемонстрируем вычисление первого элемента ft, = 04 результирующего столбца операции MixColumns. Согласно выражениям (2.3) Л, =02 • «, + 03 • а₂ + + а₃ + я₄; ft, = 02 • D4 + 03 • BF + 5D + 30.

В полиномиальном представлении получаем.

Сократим кратные слагаемые.

Переведем результат в двоичный вид (табл. 2.21).

Перевод полинома х² из GF (2^s) в двоичный вид.

Таблица 2.21

Получаем.

Операция AddRoundKey (рис. 2.45) выполняет наложение на массив данных материала ключа, а именно: для каждого байта массива данных выполняется побитовая XOR операция с соответствующим байтом ключа раунда.

Рис. 2.45. Операция AddRoundKey.

Ь_ш = а_ы © К_ш> K_i — ключ раунда I

Например, если первый байт массива данных — 04, а первый байт ключа раунда — F5, то результат операции AddRoundKey составит F1.

Примеры операции AddRoundKey: 66 © D5 —? ВЗ; СВ © D2 —? 19. Количество раундов алгоритма AES определяется длиной используемого ключа (табл. 2.22).

Число раундов AES.

Таблица 2.22

Перед первым раундом выполняется предварительное наложение на открытый текст материала ключа с помощью операции Add Round Key. Последний раунд отличается от предыдущих гем, что в нем не выполняется операция MixColumns.

Процедура расширения ключа. Задача процедуры расширения ключа состоит в формировании нужного количество слов расширенного ключа для их использования в операции AddRoundKey. Под «словом» понимается 4-байтный фрагмент расширенного ключа, один из которых используется в первичном наложении материала ключа и по одному — в каждом раунде алгоритма. Таким образом, в процессе расширения ключа формируется 4(r + 1) слов.

Рассмотрим далее процедуру расширения ключа только для алгоритма AES с 128-битовыми ключами (AES-128). Для других значений длины ключа процедура имеет незначительные отличия.

Формируются константы раунда RCon — 4-байтовые столбцы, первый байт которых равен 2' ‘¹ mod 256, i — номер раунда, а остальные байты — нулевые (табл. 2.23).

Таблица 2.23

Значения констант раунда RCon

Ключ K_i раунда i — массив байтов размером 4X4. Обозначим столбцы этой таблицы через 7) _к. Ключ К, раунда i формируется на основании ключа предыдущего раунда К,, и константы раунда RCon_r 7', формируется следующим образом:

К первому столбцу 7', ₄ ключа предыдущего раунда ТС,, применяется преобразование RotWord, заключающееся в циклическом сдвиге на один байт влево. К результату операции RotWord применяется операция SubBytes в соответствии с приведенной ранее табл. 2.17. К результату применяется операция побитового XOR с константой раунда и с T_t, ,.

Пример вычисления первого столбца («слова») ключа 2 раунда приведен на рис. 2.46.

/С, — ключ предыдущего раунда.

Рис. 2.46. Пример вычисления первого слова раундового ключа.

Остальные (кроме первого) столбцы T_{i k}, k * 1 получаются применением к предыдущему столбцу ключа T_ik__{ побитовой операции XOR с соответствующим столбцом Tj__lk ключа предыдущего раунда:

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

Рис. 2.47. Пример вычисления второго—четвертого слов раундового ключа.

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

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

Здесь стоит снова вспомнить алгоритм DES — известно, что DES с независимо задаваемыми ключами раундов оказался слабее против некоторых атак, чем исходный DES.

Процедура расшифрования AES. Структура раунда процедуры расшифрования. Для расшифрования в каждом раунде алгоритма используются следующие преобразования: InvShiftRows, InvSubBytes, AddRoundKey, InvMixColumns (рис. 2.48).

Рис. 2.48. Структура раунда расшифрования алгоритма AES.

Аналогично процедуре шифрования перед первым раундом расшифровки выполняется операция AddRoundKey, накладывающая на шифротекст значения ключа последнего (г) раунда шифрования. Последний раунд раешифровки не содержит операцию InvMixColumns.

Операция Irw Shift Rows производит циклический сдвиг вправо трех последних строк массива данных на то же количество байтов, на которое выполнялся сдвиг операцией Shift Rows при шифровании.

Операция InvSubBytes производит побайтно обратную табличную замену в соответствие с табл. 2.24.

Таблица 2.24

Таблица замен операции InvSubBytes.

Функция Add Round Key обратна сама себе, учитывая свойства используемой в ней операции XOR. Операция AddRoundKey выполняет наложение на массив данных ключа раунда, однако использование ключей раундов при расшифровке производится в обратную сторону (от г — 1 до 0). Таким образом, в г-м раунде расшифровки используется ключ (г — г)-го раунда шифрования — К_г__{.

Операция InvMixColumns выполняет умножение каждого столбца массива данных аналогично прямой операции MixColumns на полиному''(.г) = = Вх³ + Dx² + 9х + Е.

Если сравнить структуру раунда шифрования и расшифрования алгоритма AES, видно, что используются аналогичные операции, по в ином порядке (рис. 2.49). При этом порядок использования раундовых ключей является обратным по отношению к тому, который используется при зашифровании.

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

Два следующих свойства позволяют применить алгоритм прямого расшифрования (рис. 2.50), т. е. алгоритм с тем же порядком применения операций, что и при шифровании:

1) порядок использования операций SubBytes и ShiftRows не играет роли. То же самое верно и для операций InvSubBytes и InvShiftRows. Это про

Рис. 2.49. Сравнение структуры раунда шифрования и расшифрования AES

Рис. 2.50. Раунд прямого расшифрования алгоритма AES.

исходит потому, что функции SubBytes и InvSubBytes работают с байтами, а операции ShiftRows и InvShiftRows сдвигают целые байты, не затрагивая их значения;

2) операция MixColumns является линейной относительно входных данных, что означает:

где State — входной столбец данных операции.

Эти свойства функций алгоритма шифрования позволяют изменить порядок применения функций InvSubBytes и InvShiftRows. Функции AddRoundKey и InvMixColumns также могут быть применены в обратном порядке, но при условии, что столбцы (слова) раундового ключа расшифровки предварительно пропущены через функцию InvMixColumns ().

В табл. 2.25 приведены процедура шифрования, а также два эквивалентных варианта процедуры расшифрования для двухраундового варианта Rijndael. Первый вариант расшифрования представляет обычную инверсию шифрования. Второй вариант получен из первого после изменения порядка следования операций в трех парах преобразований: InvShiftRows — InvSubBytes и AddRoundKey — InvMixColumns.

Видно, что процедура зашифрования и процедура прямого расшифрования совпадают с точностью до параметров операций:

• • значений раундовых ключей, определяемых обратным порядком использования и применением InvMixColumns при расшифровании (при выполнении операции AddRoundKey);
• • направления сдвига (при выполнении операции ShiftRows и InvShiftRows);

Таблица 2.25

Порядок применения операций при шифровании и расшифровании данных для 2-раундового варианта AES.

• • таблиц замен (при выполнении операций SubBytes и InvSubBytes);
• • матриц преобразования (при выполнении операций MixColumns и InvMixColumns).

Аспекты реализации и основные принципы конструкции AES. Шифр AES может быть аффективно реализован на широком диапазоне процессоров и специализированного оборудования.

Разработчики алгоритма Rijndael, лежащего в основе AES, руководствовались тремя критериями:

• 1) устойчивость ко всем известным типам атак;
• 2) скорость и компактность кода на широком диапазоне платформ;
• 3) простота конструкции.

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

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

• • слой линейного перемешивания (ShiftRows, MixColumns) гарантирует высокую диффузию при большом числе раундов;
• • нелинейный слой (SubBytes) — параллельное применение S-блоков, имеющих оптимальные в наихудших случаях нелинейные свойства;
• • слой наложения ключа (Add Round Key) — простое применение раундового ключа с помощью побитного XOR к промежуточному состоянию.

Для того чтобы сделать сам шифр и ему обратный более сходными по структуре, зтап линейного перемешивания последнего раунда отличается от соответствующего этапа в остальных раундах (отсутствует финальная операция MixColumns/InvMixColumns). Можно показать, что это в любом случае не увеличивает и не уменьшает безопасность шифра. Это сходно с отсутствием операции перестановки в последнем раунде DES.

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

• • у алгоритма отсутствуют слабые ключи, а также возможности его вскрытия с помощью атак на связанных ключах;
• • к алгоритму не применим дифференциальный криптоанализ;
• • алгоритм не атакуем с помощью линейного криптоанализа и усеченных дифференциалов;
• • Square-атака (специфичная атака на алгоритмы со структурой «квадрат», к которым относится и ЛЕЗ) также не применима к алгоритму Rijndael.

Впоследствии были приведены некоторые атаки на усеченные версии Rijndael, однако запас криптостойкости алгоритма был признан экспертами адекватным.

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

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

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

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