261
имеется n -ступенчатый LFSR, но выход на каждом временном шаге не s0, а
вместо этого g(s0, . . . , sn−1) для некоторой нелинейной функции g. Предпо-
ложим, что коэффициенты обратной связи LFSR известны, а его начальное со-
стояние - нет.
Покажите, что каждый из следующих вариантов g не позволяет
получить хороший псевдослучайный генератор:
(a) g(s0, . . . , sn−1) = s0 ^ s1.
(b) g(s0, . . . , sn−1) = (s0 ^ s1) ⊕ s2.
Пусть F будет блочным шифром с длиной ключа и длиной блока n битов. Допустим
есть атака с регенерацией ключа на F, которая успешна с вероятностью 1 с использо-
ванием n подобранных открытых текстов и минимальными вычислительными затра-
тами.
Докажите, что формально F не может быть псевдослучайной перестановкой.
В нашей атаке на однораундовую SPN мы рассматривали блок длиной 64
бита и 16 S-блоков, каждый из которых имеет 4-битный вход. Повторите анализ
для случая 8 S-блоков, каждый из которых имеет 8-битный вход. Какова те-
перь сложность атаки? Снова повторите анализ с длиной блока 128 битов и 16
S-блоками, каждый из которых имеет 8-битный вход.
Рассмотрите модифицированную SPN, где вместо выполнения этапов ключе-
вого смешивания, замены и перестановки в чередующемся порядке для r (пол-
ных) раундов, шифр вместо этого применяет r раунднов ключевого смешива-
ния, затем выполняет r раундов замены и, наконец, применяет r смешивающих
перестановок. Проанализируйте безопасность этой конструкции.
В этой задаче мы предполагаем двухраундовую SPN с длиной блока 64 бита.
(a) Предположим, что в каждом раунде используются
вспомогательные
64-битные ключи, так что мастер-ключ имеет длину 192 бита. Покажите атаку с
регенерацией ключа, использующую менее 2192 попыток.
(b) Предположим, что первый и третий вспомогательные ключи одинаковы, а
второй вспомогательный ключ независимый, так что мастер-ключ имеет дли-
ну 128 битов. Покажите атаку с регенерацией ключа, использующую намного
менее 2128 попыток.
Каков выход r-раундовой сети Фейстеля, если на входе (L0, R0) в каждом из
следующих двух случаев:
(a) Каждая раундовая функция выводит все нули, независимо от входных данных.
(b) Каждая раундовая функция является тождественной функцией.
Пусть Feistelf1 ,f2 (•) означает двухраундовую сеть Фейстеля, использующую
функции f1 и f2 (в этом порядке). Покажите, что если Feistelf1 ,f2 (L0, R0) = (L2,
R2), то Feistelf2 ,f1 (R2, L2) = (R0, L0).
Для этого упражнения
руководствуйтесь описанием DES,
приведенным в
262
этой главе, но используйте тот факт, что в реальной конструкции DES обе эти по-
ловины выхода конечного раунда сети Фейстеля, поменялись местами. Т.е. если
выход конечного раунда сети Фейстеля (L16, R16), то выход DES - (R16, L16).
(a) Покажите, что единственная разница между вычислением DESk и DES−1-
это порядок, в котором используются вспомогательные ключи. (Опирайтесь на
предыдущее упраждение).
(b) Покажите, что для k = 056 считается, что DESk (DESk (x)) = x.
Достарыңызбен бөлісу: