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) являет-
ся псевдослучайной перестановкой.