Генераторы случайных чисел

Часто используемые параметры 

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

Младшие двоичные разряды  сгенерированных таким образом  случайных чисел демонстрируют  поведение, далёкое от случайного, поэтому рекомендуется использовать только старшие разряды. Кроме того, при использовании этого генератора для выбора точек в d-мерном пространстве, точки ложатся не более, чем на   гиперплоскостей, что ограничивает применение генератора в методе Монте-Карло.

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

 

 

 

 

 

 

 

Source	m	a	c	выдаваемые биты результата в rand() /  Random(L)
Numerical Recipes (англ.)	232	1664525	1013904223
MMIX Д. Кнута	264	6364136223846793005	1442695040888963407
Borland C/C++	232	22695477	1	биты 30..16 в rand(), 30..0 в lrand()
GNU Compiler Collection	232	69069	5	биты 30..16
ANSI C: Open Watcom, Digital Mars, Metrowerks, IBM VisualAge C/C++	232	1103515245	12345	биты 30..16
Borland Delphi, Virtual Pascal	232	134775813	1	биты 63..32 числа (seed * L)
Microsoft Visual/Quick C/C++	232	214013	2531011	биты 30..16
Apple CarbonLib	231 - 1	16807	0	см. Метод Лемера (англ.)

 

Крипто анализ 

Особенностью линейного  конгруэнтного метода является то, что если сомножитель и модуль соответствующим образом подобраны, то результирующая последовательность чисел будет статистически неотличима от случайной последовательности элементов  множества { 0, 1, 2, …, m-1 }. Однако, все элементы этой последовательности однозначно определяются четырьмя параметрами: X₀, a, c, m.

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

из которой можно получить значения параметров а, с и m.

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

Метод Фибоначчи с  запаздываниями

 

Метод Фибоначчи с запаздываниями (Lagged Fibonacci generator) — один из методов генерации псевдослучайных чисел.

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

В связи с этим линейный конгруэнтный алгоритм постепенно потерял свою популярность и его место заняло семейство фибоначчиевых алгоритмов, которые могут быть рекомендованы для использования в алгоритмах, критичных к качеству случайных чисел. В англоязычной литературе фибоначчиевы датчики такого типа называют обычно «Subtract-with-borrow Generators» (SWBG).

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

Формулы 

Один из широко распространённых фибоначчиевых датчиков основан на следующей итеративной формуле:

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

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

,

где   — число битов в мантиссе вещественного числа.

Выбор параметров 

Лаги a и b — «магические» и их не следует выбирать произвольно. Рекомендуются  следующие значения лагов:  ,   или  . Качество получаемых случайных чисел зависит от значения константы, a чем оно больше, тем выше размерность пространства, в котором сохраняется равномерность случайных векторов, образованных из полученных случайных чисел. В то же время, с увеличением величины константы a увеличивается объём используемой алгоритмом памяти.

Значения   можно рекомендовать для простых приложений, не использующих векторы высокой размерности со случайными компонентами. Значения   позволяют получать числа, удовлетворительные для большинства алгоритмов, требовательных к качеству случайных чисел. Значения  позволяют получать очень качественные случайные числа и используются в алгоритмах, работающих со случайными векторами высокой размерности. Описанный фибоначчиев датчик случайных чисел (с лагами 20 и 5) используется в широко известной системе Matlab (автором первой версии этой системы был Д. Каханер).

 

ГПСЧ  с источником энтропии или ГСЧ 

 

Наравне с существующей необходимостью генерировать легко воспроизводимые  последовательности случайных чисел, также существует необходимость  генерировать совершенно непредсказуемые  или попросту абсолютно случайные  числа. Такие генераторы называются генераторами случайных чисел (ГСЧ — англ. random number generator, RNG). Так как такие генераторы чаще всего применяются для генерации уникальных симметричных и асимметричных ключей для шифрования, они чаще всего строятся из комбинации крипто стойкого ГПСЧ и внешнего источника энтропии (и именно такую комбинацию теперь и принято понимать под ГСЧ).

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

В современных исследованиях  осуществляются попытки использования  измерения физических свойств объектов (например, температуры) или даже квантовых флуктуаций вакуума в качестве источника энтропии для ГСЧ.

