5.2. SP-сети. Проект «Люцифер»

В 1973 году в журнале ``Scientific American'' появилась статья сотрудника IBM (а ранее – ВМС США) Хорста Фейстеля (англ. Horst Feistel) «Cryptography and Computer Privacy» [37], описывающая проект функции шифрования «Люцифер», который можно считать прообразом современных блочных шифров. Развитием данной системы стал государственный стандарт США «Digital Encryption Standard» с 1979 по 2001 годы.

(a) S-блок. На вход поступают 3 бита информации, которые трактуются как двоичное представление номера одной из $2^3$ линий внутреннего p-блока. На выходе номер активной сигнальной дорожки обратно преобразуется в 3-битовое представление
(b) P-блок. Все поступающие на вход биты не меняются, но перемешиваются внутри блока
Рис. 5.2 — Возможные реализации s- и p-блоков

Фейстель высказал идею, что идеальный шифр для блока размером в 128 бит должен включать в себя блок замен (substitution box, s-box, далее s-блок), который мог бы обработать сразу 128 бит входного блока данных. S-блок принимает на вход блок битов и даёт на выходе другой блок бит (возможно, даже другого размера) согласно некоторому словарю или результату вычисления нелинейной функции

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

. К сожалению, физическая реализация (см. рис. 5.2a) действительно произвольного блока замен для входа в 128 бит потребовала бы $2^{128}$ внутренних соединений или словаря из $2^{128}$ 128-битовых значений, если реализовывать программным способом, что технологически невозможно

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

. Зато если такой блок можно было бы создать, то он был бы очень хорош с криптографической точки зрения. Даже если криптоаналитик знает произвольное число пар значений вход-выход, то это ничего не скажет ему об остальном множестве значений. То есть без полного перебора всех возможных $2^{128}$ вариантов входа криптоаналитик не сможет составить полное представление о внутренней структуре блока.

С другой стороны, блок перестановок (permutation box, p-box, далее p-блок), изображённый на рис. 5.2b, может обрабатывать блоки битов любого размера. Однако какая-либо криптографическая стойкость у него отсутствует: он представляет собой тривиальное линейное преобразование своего входа. Криптоаналитику достаточно иметь $N$ линейно независимых пар значений входа и выхода (где $N$ – размер блока), чтобы получить полное представление о структуре p-блока.

Идея Фейстеля состояла в том, чтобы комбинировать s- и p-блоки, позволяя на практике получить большой блок нелинейных преобразований (то есть один большой s-блок), как изображено на рис. 5.3. При достаточном числе «слоёв» SP-сеть начинает обладать свойствами хорошего s-блока (сложностью криптографического анализа и выявления структуры), при этом оставаясь технологически простой в реализации.

Рис. 5.3 — SP-сеть, состоящая из 4 p-блоков и 3 слоёв s-блоков, по 5 блоков в каждом слое

Следующей составляющей будущего шифра стала возможность менять используемые s-блоки в зависимости от ключа. Вместо каждого из s-блоков в SP-сети Фейстель поместил модуль с двумя разными s-блоками. В зависимости от одного из битов ключа (своего для каждой пары блоков) использовался первый или второй s-блок. Результатом данного подхода стал первый вариант шифра в проекте «Люцифер», который в упрощённом виде (с меньшим размером блока и меньшим числом слоёв) изображён на рис. 5.4.

Рис. 5.4 — Общий вид (упрощённая схема) функции шифрования в одном из вариантов проекта «Люцифер». Входной блок (в проекте «Люцифер» его объём – 128 бит) подавался на вход на несколько слоёв (в «Люцифере» слоёв 16) из p-блоков и пар s-блоков. S-блок в каждой паре выбирался в зависимости от значения соответствующего бита ключа

Разделение функции шифрования на относительно простые раунды («слои»), комбинация больших p-блоков со множеством s-блоков малого размера – всё это до сих пор используется в современных блочных шифрах.