Сеть Фейстеля
Сеть Фейстеля (также известная как конструкция Фейстеля) — это метод построения блочных симметричных шифров, предложенный немецким криптографом Хорстом Фейстелем в начале 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). Процесс шифрования состоит из последовательности раундов, в каждом из которых выполняются следующие операции:
- К правой половине блока (R) применяется раундовая функция F, зависящая от раундового ключа K<sub>i</sub>.
- Результат функции F(R, K<sub>i</sub>) складывается по модулю 2 (операция XOR) с левой половиной (L).
- Полученное значение становится новой правой половиной для следующего раунда.
- Исходная правая половина (R) без изменений становится новой левой половиной.
Математически один раунд сети Фейстеля можно описать так:
- L<sub>i+1</sub> = R<sub>i</sub>
- R<sub>i+1</sub> = L<sub>i</sub> ⊕ F(R<sub>i</sub>, K<sub>i</sub>)
где ⊕ — операция XOR, i — номер раунда.
Процесс расшифрования
Ключевым свойством сети Фейстеля является то, что процесс расшифрования идентичен процессу шифрования, но раундовые ключи используются в обратном порядке. Для расшифрования данные подаются в обратном порядке раундов, а функция F остаётся той же самой. Это достигается за счёт того, что операция XOR является обратной самой себе. Таким образом, для расшифрования не требуется реализовывать обратную функцию к F, что упрощает аппаратную и программную реализацию.
Классификация и виды
Сети Фейстеля классифицируются по нескольким признакам.
По количеству ветвей
- Классическая (сбалансированная) сеть Фейстеля: блок делится на две равные части. Наиболее распространённый тип (DES, ГОСТ 28147-89).
- Несбалансированная сеть Фейстеля: блок делится на части разного размера. Используется в некоторых шифрах (например, Skipjack) для оптимизации определённых свойств.
- Обобщённая сеть Фейстеля: блок делится на более чем две части (например, на 4 части). Примеры: шифры CAST-256, RC6.
По количеству раундов
Число раундов варьируется в зависимости от шифра и требуемого уровня безопасности. Для современных шифров типичным является от 8 до 64 раундов. Увеличение числа раундов повышает стойкость к криптоанализу, но снижает производительность.
Свойства и преимущества
- Обратимость при необратимой функции F: это главное преимущество сети Фейстеля. Разработчик может проектировать раундовую функцию F, не заботясь о том, чтобы она была биективной (обратимой). Это упрощает создание криптостойких функций, в том числе нелинейных (S-блоков).
- Идентичность процедур шифрования и расшифрования: для аппаратной реализации это означает, что один и тот же модуль может выполнять обе операции, что экономит ресурсы (площадь чипа, энергопотребление). В программной реализации это упрощает код.
- Простота анализа: структура сети Фейстеля хорошо изучена, существуют формальные методы оценки её стойкости к различным видам атак (дифференциальный и линейный криптоанализ).
Недостатки и ограничения
- Меньшая скорость распространения изменений (лавинный эффект): за один раунд изменения вносятся только в половину блока. Для достижения хорошего лавинного эффекта требуется большее количество раундов по сравнению с SP-сетями.
- Ограниченная производительность: из-за необходимости деления блока и последовательного выполнения раундов сеть Фейстеля может быть медленнее, чем SP-сети, особенно при программной реализации на современных процессорах с широкими регистрами.
Примеры шифров на основе сети Фейстеля
| Шифр | Размер блока (бит) | Размер ключа (бит) | Число раундов | Примечание |
|---|---|---|---|---|
| DES | 64 | 56 | 16 | Исторический стандарт США, ныне устарел из-за малого размера ключа. |
| ГОСТ 28147-89 | 64 | 256 | 32 | Российский стандарт шифрования, разработан в 1989 году. |
| Blowfish | 64 | от 32 до 448 | 16 | Разработан Брюсом Шнайером в 1993 году. |
| Twofish | 128 | от 128 до 256 | 16 | Финалист конкурса AES, разработан группой под руководством Брюса Шнайера. |
| Camellia | 128 | 128, 192, 256 | 18 или 24 | Разработан компаниями NTT и Mitsubishi Electric, одобрен ISO/IEC. |
| ГОСТ Р 34.12-2015 («Магма») | 64 | 256 | 32 | Современный российский стандарт, заменивший ГОСТ 28147-89. |
Криптоанализ
Стойкость сети Фейстеля зависит от свойств раундовой функции F и количества раундов. Основные методы криптоанализа, применяемые к таким шифрам:
- Дифференциальный криптоанализ: изучает влияние разности между парами открытых текстов на разность соответствующих шифротекстов.
- Линейный криптоанализ: ищет линейные аппроксимации между битами открытого текста, шифротекста и ключа.
- Атаки на основе связанных ключей: используют возможность шифрования на нескольких ключах с известной зависимостью между ними.
- Атаки типа «встреча посередине»: применимы к шифрам с малым числом раундов.
Для защиты от этих атак в раундовую функцию F включают нелинейные элементы (S-блоки, таблицы замен), перестановки (P-блоки) и операции, обеспечивающие перемешивание и рассеивание битов.
Применение
Сеть Фейстеля используется не только в блочных шифрах. Её принципы применяются:
- В криптографических хеш-функциях: некоторые хеш-функции (например, семейство MD, SHA-1) построены на основе конструкции Меркла — Дамгора, которая использует блочный шифр, часто реализованный как сеть Фейстеля.
- В генераторах псевдослучайных чисел: на основе блочных шифров могут строиться криптостойкие ГПСЧ.
- В системах аутентификации и формирования имитовставки (MAC): блочные шифры, в том числе на сети Фейстеля, используются для вычисления кодов аутентичности сообщений.
Источники
- Feistel, H. (1973). "Cryptography and Computer Privacy". Scientific American, 228(5), 15–23.
- Шнайер, Б. (2002). "Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си". Триумф.
- National Institute of Standards and Technology (NIST). (1999). "Data Encryption Standard (DES)". FIPS PUB 46-3.
- ГОСТ 28147-89. "Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования".
- ГОСТ Р 34.12-2015. "Информационная технология. Криптографическая защита информации. Блочные шифры".
BFOmetr — база данных и аналитика по компаниям России.
На главную BFOmetr →