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



Pdf көрінісі
бет193/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   189   190   191   192   193   194   195   196   ...   249
Криптография Катц

Упражнения
Предположим, что имеется 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.


Достарыңызбен бөлісу:
1   ...   189   190   191   192   193   194   195   196   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет