94
формально доказать это утверждение в Упражнении 3.14 .
В более общем плане, мы можем использовать эту идею для построения по-
точного шифра (Init, GetBits) который принимает синхропосылку IV . (См. Раз-
дел 3.3.1) Единственное отличие состоит в том, что вместо вычисления Fs на
фиксированной последовательности входных данных 1, 2, 3, . . ., мы вычисляем
F на данных IV + 1, IV + 2, . . . .
КОНСТРУКЦИЯ 3.29
Пусть F - псевдослучайная функция. Определим поточный шифр (Init,
GetBits) где каждых
вызов GetBits выдает n битов, следующим образом:
• Init на входе s∈{0,1}n и IV∈ {0,1}n так st0 := (s, IV ).
• GetBits: на входе sti=(s, IV ) на выходе IVr=IV+1и y:= Fs(IV r) и sti+1 := (s,
IV r). Вывести (y, sti+1). так st0 := (s, IV ).
Поточный шифр из любой псевдослучайной функции/блочного шифра.
Несмотря на то, что поточные шифры могут быть построены из блочных шифров,
специально созданные поточные шифры на практике обычно более эффективны,
особенно в условиях ограниченных ресурсов. С другой стороны, судя по всему, по-
точные шифры менее понятны (на практике), чем блочные шифры, и поэтому уве-
ренность в их безопасности меньше. Поэтому, рекомендуется по мере возможности
использовать блочные шифры (возможно, сначала преобразовывая их в поточные).
Рассмотрим противоположное направление. псевдослучайный
генератор tt
незамедлительно выдает псевдослучайную функцию
F с малой длиной блока.
Более конкретно, предположим, что tt имеет коэффициент расширения n • 2t(n).
Мы можем дать определение функции с ключом F :{0, 1}n×{0, 1}t(n)→{0, 1}n
следующим образом: чтобы вычислить Fk (i), сначала вычислить tt(k) и пред-
ставить результат как таблицу с количеством строк 2t(n), каждая из которых со-
держит n битов; вывести i-ую строку. Вычисление происходит в полиномиаль-
ном времени, только если t(n) = O(log n). Также можно, хотя сложнее, построить
псевдослучайные функции с
большой блочной длиной из псевдослучайных ге-
нераторов; это показано в Разделе 7.5. псевдослучайные генераторы, в свою
очередь, могут быть построены на основе определенных предположительно
сложных математических задач. Существование
псевдослучайных функций,
основанных на таких сложных математических задачах, представляют одно из
поразительных достижений современной криптографии.
Достарыңызбен бөлісу: