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

Тема 5

Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandomnumbergenerator, PRNG) — алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).

Современная информатика широко использует псевдослучайные числа в самых разных приложениях — от метода Монте-Карло и имитационного моделирования до криптографии. При этом от качества используемых ГПСЧ напрямую зависит качество получаемых результатов. Это обстоятельство подчёркивает известный афоризм математика ORNL Роберта Кавью.

ГПСЧ в криптографии.

Разновидностью ГПСЧ являются ГПСБ (PRBG) — генераторы псевдослучайных бит, а также различных поточных шифров. ГПСЧ, как и поточные шифры, состоят из внутреннего состояния (обычно размером от 16 бит до нескольких мегабайт), функции инициализации внутреннего состояния ключом или зерном (англ. seed), функции обновления внутреннего состояния и функции вывода. ГПСЧ подразделяются на простые арифметические, сломанные криптографические и криптостойкие. Их общее предназначение — генерация последовательностей чисел, которые невозможно отличить от случайных вычислительными методами.

Хотя многие криптостойкие ГПСЧ или поточные шифры предлагают гораздо более «случайные» числа, такие генераторы гораздо медленнее обычных арифметических и могут быть непригодны во всякого рода исследованиях, требующих, чтобы процессор был свободен для более полезных вычислений.

В военных целях и в полевых условиях применяются только засекреченные синхронные криптостойкие ГПСЧ (поточные шифры), блочные шифры не используются. Примерами известных криптостойких ГПСЧ являются RC4, ISAAC, SEAL, Snow, совсем медленный теоретический алгоритм Блюм — Блюма — Шуба, а также счётчики с криптографическими хеш-функциями или криптостойкими блочными шифрами вместо функции вывода.

Протокол привязки к биту

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

1. Получатель до этапа раскрытия не может узнать по блобу значение передаваемого бита. Это условие называется условием конфиденциальности.

2. Отправитель на этапе раскрытия не может успешно доказать отправителю, что один и тот же блоб соответствует как 0, так и 1. Другими словами, отправитель не может раскрыть один и тот же блоб как в 0, так и в 1. Это условие называется условием однозначности.

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

Параметр полиномиальный

Функция k:N→N называется полиномиальным параметром, если функция

1ⁿ↦1^k(n) (n∈N) полиномиально вычислима. Это условие выполнено тогда и только тогда, когда функция k полиномиально ограничена (т. е. существует полином p такой, что k(n)⩽p(n) для всех n∈N) и вычислима детерминированным алгоритмом за полиномиальное от n время.

Односторонняя функция (англ. one-wayfunction, OWF) это функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений. Неинъективность функции не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться также трудно обратимыми или необратимыми.

Существование односторонних функций до сих пор не доказано. Их существование докажет, что классы сложности P и NP не равны, попутно разрешив ряд вопросов теоретической информатики. Современная асимметричная криптография основывается на предположении, что односторонние функции все-таки существуют.

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

Определение:

Функция f: {0, 1}* → {0, 1}* является односторонней функцией, если она эффективно вычисляется за полиномиальное время на детерминированной машине Тьюринга, но не существует полиномиальной вероятностной машины Тьюринга, которая обращает эту функцию с более чем экспоненциально малой вероятностью.

Односторонние функции в криптографических системах:

Существование односторонних функций является необходимым условием для стойкости многих типов криптографических схем. В некоторых случаях этот факт устанавливается достаточно просто. Рассмотрим функцию f такую, что f(r) = K₁. Она вычислима с помощью алгоритма G за полиномиальное время. Покажем, что если f не односторонняя функция, то криптосистема нестойкая. Предположим, что существует полиномиальный вероятностный алгоритм A, который инвертирует f с вероятностью по крайней мере 1/p(n) для некоторого полинома p. Здесь n — длина ключа K₁. Атакующий может подать на вход алгоритму A ключ K₁ и получить с указанной вероятностью некоторое значение r' из прообраза. Далее злоумышленник подает r' на вход алгоритма G и получает пару ключей (K₁, K₁). Хотя K'₂ не обязательно совпадает с K₂, тем не менее, по определению криптосистемы D_K’2(E_K1(m))= m для любого открытого текста m. Поскольку K'₂ найден с вероятностью по крайней мере 1/p(n), которая в криптографии не считается пренебрежимо малой, криптосистема нестойкая.

