Псевдослучайный рандом в Python / Хабр

В этой статье хочу рассказать про нерандомность модуля random в стандартной библиотеке Python. С точки зрения криптографии и математики числа, генерируемые этим модулем, случайные лишь на вид — они порождаются детерминированным алгоритмом, что делает их псевдослучайными. Рассмотрим, как устроен генератор на основе алгоритма Mersenne Twister (MT19937), почему его выходы «нерандомны» в формальном смысле и какие практические следствия это имеет.

написано для новичков и плохо посвященных в тему людей…

Теория случайности

Алгоритмическая случайность

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

строка называется случайной тогда и только тогда, когда она короче любой компьютерной программы, способной её воспроизвести

Если последовательность можно «сжать» до короткой программы, то она не считается случайной.

Зачем нужен псевдослучай

В большинстве инженерных задач (симуляции, игры, моделирование) вполне достаточно псевдослучайных чисел: важны статистические свойства, а не криптографическая стойкость. Псевдослучайные генераторы (PRNG = pseudorandom number generator) обладают большими периодами и проходят большинство статистических тестов, но при этом остаются полностью предсказуемыми, если известно их внутреннее состояние.

❓ Период псевдослучайного генератора — это максимальная длина последовательности, которую генератор может выдать, прежде чем она начнёт повторяться.

Под капотом Python random

Python по умолчанию использует реализацию Mersenne Twister (MT19937). Основные характеристики:

Период: 2**19937-1 — один из самых больших периодов среди классических PRNG.
Состояние: массив из 624 32‑битных целых, итеративно обновляемых по линейному рекуррентному соотношению по модулю 2.
Это означает, что внутри генератора random хранится массив из 624 чисел, каждое из которых — это 32-битное целое число (то есть число от 0 до 2³²−1). Это и есть внутреннее состояние генератора. Оно полнос��ью определяет, какие "случайные" числа будут выдаваться дальше.
Если ты знаешь этот массив — ты знаешь весь будущий вывод генератора.
Упрощенно это выглядит как-то так:
```
# Массив из 624 чисел
state = [some initial 32-bit numbers]

# Для генерации следующего блока:
for i in range(624):
    x = (state[i] & upper_mask) + (state[(i + 1) % 624] & lower_mask)
    state[i] = state[(i + 397) % 624] ^ (x >> 1)
    if x % 2 != 0:
        state[i] ^= 0x9908B0DF
```
Темперинг: после расчёта нового слова применяется набор сдвигов и масок для улучшения статистических свойств.
Темперинг - это последняя стадия перед выдачей случайного числа. Он не влияет на состояние, а лишь «приукрашивает» выход, делая числа визуально более случайными.
Даже если генератор правильно обновляет своё состояние, не все биты в числе могут быть одинаково случайны. Например, старшие биты могут меняться хорошо, а младшие — оставаться слишком предсказуемыми.
Темперинг "размазывает" энтропию по всем битам числа с помощью набора побитовых операций — сдвигов, масок и побитового исключающего ИЛИ (XOR). Это повышает равномерность распределения и делает числа визуально более случайными, соответствующими требованиям, например, тестов из библиотеки TestU01.
Формально темперинг выглядит как последовательность операций вроде:
```
y ^= (y >> u) & d
y ^= (y << s) & b
y ^= (y << t) & c
y ^= (y >> l)
```
где y — это число, полученное из состояния, а u, d, s, b, t, c, l — заранее подобранные константы. Эти значения были эмпирически выбраны для оптимального качества генерации.

При генерации random() Python берёт 53 бита из темперованного внутреннего состояния и преобразует их в float двойной точности. Так достигается равномерность в [0, 1) с точностью порядка 2**{-53}.

Статистика vs математика

Модель MT19937 проходит практически все стандартные статистические тесты (NIST SP 800‑22, Dieharder, TestU01), однако:

