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, является за-
щищенной в модели со случайным оракулом.