Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Упражнения
Предположим, что имеется 6-ступенчатый LFSR (регистр сдвига с линейной обратной связью) с c0 = c5 = 1 and c1 = c2 = c3 = c4 = 0. (a) Каковы первые 10 битов выходных данных у этого LFSR если в исходном состоянии они начинаются с (1, 1, 1, 1, 1, 1)? (b) Это максимальная длина LFSR? В этой задаче мы рассмотрим нелинейный комбинационный генератор, где 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. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|