Из всего сказанного следует, что предположение о существовании односторонних функций является самым слабым криптографическим предположением, которое может оказаться достаточным для доказательства существования стойких криптографических схем различных типов. На выяснение того, является ли это условие и в самом деле достаточным, направлены значительные усилия специалистов. Трудность задачи построения криптографических схем из односторонних функций можно пояснить на следующем примере. Пусть f — односторонняя функция и нам требуется построить криптосистему с секретным ключом. В такой криптосистеме имеется только один ключ — секретный, который известен и отправителю, и получателю шифрованного сообщения. Алгоритмы шифрования E_K и дешифрования D_K оба зависят от этого секретного ключа K и таковы, что D_K(E_K(m))= m для любого открытого текста m. Ясно, что если криптограмму d сообщения m вычислять как d=f(m), то противник, перехвативший d, может вычислить m лишь с пренебрежимо малой вероятностью. Но во-первых, непонятно, каким образом сможет восстановить сообщение m из криптограммы законный получатель? Во-вторых, из того, что функция f односторонняя следует лишь, что противник не может вычислить все сообщение целиком. А это — весьма низкий уровень стойкости. Желательно, чтобы противник, знающий криптограмму d, не мог вычислить ни одного бита открытого текста.

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

Односторонняя функция f:{0,1}∗→{0,1}∗ называется односторонней перестановкой, если она биективна и сохраняет длину. В очень редких случаях под односторонней перестановкой понимают произвольную биективную одностороннюю функцию.

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

Говоря неформально, псевдослучайный генератор — это полиномиально вычислимая регулярная по длине функция g:{0,1}∗→{0,1}∗, увеличивающая длину входа и создающая на выходе распределение вероятностей, вычислительно неотличимое от равномерного распределения на множестве всех двоичных строк соответствующей длины. Применения псевдослучайных генераторов в математической криптографии многочисленны и разнообразны. В частности, псевдослучайный генератор используется в конструкции генератора псевдослучайных функций. Псевдослучайные генераторы позволяют уменьшить число случайных битов, необходимых для вероятностных алгоритмов.

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

Функция g:{0,1}∗→{0,1}∗, отображающая {0,1}n в {0,1}m(n) для всех n∈N, называется псевдослучайным генератором, если

1. g полиномиально вычислима;

2. функция m удовлетворяет неравенству m(n)>n для всех n∈N.

3. семейства случайных величин (g(u˜n)|n∈N) и (u˜m(n)|n∈N) вычислительно неотличимы;

Очевидно, что если не требовать выполнения условия 2 в этом определении, то понятие псевдослучайного генератора будет бессодержательным. Легко также видеть, что если функция g отображает {0,1}n в {0,1}m(n) для всех n∈N, причем выполнено условие 2 определения 1, то статистическое расстояние между случайными величинами g(u˜n) и u˜m(n) ограничивается снизу 1/2 и, следовательно, семейства случайных величин из условия 3 определения 1 не могут быть статистически неотличимыми.

Условие 3 определения 1 эквивалентно условию непредсказуемости следующего бита для семейства случайных величин (g(u˜n)|n∈N).

Если g — псевдослучайный генератор, отображающий {0,1}n в {0,1}m(n) при любом n∈N, то x↦g(x)[1,…,∣x∣+1] — псевдослучайный генератор, отображающий {0,1}n в {0,1}n+1 для всех n∈N. Обратно, пусть g — произвольная функция, отображающая {0,1}n в {0,1}n+1 при любом n∈N. Для произвольного i∈N определим функцию gi:{0,1}∗→{0,1}∗ (отображающую {0,1}n в {0,1}n+i при любом n∈N) индукцией по iследующим образом:

g0(x)=x,gi+1(x)=g(x)[1]gi(g(x)[2,…,∣x∣+1])(x∈{0,1}∗).

Тогда если g — псевдослучайный генератор и k — произвольный полиномиальный параметр, принимающий лишь положительные значения, то x↦gk(∣x∣)(x) — псевдослучайный генератор, отображающий {0,1}n в {0,1}n+k(n) для всех n∈N.

Предложение 2

Если существует какой либо псевдослучайный генератор, то для любого полиномиального параметра m, удовлетворяющего неравенству m(n)>n при любом n∈N, существует псевдослучайный генератор, отображающий {0,1}n в {0,1}m(n) для всех n∈N.

Теорема 3

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

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

Теорема 4

Если f:{0,1}∗→{0,1}∗ — односторонняя перестановка, а b — трудный предикат для f, то функция x↦f(x)b(x) (x∈{0,1}∗) является псевдослучайным генератором.

Для построения трудного предиката можно воспользоваться известной теоремой Гольдрайха”– Левина. Тогда получается, что если f:{0,1}∗→{0,1}∗ — односторонняя перестановка, то функция

(x,y)↦(f(x),y,⨁i=1nx[i]y[i])(x,y∈{0,1}n,n∈N).

Дата добавления: 2014-12-10