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