Современная криптография

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

Как одна конструкция решила старую проблему шифрования — и легла в основу DES, российской Магмы и десятков других алгоритмов

⏱️ 5 мин чтения

📊 Средний уровень

🔑 Фундамент DES и Магмы

Проблема, которую решал Фейстель

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

В начале 1970-х в IBM Хорст Фейстель предложил структурный трюк: разрезать блок данных пополам на L и R, прогнать одну половину — вместе с подключом раунда — через функцию F, которая может быть сколь угодно сложной и необратимой, сложить результат с другой половиной, а затем поменять половины местами. Повторить несколько раз.

Ключевая мысль: Хитрость не в функции F, а в самой структуре. Сложение по модулю 2 (XOR) само себя отменяет, а обмен половинами тривиально обратим. Поэтому весь раунд целиком обратим — даже если функция F необратима сама по себе. Расшифровка — это тот же самый алгоритм, только подключи применяются в обратном порядке.

Как устроена сеть Фейстеля

Если разобрать раунд на шаги, вся конструкция окажется на удивление простой:

Разбиение блока

Блок данных делится пополам на левую половину L и правую R. В DES это 32 и 32 бита от 64-битного блока, в игре Ludus Lab — 4 и 4 бита от одного байта.

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

Правая половина R складывается с подключом этого раунда и проходит через функцию F — в DES и Магме это набор S-блоков, таблиц замен, которые и дают шифру нелинейность.

Сложение и обмен

Результат F складывается по модулю 2 с левой половиной L — так получается новая правая половина. После этого половины меняются местами.

Повтор на много раундов

Всё повторяется снова и снова, каждый раз с новым подключом: 16 раз в DES, 32 раза в Магме. Чем больше раундов, тем труднее найти закономерность между открытым текстом и шифротекстом.

Финальный обмен и расшифровка

После последнего раунда половины меняются местами ещё раз — это и даёт главное свойство сети Фейстеля: чтобы расшифровать, Боб запускает точно такой же алгоритм, но подаёт подключи в обратном порядке.

Один раунд сети Фейстеля

L, R

Половины блока

→

F(R, K)

R + подключ → S-блоки

→

L ⊕ F

Складываем с L

→

R, L'

Половины меняются местами

F может быть какой угодно сложной и необратимой — обратима сама схема «раздели, перемешай, поменяй местами».

От Lucifer до наших дней

Идея Фейстеля не осталась теорией — на ней построена значительная часть симметричной криптографии XX века:

Lucifer (IBM, начало 1970-х)

Первый шифр на структуре Фейстеля, созданный самим Хорстом Фейстелем и его командой в IBM.

Прямой предок DES

DES (NBS, 1977)

Доработанный Lucifer стал стандартом США на четверть века — 64-битный блок, 56-битный ключ, 16 раундов.

Ключ: 56 бит — сегодня этого мало

ГОСТ 28147-89 «Магма» (СССР, 1989)

Независимая советская разработка на той же идее: 64-битный блок, но ключ 256 бит и 32 раунда.

Сегодня — ГОСТ Р 34.12-2015

Схема Фейстеля оказалась настолько удачной, что легла в основу ещё нескольких поколений шифров:

DES 3DES МАГМА (ГОСТ) Blowfish CAST-128 Twofish Camellia KASUMI

А что не Фейстель? AES и российский «Кузнечик» устроены иначе — это подстановочно-перестановочные сети (SP-сети), не сети Фейстеля. Обе идеи решают одну задачу, но по-разному.

Испытайте сеть Фейстеля на практике

В интерактивной демонстрации Ludus Lab вы сможете:

🔤
Превратить текст в биты — увидеть, как UTF-8 разбивает ваше сообщение на байты, и выбрать один для шифрования
🔑
Задать общий ключ и посмотреть, как из него по шагам получаются четыре разных подключа раундов
🌊
Проверить лавинный эффект S-блока — увидеть, как один изменённый бит входа меняет сразу несколько бит результата
🔄
Пройти все 4 раунда шифрования бит за битом — со сложением по модулю 2, S-блоком и обменом половинами
✅
Расшифровать результат тем же алгоритмом с подключами в обратном порядке — и убедиться, что сообщение восстановилось

