Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ДОКАЗАТЕЛЬСТВО
| КОНСТРУКЦИЯ 4.7
Пусть Πr = (Macr , Vrfyr) будет MAC фиксированной длины для сообщения длиной n. Определяйте MAC следующим Mac: при вводе ключ k ∈ {0, 1} и сообщение, m ∈ {0, 1} (ненулевой) длины A < 2n/4, разберите m на d блоки m1, . . . , md, каждый длиной n/4. (Последний блок дополните нулями при необходимости.) Выберите универсальный идентификатор r ∈ {0, 1 } n/4 Для i = 1, . . . , d, вычислите t ← Mac k(r"A"i"m ), где i, A зашифрованы в виде строк длиной n/4.† Выведите тег t := (r, t1, . . . , td). Vrfy: при вводе ключ k ∈ {0, 1}n , сообщение m ∈ {0, 1}* и тег A< 2n/4 и тег t = (r, t1, . . . , tdt ), разберите m на d блоки m1, . . . , md, каждый длиной n/4. (Последний блок дополните нулями при необходимости.) Выведите 1, если и только если d r = d и Vrfyr (r" A"i" m , t ) = 1 для 1 ≤ i ≤ d. _____________________________________ † Обратите внимание, что i и A могут быть зашифрованы с использованием n/4 бит, потому что i, A < 2n/4. MAC для сообщений произвольной длины из любого MAC фиксированной длины. (Технически, схема обрабатвает только лишь сообщения длиной менее 2n/4.) Асимптотически, так как это экспоненциальная граница, доверенные стороны не будут аутентифицировать сообщения такой длины, и любой полиномиально- временной злоумышленник не сможет отправить сообщение такой длины сво- ему оракулу MAC. На практике, когда конкретное значение n фиксированное , необходимо убедиться, что эта граница приемлема.) ТЕОРЕМА 4.8 Если Πr является защищенным MAC фиксированной длины для сообщений длиной n, тогда Конструкция 4.7 является защищенным MAC (для сообщений произвольной длины). ДОКАЗАТЕЛЬСТВО Интуиция подсказывает, что пока Πr под защитой, злоумышленник не может ввести новый блок с действительным тегом. Более того, дополнительная информация, включенная в каждый блок, предотвращает различные атаки (сброшенные блоки, переставленные блоки и т.д.), описанные 135 ранее. Мы докажем безопасность, фактически показав, что эти атаки являются единственными из возможных. Пусть Π будет MAC на основании Конструкции 4.7, и пусть A будет вероятност- ным полиноминально-временным злоумышленником. Мы покажем, что Pr[Mac- forgeAП(n) = 1] является пренебрежимо малым. Для начала мы представим определенное обозначение, которое будет использовано в доказательстве. Пусть Repeat обозначает событие, при котором один и тот же случайный идентификатор появляется в двух из тегов, возвращенных оракулом MAC в эксперименте Mac- forgeAП(n). Позволяя (m, t = (r, t1, . . .)) обозначать конечные выходные данные A, где m = m1, . . . имеет длину A, мы позволяем NewBlock быть событием, когда по крйней мере один из блоков r||A||i||mi никогда ранее не аутентифицировался посредством Macr в процессе ответа на A запросы Mac. (Обратие внимание, что по конструкции Π легко сказать точно, какие блоки аутентифицировались посред- ством Macr , при вычислении Mack (m).) Неформально, NewBlock - это событие, когда A пытается вывести действительный тег на блоке, который никогда не был аутентифицирован соответствующим MAC Πr фиксированной длины. Мы имеем Pr[Mac-forgeAП(n) = 1] = Pr[Mac-forgeAП(n) = 1 ^ Repeat] + Pr[Mac-forgeAП(n) = 1 ^ eRwepBeloactk^ N ] + Pr[Mac-forgeAП(n) = 1 ^ Repeat ^NewBlock] ≤ Pr[Repeat] (4.3) + Pr[Mac-forgeAП(n) = 1 ^ NewBlock] + Pr[Mac-forgeAП(n) = 1 ^ Repeat ^ NewBlock]. Мы покажем, что первые два члена Уравнения (4.3) пренебрежимо малы, а последний член - это 0. Из этого следует, что Pr[Mac-forgeAП(n) = 1] является пренебрежимо малым, как и планировалось . жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|