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

Существенный недостаток шифра Вернама состоит в том, что ключи одноразовые. Можно ли избавиться от этого недостатка за счет некоторого снижения стойкости? Один из способов решения этой проблемы состоит в следующем. Отправитель и получатель имеют общий секретный ключ К длины и с помощью некоторого достаточно эффективного алгоритма генерируют из него последовательность длины где некоторый полином. Такая криптосистема (обозначим ее ) позволяет шифровать сообщение (или совокупность сообщений) длиной до битов по формуле где поразрядное сложение битовых строк по модулю 2. Дешифрование выполняется по формуле Из результатов Шеннона вытекает, что такая криптосистема не является абсолютно стойкой, т. е. стойкой против любого противника (в чем, впрочем, нетрудно убедиться и непосредственно). Но что будет, если требуется защищаться только от полиномиально ограниченного противника, который может атаковать криптосистему лишь с помощью полиномиальных вероятностных алгоритмов? Каким условиям должны удовлетворять последовательность и алгоритм чтобы криптосистема была стойкой? Поиски ответов на эти вопросы привели к появлению понятия псевдослучайного генератора, которое было введено Блюмом и Микали [3].

Пусть функция, вычислимая за полиномиальное (от время. Такая функция называется генератором. Интуитивно, генератор является псевдослучайным, если порождаемые им последовательности неотличимы никаким полиномиальным вероятностным алгоритмом от случайных последовательностей той же длины Формально этот объект определяется следующим образом.

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

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

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

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

Всюду ниже мы для краткости будем называть криптографически стойкие псевдослучайные генераторы просто псевдослучайными генераторами. Такое сокращение является общепринятым в криптографической литературе.

Нетрудно убедиться, что для существования псевдослучайных генераторов необходимо существование односторонних функций. В самом деле, сама функция должна быть односторонней. Доказательство этого простого факта мы оставляем читателю в качестве упражнения. Вопрос о том, является ли существование односторонних функций одновременно и достаточным условием, долгое время оставался открытым. В 1982 г. Яо [10] построил псевдослучайный генератор, исходя из предположения о существовании односторонних перестановок, т. е. сохраняющих длину взаимнооднозначных односторонних функций. За этим последовала серия работ, в которых достаточное условие все более и более ослаблялось, пока наконец в 1989-1990 гг. Импальяццо, Левин и Луби [8] и Хостад [6] не получили следующий окончательный результат.

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

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

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

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

Определение 3. Криптосистема называется стойкой, если для любой полиномиальной вероятностной машины Тьюринга А, для любого полинома и всех достаточно больших

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

Покажем, что криптосистема с псевдослучайным генератором в качестве является стойкой в смысле данного определения. Предположим противное, т. е. что существуют полиномиальный вероятностный алгоритм А и полином такие, что для бесконечно многих Рассмотрим алгоритм В, который получает на входе двоичную строку длины выбирает вычисляет и вызывает А как подпрограмму, подавая ей на вход строку Получив от А пару проверяет, действительно ли и если да, то выдает 1, в противном случае — 0, и останавливается. Легко видеть, что В работает за полиномиальное (от время. Убедимся, что алгоритм В отличает псевдослучайные строки, порожденные генераторов от случайных строк длины . В самом деле, если строки поступающие на вход В, являются случайными, то криптограмма шифра Вернама и, согласно теореме Шеннона, Если строки порождены генератором то криптограммы имеют такое же распределение вероятностей, как в криптосистеме согласно предположению, для бесконечно многих Полученное противоречие с определением псевдослучайного генератора доказывает утверждение о стойкости криптосистемы

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

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

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