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



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

Подсказка: Считайте, что вспомогательные ключи генерируются 
из этого ключа.
(c) Найдите три других ключа DES с тем же свойством. Эти ключи известны как 
плохие ключи для DES. (Примечание: ключи, которые вы найдете, будут отличать-
ся от реальных плохих ключей DES из-за различий в вашем представлении).
(d) Представляют ли эти 4 плохих ключа серьезную уязвимость в использо-
вании тройного DES, в качестве псевдослучайной перестановки? Объясните.
Покажите, что DES имеет такое свойство, что DESk (x) = ¯DESk¯ (x) для 
каждого ключа k и вход x (где z¯ означает побитовое дополнение z).
(Это называется свойством комплементарности DES). Может ли это пред-
ставлять серьезную уязвимость в использовании тройного DES в качестве псев-
дослучайной перестановки? Объясните.
Опишите атаки на следующие модификации DES:
(a) Каждый вспомогательный ключ имеет длину 32 бита, а раундовая функ-
ция является просто исключающей ИЛИ вспомогательного ключа входа раун-
да (т.е. fˆ(k, R) = ki ⊕ R). Для этой задачи, список ключей не важен и вспомога-
тельные ключи ki можно рассматривать как независимые ключи.
(b) Вместо использования разных вспомогательных ключей в каждом раунде 
используется один и тот же 48-битный вспомогательный ключ. Покажите, как 
отличить шифр от случайной перестановки 248 раз.
Подсказка: Могут помочь упражнения 6.8 и 6.9. . .
(Это упражнение основано на упражнении 6.9). Наша цель в том, чтобы показать, 
что для любого плохого ключа k DES легко найти вход x такой, что DESk (x) = x.
(a) Предположим, что мы оцениваем DESk на входе (L0, R0), и выход после 
8 раундов сети Фейстеля (L8, R8) при L8 = R8. Покажите, что выход DESk (L0, 
R0) - это (L0, R0). (Напомним из упражнения 6.9, что DES меняет местами две 
половины 16-го раунда сети Фейстеля перед выводом результата).
(b) Покажите, как найти вход (L0, R0) со свойством в части (а).
Эта задача иллюстрирует атаку на тройное шифрование с двумя ключами. 


263
Пусть F будет блочным шифром с n-битной длиной блока и ключа, и задает 
(a) Предположим, что с данной парой (m1, m2) можно найти, за постоянное 
время, все ключи k2 , так что m2 = F −1(m1). Покажите, как восстановить весь 
ключ для F r (с высокой вероятностью) приблизительно за время 2n, используя 
три известных пары вход/выход.
(b) В общем, будет невозможно найти k2 , как указано выше, в течение посто-
янного времени. Тем не менее, покажите, что при использовании этапа предва-
рительной обработки, требующей времени 2n , можно, задав m2, найти (в прин-
ципе) в течение постоянного времени все ключи k2 так, чтобы m2 = F −1(0n).
(c) Предположим, что k1 известно, и что указанный выше этап предвари-
тельной обработки уже запущен. Покажите, как использовать значение y = F 
r(x) для единственного выбранного открытого текста x, чтобы определить k2 в 
течение постоянного времени.
(d) Поместите указанные выше компоненты вместе, чтобы разработать атаку, 
которая восстанавливает весь ключ F r при выполнении, приблизительно в тече-
ние времени 2n и запрашивании шифрования примерно 2n выбранных входов.
Допустим, что список ключей DES модифицируется следующим образом: 
левая половина мастер-ключа используется, чтобы получить все вспомогатель-
ные ключи в раундах 1-8, тогда как правая половина мастер-ключа использу-
ется, чтобы получить все вспомогательные ключи в раундах 9–16. Покажите 
атаку на эту модифицированную схему, которая восстанавливает весь ключ 
приблизительно за время 228.
6.15 Пусть f:{0, 1}m×{0, 1}A→{0, 1}A и g:{0,1}n×{0,1}A→{0,1}A 
будут безопасными блочными шифрами с m > n, и определим Fk1 ,k2 (x) = fk1 
(gk2 (x)). Покажите атаку с регенерацией ключа F с использованием времени 
O(2m) и пространства O(A • 2n).
Определите DESYk,kt (x) = DESk (x ⊕ kr). Длина ключа DESY равна 120 би-
там. Покажите атаку на DESY с регенерацией ключа, требующую времени и 
пространства ≈ 264.
Выберите случайные S-блоки и смешивающие перестановки для сетей SPN 
разных размеров и разработайте дифференциальные атаки на них. Мы реко-
мендуем попробовать пятираундовые SPN с блоками длиной 16 и 24 бита, ис-
пользуя S-блоки с 4-битным входом/выходом. Запишите код, чтобы вычислить 
таблицы дифференциалов и провести атаку.
Обеспечьте компромисс по времени/пространству для 40-битного DES (т.е. 
зафиксируйте первые 16 битов ключа DES на нуле). Рассчитайте необходимые 


264
время и память, и эмпирически оцените вероятность успеха. Эксперименталь-
но проверьте увеличение вероятности успеха, поскольку количество таблиц 
увеличивается. (Предупреждение: это большой проект).
Для каждой из следующих конструкций функции сжатия h из блочного шиф-
ра F, либо покажите атаку, либо докажите устойчивость к коллизиям в модели 
идеального шифра:
(a) h(k, x) = Fk (x).
(b) h(k, x) = Fk (x) ⊕ k ⊕ x.
(c) h(k, x) = Fk (x) ⊕ k.
Рассмотрите использование DES, чтобы сконструировать функцию сжатия 
следующим образом: Определите h :{0,1}112→{0, 1}64 как h(x,x ) DES
(DES (064)) где |x1| = |x2| = 56.
(a) Запишите явную коллизию в h. 


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




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

    Басты бет