Раздел четырнадцатый

1. Псевдослучайные генераторы.

В практической криптографии потребность получения случайных последовательностей весьма велика. Они требуются для работы вероятностных алгоритмов и в некоторых других случаях. Напомним, что случайной последовательностью битов длины n называют случайную величину, которая принимает каждое значение из множества с вероятностью . Для малых n такую последовательность можно создать подкидыванием монеты. В случае же больших n эта задача может оказаться сложной и для ЭВМ.

Рассмотрим следующую задачу. Пусть имеется возможность генерировать случайную двоичную последовательность длины n. Спрашивается, можно ли ее расширить до случайной в определенном смысле последовательности длины , где d – константа? Сам термин «расширить» означает получить из имеющейся с помощью детерминированного алгоритма. Ясно, что в результате такого «расширения» нельзя получить истинно случайную последовательность длины . Однако хотелось бы получить хотя бы псевдослучайную последовательность длины , т.е. такую, которая бы походила на случайную.

Определение. Ансамблем называется последовательность случайных величин , , которые принимают значения во множестве двоичных слов.

Определение. Ансамбли и называются неразличимыми за полиномиальное время, если для любого полиномиального вероятностного алгоритма А выполняется

,

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

Определение. Пусть – функция такая, что . Генератором с расширением l называется полиномиальный детерминированный алгоритм G, который двоичную последовательность превращает в последовательность .

Из соображений технического удобства договоримся, что генератор G может давать отказ, и тогда G(x) может быть не определена.

Остается договориться, какой генератор заслуживает быть названным генератором псевдослучайных последовательностей. Здесь главной чертой такого генератора должно быть то, что случайную величину G(x), где случайное , никаким полиномиальным вероятностным алгоритмом нельзя отличить от случайной величины, равномерно распределенной на .

Определение. Пусть G – генератор с расширением l. Обозначим через случайную величину G(x) со значениями в для х, которое равномерно распределено на . Через обозначим случайную величину, равномерно распределенную на . Генератор G называется псевдослучайным, если ансамбли и неразличимы за полиномиальное время. Двоичную последовательность G(x), полученную с помощью псевдослучайного генератора G, называют псевдослучайной.

Интересно то, что расширение l не играет принципиальной роли как количественная характеристика генератора. Оказывается, как это видно из следующей теоремы, генератор с минимальным расширением можно превратить в генератор с произвольным расширением.

Теорема (Гольдрайх, Микели). Из произвольного псевдослучайного генератора G с расширением можно получить псевдослучайный генератор с расширением для произвольной целой константы d >1.

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

Теорема. Псевдослучайные генераторы существуют если и только если существуют односторонние функции.

2. Криптографические приложения.

В криптографии от псевдослучайных генераторов G требуется выполнение следующего условия. Пусть противник наблюдает случайную величину G(x), распределенную на и порожденную равномерным распределением х на . Допустим, что сначала ему открываются лишь первые i битов величины G(x). Тогда требуется, чтобы противник не мог предсказать i+1-й бит с вероятностью, существенно большей ½. Иными словами, криптограф заинтересован в том, чтобы не было лучшего пути получить i+1-й бит на основе знания предыдущих битов нежели простым угадыванием. Связь такого требования с криптографической стойкостью можно пояснить таким примером. Пусть противник перехватил шифртекст в двоичном алфавите, и ему известны следующие факты:

1. использован шифр одноразового блокнота;

2. ключом является псевдослучайная последовательность;

3. открытый текст начинается словами “Dear Sir!”.

Прибавив известный ему префикс открытого текста к соответствующему префиксу шифртекста, противник получает первые i битов псевдослучайного ключа. Если генератор, который был использован для выбора ключа, не обладает описанным выше свойством, то противник может экстраполировать следующие биты ключа и добыть из шифртекста еще больше информации.

Определение. Пусть для каждого натурального n случайная величина принимает значения в . Ансамбль называется непредсказуемым, или, как еще говорят, выдерживает тестирование следующего бита, если выполняется такое условие. Допустим, что – префикс случайного слова , где и , причем длина k этого префикса является случайным числом от 1 до n. Пусть А – произвольный полиномиальный вероятностный алгоритм, который получает на вход s. Тогда

для произвольного полинома р и достаточно больших n.

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

Теорема. Пусть – генератор с расширением l. Обозначим через случайную величину G(x) со значениями в для х, равномерно распределенного на . Генератор G является псевдослучайным тогда и только тогда, когда ансамбль непредсказуем.

На основании вышесказанного, псевдослучайные генераторы называют криптографически надежными.

3. Возвращение к односторонним функциям.

Как известно, функции RSA, SQUARE, EXP предполагаются односторонними. После фиксации соответствующих параметров эти функции становятся перестановками некоторого множества D. Имея ввиду эти примеры, рассмотрим эффективно вычислимое биективное отображение . Одновременно рассмотрим эффективно вычислимый предикат – для каждого легко можно вычислить бит . Пусть . Поскольку f – биекция, то однозначно определяется элементом y. Однако, это не означает, что имея y, легко получить . Если нет эффективного алгоритма, который бы для большинства элементов по заданному значению давал бы бит , то предикат В называется ядром функции f. Совершенно ясно, что если функция (биекция) имеет ядро, то она односторонняя. Действительно, если бы был эффективный алгоритм для вычисления , то можно было бы легко получить из у композицией алгоритмов для вычисления и В.

Дадим формальное определение этому понятию. Пусть – последовательность множеств, для которой .

Определение. Полиномиально вычислимый предикат В, называется ядром функции , если любой полиномиальный вероятностный алгоритм на входе f(x), где х – случайный элемент из , дает значение с вероятностью меньшей, чем для произвольного полинома р и достаточно большого n. Вероятность берется по случайному выбору х и по случайной последовательности вероятностного алгоритма.

По сути, определение говорит, что нет никакого лучшего способа получить по f(x), чем просто взять наугад случайный бит.

Для указанных выше функций предложены следующие предикаты: для функции с фиксированными параметрами e и m, а также для функции с фиксированным параметром m, B есть предикат четности, т.е. для нечетных n и только для них. Для функции с фиксированными параметрами p и g предикат B задается соотношением