Равномерно распределённая случайная последовательность и её свойства

Случайные числа и их генераторы являются неотъемлемыми современных криптосистем. Приведём конкретные примеры использования случайных чисел в криптологии:

1). Сеансовые и другие ключи для симметрических криптосистем, таких как DES, ГОСТ 28 147-89, Blowfish;

2). Стартовые значения для программ генерации ряда математических величин в асимметрических криптосистемах, например, “больших простых чисел” в криптосистемах RSA, ElGamal;

3). Случайные слова, комбинируемые с парольными для нарушения “атаки угадывания” пароля криптоаналитика;

4). Вектор инициализации для блочных криптосистем, работающих в режиме обратной связи;

5). Случайные значения параметров для многих систем электронной цифровой, например DSA;

6). Случайные выборы в протоколах аутенфинации, например в протоколе Цербер (Kerberos);

7). Случайные параметры протоколов для обеспечения уникальности различных реализаций одного и того же протокола, например в протоколах SET и SSL.

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

Известно, что проблема генерации случайной последовательности с произвольным законом распределения вероятностей сводится к проблеме генерации так называемой равномерно распределённой случайной последовательности (РРСП), или, как её часто называют в криптографических приложениях, “число случайной” последовательности.

РРСП – случайная последовательность  со значениями в дискретном множестве , определённая на вероятностном пространстве  и удовлетворяющая двум свойствам -  и .

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

Свойство . Для любого номера  случайная величина  имеет дискретное равномерное на  распределении вероятностей:

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

Свойство . Если  – РРСП, то для любого  и любой фиксированной последовательности индексов –мерное дискретное распределение вероятностей вектора (слова)  является равномерным:

Свойство . Если  – элемент РРСП, то  справедливы следующие выражения его начального и центрального моментов – го порядка:

Где  – числа Бернулли.

Свойство . Для новариационной функции и спектральной плотности РРСП  справедливы следующие выражения:

Свойство . (воспроизводимость при прореживании). Для любой фиксированной последовательности моментов времени  при “прореживании” РРСП  возникает последовательность

,

которая тоже является РРСП.

Свойство . (воспроизводимость при суммировании). Если - РРСП, а – произвольная неслучайная либо случайная последовательность, не зависящая от , то случайная последовательность  также является РРСП.

Свойство . Если  - РРСП, то  количество информации по Шеннону, содержащейся в отрезке последовательности , о будущем элементе  равно нулю:

,

поэтому для любого алгоритма прогнозирования  вероятность ошибки не может быть меньше, чем для “угадывания по жребию”:

.

Свойство . Если  - РРСП, то для любого  и произвольной борелевской функции  переменных , при  имеет место сходимость “почти наверное”:

Свойство . Если  – равномерно распределенная последовательность порядка , то  – РРСП.

С учетом свойств  определим понятия генератора случайной последовательности и его типов.

Генератор РРСП – устройство, позволяющее по запросу получить реализацию равномерно распределенной случайной последовательности  длиной ; элементы  этой реализации принято называть случайными числами. Существует три типа генераторов РРСП:

1. Табличный.

2. Физический.

3. Программный.

В следующем разделе мы рассмотрим программный генератор.

Программный генератор РРСП – программа имитации на компьютере реализации РРСП. Имитируемая последовательность  называется псевдослучайной, так как она вычисляется на компьютере по известному детерминированному (обычно рекуррентному) соотношению, и в то же время её статические свойства “близкие” к свойствам РРСП.

В разделе “Алгоритмы генерации псевдослучайных последовательностей” мы познакомимся с основными методами генерации псевдослучайных последовательностей, а в разделе “Методы генерации истинно случайных последовательностей” мы рассмотрим различные методы повышения “случайности” генераторов РРСП.