SubBytes

SubBytes — это нелинейная операция замены байтов, являющаяся одним из четырёх основных этапов алгоритма симметричного блочного шифрования AES (Advanced Encryption Standard, принят в США в 2001 году, в России — ГОСТ Р ИСО/МЭК 18033-3-2014). SubBytes применяется к каждому байту состояния (State) — двумерного массива байтов размером 4×4, который представляет собой текущее шифруемое или расшифровываемое сообщение. Операция выполняет замену каждого байта на другой байт в соответствии с фиксированной таблицей замены (S-блоком, S-box), обеспечивая криптостойкость за счёт нелинейности преобразования.

История и происхождение

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

Принцип работы

SubBytes применяется к каждому байту состояния независимо. Операция состоит из двух математических этапов:

1. Нахождение мультипликативного обратного элемента в поле Галуа GF(2⁸). Каждый байт интерпретируется как элемент конечного поля GF(2⁸) с неприводимым многочленом x⁸ + x⁴ + x³ + x + 1. Для байта, равного нулю (0x00), обратный элемент не существует, поэтому он остаётся нулём. Для всех остальных байтов вычисляется обратный элемент — такой, что их произведение в поле даёт единицу. Этот шаг обеспечивает нелинейность, так как операция мультипликативного обращения является нелинейной в поле.

1. Аффинное преобразование. К полученному обратному элементу применяется линейное аффинное преобразование над GF(2). Оно представляет собой умножение на фиксированную матрицу 8×8 и сложение с константой (0x63). Формально: b' = A * b + c, где A — матрица, c — константа. Это преобразование разрушает возможные алгебраические структуры и предотвращает атаки, основанные на свойствах поля.

Результат — новый байт, который заменяет исходный. Вся операция выполняется для каждого из 16 байтов состояния за один раунд.

Математическое описание

Пусть x — байт состояния (0 ≤ x ≤ 255). Тогда SubBytes(x) = A * (x⁻¹) + c, где:

• x⁻¹ — мультипликативный обратный элемент в GF(2⁸), при x = 0 → x⁻¹ = 0;
• A — матрица 8×8 над GF(2):

`` [1 0 0 0 1 1 1 1] [1 1 0 0 0 1 1 1] [1 1 1 0 0 0 1 1] [1 1 1 1 0 0 0 1] [1 1 1 1 1 0 0 0] [0 1 1 1 1 1 0 0] [0 0 1 1 1 1 1 0] [0 0 0 1 1 1 1 1] ``

• c — константа 0x63 (в двоичном виде 01100011).

S-блок AES

Результат вычислений для всех 256 возможных байтов (0x00–0xFF) сводится в таблицу размером 16×16, называемую S-блоком AES. Эта таблица является фиксированной и используется как при шифровании, так и при расшифровании (для обратной операции InvSubBytes применяется обратная таблица). S-блок AES обладает рядом криптографических свойств:

• Нелинейность: минимальная корреляция между входными и выходными битами.
• Лавинный эффект: изменение одного бита входа приводит к изменению примерно половины битов выхода.
• Отсутствие фиксированных точек: SubBytes(x) ≠ x для всех x, кроме x = 0x63 (случайное совпадение).
• Устойчивость к дифференциальному криптоанализу: максимальная вероятность дифференциала не превышает 2⁻⁶.

Пример S-блока (первые строки)

Полная таблица доступна в спецификации AES (FIPS PUB 197).

Роль в алгоритме AES

SubBytes является частью каждого раунда AES (кроме последнего, где отсутствует операция MixColumns). В AES-128 выполняется 10 раундов, в AES-192 — 12, в AES-256 — 14. SubBytes применяется на каждом раунде после операции AddRoundKey (сложение с ключом раунда) и перед ShiftRows (циклический сдвиг строк) и MixColumns (смешивание столбцов). Совместно с другими операциями SubBytes обеспечивает:

• Конфузию (запутывание): затрудняет установление статистической зависимости между ключом и шифротекстом.
• Диффузию (рассеивание): хотя SubBytes действует на отдельные байты, в сочетании с ShiftRows и MixColumns изменения распространяются на всё состояние.

Обратная операция: InvSubBytes

При расшифровании AES используется обратная операция InvSubBytes. Она состоит из обратного аффинного преобразования и нахождения мультипликативного обратного элемента. Обратная таблица (Inverse S-box) получается путём применения этих шагов в обратном порядке. InvSubBytes не требует дополнительных вычислений, так как таблица предварительно рассчитана и хранится в памяти.

Криптоанализ и устойчивость

SubBytes считается одной из причин высокой стойкости AES. Нелинейность S-блока делает AES устойчивым к:

• Линейному криптоанализу: минимальная линейная аппроксимация.
• Дифференциальному криптоанализу: низкая вероятность дифференциалов.
• Алгебраическим атакам: аффинное преобразование усложняет представление системы уравнений.

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

Реализация в программном и аппаратном обеспечении

SubBytes может быть реализована двумя способами:

1. Табличный метод (lookup table): предварительно вычисленный S-блок размером 256 байт используется для замены. Это быстрый, но потенциально уязвимый к атакам по времени метод (если таблица не выровнена в памяти).
2. Вычислительный метод (on-the-fly): расчёт обратного элемента и аффинного преобразования в реальном времени. Медленнее, но безопаснее для встраиваемых систем.

В современных процессорах (например, с поддержкой AES-NI в архитектуре x86) SubBytes реализована аппаратно, что обеспечивает высокую скорость и устойчивость к атакам по сторонним каналам.

Сравнение с другими шифрами

В отличие от DES, где S-блоки были фиксированными, но меньшего размера (6-битный вход → 4-битный выход), SubBytes использует 8-битный вход и 8-битный выход, что упрощает реализацию и повышает криптостойкость. В шифре ГОСТ 28147-89 (Россия) также применяются S-блоки, но они не являются фиксированными и могут различаться в разных реализациях, что снижает стандартизацию.

Источники

• FIPS PUB 197, «Advanced Encryption Standard (AES)», National Institute of Standards and Technology, 2001.
• Joan Daemen, Vincent Rijmen, «The Design of Rijndael: AES — The Advanced Encryption Standard», Springer, 2002.
• William Stallings, «Cryptography and Network Security: Principles and Practice», 6th edition, Pearson, 2014.
• Bruce Schneier, «Applied Cryptography: Protocols, Algorithms, and Source Code in C», 2nd edition, Wiley, 1996.
• ГОСТ Р ИСО/МЭК 18033-3-2014, «Информационная технология. Методы обеспечения безопасности. Алгоритмы шифрования. Часть 3. Блочные шифры», 2014.