Введение в современную криптографию

227
бого блочного шифра является то, что изменение входного элемента должно 
«повлиять» на каждый бит результата. Мы назовем это явление лавинным эф-
фектом. Один из способов вызвать лавинный эффект в подстановочно-переста-
новочной сети - это обеспечить наличие следующих двух свойств (при макси-
мальном количестве раундов):
1. S-блоки разработаны так, чтобы, изменяя один бит входного элемента, 
S-блок меняет как минимум два бита в выходном элементе S-блока.
2. Смешивающие перестановки разработаны так, чтобы выходные биты лю-
бого доступного S-блока использовались как входные элементы в множествен-
ные S-блоки в следующем раунде.
Чтобы увидеть, как это производит лавинный эффект, по крайней мере эвристи-
чески, предположим, что S-блоки все такие, что изменение одного бита входного 
элемента S-блока выливается в изменение ровно двух битов выходного элемента 
S-блока, и что смешивающие перестановки выбраны, как указано выше. Для кон-
кретики, предположим, что S-блоки имеют входной/выходной размер в 8 бит, и 
что длина блока шифра - 128 бит. Рассмотрим сейчас, что случится, когда блочный 
шифр примениться к двум входным элементам, которые отличаются одним битом:
1. После первого раунда промежуточные значения отличаются ровно в двух 
положениях битов. Это потому что сложение по модулю 2, текущего ключа 
сохраняет 1-битную разницу в промежуточных значениях, и поэтому входные 
элементы во все S-блоки, кроме одного, - идентичны. В одном S-блоке, в ко-
тором входные элементы отличаются, выходной результат S-блока показывает 
2-битную разницу. Смешивающая перестановка, применяемая к результатам, 
меняет позиции эти изменений, но сохраняет 2-битную разницу.
2. Смешивающая перестановка, применяемая в конце первого раунда, рас-
пространяет две позиции битов, в которых промежуточные результаты отлича-
ются, в два различных S-блока во втором раунде. Это остается истинным, даже 
после того, как соответствующий ключ складывается по модулю 2 с результа-
том предыдущего раунда. Итак, во втором раунде у нас теперь два S-блока, ко-
торые получили входные элементы, отличающиеся на один бит. Таким образом, 
в конце второго раунда промежуточные значения отличаются на 4 бита.
3. Продолжая тот же аргумент, мы прогнозируем 8 бит промежуточного зна-
чения после третьего раунда, 16 бит - после четвертого раунда и все 128 бит 
выходного результата в конце седьмого раунда.
Последняя точка не очень точная, и определенно есть вероятность, что будет не-
которые отличия результатов какого-либо из раундов от прогнозируемых. (Факти-
чески, так и должно быть, потому что результаты не должны отличаться по всем 
битам.) Однако, вышеописанный анализ, дает нижнюю границу по количеству 

228
раундов: если используется менее 7 раундов, тогда должен быть некий набор вы-
ходных битов, которые не затронет однобитное изменение во входных данных, 
вызвав тем самым возможность распознать шифр из случайной перестановки.
Можно ожидать, что «наилучшим» способом разработать S-блоки было бы вы-
брать их случайным образом (учитывая то ограничение, что они являются пере-
становками). Интересно, что это нам не подходит, по крайней мере, если мы хо-
тим удовлетворить коректный критерий, упомянутый ранее. Рассмотрим случай, 
когда S-блок, работающий с 4-битными входными данными, и пусть x и xr будут 
двумя разными значениями. Пусть y = S(x), и теперь рассмотрим выбор универ-
сального yr ƒ= y в качестве значения S(xr). Имеется 4 строки, отличающиеся от 
y только лишь одним битом, и поэтому с вероятностью 4/15 мы выберем yr , ко-
торое не отличается от y на два или более бита. Проблемаусугубляется, если при-
нять во внимание все пары входных элементов, которые отличаются на один бит.
Сделаем вывод, основанный на этом примере, что, как правило, S-boxes 
должны быть тщательно разработы, а не просто выбраны случайным образом. 
Случайные S-блоки - это также нехорошо для защиты от атак, как и блоки, ко-
торые мы покажем в Разделе 6.2.6.
Если блочный шифр должен также быть строго псевдослучайным, тогда лавин-
ный эффект должен обязательно применяться к его обратному варианту. То есть из-
менение одного бита выходного элемента должно влиять на каждый бит входного 
элемента. Поэтому это очень полезно, если S-блоки разрабатываются так, чтобы, 
меняя один бит выходного элемента S-блока, менялись по крайней мере два бита 
входного элемента в S-блоке . Достижение лавинного эффекта в обоих направлени-
ях - это еще одна причина для дальнейшего увеличения количества раундов.

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

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