Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- КОНСТРУКЦИЯ 5.5
- Случай 1
| 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. Сейчас мы превратим вышесказан- ное в формальное доказательство. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|