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



Pdf көрінісі
бет189/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   185   186   187   188   189   190   191   192   ...   249
Криптография Катц

ТЕОРЕМА 6.5 Если F моделируется в качестве идеального шифра, то кон-
струкция Мейера-Дэвиса дает устойчивую к коллизиям функцию сжатия. Точ-
нее, любой взломщик, делая q < 2A/2 запросов к прогнозам идеального шифра 
обнаруживает коллизию с вероятностью, чаще всего, q2/2A.
ДОКАЗАТЕЛЬСТВО Чтобы было ясно, мы рассмотрим здесь вероятностный 
эксперимент, в котором F отбирается случайным образом (точнее, для каждого k 

{0, 1}n функция F (k, •) : {0, 1}A → {0, 1}A выбирается равномерно из множе-
ства PermA перестановок A-битных строк) а затем взломщик получает доступ к 
прогнозу F и F −1. Взломщик пытается затем найти пару с коллизией (k, x), (kr, xr), 
т.е. для которой F (k, x)⊕ x = F (kr , xr)⊕ xr. Никакие вычислительные ограничения 
не действуют на взломщика кроме ограничения количества запросов прогноза, 
которые он делает. Скажем, предполагаем, что если взломщик выводит пары с 
коллизией (k, x), (kr , xr), то он предварительно сделал запросы прогноза, необхо-
димые для вычисления значений F (k, x) и F (kr, xr). Мы также предполагаем, что 
взломщик никогда не делает один и тот же запрос более, чем один раз и никогда 
не запрашивает F −1(k, y), если уже узнал, что y = F (k, x) (и наоборот). Все эти 
предположения сделаны без ограничения общности.
Рассмотрим i-й запрос взломщика, сделанный по его прогнозам. Запрос (ki, 
xi)к F показывает только значение хэш-функции hi h(ki, xi) = F (ki, xi) ⊕ 
xi; аналогично, запрос к F −1 , дающий результат xi = F −1(ki, yi), дает только 
значение хэш-функции hi h(ki, xi) = yi ⊕ F −1(ki, yi). Взломщик не получит 
коллизии кроме hi = hj для некоторых i ƒ= j. 
Зафиксируем i, j при i > j и рассмотрим вероятность того, что hi = hj . Во время 
i-го запроса значение hj зафиксировано. Коллизия между hi и hj получается на 
i-м запросе, только если взломщик обращается с запросом (ki, xi) к F и получает 
результат F (ki, xi) = hj ⊕ xi, или обращается с запросом (ki, yi) к F −1 и получает 


257
результат F −1(ki, yi) = hj ⊕ yi. Либо событие происходит с вероятностью, чаще всего, 
1/(2A − (i − 1)) поскольку, например, F (ki, xi) равномерна по {0, 1}A, за исключени-
ем того, что она не может быть равна любому значению F (ki, x) уже определенному 
взломщиком (чаще всего) i − 1 предыдущими запросами прогноза с использованием 
ключа ki. Поскольку i ≤ q < 2A/2, вероятность того, что hi = hj чаще всего равна 2/2A.
Принимая границу объединения по всем .q/2. < q2/2 различным парам i, j дает 
результат, указанный в теореме.


Достарыңызбен бөлісу:
1   ...   185   186   187   188   189   190   191   192   ...   249




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

    Басты бет