В этой статье хочу рассказать про нерандомность модуля 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 отлично подходит для большинства прикладных задач, связанных с симуляцией и моделированием. Тем не менее он не обеспечивает ни криптографическую стойкость, ни математическую непредсказуемость. Формальные доказательства линейности и возможность клонирования состояния показывают, что это всего лишь детерминированный алгоритм с конечным периодом. При необходимости настоящей случайности стоит обращаться к аппаратным (квантовым) или криптографически надёжным источникам.