В персональных компьютерах  авторы программных ГСЧ используют гораздо более быстрые источники  энтропии, такие, как шум звуковой карты или счётчик тактов процессора. Сбор энтропии являлся наиболее уязвимым местом ГСЧ. Эта проблема до сих пор полностью не разрешена во многих устройствах (например, смарт-картах), которые таким образом остаются уязвимыми. Многие ГСЧ используют традиционные испытанные, хотя и медленные, методы сбора энтропии вроде измерения реакции пользователя (движение мыши и т. п.), как, например, в PGP и Yarrow, или взаимодействия между потоками, как, например, в Java SecureRandom.

 

Пример простейшего  ГСЧ с источником энтропии 

 

Если в качестве источника  энтропии использовать текущее время, то для получения натурального числа от 0 до N достаточно вычислить остаток от деления текущего времени в миллисекундах на число N+1. Недостатком этого ГСЧ является то, что в течение одной миллисекунды он выдает одно и то же число.

 

Примеры ГСЧ  и источников энтропии

 

	Источник энтропии	ГПСЧ	Достоинства	Недостатки
/dev/random вUNIX/ Linux	Счётчик тактов процессора, однако собирается только во время аппаратных прерываний	LFSR, с хешированием выхода через SHA-1	Есть во всех Unix, надёжный источник энтропии	Очень долго «нагревается», может надолго «застревать», либо работает как ГПСЧ (/dev/urandom)
Yarrow отБрюса Шнайера[4]	Традиционные методы	AES-256 и  SHA-1 маленького внутреннего состояния	Гибкий крипто стойкий дизайн	Медленный
MicrosoftCryptoAPI	Текущее время, размер жёсткого диска, размер свободной памяти, номер  процесса и NETBIOS-имя компьютера	MD5-хеш внутреннего состояния размером в 128 бит	Встроен в Windows, не «застревает»	Сильно зависит от используемого  криптопровайдера (CSP).
JavaSecureRandom	Взаимодействие между  потоками	SHA-1-хеш внутреннего состояния (1024 бит)	Большое внутреннее состояние	Медленный сбор энтропии
Chaos от Ruptor	Счётчик тактов процессора, собирается непрерывно	Хеширование 4096-битового внутреннего  состояния на основе нелинейного  варианта Marsaglia-генератора	Пока самый быстрый  из всех, большое внутреннее состояние, не «застревает»	Оригинальная разработка, свойства приведены только по утверждению  автора
RRAND от Ruptor[6]	Счётчик тактов процессора	Зашифровывание внутреннего  состояния поточным шифром EnRUPT в authenticated encryption режиме (aeRUPT)	Очень быстр, внутреннее состояние произвольного размера по выбору, не «застревает»	Оригинальная разработка, свойства приведены только по утверждению  автора. Шифр EnRUPT не является криптостойким.

 

 

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

 

Основная статья: Криптографически стойкий генератор псевдослучайных чисел

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

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

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

 

Примеры крипто стойких ГПСЧ 

Циклическое шифрование 

В данном случае используется способ генерации ключа сессии из мастер-ключа. Счетчик с периодом N используется в качестве входа в шифрующее устройство. Например, в случае использования 56-битного ключа DES может использоваться счетчик с периодом 256. После каждого созданного ключа значение счетчика повышается на 1. Таким образом, псевдослучайная последовательность, полученная по данной схеме, имеет полный период: каждое выходное значение Х0, Х1,…XN-1 основано на разных значениях счетчика, поэтому Х0 ≠ X1 ≠ XN-1. Так как мастер-ключ является секретным, легко показать, что любой секретный ключ не зависит от знания одного или более предыдущих секретных ключей.

 

ANSI X9.17 

ГПСЧ из стандарта ANSI X9.17 используется во многих приложениях финансовой безопасности и PGP. В основе этого ГПСЧ лежит тройной DES. Генератор ANSI X9.17 состоит из следующих частей:

1. Вход: генератором управляют два псевдослучайных входа. Один является 64-битным представлением текущих даты и времени, которые меняются каждый раз при создании числа. Другой является 64-битным исходным значением. Оно инициализируется некоторым произвольным значением и изменяется в ходе генерации последовательности псевдослучайных чисел.
2. Ключи: генератор использует три модуля тройного DES. Все три используют одну и ту же пару 56-битных ключей, которая держится в секрете и применяется только при генерации псевдослучайного числа.
3. Выход: выход состоит из 64-битного псевдослучайного числа и 64-битного значения, которое будет использоваться в качестве начального значения при создании следующего числа.

• DTi — значение даты и времени на начало i-ой стадии генерации.

• Vi — начальное значение для i-ой стадии генерации.
• Ri — псевдослучайное число, созданное на i-ой стадии генерации.
• K1, K2 — ключи, используемые на каждой стадии.