Сеть Фейстеля¶

Сеть Фейстеля (также известная как конструкция Фейстеля) — это метод построения блочных симметричных шифров, предложенный немецким криптографом Хорстом Фейстелем в начале 1970-х годов. Основная идея заключается в разделении блока данных на две половины и многократном применении к ним необратимой функции (функции раунда) с использованием ключа шифрования, что позволяет получить обратимый (шифрующий и дешифрующий) алгоритм даже при необратимой внутренней функции. Сеть Фейстеля лежит в основе многих классических и современных шифров, включая DES (Data Encryption Standard), ГОСТ 28147-89, Blowfish, Twofish и ряд других.

¶История

Концепция сети Фейстеля была разработана Хорстом Фейстелем в лаборатории IBM Watson Research Center в конце 1960-х — начале 1970-х годов. Первой практической реализацией этой конструкции стал шифр Lucifer, созданный под руководством Фейстеля. В 1973 году Национальное бюро стандартов США (NBS, ныне NIST) объявило конкурс на разработку стандарта шифрования для государственных и коммерческих нужд. В результате конкурса в 1977 году был принят стандарт DES (Data Encryption Standard), основанный на модифицированной версии шифра Lucifer и использующий 16-раундовую сеть Фейстеля с 56-битным ключом. DES стал одним из самых широко распространённых блочных шифров в мире и оставался стандартом США до 2001 года, когда на смену ему пришёл AES (Advanced Encryption Standard), построенный на иной архитектуре (подстановочно-перестановочная сеть, или SP-сеть). Тем не менее, сеть Фейстеля продолжает активно использоваться в современных криптосистемах, включая российский стандарт ГОСТ Р 34.12-2015 («Магма» и «Кузнечик»), где «Магма» представляет собой классическую сеть Фейстеля.

¶Устройство и принцип работы

¶Базовая структура

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

1. К правой половине блока (R) применяется раундовая функция F, зависящая от раундового ключа K_i.
2. Результат функции F(R, K_i) складывается по модулю 2 (операция XOR) с левой половиной (L).
3. Полученное значение становится новой правой половиной для следующего раунда.
4. Исходная правая половина (R) без изменений становится новой левой половиной.

Математически один раунд сети Фейстеля можно описать так:

• L_i+1 = R_i
• R_i+1 = L_i ⊕ F(R_i, K_i)

где ⊕ — операция XOR, i — номер раунда.

¶Процесс расшифрования

Ключевым свойством сети Фейстеля является то, что процесс расшифрования идентичен процессу шифрования, но раундовые ключи используются в обратном порядке. Для расшифрования данные подаются в обратном порядке раундов, а функция F остаётся той же самой. Это достигается за счёт того, что операция XOR является обратной самой себе. Таким образом, для расшифрования не требуется реализовывать обратную функцию к F, что упрощает аппаратную и программную реализацию.

¶Классификация и виды

Сети Фейстеля классифицируются по нескольким признакам.

¶По количеству ветвей

• Классическая (сбалансированная) сеть Фейстеля: блок делится на две равные части. Наиболее распространённый тип (DES, ГОСТ 28147-89).
• Несбалансированная сеть Фейстеля: блок делится на части разного размера. Используется в некоторых шифрах (например, Skipjack) для оптимизации определённых свойств.
• Обобщённая сеть Фейстеля: блок делится на более чем две части (например, на 4 части). Примеры: шифры CAST-256, RC6.

¶По количеству раундов

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

¶Свойства и преимущества

• Обратимость при необратимой функции F: это главное преимущество сети Фейстеля. Разработчик может проектировать раундовую функцию F, не заботясь о том, чтобы она была биективной (обратимой). Это упрощает создание криптостойких функций, в том числе нелинейных (S-блоков).
• Идентичность процедур шифрования и расшифрования: для аппаратной реализации это означает, что один и тот же модуль может выполнять обе операции, что экономит ресурсы (площадь чипа, энергопотребление). В программной реализации это упрощает код.
• Простота анализа: структура сети Фейстеля хорошо изучена, существуют формальные методы оценки её стойкости к различным видам атак (дифференциальный и линейный криптоанализ).

¶Недостатки и ограничения

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

¶Примеры шифров на основе сети Фейстеля

¶Криптоанализ

Стойкость сети Фейстеля зависит от свойств раундовой функции F и количества раундов. Основные методы криптоанализа, применяемые к таким шифрам:

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

Для защиты от этих атак в раундовую функцию F включают нелинейные элементы (S-блоки, таблицы замен), перестановки (P-блоки) и операции, обеспечивающие перемешивание и рассеивание битов.

¶Применение

Сеть Фейстеля используется не только в блочных шифрах. Её принципы применяются:

• В криптографических хеш-функциях: некоторые хеш-функции (например, семейство MD, SHA-1) построены на основе конструкции Меркла — Дамгора, которая использует блочный шифр, часто реализованный как сеть Фейстеля.
• В генераторах псевдослучайных чисел: на основе блочных шифров могут строиться криптостойкие ГПСЧ.
• В системах аутентификации и формирования имитовставки (MAC): блочные шифры, в том числе на сети Фейстеля, используются для вычисления кодов аутентичности сообщений.

¶Источники

1. Feistel, H. (1973). "Cryptography and Computer Privacy". Scientific American, 228(5), 15–23.
2. Шнайер, Б. (2002). "Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си". Триумф.
3. National Institute of Standards and Technology (NIST). (1999). "Data Encryption Standard (DES)". FIPS PUB 46-3.
4. ГОСТ 28147-89. "Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования".
5. ГОСТ Р 34.12-2015. "Информационная технология. Криптографическая защита информации. Блочные шифры".