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



Pdf көрінісі
бет99/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   95   96   97   98   99   100   101   102   ...   249
Криптография Катц

УТВЕРЖДЕНИЕ 4.10 Pr[Mac-forgeAП(n) = 1 ^ NewBlock] является прене-
брежимо малым.
Утверждение основывается на безопасности Πr. Мы сконструировали ppt 
злоумышленника Ar, который атакует MAC Πr фиксированной длины и до-
бивается успеха в выведении действительной подделки прежде неаутентифи-
цированного сообщения с вероятностью
Pr[Mac-forgeArПr(n) = 1] ≥ Pr[Mac-forgeAП(n) = 1 ^ NewBlock]. (4.4)
Безопасность Πr означает, что левая стороны пренебрежимо мала, доказывая утверж-
дение. Конструкция Ar вполне очевидна, поэтому мы описываем ее вкратце. Ar запу-
скает A в качестве подпрограммы и отвечает на запрос от A касательно тега на m, под-
бирая r ← {0, 1}n/4 , разбирая m соответствующим образом, и выполняя необходимые 
запросы своему собственному оракулу MAC Macr (•). Когда A выводит (m, t =(r, t1, . . 
.)), тогда Ar проверяет, случиться ли NewBlock (это легко сделать, поскольку Ar может 
отслеживать все запросы, которые он делает своему собственному оракулу). Если так, 
тогда Ar находит первый блок r»A»i»mi, который никогда ранее не аутентифицировался 
посредством Macr, и выводит (r»A»i»mi, ti). (Если нет, Ar не выводит ничего.)


137
Видимость A , когда он запущен в качестве подпрограммы посредством Ar, 
распространяется идентично видимости A в эксперименте Mac-forgeAП(n) , и 
поэтому вероятности событий Mac-forge A(n) = 1, а NewBlock не меняется. Если 
случается NewBlock , тогда Ar выводит блок r||A||i||mi, который никогда ранее не 
был аутентифицирован собственным оракулом MAC; если Mac-forgeAП(n) = 
1, тогда тег на каждом блоке будет действительным (относительно Πr), и по-
этому, в частности, это истинно для блока, выведеного посредством Ar. Это 
означает, что не имеет значение, верно ли, что Mac-forgeAП(n) = 1, случается ли 
NewBlock, мы имеем Mac-forgeAП(n) = 1, доказывая Уравнение (4.4).
4.4 CBC-MAC 
Теоремы 4.6 и 4.8 показывают, что можно создать защищенный код аутентифика-
ции сообщений для сообщений произвольной длины из псевдослучайной функции, 
прини мающей данные фиксированной длины n. Это, в принципе, демонстрирует, что 
безопасные КАС могут быть созданы из блочных шифров. К сожалению, полученная 
конструкция чрезвычайно неэффективна: чтобы вычислить тег на сообщении длиной 
dn, блочный шифр вычисляется 4d раз; тег - более 4dn бит в длину. К счастью, доступны 
намного более эффективные конструкции. Мы изучаем одну такую конструкцию здесь, 
которая основывается исключительно на блочных шифрах, а еще одну - в Разделе 5.3.2, 
которая использует дополнительный криптографический примитив.


Достарыңызбен бөлісу:
1   ...   95   96   97   98   99   100   101   102   ...   249




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

    Басты бет