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



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

КОНСТРУКЦИЯ 5.7
Пусть (GenH, H) будет хэш-функцией, сконструированной с применением 
преобрахзования Меркле-Дамгорда для функции сжатия (GenH, h), принима-
ющей входные данные длиной n + nr. (См. текст.) Пусть opad и ipad будут фик-
сированными константами длиной nr. Определяйте MAC следующим образом:
• Gen: при вводе 1n, запустите GenH (1n), чтобы получить ключ s. Также под-
берите универсальный k ∈ {0, 1 nt . } Выведите ключ (s, k). 
• Mac: при вводе ключа (s, k) и сообщения m ∈ {0, 1}* , выведите 
t := Hs.(k ⊕ opad) " Hs. (k ⊕ ipad) " m.. .
• Vrfy: при вводе ключа (s, k), сообщения m ∈ {0, 1}* и тега t, выведите 1, 
если и только если t =? Hs.(k ⊕opad) || Hs. (k ⊕ ipad) || m...
HMAC. 
РИСУНОК 5.2: HMAC, наглядный пример.
Почему у нас должна быть какая-то уверенность, что HMAC является за-
щищенным? Одна из причин заключается в том, что мы можем рассматривать 
HMAC как специфическую реализацию парадигмы хэш-и-MAC из предыду-
щего раздела. Чтобы это увидеть, мы заглянем «за кулисы» на то, что проис-
ходит, когда сообщение проходит аутентификацию; см. Рисунко 5.2. Мы так же 


178
должны более тщательно определять параметры и более подробно остановится 
на том, как на практике внедряется преобразование Меркле-Дамгорда.
Скажем, (GenH, H) сконструирована на основе функции сжатия (GenH, h), в 
которой h преоразовывает входные данные длиной n + nr в выходные данные 
длиной n (где, строго говоря, nr - это функция n). Когда мы описывали преоб-
разование Меркле-Дамгорда в Разделе 5.2, мы предполагали, что nr = n, но не 
обязательно должно быть именно так. Мы также говорили, что длина сообще-
ния, которое должно хэшироваться, была зашифрована в дополнительный блок, 
который присодинялся к сообщению. На практике длина вместо этого зашиф-
ровывается в часть блока с использованием битов A < nr . То есть вычисление 
Hs(x) начинается с добавления x с нулями к строке длиной ровно на A меньше, 
чем кратное nr; затем добавляется длина L = |x|, зашифрованная с использова-
нием ровно A бит. Хэш получившейся последовательности nr-битных блоков 
x1, . . . затем вычисляется как в Конструкции 5.3. Мы предположим, что n + A ≤ 
nr. Это означает, в частности, что если мы хэшируем входные данные x длиной 
nr + n, тогда дополненный результат (включая длину) будет точно длиной 2nr 
бит. Доказательство Теоремы 5.4, показывающее, что (GenH, H) является стой-
кой к коллизиям, если (GenH, h) стойкая к коллизиям, остается неизменным. 
Возвращаясь к HMAC и глядя на Рисунок 5.2, мы можем увидеть, что общая 
форма HMAC задействует хэширование сообщения произвольной длины в ко-
роткую строку y Hs( (k ⊕ ipad) « m), а затем вычисление (секретно кодиро-
ванной) функции Hs((k ⊕ opad) « y) результата. Но мы можем сказать даже еще 
больше. Сначала обратите внимания, что «внутреннее» вычисление
H˜ s(m) Hs( (k ⊕ ipad) || m) 
является стойким к коллизиям (предпологая, что h имеет место) при любом зна-
чении k ∈ ipad. Более того, первый шаг «внешнего» вычисления Hs((k ⊕ opad) || 
y) должен вычислить значение kout hs(IV || (k ⊕ opad)). Затем, мы определим 
hs(k|| yˆ), где y сслыается на дополненное значение y (то есть включая длину (k 

opad) || y, которая всегда nr + n бит, зашифрованная с использованием ровно 
A бит). Таким образом, если мы будем считать kout как универсальным, мы 
будем относиться к нижеописанному более формально и предположим, что
M˜ac (y) hs(k || yˆ)
(5.2)
является защищенным MAC фиксированной длины, тогда HMAC можно рас-
симатривать как реализацию подхода хэш-и-MAC с
HMACs,k (m) = M˜ackout (H˜ (m)) 
(5.3)
(где kout = hs(IV || (k ⊕ opad))). Благодаря способу разработки функции сжатия 
h (см. Раздел 6.3.1), предположение, что M˜ac является защищенным MAC фик-
сированной длины, имеет смысл.


179


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




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

    Басты бет