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

Next: 2.5. Доказательства с нулевым Up: 2. Криптография и теория Previous: 2.3. Односторонние функции Contents: Содержание

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

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

Пусть $g\colon\{ 0,1\} ^n\to \{ 0,1\} ^{q(n)}$ - функция, вычислимая за полиномиальное (от ) время. Такая функция называется генератором. Интуитивно, генератор является псевдослучайным, если порождаемые им последовательности неотличимы никаким полиномиальным вероятностным алгоритмом от случайных последовательностей той же длины . Формально этот объект определяется следующим образом.

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

$\begin{displaymath}P_1(A,n)=Pr\{ A(r)=1\mid r\in _R\{ 0,1\} ^{q(n)}\}.\end{displaymath}$

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

и случайными величинами, которые

использует в своей работе. Пусть

$\begin{displaymath}P_2(A,n)=Pr\{ A(g(s))=1\mid s\in _R\{ 0,1\} ^n\}.\end{displaymath}$

Эта вероятность определяется случайным выбором строки

и случайными величинами, которые

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

вычисляется детерминированным алгоритмом.

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

$\begin{displaymath}\vert P_1(A,n)-P_2(A,n)\vert<1/p(n).\end{displaymath}$

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

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

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

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

Пусть - алгоритм шифрования криптосистемы с секретным ключом. Обозначим результат его работы , здесь - секретный ключ длиной битов, а - открытый текст длиной битов. Через обозначается -ый бит открытого текста. Пусть - полиномиальная вероятностная машина Тьюринга, которая получает на вход криптограмму и выдает пару $(i,\sigma )$ , где $i\in \{ 1,\dots ,q(n)\}$ , $\sigma \in \{ 0,1\}$ . Интуитивно, криптосистема является стойкой, если никакая машина Тьюринга не может вычислить ни один бит открытого текста с вероятностью успеха, существенно большей, чем при простом угадывании.

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

$\begin{displaymath} Pr\{ A(d)=(i,\sigma )\mathrel{\&} \sigma=m_i \mathrel{\big\v... ...{ 0,1\} ^n, m\in _R\{ 0,1\} ^{q(n)}\} <\frac12+\frac1{p(n)}. \end{displaymath}$

Эта вероятность (всюду ниже для краткости мы ее обозначаем просто

) определяется случайным выбором секретного ключа

, случайным выбором открытого текста

из множества всех двоичных строк длины

и случайными величинами, которые

использует в своей работе.

Покажем, что криптосистема с псевдослучайным генератором в качестве является стойкой в смысле данного определения. Предположим противное, т.е. что существуют полиномиальный вероятностный алгоритм и полином такие, что $Pr\geq 1/2+1/p(n)$ для бесконечно многих . Рассмотрим алгоритм , который получает на входе двоичную строку длины , выбирает $m\in _R \{ 0,1\} ^{q(n)}$ , вычисляет $d=m\oplus r$ и вызывает как подпрограмму, подавая ей на вход строку . Получив от пару $(i,\sigma )$ , проверяет, действительно ли $m_i=\sigma$ и если да, то выдает 1, в противном случае - 0, и останавливается. Легко видеть, что работает за полиномиальное (от ) время. Убедимся, что алгоритм отличает псевдослучайные строки, порожденные генератором , от случайных строк длины . В самом деле, если строки , поступающие на вход , являются случайными, то - криптограмма шифра Вернама и, согласно теореме Шеннона, . Если строки порождены генератором , то криптограммы имеют такое же распределение вероятностей, как в криптосистеме , и, согласно предположению, $Pr\geq 1/2+1/p(n)$ для бесконечно многих . Полученное противоречие с определением псевдослучайного генератора доказывает утверждение о стойкости криптосистемы .

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

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