Принципы шифрования данных в стандарте AES

Содержание

1. 1. Криптографический контекст и задачи AES3
2. 2. Математические основы и структура блока5
3. 3. Раундовые преобразования и их назначение7
4. 4. Расширение ключа и итоговая оценка стойкости9

1. Криптографический контекст и задачи AES

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

Долгое время эталоном симметричных алгоритмов оставался DES, принятый в США ещё в 1977 году. К концу 1990-х его 56-битный ключ перестал быть надёжным барьером: при достаточных вычислительных мощностях его можно было вскрыть полным перебором. Нужен был принципиально новый стандарт, и в 1997 году Национальный институт стандартов и технологий (NIST) объявил открытый конкурс. Участвовать могли все желающие, критерии отбора публиковались заранее. Первый этап прошли пятнадцать кандидатов. После нескольких лет публичных обсуждений, тестов и криптоаналитических атак победил алгоритм Rijndael, предложенный бельгийскими криптографами Винсентом Рэйменом и Джоан Даймен.

В 2001 году NIST официально утвердил Rijndael как стандарт AES (Advanced Encryption Standard). Он сменил DES, который к тому моменту уже не отвечал актуальным требованиям. Финальный выбор был сделан не за закрытыми дверями, а по итогам публичной экспертизы: любой желающий мог попытаться найти уязвимости в предлагаемых алгоритмах. Такой подход в криптографии стал образцом прозрачности.

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

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

AES относится к классу блочных шифров. Это значит, что он обрабатывает данные не побайтово, а фиксированными порциями. Размер блока в AES составляет 128 бит, то есть 16 байт. Если исходное сообщение длиннее, его разбивают на такие блоки и обрабатывают каждый отдельно, используя определённый режим сцепления. Длина ключа при этом может быть 128, 192 или 256 бит, что определяет количество раундов преобразования, хотя сама структура алгоритма остаётся неизменной. Именно сочетание фиксированного размера блока и переменной длины ключа сделало AES универсальным, и это позволило ему стать основой современных протоколов шифрования.

2. Математические основы и структура блока

Любая операция в AES, независимо от её сложности, работает не с потоком битов, а с конечной структурой данных. В спецификации алгоритма, опубликованной NIST в 2001 году, эта структура называется «состоянием» (state). Это двумерный массив размером 4 на 4 байта, который заполняется входным блоком в 128 бит. Можно представить матрицу, где каждый элемент это один байт, то есть восемь бит. Такой формат позволяет унифицировать все преобразования: перестановки, замены и смешивание данных.

Байт в этой матрице является атомарной единицей. С точки зрения памяти, блок это просто последовательность из 16 байт, но логически он организован по колонкам. Сначала массив заполняется по столбцам: первый байт входных данных попадает в первую строку первой колонки, пятый байт во вторую строку первой колонки, и так далее. Эта схема напрямую влияет на скорость работы алгоритма на процессорах с 32-битной архитектурой. Если бы байты шли подряд, процессору пришлось бы выполнять лишние операции для извлечения и упаковки данных. Колоночная структура позволяет загрузить целую колонку как одно 32-битное слово.

Однако просто хранить данные мало, с ними нужно выполнять арифметические операции. Здесь возникает принципиальная сложность: обычное сложение и умножение байтов не подходит, так как результат может выйти за пределы 8 бит. Поэтому в AES все вычисления выполняются не в целых числах, а в конечном поле Галуа, обозначаемом как GF(2^8). Это поле содержит ровно 256 элементов, что идеально совпадает с количеством возможных значений байта. Сложение в этом поле это простая операция XOR, а вот умножение устроено сложнее.

Чтобы перемножить два байта, их представляют как полиномы с бинарными коэффициентами. Например, число 0x57 (бинарно 01010111) превращается в полином x^6 + x^4 + x^2 + x + 1. Умножение двух таких

