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



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

ТЕОРЕМА 5.4  Если (Gen, h) является стойкой к коллизиям, тогда (Gen, H) тоже.
ДОКАЗАТЕЛЬСТВО Мы покажем, что для любых s коллизия в Hs даст 
коллизию в hs. Пусть x и xr будут две различные строки длиной L и Lr, соответ-
ственно, так что Hs(x) = Hs(xr). Пусть x1, . . . , xB будет блоками B дополненной 
x, и x1 xz... xB xB+1=L zo = IV hs z1 hs... hszB hs H (x) пусть xr , . . . , xr будет 
блоками Br дополненной xr. Напомним, что xB+1 = L и 1 Bt xr r Bt+1 = L . Для 
рассмотрения имеется два случая:
FIGURE 5.1: Преобразование Меркле-Дамгорда.
1. Случай 1: L ƒ= Lr. В этом случае последний шаг вычислений
Hs(x) - это zB+1 := hs(zB ||L), а последний шаг вычислений 
Hs(xr) - это zr := h
s
(zr ||Lr). Так как Hs(x) = Hs(xr), из этого следует, что hs(zB 
«L) = hs(zr ||Lr). Однако, L ƒ= Lr, и поэтому zB ||L и zr ||Lr являются двумя раз-
личными строками, которые сталкиваются под hs.
2. Случай 2: L = Lr. Это означает, что B = Br. Пусть z0, . . . , zB+1 будут значе-
ниями, определенными во время вычисления Hs(x), пусть Ii zi−1||xi обозна-
чает входные данные i для hs, и установим IB+2 zB+1 Определеите Ir , . . . , Ir 
аналогично 1 B+2 относительно xr. Пусть N будет наибольшим индексом, для 


174
которого IN ƒ= Ir . Поскольку |x| = |xr|, но x ƒ= xr, имеет место i с xi ƒ= xr , и 
поэтому такой N определенно существует. Потому что
IB+2= zB+1 =Hs(x) = Hs(xr) = zrB+1= IB+2
мы имеем N ≤ B + 1. По максимальности N, мы имеем IN +1 = Ir и в частности 
zN = zr . Но это означает, что IN , Ir являются коллизией в hs. 
Мы оставим это в качестве упражнения для превращения вышесказанного в 
формальное сжатие. 
5.3 Аутентификация сообщений с использованием хэш-функций 
В предыдущей главе мы представили конструкции кодов аутентификации 
сообщений для сообщейний произвольной длины. Первый подход был типич-
ным, но неэффективным. Второй подход, CBC-MAC, основывался на псевдос-
лучайных функциях. Тут мы увидим еще один подход, который мы называем 
«хэш и MAC» (hash-and-MAC), который опирается на стойкое к коллизиям хэ-
ширование вместе с кодом аутентификации сообщений. Затем мы рассмотрим 
стандартизированную и широко используемую конструкцию под названием 
HMAC, которую можно считать реализацией данного подхода.


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




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

    Басты бет