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 итерациях первого круга:
Достарыңызбен бөлісу: