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



Pdf көрінісі
бет155/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   151   152   153   154   155   156   157   158   ...   249
Криптография Катц

Упражнения
5.1 Представьте формальные определения для стойкости к нахождению вто-
рого прообраза и стойкости нахождению прообраза. Докажите, что любая 
хэш-функция, которая является стойкой к коллизиям, является также стойкой 
к нахождению второго прообраза, а любая хэш-функция, которая стойкая к на-
хождению второго прообраза, является также стойкой к нахождению прообраза.
Пусть (Gen1, H1) и (Gen2, H2) будут двумя хэш-функциями. Определите 
(Gen, H) так, чтобы Gen запускал Gen1 и Gen2 , чтобы получить ключи s1 и s2, 
соответственно. Затем определите Hs1 ,s2 (x) = Hs1 (x)||Hs2 (x).
(a) Докажите, что, если по крайней мере одна из (Gen1, H1) и (Gen2, H2) явля-
ется стойкой к коллизиям, тогда (Gen, H) является стойкой к коллизиям.
(b) Определите, справедливо ли аналогичное заявление касательно стойкости 
к нахождению второго прообраза и стойкости к нахождению прообраза, соот-
ветственно. Докажите ваш ответ по каждому из случаев. 
Пусть (Gen, H) будет стойкой к коллизиям хэш-функцией. Обязательно ли (Gen, 
Hˆ ), определенная посредством Hˆ s(x) Hs(Hs(x)), является стойкой к коллизиям? 
Предоставьте формальное доказательство Теоремы 5.4 (то есть опишите редукцию).
Обобщите преобразование Меркле-Дамгорда (Конструкция 5.3) для случая, 
когда хэш-функция фиксированной длины h имеет входную длину n + κ (при κ 
> 0) и выходную длину n, и длина входных данных в H должна быть зашифро-
вана как A-битное значение (как описано в Разделе 5.3.2). Докажите стойкойсть 
к коллизиям (Gen, H), принимая во внимание стойкость к коллизиям (Gen, h).
Для каждой из следующих модификаций преобразования Меркле-Дамгорда 
(Конструкция 5.3) определите, стойкий ли результат к коллизиям. Если да - пре-
доставьте доказательство; если нет - продемонстрируйте атаку.
(a) Измените конструкцию таким образом, чтобы входная длина не была 
включена вообще (то есть выведите zB , а не zB+1 = hs(zB||L)). (Предположите, 
что искомая хэш-функция определена только для входных данных, длина кото-
рых - это целое число кратное длине блока.)
(b) Измените конструкцию так, чтобы вместо вывода z = hs(zB «L), алгоритм 
выводил zB ||L.
(c) Вместо использования IV просто начинте вычисление с x1. То есть опре-
делите z1 := x1 , а затем вычислите zi := hs(zi 1»xi) для i = 2, . . . , B + 1 и вы-
ведите zB+1 , как ранее.
(d) Вместо использования фиксированного IV , установите z0 := L , а затем 
вычислите zi := hs(zi 1||x ) для i = 1, . . . , B и выведите z .
Предположите, что стойкая к коллизиям хэш-функция имеет место. Покажи-


210
те конструкцию хэш-функции фиксированной длины (Gen, h), которая не яв-
ляется стойкой к коллизиям, но так, чтобы хэш-функция (Gen, H), полученная 
из преобразования Меркле-Дамгорда в (Gen, h), как в Конструкции 5.3, была 
стойкой к коллизиям.
Докажите или опровергните: если (Gen, h) является стойкой к нахождению 
прообраза, то и хэш-функция (Gen, H), полученная путем применения преоб-
разования Меркле-Дамгорда к (Gen, h), как в Конструкции 5.3, также является 
стойкой к нахождению прообраза. 
Докажите или опровергните: если (Gen, h) является стойкой к нахождению 
второго прообраза, то и хэш-функция (Gen, H), полученная путем применения 
преобразования Меркле-Дамгорда к (Gen, h), как в Конструкции 5.3, также яв-
ляется стойкой к нахождению второго прообраза.
Перед HMAC было нормально определять MAC для сообщений произволь-
ной блины путем Macs,k (m) = Hs(k»m), где H - это стойкая к коллизиям хэш-
функция.
(a) Покажите, что это совсем не защищенный MAC, если H сконструирована 
посредством преобразования Меркле-Дамгорда. (Предположите, что хэш-ключ 
s известен атакующему, и только k содержится в секрете.)
(b) Докажите, что это защищенный MAC, если H смоделирована как случай-
ный оракул.
Докажите, что конструкция псевдослучайной функции, приведенная в Раз-
деле 5.5.1, является защищенной в модели со случайным оракулом.
Докажите Теорему 5.11.
Покажите, как найти коллизию в конструкции дерева Меркле, если значение 
t нефиксированное. В частности, покажите, как найти два набора входных дан-
ных x1, . . . , xt и 1, . . . , x2t так, чтобы MT t(x1, . . . , xt) = MT 2t(x1, . . . , x2t).
Рассмотрите сценарий, представленный в Разделе 5.6.2, в котором клиент 
хранит файлы на сервере и хочет проверить, чтобы файлы вернулись неизме-
ненными.
(a) Предоствьте формальное определение безопасности для этих условий.
(b) Формализуйте конструкцию, основанную на деревьях Меркле, как описа-
но в Разделе 5.6.2.
(c) Докажите, что конструкция защищенная относительно вашему определе-
нию при допущении, что (GenH, H) является стойкой к коллизиям.
Докажите, что схема обязательства, описанная в Разделе 5.6.5, является за-
щищенной в модели со случайным оракулом. 


211


Достарыңызбен бөлісу:
1   ...   151   152   153   154   155   156   157   158   ...   249




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

    Басты бет