Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Подсказка: Считайте, что вспомогательные ключи генерируются
из этого ключа. (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. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|