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

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 отличаются последним битом с такой вероятностью). Если сталкивающие-
ся сообщения одинакового типа, процесс может быть повторен вновь с нуля. 

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: