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


ТЕОРЕМА 5.6 Если Π является защищенным MAC для сообщений длиной  A и ΠH являейтся стойкой к коллизиям, тогда Конструкция 5.5 является за-



Pdf көрінісі
бет129/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   125   126   127   128   129   130   131   132   ...   249
Криптография Катц

ТЕОРЕМА 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):


Достарыңызбен бөлісу:
1   ...   125   126   127   128   129   130   131   132   ...   249




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

    Басты бет