Rambler's Top100 Service
Поиск   
 
Обратите внимание!   Обратите внимание!
 
  Наука >> Математика >> Алгебра, математическая логика и теория чисел | Книги
 Написать комментарий  Добавить новое сообщение
Next: 2.5. Доказательства с нулевым Up: 2. Криптография и теория Previous: 2.3. Односторонние функции Contents: Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\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$) определяется случайным выбором секретного ключа $ K$, случайным выбором открытого текста $ m$ из множества всех двоичных строк длины $ q(n)$ и случайными величинами, которые $ A$ использует в своей работе.

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

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

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


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


Написать комментарий
 Copyright © 2000-2015, РОО "Мир Науки и Культуры". ISSN 1684-9876 Rambler's Top100 Яндекс цитирования