Функция раунда

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

История и развитие

Концепция функции раунда возникла с появлением итеративных шифров, где безопасность достигается не за счёт одного сложного преобразования, а за счёт многократного повторения относительно простых и одинаковых операций. Первым широко известным алгоритмом, использующим повторяющиеся раунды, стал шифр Люцифера, разработанный в IBM в начале 1970-х годов. Его идеи легли в основу стандарта DES (Data Encryption Standard), принятого в 1977 году.

В DES функция раунда включала в себя перестановку битов, расширение, XOR с раундовым ключом и подстановку через S-блоки. Этот подход оказался настолько удачным, что лёг в основу целого семейства шифров — сети Фейстеля. Позднее, с развитием криптоанализа, стали появляться альтернативные структуры, такие как подстановочно-перестановочная сеть (SPN), используемая в AES (Advanced Encryption Standard), принятом в 2001 году. В SPN функция раунда строится на последовательности слоёв: подстановка (S-блоки), перестановка (P-слой) и наложение ключа.

Структура и компоненты

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

Нелинейное преобразование (Confusion): Осуществляется с помощью таблиц замен (S-блоков). S-блоки отображают небольшой блок входных битов (например, 4 или 8 бит) на выходной блок того же размера по нелинейному закону. Это затрудняет аппроксимацию функции линейными или аффинными уравнениями, что является основой для защиты от дифференциального и линейного криптоанализа.
Перемешивание (Diffusion): Обеспечивает распространение влияния одного бита входных данных на множество битов выходных данных. Достигается с помощью перестановок (P-слоёв), циклических сдвигов, умножения в конечных полях (например, в AES — операция MixColumns) или линейных преобразований. Цель — чтобы изменение одного бита входных данных приводило к изменению примерно половины битов выходных данных после нескольких раундов (лавинный эффект).
Наложение ключа (Key Mixing): Объединение текущего состояния данных с раундовым ключом. Чаще всего выполняется с помощью операции «исключающее ИЛИ» (XOR) или, реже, сложения по модулю. Раундовые ключи получаются из основного ключа шифрования с помощью процедуры развёртывания ключа (key schedule).

Типы структур раундов

Выделяют несколько основных архитектур, определяющих порядок применения этих компонентов:

Сеть Фейстеля (Feistel Network): Блок данных делится на две половины. В каждом раунде одна половина преобразуется с помощью функции F, зависящей от раундового ключа, и затем складывается по XOR со второй половиной. После этого половины меняются местами. Преимущество: функция шифрования и дешифрования могут быть идентичными (с обратным порядком ключей). Примеры: DES, Blowfish, Twofish.
Подстановочно-перестановочная сеть (SPN — Substitution-Permutation Network): Весь блок данных проходит последовательно через слои подстановки (S-блоки) и перестановки (P-слой), после чего накладывается ключ. Эта структура обычно обеспечивает более быстрое распространение изменений (лавинный эффект) за меньшее число раундов, чем сеть Фейстеля. Примеры: AES, Serpent.
ARX-конструкция (Addition, Rotation, XOR): Функция раунда строится исключительно из трёх арифметических и бинарных операций: сложения по модулю, циклического сдвига и XOR. Это позволяет добиться высокой производительности на процессорах общего назначения, так как эти операции выполняются аппаратно. Примеры: ChaCha20, Salsa20, Threefish (SHA-3).
Конструкция на основе сжатия (для хеш-функций): В хеш-функциях функция раунда обычно является частью функции сжатия, которая принимает блок сообщения и текущее состояние (или предыдущее хеш-значение) и выводит новое состояние. Примеры: SHA-2 (использует структуру, похожую на сеть Фейстеля), SHA-3 (использует конструкцию «губка» (sponge) с функцией f, которая является итеративной комбинацией раундов).

Примеры в известных алгоритмах

AES (Rijndael)

AES использует SPN-структуру. Функция раунда для шифрования состоит из четырёх преобразований, применяемых к матрице байтов размером 4×4 (для 128-битного блока):

SubBytes: Нелинейная замена каждого байта с помощью фиксированного S-блока (основан на обратном элементе в поле Галуа GF(2^8) и аффинном преобразовании).
ShiftRows: Циклический сдвиг строк матрицы влево на разное количество байтов (0, 1, 2, 3 для строк 0, 1, 2, 3 соответственно). Обеспечивает перемешивание между колонками.
MixColumns: Умножение каждой колонки матрицы на фиксированную матрицу в поле GF(2^8). Обеспечивает перемешивание внутри колонки. В последнем раунде этот шаг опускается.
AddRoundKey: Побитовое XOR с раундовым ключом.

