Введение в современную криптографию
РИС. 7.3: Трехраундовая сеть Фейстеля, используемая для построения псев- дослучайной перестановки из псевдослучайной функции. ДОКАЗАТЕЛЬСТВО
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| РИС. 7.3: Трехраундовая сеть Фейстеля, используемая для построения псев-
дослучайной перестановки из псевдослучайной функции. ДОКАЗАТЕЛЬСТВО В стандартном способе мы можем заменить псевдос- лучайные функции, используемые при построении F (3), функциями, выбран- ными равномерно наугад. Псевдослучайность F предполагает, что функция имеет лишь пренебрежимо малое влияние на выход любого вероятностного полиномиально-временного отличительного признака, взаимодействующего с F (3) в качестве прогноза. Оставляем детали в качестве упражнения. Пусть D – вероятностный полиномиально-временной отличительный признак. В оставшейся части доказательства покажем, что следующее пренебрежимо мало: где первая вероятность берется по равномерному и независимому выбору f1, f2, f3 из Funcn, а вторая вероятность берется по равномерному выбору π из Perm2n. Зафиксируем некоторое значение для параметра безопасности n, и пусть q = q(n) обозначает полином верхней границы количества запросов прогноза, сделанных D. Без потери общности, предположим, что D никогда не делает один и тот же за- прос прогноза дважды. Сосредоточив внимание на взаимодействии D с Feistelf1 ,f2,f3 (•), допустим, что (Li0 , Ri0 ) обозначает i-й запрос, который D делает по своему прогнозу, и допустим, что (Li3 , Ri3 ), (Li1 , Ri1 ), и (Li2 , Ri2 ) обозначает промежуточные значения после раундов 1, 2 и 3, соответственно, являющиеся ре- зультатом этого запроса. (См. рис. 7.3). Обратите внимание, что D выбирает (Li0 , Ri0 )и видит результат Li3 , Ri3 ), но прямо не видит (Li1 , Ri1 ) или (Li2 , Ri2). Мы говорим, что имеется коллизия при R1, если Ri1 = Rj1 для некоторого отдельного i, j. Сначала докажем, что коллизия при R1 возникает лишь с прене- брежимо малой вероятностью. Рассмотрим любое фиксированное, отдельное i, j. Если Ri1 = Rj1, то Li0 ƒ= Lj0 , но тогда 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. |