полиномов даёт результат степени до 14, который не помещается в один байт. Чтобы вернуть результат в поле, его делят на неприводимый полином m(x) = x^8 + x^4 + x^3 + x + 1, выбранный создателями алгоритма Йоаном Дайменом и Винсентом Рэйменом. Остаток от такого деления и есть искомый байт. Это гарантирует, что произведение двух любых ненулевых элементов никогда не даст ноль, а значит, для каждого байта существует обратный элемент.

Именно полиномиальная природа поля обеспечивает нелинейность, которая критична для безопасности. Если бы преобразования были линейными, как обычное сложение, злоумышленник мог бы решить систему уравнений и восстановить ключ. Умножение в GF(2^8) с редукцией по неприводимому полиному ведёт себя непредсказуемо: малейшее изменение входного байта приводит к совершенно другому результату на выходе. Эта математическая конструкция лежит в основе S-блока, который используется в операции подстановки байтов. Сам по себе S-блок это таблица, но вычисляется он через нахождение мультипликативного обратного элемента в поле, что делает его криптографически стойким.

Порядок байтов внутри состояния, о котором говорилось выше, определяет и то, как эти математические операции будут исполняться на практике. Для 8-битных микроконтроллеров безразлично, как расположены данные, они обрабатывают байт за байтом. Но для 32-битных процессоров, которые составляют основу современных компьютеров, выгодно, чтобы операции умножения и сложения выполнялись сразу над целым словом. Поэтому в спецификации AES колонки состояния выровнены по 32-битным границам. Это позволяет реализовать преобразование MixColumns, о котором речь пойдёт позже, как умножение матрицы на вектор, где каждая колонка загружается одной инструкцией процессора. Такая организация превращает абстрактную алгебру в эффективный машинный код, и это стало одной из причин победы AES в конкурсе NIST.

3. Раундовые преобразования и их назначение

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

Сначала выполняется SubBytes. Это единственная нелинейная операция во всём шифре. Каждый байт состояния заменяется на другой по таблице, которая называется S-блоком. Таблица строится на основе вычисления мультипликативной инверсии в поле GF(2^8) с последующим аффинным преобразованием. Такая конструкция выбрана не случайно. Именно она даёт устойчивость к дифференциальному и линейному криптоанализу, потому что делает зависимость между входными и выходными битами максимально сложной. Если бы не эта нелинейность, весь шифр сводился бы к системе линейных уравнений, которую можно решить за полиномиальное время.

Дальше идёт ShiftRows. Здесь байты перемещаются внутри строк состояния. Первая строка остаётся на месте, вторая сдвигается на один байт влево, третья на два, четвёртая на три. Казалось бы, простая перестановка, но её значение трудно переоценить. Сдвиг строк заставляет байты из разных колонок взаимодействовать друг с другом на следующем этапе. Этот шаг создаёт предпосылку для перемешивания данных по всему блоку.

Третья операция, MixColumns, выполняет линейное преобразование каждой колонки состояния. Каждая колонка рассматривается как многочлен и умножается на фиксированный многочлен по модулю x^4 + 1 в поле Галуа. Результат умножения даёт эффект диффузии: изменение одного входного байта колонки влияет на все четыре выходных байта. В криптографических терминах это означает, что после нескольких раундов каждый бит шифротекста зависит от каждого бита

открытого текста. Такое свойство называется лавинным эффектом, и MixColumns вносит в него основной вклад.

Завершает раунд операция AddRoundKey. Раундовый ключ, полученный из исходного ключа шифрования, складывается с состоянием поразрядно через XOR. Здесь нет сложной математики, только простая логическая операция. Но именно она связывает результат всех предыдущих преобразований с секретным ключом. Без неё шифрование превратилось бы в детерминированную перестановку, которую можно было бы проанализировать без знания ключа.

Операции не работают по отдельности. ShiftRows и MixColumns вместе обеспечивают перемешивание между байтами, а SubBytes и AddRoundKey добавляют нелинейность и зависимость от ключа. Если убрать любую из них, шифр становится уязвимым. Например, без ShiftRows колонки обрабатывались бы независимо, и можно было бы взломать шифр поблочно.