Главный урок игры: Расшифровка работает не потому, что кто-то отменяет функцию F, а потому что сама структура сети Фейстеля симметрична относительно порядка подключей. Разберитесь в этом на одном байте — и принцип DES, Магмы и десятков других шифров станет понятен.

Для любознательных

DES и Магма рядом

Оба алгоритма — сети Фейстеля, но с разным масштабом и разной судьбой:

Параметр	DES	Магма (ГОСТ 28147-89)
Страна разработки	США	СССР / Россия
Год принятия	1977	1989 (сегодня — ГОСТ Р 34.12-2015)
Архитектура	Сеть Фейстеля	Сеть Фейстеля
Размер блока	64 бита	64 бита
Длина ключа	56 бит	256 бит
Число раундов	16	32
S-блоки	Зафиксированы стандартом с 1977 года	Изначально ведомственный секрет; единый набор закреплён лишь в 2015-м
Регулятор	NIST (США)	ФСБ России

Тайна S-блоков и дифференциальный криптоанализ

В 1990 году криптографы Эли Бихам и Ади Шамир опубликовали дифференциальный криптоанализ — мощную атаку на блочные шифры. Публика была поражена: оказалось, что S-блоки DES на удивление хорошо устойчивы именно к этой атаке.

Ответ нашёлся позже: по словам одного из инженеров IBM, Дона Копперсмита, команда IBM знала о дифференциальном криптоанализе ещё в начале 1970-х и намеренно спроектировала S-блоки DES так, чтобы противостоять ему — но по требованию АНБ держала это в секрете почти два десятилетия.

Конец DES: взлом перебором

56-битный ключ DES даёт около 7×10¹⁶ вариантов — в 1977 году этого хватало. К 1998 году фонд Electronic Frontier Foundation построил специализированную машину «Deep Crack» стоимостью около 250 000 долларов, которая перебрала ключ примерно за 56 часов.

Это публично доказало, что 56 бит недостаточно. На замену пришёл переходный 3DES (тройное применение DES), а затем, в 2001 году, — AES, выбранный по итогам открытого международного конкурса.

Blowfish и Twofish

Открытые альтернативы DES без патентных ограничений, разработанные Брюсом Шнайером в 1990-х

Camellia

Совместная разработка японских компаний, международный стандарт ISO/IEC, используется в TLS

KASUMI

Сеть Фейстеля в основе алгоритмов конфиденциальности сетей 3G/UMTS

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

Оригинальный Lucifer работал со 128-битным ключом; АНБ настояло на сокращении до 56 бит перед принятием DES
DES оставался официальным стандартом США более 20 лет, пока в 2001 году его не сменил AES
S-блоки исходного ГОСТ 28147-89 не были частью открытого стандарта — их могли задавать разные ведомства
AES и «Кузнечик» — не сети Фейстеля, а подстановочно-перестановочные сети (SP-сети)
Расшифровка в сети Фейстеля использует ту же самую схему, что и шифрование, — только подключи идут в обратном порядке

Философский момент: Сеть Фейстеля — редкий случай, когда простая структурная идея оказалась мощнее сложной математики. За полвека она пережила смену эпох: от механических шифровальных машин до постквантовой криптографии — и до сих пор используется там, где нужна проверенная временем конструкция.

Теперь вы понимаете, почему функция F не обязана быть обратимой, и как из этой идеи выросли DES, Магма и десятки других шифров

🚀 Запустить демонстрацию сети Фейстеля ← Вернуться к списку тем

В демонстрации вы на одном байте пройдёте весь путь от открытого текста до шифротекста и обратно — и увидите, почему эта структура работает