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


Атаки «дней рождения « малого пространства



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

5.4.2 Атаки «дней рождения « малого пространства 
Атаки «дней рождения», описанные выше, требуют большого количества па-
мяти; они требуют от атакующего хранить все O(q) = O(2A/2 ) значения {yi}, 
потмоу что атакующий не знает заранее, какая пара значение вызовет колли-
зию. Это серьезный недостаток, потому что память, в общем, является более 
ограниченным ресурсом, чем время. И, пожалуй, сложнее разместить и орга-
низовать хранилище для 260 байтов, чем выполнить 260 команд процессора. 


183
Более того, всегда можно позволить вычислению работать автономно, в то же 
время требования алгоритма к памяти должны быть удовлетворены сразу же, 
как эта память потребуется.
Мы покажем здесь более продвинутую атаку «дней рождения» с существенно 
уменьшенными требованиями к памяти. В действительности, она имеет такую 
же временную сложность и вероятность успеха, как и прежняя, однако исполь-
зует только постоянный объем памяти. Атака начинается с подбора случайного 
значения x0 и вычисления xi := H(xi−1) и x2i := H(H(x2(i−1))) для i = 1, 2, . . .. 
(Обратите внимание, что xi = H(i)(x0) для всех i, где H(i) ссылается на i-кратную 
итерацию H.) На каждом шаге значения xi и x2i сравниваются; если они идентич-
ны, значит коллизия происходит где-то в последовательности x0, x1, . . . , x2i−1. 
Затем алгоритм находит наименьшее значение j , для которого xj = xj+i (обратите 
внимание, что j ≤ i, так как j = i работатет) и выводит xj−1, xj+i−1 в качестве колли-
зии. Данная атака, описанная формально как Алгоритм 5.9 и проанализированная 
ниже, требует только хранилища для двух хэш-значений при каждой итерации.
АЛГОРИТМ 5.9
Атака "дней рождения" малого пространства
Вход: Хэш-функция H : {0, 1 }* → {0, 1 }A 
Выход: Различные x, xr при H(x) = H(xr)
Сколько итераций первого круга мы прогнозировали ранее xr = x? РАссмотрите по-
следовательность значений x1, x2, . . ., где xi = H(i)(x0), как было определено ранее. Есл 
и мы смоделируем H в качестве случайной функции, каждое из этих значений будет 
равномерно и независимо распределяться в {0, 1}A, пока не случится первый повтор.
Таким образом, мы ожидаем, что повтор случится с вероятностью 1/2 в первых q = 
Θ(2A/2) членах последовательности. Мы покажем, что повтор случится в первых q 
элементах, алгоритм найдет повтор в максимум q итерациях первого круга:


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




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

    Басты бет