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