184
ДОКАЗАТЕЛЬСТВО Последовательность xI, xI+1, . . . повторяется с перио-
дом ∆ = J − I. То есть для всех i ≥ I и k ≥ 0
справедливо, что xi = xi+k•∆.
Пусть i
будет наименьшим кратным ∆, которое также больше или равно I. Мы имеем i < J,
так как последовательность значений ∆ I, I + 1, . . . I + (∆ − 1) = J − 1 содержит крат-
ное ∆. Так как i ≥ I и 2i − i = i - это кратное ∆, следует, из этого следует, что xi = x2i.
Таким образом, если имеет место повторяющееся значение в последователь-
ности x1, . . . , xq , тогда имеет место i < q , для которого xi = x2i. Но затем в
итерации i нашего алгоритма мы имеем x = xr , и алгоритм выходит из перво-
го круга. В этой точке алгоритма мы знаем, что xi = xi+i.
Затем алгоритм
устанавливает xr := x(= xi) и x := x0, и продолжает искать наименьшее j ≥ 0, для
которого xj = xj+i. (Обратите внимание, что j ƒ= 0, потому что |x0| = A + 1.) Он
выводит xj−1 , xj+i−1 в качестве коллизии.
Нахождение значимых коллизий. Алгоритм, описанный выше,
Тем не ме-
нее, мы покажем, что нахождение значимых коллизий возможно.
Трюк в том,
чтобы найти коллизию в правильной функции!
Предположим, как и ранее, что Алиса желает найти коллизию между сообще-
ниями двух различных «типов», то есть письмо, объясняющее, почему Алиса
была уволена, и преу величенное рекомендательное письмо, которые оба хэши-
руются до одного и того же значения. Затем Алиса пишет каждое сообщение так,
чтобы в них было A − 1 взаимозаменяемых слов; то есть имеет место 2A−1 со-
общений каждого типа. Определите «one-to-one» функцию g : {0, 1}A → {0, 1}*,
так что A входного элемента выбирает между сообщениями типа 0 или типа 1, а
бит i (для 1 ≤ i ≤ A − 1) выбирает между вариантами взаимозаменяемого слова i в
сообщениях соотвествующего типа.
Например, рассмотрите предложение:
0: Боб -
хороший/усердный и честный/добросовестный работник/сотруд-
ник. 1: Боб -
трудный/проблематичный и напрягающий/раздражающий ра-
ботник/сотрудник.
Определите функцию g, которая принимает 4-битный входной элемент, где
последний бит определяет тип выходного предложения, а начальные три бита
определяют выбор слов в предложении. Например:
g(0000) = Боб - хороший и честный работник.
g(0001) = Боб - трудный и напрягающий работник.
g(1010) = Боб - усердный и честный сотрудник.
g(1011) = Боб проблематичный и напрягающий сотрудник.
Теперь определите f:{0, 1}A→{0, 1}A по f (x) H(g(x)). Алиса может найти кол-
лизию в f , используя атаку «дней рождения» малого пространства, показанную ранее.
Суть в том, что
любая коллзия x, xr в f дает два сообщения g(x), g(xr), которые сталки-
185
ваются под H. Если x, xr является случайной коллизией, тогда мы прогнозируем, что с
вероятностью 1/2 сталкивающиеся сообщения g(x), g(xr) будут различных типов (так
как x и xr отличаются последним битом с такой вероятностью). Если сталкивающие-
ся
сообщения одинакового типа, процесс может быть повторен вновь с нуля.
Достарыңызбен бөлісу: