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



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

5.3.1 Хэш и MAC
Идея, что кроется под хэш и MAC, проста. Для начала сообщение произволь-
ной длины m хэшируется в строку фиксированной длины Hs(m) при помощи 
стойкой к коллизиям хэш-функции. Затем MAC (фиксированной длины) при-
меняется к результату. См. Конструкцию 5.5 для формального описания.
КОНСТРУКЦИЯ 5.5
Пусть Π = (Mac, Vrfy) будет MAC для сообщений длиной A(n), и пусть ΠH
= (GenH, H) будет хэш-функцией с длиной выходных данных A(n). Постройте 
MAC Πr = (Genr , Macr , Vrfyr) для сообщений произвольной длины следующим 
образом:
• Genr : при вводе 1n, подберите универсальный k ∈ {0, 1}, и запустите GenH 
(1n) чтобы получить s; ключ - kr := (k, s). 
• Macr : при вводе ключа (k, s) и сообщения m ∈ {0, 1}*, выведите
t ← Mack(Hs(m)).
• Vrfyr : при вводе ключа (k, s), сообщение m ∈ {0, 1}*, и tag t MAC, выведите 
1, если и только если Vrfy (Hs(m), t) =? 1.
Парадигма хэш-и-MAC. 
Конструкция 5.5 является защищенной, если Π является защищенным MAC для со-
общений фиксированной длины, и (Gen, H) является стойкой к коллизиям. Очевидно, по-
скольку хэш-функция является стойкой к коллизиям, аутентификация Hs(m) настолько же 
эффективна, как и и аутентификация смого m : если отправитель может убедиться в том, 


175
что получатель получит правильное значение Hs(m), стойкость к коллизиям гарантирует, 
что атакующий не сможет найти отдельное сообщение mr , которое хэшируется в это же 
значение. Строго говоря, скажем, отправитель использует Конструкцию 5.5, чтобы аутен-
тифицировать некоторый набор сообщений Q, а атакующий A может подделать верный 
тег на новом сообщении m* ƒ∈ Q. Существуют два возможных случая:
Случай 1: есть сообщение m  Q , так чтоHs(m*) = Hs(m). Тогда A нашел 
коллизию в Hs, противоречащую стойкости к коллизиям (Gen, H).
Случай 2: для каждого сообщения m  Q справедливо, что Hs(m*) ƒ= Hs(m). 
Пусть Hs(Q) {Hs(m) | m ∈ Q}. Тогда Hs(m*) ∉/ Hs(Q). В этом случае A 
подделал верный тег на «новом сообщении» Hs(m*) относительно кода аутен-
тификации сообщений фиксированной длины Π. Это противоречит предполо-
жению, что Π является защищенным MAC. Сейчас мы превратим вышесказан-
ное в формальное доказательство. 


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




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

    Басты бет