Схемы построения псевдослучайных генераторов

Описание псевдослучайного генератора

Пусть g:{0; 1}" —* {0; 1}" — функция, вычислимая за полиномиальное (от п) время. Такая функция называется генератором. Интуитивно генератор является псевдослучайным, если порождаемые им последовательности неотличимы никаким полиномиальным вероятностным алгоритмом от случайных последовательностей той же длины q{n). Формально псевдослучайный генератор определяется следующим образом.

Пусть А — полиномиальная вероятностная машина Тьюринга, которая получает на входе двоичные строки длины с/(п) и выдает в результате своей работы 1 бит. Пусть.

Вероятность здесь определяется случайным выбором строки г и случайными величинами, которые А использует в своей работе. Пусть.

Эта вероятность определяется случайным выбором строки s и случайными величинами, которые Л использует в своей работе. Подчеркнем, что функция g вычисляется детерминированным алгоритмом.

Генератор g называется криптографически стойким псевдослучайным генератором, если для любой полиномиальной вероятностной машины Тьюринга Л, для любого полинома р и всех достаточно больших п Р₁(А, п) — Р₂(А, п) | < 1 /р (п).

Для размышления Нетрудно убедиться, что для существования псевдослучайных генераторов необходимо существование однонаправленных функций.

но определяется x_j+] = xf (mod n) и пусть b_i — наименьший значащий бит х_г Для любого целого ?, первые t битов генерируются из короткого первоначального значения (действительно случайного) х₀ и, таким образом, определяется псевдослучайная последовательность ЧСГ_{Я t}(x₀) b₀b_lb₂—b_t_ _t.