Псевдослучайные числа в компьютерных системах¶
Псевдослучайные числа — это последовательности чисел, формируемые алгоритмически таким образом, что они имитируют свойства истинно случайных величин, но при этом полностью определяются начальным состоянием генератора. Термин «рандомный» (от англ. random — «случайный») в вычислительной практике чаще всего относится именно к псевдослучайным значениям, поскольку компьютеры, работающие по детерминированным инструкциям, не способны порождать принципиально непредсказуемые последовательности без использования специальных аппаратных источников энтропии.
¶Природа случайности в вычислениях
Классическая программа представляет собой детерминированную систему: одинаковые входные данные всегда приводят к одинаковому результату. Истинная случайность, в смысле физики, подразумевает непредсказуемость результата даже при полном знании состояния системы. Компьютер, исполняющий машинный код, такой непредсказуемостью не обладает. Поэтому в программировании под «случайными числами» понимают последовательности, обладающие статистическими свойствами случайных величин: равномерное распределение, отсутствие корреляций между соседними значениями, непредсказуемость следующего числа при известных предыдущих.
Для большинства практических задач — моделирование, генерация тестовых данных, разрешение конфликтов в сетевых протоколах — псевдослучайности достаточно. Там, где требуется криптографическая стойкость, используются отдельные классы генераторов.
¶Основные алгоритмы
¶Линейный конгруэнтный метод
Простейший и один из старейших алгоритмов, предложенный Д. Лемером в 1949 году. Заключается в итеративном вычислении:
Xₙ₊₁ = (a · Xₙ + c) mod m
где a, c и m — целые константы, X₀ — начальное значение (seed). При корректно подобранных параметрах последовательность имеет период m. Этот метод использовался в стандартной библиотеке C (функция rand()) и в ранних версиях многих языков программирования. Его недостаток — предсказуемость: зная несколько последовательных значений, можно восстановить параметры генератора и вычислить все последующие числа.
¶Мерсенновский штучный вихрь
Алгоритм Mersenne Twister, разработанный в 1997 году Макото Матсумото и Цуёси Нисимурой, стал де-факто стандартом для некриптографических задач. Он обеспечивает период 2¹⁹⁹³⁷ − 1 и проходит стандартные статистические тесты на случайность (например, набор TestU01). Используется в стандартных библиотеках Python, Ruby, PHP, R и многих других. Для инициализации требуется массив из 624 32-битных слов.
¶Криптографические генераторы
Для задач, где предсказуемость недопустима (генерация ключей, токенов, одноразовых паролей), применяют криптографически стойкие генераторы псевдослучайных чисел (КСПСЧ). Их построение основано на криптографических примитивах — хеш-функциях или шифрах в режиме, обратном по трудности. Примеры: HMAC-DRBG (используется в OpenSSL), ChaCha20 в качестве PRNG, ГОСТ Р 34.12-2015 «Кузнечик» в российских криптобиблиотеках. Для таких генераторов вычислительная сложность восстановления внутреннего состояния по выходной последовательности должна быть практически непреодолимой.
¶Источники энтропии
Для инициализации (seed) псевдослучайных генераторов в реальных системах используют аппаратные источники непредсказуемости. В Linux это файл /dev/random и подсистема entropy pool, наполняемая прерываниями от клавиатуры, таймеров, движений мыши и шумом дисков. Современные процессоры (Intel RDRAND, AMD RDSEED) содержат аппаратные генераторы на основе квантовых шумов. В Windows аналогичную роль играет API CryptGenRandom и его преемник BCryptGenRandom.
Если seed выбирается предсказуемо (например, берётся текущее время с точностью до секунды), вся последовательность становится воспроизводимой для злоумышленника. Эта уязвимость была, в частности, причиной криптографических инцидентов в генераторах Debian (2008) и Dual_EC_DRBG.
¶Применение
Псевдослучайные числа используются в широком спектре задач:
- Моделирование — метод Монте-Карло для численного интегрирования, расчёта вероятностей, имитации физических процессов;
- Игры и генеративный дизайн — процедурная генерация уровней, выпадение предметов, поведение неигровых персонажей;
- Тестирование — фаззинг, генерация случайных входных данных для проверки устойчивости программ;
- Распределённые системы — случайный выбор узлов, джемпинг в сетевых протоколах, балансировка нагрузки;
- Статистика — бутстрэп, перестановочные тесты, кросс-валидация.
В языках программирования генерация случайных чисел реализована стандартными средствами: random в Python, java.util.Random и SecureRandom в Java, math/rand и crypto/rand в Go, std::mt19937 в C++.
¶Ограничения
Псевдослучайная последовательность полностью воспроизводима при одинаковом seed. Это свойство является преимуществом при отладке и тестировании, но недостатком там, где требуется реальная непредсказуемость. Кроме того, ни один алгоритмический генератор не способен создать информацию в смысле теории информации — энтропия его выхода не превышает энтропии начального состояния.
Источники:
- Knuth D. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms
- Matsumoto M., Nishimura T. Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator (1998)
- ГОСТ Р 34.12-2015. Блоки симметричного преобразования
- 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)