Детерминированный генератор случайных чисел¶

Детерминированный генератор случайных чисел (ДГСЧ, англ. PRNG — Pseudorandom Number Generator) — алгоритм, формирующий последовательность чисел, обладающую статистическими свойствами случайной последовательности, при этом полностью определяемую начальным значением (seed). В отличие от аппаратных генераторов, использующих физические процессы, ДГСЧ детерминирован: одна и та же начальная маска всегда порождает одну и ту же последовательность.

¶Принцип работы

Алгоритм ДГСЧ основан на итеративном преобразовании внутреннего состояния. На каждом шаге состояние обновляется по детерминированному правилу, а из него извлекается выходное значение. Ключевые свойства:

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

Для оценки качества используется набор статистических тестов (например, набор TestU01 или NIST SP 800-22), проверяющих равномерность распределения, корреляции и независимость бит.

¶Основные классы

¶Линейный конгруэнтный генератор

Простейший и один из старейших классов. Состояние обновляется по формуле:

$$X_{n+1} = (a X_n + c) \mod m$$

где $a$, $c$, $m$ — фиксированные константы. Максимальный период достигается при выполнении условий Халл–Доуэла. Примером служит функция rand() в стандартной библиотеке C, хотя её параметры в некоторых реализациях признаны слабыми.

¶Генератор с регистром сдвига с обратной связью (LFSR)

Использует сдвиговый регистр, выход которого через линейную обратную связь подаётся на вход. При правильном выборе многочлена обратной связи достигается максимальный период $2^n - 1$. LFSR применяются в телекоммуникации (кодирование, расширение спектра) и встроены во многие микроконтроллеры.

¶Генератор Мерсенна-Твистера

Разработан в 1997 году Харуки Мамацумото и Такудзи Нисимурой. Использует массив из 624 32-битных слов и линейное преобразование над вектором в поле Галуа. Период составляет $2^{19937} - 1$. Стандарт де-факто для научных вычислений и встроено в стандартные библиотеки Python, PHP, Ruby и многие другие.

¶Криптографически стойкие генераторы

Для задач криптографии обычные ДГСЧ непригодны: зная несколько выходных значений, можно восстановить состояние и предсказать весь поток. Криптографически стойкие генераторы (КСГ, CSPRNG) проектируются так, чтобы восстановление состояния было вычислительно неосуществимо. Примеры:

• Хэш-цепочка — состояние обновляется через криптографические хэш-функции.
• CTR_DRBG — стандарт NIST, основанный на блочном шифре в режиме счётчика.
• ChaCha20 — поточный шифр, используемый как генератор в Linux (/dev/urandom), OpenSSL и WireGuard.

¶Применение

ДГСЧ применяются в широком спектре задач:

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

¶Проблемы и ограничения

Основная проблема — «слабая маска». Если начальное значение выбирается предсказуемо (время системы, PID процесса), вся последовательность становится воспроизводимой для злоумышленника. Исторические примеры:

• Казино в Монте-Карло, 1993 — посетители, заметившие паттерн на рулетке, выиграли около миллиона долларов.
• Debian OpenSSL, 2008 — закомментированная строка кода привела к тому, что генерация ключей SSH свелась к перебору ~32 000 вариантов.
• Микробраузерное шифрование в Windows — уязвимость家族 (CVE-2008-0163) в библиотеке libgcrypt была вызвана ошибкой в реализации LFSR.

Для криптографических задач рекомендуется использовать только проверенные КСГ и обеспечивать энтропийную маску из аппаратных источников (например, /dev/random или getrandom() в Linux).

¶См. также

• Случайность
• Криптографическая стойкость
• Тестирование генераторов случайных чисел
• Метод Монте-Карло

¶Источники

• Knuth D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms.
• Matsuomoto T., Nishimura T. Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator, 1998.
• NIST SP 800-90A. Recommendation for Random Number Generation Using Deterministic Random Bit Generators.
• L'Ecuyer P. Random Number Generation. Handbook of Computational Statistics, 2012.