DES

DES использует сеть Фейстеля с 16 раундами. Функция раунда F(R, K) работает с 32-битной правой половиной R и 48-битным раундовым ключом K:

Expansion (E-box): Расширение 32-битного входа до 48 бит путём дублирования некоторых битов.
XOR с ключом: Результат складывается по XOR с 48-битным раундовым ключом.
S-блоки: 48-битный результат разбивается на 8 блоков по 6 бит, каждый из которых проходит через свой S-блок (таблицу замены 6×4 бита). На выходе получается 32 бита.
Permutation (P-box): Фиксированная перестановка 32 бит.

ChaCha20

ChaCha20 — это ARX-шифр, работающий на основе 512-битного состояния (матрица 4×4 32-битных слов). Функция раунда называется «четверть-раундом» (quarter round) и применяется к четырём словам. Один полный раунд ChaCha20 состоит из 8 четверть-раундов (4 для столбцов и 4 для диагоналей). Четверть-раунд включает в себя: сложение по модулю 2^32, XOR и циклический сдвиг.

Криптоанализ и стойкость

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

Достаточное число раундов: Должно быть выбрано таким образом, чтобы после последнего раунда не оставалось статистических зависимостей между открытым текстом и шифртекстом, которые можно было бы использовать для атак. Для AES минимальное число раундов зависит от длины ключа: 10 для 128-битного ключа, 12 для 192-битного и 14 для 256-битного.
Отсутствие слабых ключей: Функция раунда не должна иметь таких значений ключа, при которых шифр становится уязвимым (как в DES для некоторых ключей, где S-блоки вели себя линейно).
Устойчивость к дифференциальному криптоанализу: S-блоки должны иметь низкую вероятность дифференциала (максимальное значение дифференциальной вероятности должно быть минимальным).
Устойчивость к линейному криптоанализу: S-блоки должны иметь низкое смещение линейной аппроксимации.

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

Применение

Функции раунда используются не только в симметричных блочных шифрах и хеш-функциях, но и в:

Поточных шифрах: Некоторые поточные шифры (например, HC-128) используют итеративные функции раунда для генерации псевдослучайного ключевого потока.
Криптографических примитивах для аутентификации: В режимах работы блочных шифров (например, GCM, CCM) функции раунда применяются для вычисления кодов аутентичности сообщения (MAC).
Постквантовой криптографии: Многие конкурирующие схемы (например, на основе решёток) используют итеративные функции для повышения производительности, хотя их раунды часто отличаются от классических (например, умножение матриц).

Интересные факты

В шифре DES 16 раундов были выбраны не случайно: изначально IBM предложила 32 раунда, но по настоянию АНБ (Агентства национальной безопасности США) число было сокращено до 16. Позднее выяснилось, что 16 раундов достаточно для защиты от дифференциального криптоанализа, который в то время был секретно известен АНБ.
S-блоки в AES были разработаны с использованием алгебраических свойств поля Галуа, что делает их математически прозрачными, но при этом устойчивыми к известным атакам. Это контрастирует с S-блоками DES, которые были сконструированы эмпирически и до сих пор не имеют полного математического объяснения своей оптимальности.
Шифр ГОСТ 28147-89 (российский стандарт) использует 32 раунда сети Фейстеля с 64-битным блоком и 256-битным ключом. Его функция раунда включает сложение по модулю 2^32, что является характерной чертой советской и российской криптографической школы.

Источники

Шнайер Б. «Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си». — М.: Триумф, 2002.
Менезес А., ван Орсхот П., Ванстоун С. «Справочник по прикладной криптографии». — М.: Мир, 2002.
Daemen J., Rijmen V. «The Design of Rijndael: AES — The Advanced Encryption Standard». — Springer, 2002.
Национальный институт стандартов и технологий США (NIST). «FIPS PUB 197: Advanced Encryption Standard (AES)». — 2001.
Национальный институт стандартов и технологий США (NIST). «FIPS PUB 46-3: Data Encryption Standard (DES)». — 1999.
Bernstein D. J. «ChaCha, a variant of Salsa20». — 2008.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →