Подстановочно-перестановочные сети

223
перестановок A-битных строк, поэтому представление произвольной перестановки 
с A-битной длиной блока требует log(2A !) ≈ A • 2A бит. Это непрактично для 
A > 20 и невозможно для A > 50. (Забегая вперед, современные блочные шифры 
имеют длину блока A ≥ 128.) Трудность при разработке блочного шифра состоит в 
том, чтобы построить набор перестановок с компактным описанием (а именно, ко-
ротким ключом), который ведет себя как случайная перестановка. В частности, все 
прямо как при вычислении случайной перестановки при двух входных элементах 
разница, лишь в том, что одиночный бит должен дать два (почти) независимых вы-
ходных элемента (они не могут быть полностью независимы, так как они не могут 
быть равны), при этом также изменение одного из битов выходного элемента на Fk 
(•), где k является универсальным и неизвестным атакующему, должно дать (поч-
ти) независимый результат. Подразумевается, что одно-битовое изменение во вход-
ном элементе должно «повлиять» на каждый бит выходного элемента. (Обратите 
внимание, что это не значит, что все выходные биты будут изменены, это было бы 
другим поведением, которое можно было бы спрогнозировать для случайно пере-
становки. Скорее, мы лишь неформально имеем в виду, что каждый бит выходного 
элемента изменится, с приблизительно половинной вероятностью.) Для этого не-
обходимо будет проделать кое-какую работу.
Парадигма смешения-рассеивания. В дополнение к своей работе об идеаль-
ной стойкости, Шеннон (Shannon) также представил базовую парадигму констру-
ирования компактных, псевдослучайных перестановок. Основной идеей является 
конструирование псевдослучайных перестановок F с большой длиной блоков из 
множества более мелких случайных (или псевдослучайных) перестановок {fi}, с 
маленькой длиной блока. Давайте посмотрим, как это работает на базовом уров-
не. Скажем, мы хотим, чтобы длина блока F была 128 бит. Мы можем определить 
F следующим образом: ключ k для F определит 16 перестановок f1, . . . , f16 , каж-
дая из которых имеет длину блока в 8 бит (1 байт). 3 Учитывая входные данные 
x ∈{0, 1}
128
, мы разбираем ее на 16 байтов x1 • • • x16 и затем устанавливаем
Fk (x) = f1(x1)|| • • • ||f16(x16). (6.2)
Эти раундовые функции {fi} должны ввести смешение в F .
Необходимо немедленно прояснить, однако, что F, как определено выше, не 
будет псевдослучайной. В частности, если x и xr отличаются только первым би-
том, тогда Fk (x) и Fk (xr) будут отличаться только первым байтом (независимо 
от ключа k). В то же время, если F была бы истинно случайной перестановкой, 
_____________________________________________________
3Произвольная перестановка на 8 битах может быть представлена с использованием log(28!) 
≈ 1600 бит, поэтому длина ключа для F составит 16 • 1600 бит или 3 килобайта. Это намного 
меньше, чем ≈ 128 • 2128 бит, которые понадобились бы для определения произвольной пере-
становки на 128 битах.

224
тогда изменение первого бита входных данных, возможно, повлияло бы на все 
байты результата.
По этой причине вводится шаг рассеивание , когда биты результата перестав-
ляются или «смешиваются», используя смешивающую перестановку. Это дает 
эффект распространения локального изменения (например, изменение первого 
байта) по всему блоку. Шаги смешения/рассеивания, вместе называемые раун-
довые, повторяются множество раз. Это помогает обеспечить изменение оди-
ночного бита входных данных, что повлияет на все биты результата.
В качестве примера двухраундовый блочный шифр согласно данному под-
ходу будет работать следующим образом. Сначала вводится смешение путем 
вычисления промежуточного результата f1(x1)|| • • • ||f16(x16), как в Уравнении 
(6.2). Биты результата, таким образом, «перетасовываются» или переорганизо-
вываются, чтобы дать xr. Затем вычисляется f 1 r (xr )» • • • ||f r(xr) (где xr = xr • 
• • xr ), используя, возможно, различные функции f r, и биты результата пере-
ставляются, чтобы выдать xrr. {fi}, {f r} и смешивающая(-ие) перестановка(-и) 
могли бы быть случайными и зависимыми от ключей, как мы описали выше. 
На практике, однако, они специально разрабатываются и фиксируются, а ключ 
вводится различными способами, как мы опишем ниже.

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: