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

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

История

Первые попытки создания механических устройств для генерации случайных чисел относятся к началу XX века. В 1927 году британский статистик Леонард Типпет опубликовал таблицу из 41 600 случайных цифр, полученных путём измерения площадей сельскохозяйственных угодий. В 1939 году американский математик Морис Кендалл и его коллеги создали «Таблицы случайных чисел», используя электромеханические барабаны.

С появлением электронных вычислительных машин возникла потребность в программных генераторах. В 1946 году Джон фон Нейман предложил метод «средних квадратов»: число возводилось в квадрат, из середины результата извлекались цифры. Однако метод оказался статистически неудовлетворительным — последовательности быстро зацикливались.

В 1951 году Деррик Лемер разработал линейный конгруэнтный генератор (ЛКГ) — алгоритм, ставший основой для большинства ранних ГПСЧ. Формула ЛКГ: X_{n+1} = (a * X_n + c) mod m, где a, c и m — константы. Этот метод до сих пор используется во многих стандартных библиотеках, хотя обладает известными недостатками, такими как корреляция между последовательными числами.

В 1960-х годах появились более сложные генераторы: регистры сдвига с линейной обратной связью (LFSR), генераторы на основе алгоритма «вихрь Мерсенна» (Mersenne Twister, 1997, Макото Мацумото и Такудзи Нисимура), который до сих пор является стандартом для многих приложений, не требующих криптографической стойкости.

Классификация

ГПСЧ делятся на несколько категорий в зависимости от области применения и требований к безопасности:

По области применения

Статистические ГПСЧ — предназначены для моделирования, численных методов, игр. Основное требование — хорошие статистические свойства (равномерность распределения, отсутствие корреляций). Примеры: Mersenne Twister, PCG (Permuted Congruential Generator), XorShift.
Криптографически стойкие ГПСЧ (CSPRNG) — используются в криптографии, шифровании, генерации ключей. Должны быть непредсказуемыми: даже зная часть последовательности, невозможно восстановить предыдущие или следующие числа без знания начального состояния. Примеры: Fortuna, Yarrow, ChaCha20, алгоритмы на основе хеш-функций (SHA-256) или блочных шифров (AES-CTR).
Специализированные ГПСЧ — для конкретных задач, например, генерация случайных чисел с заданным распределением (нормальным, экспоненциальным).

По алгоритмической основе

Линейные конгруэнтные генераторы — простые, быстрые, но имеют короткий период и корреляции.
Регистры сдвига с линейной обратной связью (LFSR) — эффективны для аппаратной реализации, используются в телекоммуникациях.
Генераторы на основе клеточных автоматов — используют правила клеточных автоматов (например, правило 30 Стивена Вольфрама).
Генераторы на основе эллиптических кривых — применяются в криптографии, например, Dual_EC_DRBG (вызвал споры из-за возможной закладки от АНБ).
Генераторы на основе физических процессов — хотя формально это ГИСЧ, иногда их комбинируют с ГПСЧ для повышения производительности.

Устройство и принцип работы

Основной принцип ГПСЧ — детерминированный алгоритм, который преобразует начальное состояние (seed) в последовательность чисел. Ключевые параметры:

Seed (зерно) — начальное число, от которого зависит вся последовательность. При одинаковом seed генератор выдаёт одинаковую последовательность, что позволяет воспроизводить результаты.
Период — длина последовательности до её повторения. Для качественных ГПСЧ период должен быть очень большим (например, у Mersenne Twister — 2^19937 − 1).
Равномерность распределения — все числа в диапазоне должны появляться с одинаковой вероятностью.
Независимость — отсутствие корреляции между последовательными числами.

Алгоритм обычно состоит из:

Инициализация — установка seed.
Генерация — применение рекуррентной формулы для получения следующего числа.
Постобработка — преобразование полученного числа в требуемый диапазон (например, [0,1) для моделирования).

Для CSPRNG дополнительно требуется:

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

Применение

ГПСЧ находят применение в самых разных областях:

Моделирование и численные методы

Метод Монте-Карло для вычисления интегралов, моделирования физических процессов, финансовых рисков.
Имитационное моделирование (например, работа сетей, очередей, транспортных потоков).
Генерация случайных выборок в статистике.

Криптография и информационная безопасность

Генерация ключей шифрования, сессионных токенов, одноразовых паролей.
Создание случайных векторов инициализации (IV) для блочных шифров.
Протоколы аутентификации и цифровые подписи.

Компьютерные игры и графика

Генерация уровней, текстур, случайных событий.
Симуляция физики (например, разлёт осколков, поведение частиц).
Процедурная генерация контента (например, в игре Minecraft).

Научные исследования

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

Телекоммуникации

Псевдослучайные последовательности для тестирования каналов связи.
Генерация шумоподобных сигналов в системах с расширенным спектром (CDMA).

Критика и проблемы

Статистические недостатки

Многие ГПСЧ, особенно старые (например, ЛКГ с плохо подобранными параметрами), имеют корреляции между последовательными числами, что может приводить к ошибкам в моделировании. Например, известный генератор RANDU (использовавшийся в 1960-х) давал точки, лежащие на плоскостях, что делало его непригодным для многомерных задач.

Криптографические уязвимости

Некриптографические ГПСЧ (например, Mersenne Twister) легко предсказываются — достаточно получить 624 последовательных числа, чтобы восстановить всё внутреннее состояние. Это делает их непригодными для криптографии. В CSPRNG могут быть обнаружены закладки (как в Dual_EC_DRBG, где АНБ подозревалось во внедрении уязвимости).

Проблема seed

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

Тестирование

Для проверки качества ГПСЧ используются статистические тесты, такие как набор Diehard (Джордж Марсалья, 1995) и TestU01 (Пьер Л'Экуайе, 2007). Однако даже успешное прохождение тестов не гарантирует криптографической стойкости.

Примеры известных ГПСЧ

Mersenne Twister (MT19937) — самый популярный статистический ГПСЧ. Период 2^19937−1, быстрый, но не криптостойкий. Используется в Python, R, MATLAB.
PCG (Permuted Congruential Generator) — современный семейство ГПСЧ с хорошими статистическими свойствами и высокой скоростью.
XorShift — простой и быстрый генератор, основанный на операциях XOR и сдвига.
ChaCha20 — криптостойкий ГПСЧ, используемый в Linux (в составе /dev/urandom) и в протоколе TLS.
Fortuna — CSPRNG, разработанный Брюсом Шнайером, использует несколько энтропийных пулов.
Датчик случайных чисел в процессорах Intel (RDRAND) — аппаратный ГПСЧ, использующий тепловой шум, но с постобработкой через AES.

Интересные факты

В 1999 году математик Джордж Марсалья опубликовал набор тестов Diehard, который выявил недостатки многих популярных ГПСЧ того времени.
Генератор RANDU, использовавшийся в IBM System/360, был настолько плох, что его последовательности образовывали структуры в трёхмерном пространстве, что делало моделирование методом Монте-Карло бесполезным.
В 2007 году было обнаружено, что генератор Dual_EC_DRBG, рекомендованный NIST, содержит потенциальную закладку от АНБ, что вызвало скандал и привело к отказу от его использования.
В операционной системе Linux для генерации случайных чисел используются два устройства: /dev/random (блокируется, если энтропии недостаточно) и /dev/urandom (не блокируется, использует CSPRNG).

Источники

Кнут Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы. — 3-е изд. — М.: Вильямс, 2001.
Marsaglia G. Diehard: A Battery of Tests of Randomness. — 1995.
Matsumoto M., Nishimura T. Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator // ACM Transactions on Modeling and Computer Simulation. — 1998. — Vol. 8, № 1.
Schneier B. Applied Cryptography. — 2nd ed. — John Wiley & Sons, 1996.
NIST Special Publication 800-90A: Recommendation for Random Number Generation Using Deterministic Random Bit Generators. — 2015.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →