Шифр Фейстеля

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

История

Предпосылки создания

До появления шифра Фейстеля криптографические алгоритмы часто были либо слишком простыми для взлома, либо требовали сложной аппаратной реализации. В 1960-х годах в IBM велись работы над созданием надёжной системы шифрования для коммерческого использования. Хорст Фейстель, немецкий криптограф, эмигрировавший в США, в 1971 году опубликовал описание конструкции, которая позволяла использовать простые необратимые функции для построения обратимого шифрования. Эта конструкция была запатентована IBM и впоследствии стала основой для стандарта шифрования данных (DES), принятого в 1977 году.

Развитие и стандартизация

В 1970-х годах на основе шифра Фейстеля был разработан алгоритм Lucifer, который стал предшественником DES. После принятия DES в качестве федерального стандарта США в 1977 году конструкция Фейстеля получила широкое распространение. В 1989 году в СССР был принят стандарт ГОСТ 28147-89, также основанный на сети Фейстеля. В 1990-х годах появились усовершенствованные варианты, такие как Blowfish (1993) и Twofish (1998). В 2001 году был принят Advanced Encryption Standard (AES), который использует не сеть Фейстеля, а подстановочно-перестановочную сеть, однако шифр Фейстеля остаётся одной из самых изученных и применяемых конструкций.

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

Основная структура

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

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

где:

• L_i и R_i — левая и правая половины на текущем раунде;
• K_i — раундовый ключ, полученный из основного ключа;
• F — функция Фейстеля (необратимая функция, выполняющая подстановку, перестановку и другие преобразования);
• ⊕ — операция XOR (исключающее ИЛИ).

После последнего раунда выполняется завершающая перестановка (в некоторых реализациях — обмен половин).

Функция Фейстеля

Функция F не обязана быть обратимой, что является ключевым преимуществом конструкции. Она может включать в себя:

• подстановку (S-блоки);
• перестановку (P-блоки);
• сложение с раундовым ключом;
• нелинейные преобразования (например, умножение в конечном поле).

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

Расшифрование

Расшифрование в шифре Фейстеля аналогично шифрованию, но раундовые ключи применяются в обратном порядке. Для каждого раунда расшифрования:

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

Это свойство делает реализацию шифра и дешифратора практически идентичными, что упрощает аппаратную и программную реализацию.

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

По числу раундов

• Малораундовые (4–8 раундов) — используются в учебных или лёгких шифрах, не обеспечивают достаточной стойкости.
• Среднераундовые (16–32 раунда) — типичны для большинства промышленных шифров (DES — 16 раундов, ГОСТ 28147-89 — 32 раунда).
• Многораундовые (более 32 раундов) — встречаются в шифрах с повышенными требованиями к безопасности.

По типу функции Фейстеля

• Классическая сеть Фейстеля — функция F не зависит от номера раунда (кроме ключа).
• Модифицированная сеть Фейстеля — функция F может изменяться от раунда к раунду (например, в ГОСТ 28147-89 используется разная функция в зависимости от режима).
• Обобщённая сеть Фейстеля — блок делится на более чем две части (например, на 4 части в шифре CAST-256).

По размеру блока

• Малые блоки (32–64 бита) — устаревшие, уязвимы для атак на основе словаря (DES — 64 бита).
• Средние блоки (64–128 бит) — наиболее распространённые (Blowfish — 64 бита, Twofish — 128 бит).
• Большие блоки (128–256 бит) — современные, обеспечивают высокую стойкость.

Применение

Коммерческие стандарты

• DES (Data Encryption Standard) — принят в США в 1977 году, использовался до 2000-х годов. Длина ключа — 56 бит, блок — 64 бита. Из-за малой длины ключа в настоящее время считается небезопасным.
• 3DES (Triple DES) — улучшенная версия DES, применяющая три последовательных шифрования с разными ключами. Используется в финансовых системах до сих пор.
• ГОСТ 28147-89 — российский стандарт шифрования, принятый в 1989 году. Длина ключа — 256 бит, блок — 64 бита, 32 раунда. Активно применяется в государственных и коммерческих системах РФ.

Открытые алгоритмы

• Blowfish — разработан Брюсом Шнайером в 1993 году. Длина ключа от 32 до 448 бит, блок — 64 бита. Использовался в VPN и файловых системах (например, в OpenBSD).
• Twofish — финалист конкурса AES (1998–2000). Длина ключа до 256 бит, блок — 128 бит. Применяется в некоторых криптографических библиотеках.
• Camellia — японский алгоритм, одобренный ISO/IEC. Используется в TLS и IPsec.

Специализированные применения

• Аппаратные реализации — шифр Фейстеля часто реализуется в виде интегральных схем (например, в смарт-картах и банковских терминалах) благодаря простоте и симметричности.
• Криптографические протоколы — используется в протоколах аутентификации и шифрования данных (например, в Kerberos).

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

Атаки на шифр Фейстеля

• Дифференциальный криптоанализ — основан на анализе различий между парами шифротекстов. Для DES был предложен в 1990 году, но конструкция оказалась устойчивой при 16 раундах.
• Линейный криптоанализ — использует линейные аппроксимации функции F. Для DES требует 2⁴⁷ известных открытых текстов, что практически нереализуемо.
• Атаки на основе времени — возможны при неоптимальной реализации (например, на процессорах с кэшем).
• Атаки на основе связанных ключей — уязвимость некоторых реализаций ГОСТ 28147-89.

Факторы стойкости

Стойкость шифра Фейстеля зависит от:

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

Современное состояние

На 2025 год шифры на основе сети Фейстеля с достаточным числом раундов (32 и более) и длиной ключа не менее 128 бит считаются криптостойкими. Однако для новых проектов рекомендуется использовать AES или другие современные алгоритмы, прошедшие широкий анализ.

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

• Хорст Фейстель в 1970 году был одним из первых, кто предложил использовать электронные схемы для реализации криптографических алгоритмов.
• В DES функция F включает 8 S-блоков, каждый из которых представляет собой таблицу подстановки размером 4×16 бит.
• Шифр Фейстеля иногда называют «сетью Фейстеля» (Feistel network) или «конструкцией Фейстеля».
• В некоторых реализациях (например, в ГОСТ 28147-89) функция F может быть разной для разных раундов, что усложняет криптоанализ.
• Шифр Фейстеля используется не только в шифровании, но и в хеш-функциях (например, в MD5 и SHA-1, хотя они основаны на модифицированной конструкции).

Источники

• Хорст Фейстель. «Cryptography and Computer Privacy». Scientific American, 1973.
• Брюс Шнайер. «Applied Cryptography». John Wiley & Sons, 1996.
• ГОСТ 28147-89. «Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования».
• NIST. «Data Encryption Standard (DES)». Federal Information Processing Standards Publication 46-3, 1999.
• Брюс Шнайер. «Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)». Fast Software Encryption, 1994.