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

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

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

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

¶Аппаратные (истинно случайные) генераторы

Используют непредсказуемые физические процессы: тепловой шум электронных компонентов, радиоактивный распад, фотонный шум, дрейф частоты, атмосферные помехи. Такие генераторы называют TRNG (True Random Number Generator). Их выход принципиально невоспроизводим, что делает их пригодными для задач, где важна непредсказуемость, — например, при генерации криптографических ключей.

¶Программные (псевдослучайные) генераторы

Детерминированные алгоритмы, выдающие последовательность, лишь внешне похожую на случайную. Их обозначают ПСЧ (псевдослучайные числа) или PRNG (Pseudo-Random Number Generator). Работа основаны на начальном значении — «зерне» (seed). При одинаковом зерне последовательность полностью воспроизводима, что удобно для отладки и повторяемых экспериментов, но неприемлемо для криптографии без дополнительных мер.

¶Устройство и алгоритмы

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

• Линейный конгруэнтный метод — рекуррентное соотношение вида X(n+1) = (a·X(n) + c) mod m; прост и быстр, но обладает коротким периодом при неудачном выборе параметров.
• Регистр сдвига с линейной обратной связью (LFSR) — применяется в потоковых шифрах и тестировании.
• Вихрь Мерсенна (Mersenne Twister) — широко используемый алгоритм с огромным периодом, входящий в стандартные библиотеки многих языков программирования.
• Криптостойкие генераторы — используют хеш-функции и блочные шифры; к ним предъявляются требования стойкости к предсказанию следующего бита.

¶Применение

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

¶Проверка качества

Случайность последовательности оценивают статистическими тестами: проверка частот, серий, автокорреляции, спектральный анализ. Известны наборы тестов NIST SP 800-22, Diehard и TestU01. Ни один набор тестов не доказывает истинную случайность — он лишь выявляет отклонения от неё.

¶История

Первые механические устройства для получения случайных чисел — игральные кости, жребий, монета — известны с древности. В XX веке с развитием вычислительной техники появились таблицы случайных чисел (например, таблицы Рэнд корпорации RAND, 1955). В 1946 году Джон фон Нейман предложил метод середины квадрата — один из первых программных алгоритмов. В 1950–1960-х годах разработаны линейные конгруэнтные генераторы, а в 1997 году — вихрь Мерсенна. В России генераторы случайных чисел применяются в системах защиты информации, в том числе в средствах криптографической защиты, сертифицируемых ФСБ России.

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

• Аппаратные ГСЧ на основе радиоактивного распада использовались в ранних ЭВМ.
• В 2013 году выяснилось, что генератор Dual_EC_DRBG, рекомендованный одним из американских стандартов, содержал потенциальную криптографическую «закладку».
• Для лотерей и жеребьёвок в ряде стран применяются физические лототроны, а не программные генераторы, — ради наглядности и доверия участников.

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

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

Источники: NIST SP 800-22, документация по алгоритму Mersenne Twister, материалы RAND Corporation, публикации по методу Монте-Карло.