297
Если R0i ƒ= R0i, то f1(R0i ) и f1(R0i ) являются равномерными и независимы-
ми, таким образом,
Учет границы объединения по всем отдельным i, j показывает, что вероятность
коллизии при R1 не более q2/2n.
Скажем, существует коллизия при R2, если R2i = R2i для некоторого отдель-
ного i, j. Докажем, что обусловленная отсутствием коллизии при R1, вероят-
ность коллизии при R2 пренебрежимо мала.
Проведем анализ, как указано
выше: рассмотрим любое фиксированное i, j и отметим, что если отсутствует
коллизия при R1, то R1i ƒ=R1i . Таким образом, f2(R1i ) и f2(R1i ) являются
равномерными и независимыми, и
поэтому
(Обратите внимание, что f2 независимо от f1, что облегчает указанное выше
вычисление). Учет границы объединения по всем отдельным i,
j дает
Pr[коллизии при R2 | отсутствие коллизии при R1] ≤ q2/2n.
Обратите внимание, что L3i=R2i=L1i ⊕f2(R1i); таким образом, обусловлено отсут-
ствие какой-либо коллизии при R1, все значения L1, . . . , Lq независимы и равно-
мерно распределены в {0, 1}n. Если дополнительно выдвинуть условие для события
отсутствия коллизии при R2, то значения L1, . . . , Lq равномерно распределены среди
всех последовательностей q различных значений в {0, 1}n. Аналогично, Ri = Li ⊕
f3(Ri ); таким образом, обусловлено отсутствие коллизии при R2, все значения R1, . .
. , Rq равномерно распределены в {0, 1}n, а также независимы друг от друга L1, . . . , Lq
. Подведем итог: при запросе F (3) (с равномерными раундовыми функциями) на се-
рии q различных входов, кроме как с пренебрежимо малой вероятностью, выходные
значения (L1, R1), . . . , (Lq, Rq ) распределены так, что {Li } являются равномерными
и независимыми, но различными, n-битными значениями, и {Ri } являются равно-
мерными и независимыми n-битными значениями. В противоположность этому, при
запросе случайной перестановки на серии q различных входов,
выходные значения
(L1, R1), . . . , (Lq, Rq ) равномерные и независимые, но различные 2n-битные значе-
ния. Лучшая отличительная атака для D, состоит в том, чтобы догадаться, что он вза-
имодействует со случайной перестановкой, если Li= Lj для некоторого отдельного i,
j. Но данное событие возникает с пренебрежимо малой вероятностью, в этом случае.
Это можно превратить в формальное доказательство.
F(3) не является строгой псевдослучайной перестановкой, что будет пред-
ложено вам продемонстрировать в упражнении 7.17. К счастью, добавление
четвертого раунда дает в результате, строгую псевдослучайную перестановку.
Детали приведены в виде конструкции 7.24.