Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- 5.3 Аутентификация сообщений с использованием хэш-функций
| ТЕОРЕМА 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, которую можно считать реализацией данного подхода. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|