Количество раундов определяется длиной ключа и зафиксировано в стандарте. Для ключа в 128 бит выполняется 10 раундов, для 192 бит 12 раундов, для 256 бит 14 раундов. Перед первым раундом выполняется дополнительная операция AddRoundKey, чтобы даже на начальном этапе данные были смешаны с ключом. Такая схема гарантирует, что увеличение длины ключа пропорционально увеличивает вычислительную сложность взлома, сохраняя при этом одинаковую скорость шифрования на всех длинах ключей.

4. Расширение ключа и итоговая оценка стойкости

Каждое преобразование внутри раунда работает с состоянием, но само состояние ещё нужно связать с секретным ключом. Эту связь обеспечивает процедура расширения ключа, или Key Expansion. Исходный ключ, длина которого может быть 128, 192 или 256 бит, слишком мал, чтобы напрямую наложить его на все раунды. Поэтому из него разворачивается линейная последовательность раундовых ключей, общий объём которых равен размеру блока, умноженному на число раундов плюс один. Для стандартного варианта со 128-битным ключом это 176 байт: по 16 байт на каждый из 11 этапов, включая начальное наложение.

Алгоритм генерации работает с четырёхбайтовыми словами. Первые Nk слов (где Nk равно длине ключа, делённой на 32) просто копируются из исходного ключа. Каждое последующее слово вычисляется как XOR предыдущего слова с тем, что стоит на Nk позиций раньше. Однако для слов, чей индекс кратен Nk, процедура усложняется. Сначала выполняется операция RotWord: слово циклически сдвигается на один байт влево. Затем каждый байт этого сдвинутого слова пропускается через тот же S-блок, что и в операции SubBytes, это называется SubWord. И наконец, результат складывается с константой раунда Rcon. Эта константа зависит от номера раунда и вычисляется как степень двойки в поле Галуа, но важно другое: она ломает симметрию между раундами. Если бы Rcon не использовалась, два раунда с одинаковыми ключами вели бы себя идентично, что открыло бы путь для атак.

Зачем такая сложная схема? Раундовые ключи должны быть статистически независимы от исходного ключа. Даже если злоумышленник знает часть расширенного ключа, он не может восстановить остальные части или сам мастер-ключ. Каждая операция в этой цепочке нелинейна из-за SubWord, поэтому связь между битами ключа быстро запутывается. На практике это означает, что изменение одного бита исходного ключа приводит к

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

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

На сегодняшний день полный AES не имеет известных практических атак. Теоретические результаты, такие как атаки на основе связанных ключей или биклики, требуют нереальных условий: либо сокращённого числа раундов, либо специфических отношений между ключами, которые не встречаются в реальных протоколах. Для полного 10-раундового варианта со 128-битным ключом лучшая известная атака имеет вычислительную сложность около 2 в степени 126, что лишь немногим лучше полного перебора. Это делает AES устойчивым даже против гипотетических квантовых компьютеров при использовании классического ключа: атака Гровера снижает стойкость до 2 в степени 64, но это всё ещё недостижимо на практике.

Подтверждением надёжности служит повсеместное внедрение AES. Протокол TLS, защищающий HTTPS-соединения, использует AES-GCM для шифрования веб-трафика. VPN-решения, такие как OpenVPN и WireGuard, полагаются на него для защиты туннелей. Инструменты шифрования дисков BitLocker и LUKS применяют AES в режиме XTS. Аппаратные инструкции AES-NI в процессорах Intel и AMD выполняют операции шифрования на уровне микрокода, что делает AES одним из самых быстрых и одновременно самых изученных алгоритмов в истории криптографии. Стандарт, принятый NIST в 2001 году, остаётся эталоном спустя более чем два десятилетия, и ни одна серьёзная уязвимость в его конструкции так и не была найдена.