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

Генератор случайных чисел (ГСЧ, англ. Random Number Generator, RNG) — это алгоритм, устройство или программное обеспечение, предназначенное для получения последовательности чисел, лишённой какой-либо закономерности или предсказуемости. В зависимости от способа получения случайности, различают аппаратные (физические) генераторы, использующие случайные физические процессы (например, тепловой шум или радиоактивный распад), и программные (псевдослучайные) генераторы, которые вырабатывают последовательности, лишь имитирующие случайность на основе детерминированных алгоритмов.

История

Потребность в случайных числах возникла задолго до появления компьютеров. В древности для жеребьёвки, гаданий и азартных игр использовались кости, монеты, палочки и другие подручные средства. В математике и статистике случайные числа стали применяться с развитием теории вероятностей в XVII—XVIII веках (работы Блеза Паскаля, Пьера Ферма, Якоба Бернулли). Однако до середины XX века генерация случайных чисел оставалась трудоёмким ручным процессом: исследователи использовали таблицы случайных чисел, составленные по результатам подбрасывания монет или вращения рулетки.

С появлением электронных вычислительных машин в 1940-х годах возникла необходимость в автоматической генерации случайных чисел. Первые программные ГСЧ были разработаны в 1946 году Джоном фон Нейманом (метод «серединных квадратов»). В 1950-х годах появились более совершенные алгоритмы, такие как линейный конгруэнтный генератор (Д. Лемер, 1951). В 1960-х годах началось активное применение аппаратных ГСЧ, основанных на электронном шуме, для нужд криптографии и моделирования.

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

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

Аппаратные (физические) ГСЧ

Аппаратные ГСЧ (True Random Number Generator, TRNG) получают случайность из физических процессов, которые считаются принципиально непредсказуемыми. Ключевое преимущество — высокая степень случайности, не зависящая от алгоритма. Основные виды:

• На основе теплового шума: Используют флуктуации напряжения на полупроводниковых элементах (например, на диодах или транзисторах). Шум усиливается, оцифровывается и преобразуется в битовую последовательность.
• На основе радиоактивного распада: Фиксируют моменты распада радиоактивных изотопов с помощью счётчика Гейгера. Интервалы между событиями или их количество за единицу времени дают случайные числа.
• На основе атмосферного шума: Используют радиоприёмники, настроенные на частоту, свободную от сигналов, для регистрации атмосферных помех.
• На основе квантовых эффектов: Применяют квантово-механические явления, например, случайное направление поляризации фотона или фазовый шум в лазерах. Такие генераторы считаются наиболее надёжными с точки зрения непредсказуемости.
• На основе хаотических систем: Используют нелинейные динамические системы (например, маятники, турбулентные потоки), поведение которых чувствительно к начальным условиям.

Программные (псевдослучайные) ГСЧ

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

• Линейный конгруэнтный генератор (ЛКГ): Один из старейших и простейших. Вычисляет следующее число по формуле: X_{n+1} = (a * X_n + c) mod m. Параметры a, c, m подбираются для обеспечения длинного периода и хороших статистических свойств.
• Вихрь Мерсенна (Mersenne Twister): Разработан в 1997 году японскими учёными. Обладает огромным периодом (2^19937 - 1) и хорошим распределением. Широко используется в научных расчётах, но не пригоден для криптографии.
• Генераторы на основе регистров сдвига с линейной обратной связью (LFSR): Быстрые и компактные, используются в телекоммуникациях и встроенных системах.
• Криптостойкие ГСЧ (CSPRNG): Разработаны для нужд криптографии. Их выходная последовательность должна быть неотличима от истинно случайной даже для противника, знающего алгоритм, но не знающего начальное состояние. Примеры: алгоритмы на основе блочных шифров (CTR_DRBG), хеш-функций (Hash_DRBG) или эллиптических кривых.

Характеристики и критерии качества

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

• Случайность (энтропия): Мера непредсказуемости последовательности. Для аппаратных ГСЧ оценивается как количество бит случайности на единицу времени.
• Период: Длина последовательности, после которой она начинает повторяться. Для качественных PRNG период должен быть очень большим (например, у вихря Мерсенна — 2^19937 - 1).
• Равномерность распределения: Все возможные значения должны появляться с примерно одинаковой частотой.
• Независимость: Отсутствие корреляции между соседними и отдалёнными членами последовательности.
• Криптостойкость: Невозможность восстановить внутреннее состояние генератора или предсказать будущие значения по известной выходной последовательности.

Для проверки качества ГСЧ используются стандартные статистические тесты, такие как наборы NIST SP 800-22 (США), Diehard (Джордж Марсалья), TestU01 (Пьер Л'Экуйе). Аппаратные ГСЧ также проходят тесты на физическую энтропию.

Применение

Генераторы случайных чисел находят применение в самых разных областях:

• Криптография: Генерация ключей шифрования, цифровых подписей, одноразовых паролей, nonce (однократно используемых чисел). Для этих целей применяются только криптостойкие ГСЧ (CSPRNG) или аппаратные ГСЧ.
• Моделирование и симуляция: Метод Монте-Карло для расчёта интегралов, моделирования физических процессов (ядерные реакции, диффузия), финансовых рисков, климатических систем.
• Азартные игры и игровые автоматы: Обеспечение случайности выпадения комбинаций в слотах, рулетке, покере. В РФ и других странах игровые автоматы подлежат обязательной сертификации, включающей проверку ГСЧ.
• Компьютерные игры: Генерация игрового мира (процедурная генерация), поведения противников, случайных событий, выпадения предметов.
• Научные исследования: Статистические эксперименты, рандомизация выборок, тестирование гипотез.
• Лотереи и розыгрыши: Выбор выигрышных номеров. В ряде стран (включая РФ) государственные лотереи используют аппаратные ГСЧ для обеспечения честности.
• Искусство и музыка: Генерация случайных мелодий, цветовых палитр, текстур, а также в алгоритмическом искусстве.

Критика и ограничения

Несмотря на широкое применение, ГСЧ имеют ряд ограничений и подвергаются критике:

• Предсказуемость PRNG: Если злоумышленник узнает начальное значение (seed) или внутреннее состояние генератора, он может предсказать всю последовательность. Это привело к ряду громких взломов в криптографии и азартных играх.
• Проблемы с энтропией: Аппаратные ГСЧ могут давать недостаточно энтропии, если физический процесс нестабилен или подвержен внешним воздействиям (температура, электромагнитные помехи). В некоторых реализациях (например, в старых версиях Linux /dev/random) система могла «зависнуть» в ожидании накопления энтропии.
• Неверное использование: Применение нестойкого PRNG (например, вихря Мерсенна) в криптографии делает систему уязвимой. Также распространена ошибка — использование одного и того же seed для разных сессий или предсказуемого seed (например, на основе времени).
• Психологическая неслучайность: Люди склонны считать случайными те последовательности, которые не содержат длинных серий одинаковых чисел, хотя в истинно случайной последовательности такие серии возможны. Это приводит к тому, что «человеческая» случайность часто оказывается менее случайной, чем машинная.

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

• В 2018 году исследователи из Университета Массачусетса продемонстрировали аппаратный ГСЧ на основе хаотического движения бактерий.
• Самый длинный период среди известных PRNG имеет генератор на основе вихря Мерсенна (2^19937 - 1), что примерно равно числу атомов в наблюдаемой Вселенной.
• В СССР для генерации случайных чисел в криптографии использовались ламповые генераторы шума, а позже — полупроводниковые.
• В 2020 году Национальный институт стандартов и технологий США (NIST) выпустил обновлённый стандарт для криптостойких ГСЧ (SP 800-90A Rev. 1).
• В некоторых операционных системах (например, Linux) для обеспечения работы ГСЧ используется энтропия от движений мыши, нажатий клавиш и дисковых операций.

Источники

• Кнут Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы. — 3-е изд. — М.: Вильямс, 2007.
• Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC Press, 1996.
• NIST Special Publication 800-90A Rev. 1. Recommendation for Random Number Generation Using Deterministic Random Bit Generators. — 2015.
• Marsaglia G. Diehard: A Battery of Tests of Randomness. — 1996.
• L’Ecuyer P. TestU01: A C Library for Empirical Testing of Random Number Generators. — 2007.