Построение (строгой) псевдослучайной перестановки

295
даже когда оппоненту предоставлен доступ к прогнозу, как для самой переста-
новки, так и для ее инверсии
Еще раз о сетях Фейстеля. Сеть Фейстеля, представленная в разделе 6.2.2, 
обеспечивает способ построения обратимой функции из произвольного мно-
жества функций. Сеть Фейстеля работает в серии раундов. Входные данные 
для i-го раунда, представляют собой строку длиной 2n, разделенную на две 
n-битных половины Li−1 и Ri−1 («левая половина» и «правая половина», соот-
ветственно). Выход i-го раунда – 2n-битная строка (Li, Ri), где
Li := Ri−1 и Ri := Li−1 ⊕ fi(Ri−1)
для некоторой вычисляемой (но не обязательно обратимой) функции, fi, отобра-
жающей n-битные входы на n-битные выходы. Обозначим через Feistelf1 ,...,fr r-й 
раунд сети Фейстеля, используя функции f1, . . . , fr. (То есть, Feistelf1 ,...,fr (L0, R0) 
выводит 2n-битную строку (Lr, Rr)). В разделе 6.2.2 мы видели, что Feistelf1 ,...,fr 
является эффективной обратимой перестановкой независимо от {fi}.
Можно определить ключевую перестановку с использованием сети Фейстеля, 
в которой {fi} зависит от ключа. Например, пусть F : {0, 1}n × {0, 1}n → {0, 1}
n – псевдослучайная функция, тогда определим ключевую перестановку F(1) как
Fk(1) (x) = FeistelFk (x).
(Обратите внимание, F (1) имеет n-битный ключ и отображает 2n-битные 
входы на 2n-битные выходы). Является ли F (1) псевдослучайной? Небольшое 
размышление показывает, что это явно не так. Для любого ключа k∈{0, 1}n 
первые n битов выхода Fk(1) (то есть, L1) равны последним n битам входа (т.е., 
R0), это то, что происходит только при пренебрежимо малой вероятности для 
случайной функции.
Попытаемся еще раз, определим F : {0, 1}2n × {0, 1}2n → {0, 1}2n следую-
щим образом:
Fk1k2(2) (x) FeistelFk1k2 (x). 
(7.15)
(Заметим, что k1 и k2 являются независимыми ключами). К сожалению, F (2) – не 
псевдослучайная в любом случае, как вас просили показать в упражнении 7.16.
С учетом этого, может быть несколько удивительным то, что трехраундовая сеть Фей-
стеля является псевдослучайной. Определим ключевую перестановку F (3), взяв ключ 
длиной 3n и отобразив 2n-битные входы на 2n-битные выходы, следующим образом:
Fk1k2k3(3) (x) FeistelFk1k2k3 (x)
где еще раз, k1, k2 и k3 – независимые. Имеем:
ТЕОРЕМА 7.23Если F является псевдослучайной функцией, то F (3) являет-
ся псевдослучайной перестановкой.

296

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

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