Линейные зависимости
Mersenne Twister использует линейную рекурсию по модулю 2 — то есть новые значения состояния вычисляются через побитовые операции (XOR, сдвиги) над предыдущими, рассматриваемыми как векторы в поле GF(2). Это делает поведение генератора полностью линейным и, как следствие, предсказуемым: между выходными значениями существуют линейные зависимости.
Если собрать достаточно выходных чисел (например, 624), можно восстановить внутреннее состояние генератора и предсказывать все будущие значения. Поэтому Mersenne Twister не подходит для задач, где важна непредсказуемость — он не предназначен для криптографии и пр.
Существует несколько статей (https://doi.org/10.48550/arXiv.1301.5435) и проектов (https://github.com/twisteroidambassador/mt19937-reversible), которые занимались восстановлением внутреннего состояния.
Плоскостность многомерных распределений
Хотя Mersenne Twister обеспечивает хорошее равномерное распределение в одномерных выходах, в многомерных пространствах (например, при рассмотрении последовательностей из нескольких подряд идущих чисел) его выходы могут демонстрировать плоскостные структуры. Это означает, что такие точк�� в k-мерном ( векторы длины k) пространстве не заполняют его равномерно, а располагаются на ограниченном числе гиперплоскостей.
Это означает, что даже если одномерные выходы выглядят случайными, их комбинации в более высоких измерениях показывают регулярность, и это выявляется специальными статистическими тестами (Lattice Structure Test, Spectral Test (в линейных конгруэнтных генераторах), Equidistribution test).
💡 Существует визуализация в вольфраме - можете поиграться и посмотреть на разброс разных алгоритмов генерации псевдорандома.

Практическая атака: клонирование состояния

Ниже — минимальный и понятный пример, который показывает, как, зная 624 последовательных 32‑битных вывода из random.getrandbits(32), полностью восстановить внутреннее состояние Mersenne Twister и предсказать все последующие значения.

Функции для «раскрутки» (untemper) темперинга MT19937.
Сбор 624 выводов.
Восстановление состояния и проверки, что клон выдаёт точно такие же числа.

import random

# 1) функции для "раскрутки" темперинга (они обратны операциям в genrand_uint32: y ^= y>>11; y ^= (y<<7)&B; y ^= (y<<15)&C; y ^= y>>18)

B = 0x9d2c5680
C = 0xefc60000

def unshift_right(x, shift):
    # возвращаем исходное x до операции x ^= x >> shift
    res = x
    for _ in range(32):
        res = x ^ (res >> shift)
    return res

def unshift_left(x, shift, mask):
    # возвращаем исходное x до операции x ^= (x << shift) & mask
    res = x
    for _ in range(32):
        res = x ^ ((res << shift) & mask)
    return res

def untemper(y):
    # обратный порядок темперинга
    y = unshift_right(y, 18)
    y = unshift_left(y, 15, C)
    y = unshift_left(y, 7,  B)
    y = unshift_right(y, 11)
    return y
# 2) собираем 624 вывода оригинального генератора
orig = random.Random()
orig.seed(123456)            # например, неизвестный нам сид

# пропускаем несколько первых выводов (чтобы показать, что работает в любой точке)
for _ in range(1000):
    orig.getrandbits(32)

# теперь "подслушиваем" 624 подряд getrandbits(32)
outputs = [orig.getrandbits(32) for _ in range(624)]
# === 3) клонируем состояние и проверяем предсказание ===
# восстанавливаем массив mt[i] = untemper(outputs[i])
mt_state = tuple(untemper(y) for y in outputs)

# format state для random.setstate: (version, (mt_index, mt_array), gaussian)
# после выдачи 624 значений индекс ровняется 624
state = (3, mt_state + (624,), None)

cloned = random.Random()
cloned.setstate(state)

# Сравниваем следующие 10 значений
for i in range(10):
    orig_val = orig.getrandbits(32)
    clone_val = cloned.getrandbits(32)
    print(f"{i+1:2d}: original = {orig_val:10d}, clone = {clone_val:10d}",
          "✓" if orig_val == clone_val else "✗")

Практические рекомендации

Для криптографических задач вместо random используйте модуль secrets или класс random.SystemRandom, который черпает байты из ОС‑генератора.

secrets использует системный криптографический генератор случайных чисел (например, /dev/urandom на Linux/macOS или CryptGenRandom на Windows). SystemRandom — обёртка вокруг тех же криптографических источников, но предоставляет тот же API, что и random.Random. Это удобно, если нужно сохранить интерфейс, но повысить надёжность.

Если криптографическая стойкость не требуется, но важна высокая скорость генерации и надёжные статистические свойства, вместо random стоит обратить внимание на современные генераторы, такие как PCG, Xorshift+ и WELL.

PCG (Permuted Congruential Generator) — это семейство генераторов, отличающееся качественным равномерным распределением битов и устранением типичных слабостей Mersenne Twister. В отличие от MT, где младшие биты обладают худшей энтропией, PCG обеспечивает хорошее распределение по всем разрядам. Он компактен, прост в реализации и даёт отличные результаты в тестах случайности. Подходит для большинства прикладных задач, включая симуляции и игры. Используется для генерации игрового мира в Minecraft!
Xorshift+ и Xorshift-128+ — это крайне быстрые генераторы, построенные на простых побитовых операциях (XOR и сдвиги). Они часто используются в задачах, где критична скорость, например в графических приложениях и процедурной генерации контента.
WELL (Well Equidistributed Long-period Linear) — это линейный генератор, созданный как улучшение Mersenne Twister. Он устраняет ряд его теоретических недостатков, включая плохую равномерность многомерного распределения. WELL показывает лучшую стабильность в статистических тестах и может использоваться в научных расчётах, требующих высокой надёжности генерации.

Вывод

Python‑генератор random на базе MT19937 отлично подходит для большинства прикладных задач, связанных с симуляцией и моделированием. Тем не менее он не обеспечивает ни криптографическую стойкость, ни математическую непредсказуемость. Формальные доказательства линейности и возможность клонирования состояния показывают, что это всего лишь детерминированный алгоритм с конечным периодом. При необходимости настоящей случайности стоит обращаться к аппаратным (квантовым) или криптографически надёжным источникам.

Псевдослучайный рандом в Python