Введение в современную криптографию
ТЕОРЕМА 5.6 Если Π является защищенным MAC для сообщений длиной A и ΠH являейтся стойкой к коллизиям, тогда Конструкция 5.5 является за-
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| ТЕОРЕМА 5.6 Если Π является защищенным MAC для сообщений длиной
A и ΠH являейтся стойкой к коллизиям, тогда Конструкция 5.5 является за- щищенным MAC (для сообщений произвольной длины). ДОКАЗАТЕЛЬСТВО Пусть Πr обозначает Конструкцию 5.5, и пусть Ar будет ppt злоумышленником, атакующим Πr. При выполнении эксперимента Mac-forge A ,Π t t (n), пусть kr = (k, s) обозначает ключ MAC, пусть Q обозначает набор сообщений, теги которых были запрошены Ar, и пусть (m* , t) будут конечными выходными данными Ar. Предположим без потери обобщенности, что m* ƒ∉ Q. Определите coll как событие, которое в эксперименте Mac-forge A ,Π t t (n), су- ществует m ∈ Q , для которого Hs(m*) = Hs(m). Мы имеем Pr[Mac-forge t t (n) = 1] Мы покажем, что оба члена Уравнения (5.1) пренебрежимо малы, таким обра- зом, завершив доказательство. Очевидно, что первый член пренебрежимо мал из- за стойкости к коллизиям ΠH, а второй член пренебрежимо мал из-за защиты Π. Рассмотрите следующий алгоритм C на предмет поиска коллизий в ΠH : Алгоритм C: В алгоритм вводится s в качестве входных данных (с подразумеваемым n). • Подберите универсальный k ∈ {0, 1}n. • Запустите Ar(1n). Когда Ar запросит тег на сообщение i mi ∈ {0, 1}*, вы- числите ti ← Mack (Hs(mi)) и дайте (Ar) (ti). • Если Ar выведет (m* , t), тогда, если i, для которого Hs(m*) = Hs(mi), вы- 176 ведите (m* , mi). Очевидно, что C работает в полиномиальном времени. Давайте проанализи- руем его поведение. Если входные данные для C генерируются работающим GenH (1n) для получения s, видимость Ar при работе в качестве подпрограммы C распространяется идентично видимости Ar в эксперименте Mac-forge A ,Π t t (n). В частности, теги, полученные Ar от C имеют такое же распространение, как и теги, которые Ar получает отMac-forge A ,Π. Поскольку C выводит колли- зию сразу же, как случается coll, мы имеем Pr[Hash-collC,ΠH (n) = 1] = Pr[coll]. Так как ΠH является стойкой к коллизии, сделаем вывод, что Pr[coll] прене- брежимо мала. Теперь продолжим доказывать, что второй член в Уравнении (5.1) пренебре- жимо малым. Рассмотрите следующего злоумышленника A, атакующего Π в Mac-forge A ,Π(n): жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|