Разгадываем тайны ГСЧ: мифы, реальность и практические советы". Count characters.

Вопрос «как угадать число в генераторе случайных чисел (ГСЧ)» волнует умы людей десятилетиями: от игроков в казино и лотереи до специалистов по кибербезопасности. Короткий ответ: надежно угадать число истинно случайного генератора невозможно. Однако в цифровом мире мы почти всегда имеем дело не с истинной случайностью, а с псевдослучайными генераторами (ПСГЧ), которые подчиняются строгим алгоритмам;

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

Два фундаментальных типа генераторов

Прежде чем пытаться что-то предсказать, нужно понять, с чем именно вы имеете дело.

Истинные генераторы случайных чисел (True RNG / HRNG)

Эти устройства извлекают энтропию из физических процессов:

Тепловой шум (Johnson-Nyquist noise) в резисторах.
Квантовые эффекты (фотоэлектрический эффект, распад радиоактивных изотопов).
Атмосферный шум (используется, например, в random.org).
Джиттер тактового генератора процессора (Intel RDRAND, AMD RdSeed).

Вердикт: Угадать следующее число теоретически невозможно, так как нет никакого алгоритма или скрытого состояния. Единственный способ — физически вмешаться в измерительное устройство или подслушать побочные каналы (side-channel attacks).

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

Это детерминированные алгоритмы. Они принимают начальное значение (Seed / зерно) и производят последовательность бит, которая выглядит случайно, но полностью предопределена Seed.

Если вы знаете алгоритм и текущее внутреннее состояние (State) — вы знаете все будущие числа.
Если вы знаете только алгоритм, но не знаете State — задача сводится к взлому криптографии или подбору Seed.

Классификация ПСГЧ: от «игрушечных» до криптографических

Сложность «угадывания» напрямую зависит от класса генератора.

Некриптографические (статистические) генераторы

Примеры: Linear Congruential Generator (LCG), Mersenne Twister (MT19937), Xorshift, стандартные rand в C/C++, java.util.Random, random.random в Python (до 3.11), Math.random в JS (V8 до 2015 года).

Суть уязвимости: Они оптимизированы для скорости и равномерности распределения, а не для непредсказуемости.

LCG: Формула X_{n+1} = (a * X_n + c) mod m; Зная всего несколько последовательных чисел, можно решить систему уравнений и восстановить a, c, m и текущее состояние.
Mersenne Twister: Период 2^19937-1, но внутреннее состояние — 624 32-битных числа (2.5 КБ). Если перехватить 624 последовательных 32-битных выхода, можно полностью клонировать состояние генератора и предсказывать все будущие числа навсегда. Существуют готовые инструменты (например, untwister, mersenne-twister-predictor).

Криптографически стойкие генераторы (CSPRNG)

Примеры: ChaCha20 (современный стандарт в Linux, BSD, Chrome, Node.js), AES-CTR-DRBG (NIST SP 800-90A), HMAC-DRBG, /dev/urandom, getrandom, CryptGenRandom (Windows), secrets module (Python), crypto.getRandomValues (Web Crypto API).

Свойства:

Forward Secrecy: Зная текущее состояние, нельзя восстановить предыдущие числа.
Backtracking Resistance: Даже при компрометации состояния в момент t, атакующий не может предсказать числа в момент t+1 без знания секретного ключа/энтропии.
Computational Indistinguishability: Никакой полиномиальный алгоритм не может отличить выход от истинной случайности с вероятностью > 0.5 + negl(n).

Вердикт: «Угадать» число здесь означает сломать базовую криптографическую примитиву (ChaCha20, AES, SHA). На данный момент это вычислительно неосуществимо на классических компьютерах.

Реальные векторы атак (Как это делают хакеры, а не маги)

Поскольку прямой криптоанализ современных CSPRNG неработоспособен, атаки направлены на источник энтропии (Seed) и побочные каналы.

Атака на слабую инициализацию (Seed Prediction)

Если разработчик использовал new Random(DateTime.Now.Ticks) или srand(time(NULL)):

Пространство поиска Seed сужается до миллисекунд/микросекунд запуска процесса.
Атакующий перебирает возможное время запуска, генерирует последовательность и сверяет с известными выходами (например, ID сессии, токеном сброса пароля, картой в покере).
Пример: В 2008 году в Debian OpenSSL баг оставил только PID процесса как источник энтропии (32768 вариантов) — ключи RSA ломались за секунды.

Утечка состояния (State Compromise)

Memory Dump: Если атакующий получил доступ к памяти процесса (через /proc/pid/mem, дамп ядра, уязвимость типа Heartbleed, Spectre/Meltdown) — он извлекает внутреннее состояние генератора.
Fork без реинициализации: Классическая проблема Unix. Родительский процесс инициализировал PRNG, сделал fork. У родителя и ребенка идентичное состояние. Если ребенок сгенерировал число, атакующий, наблюдающий за ребенком, знает следующее число родителя.

Побочные каналы (Side-Channel Attacks)

Timing attacks: Измерение времени выполнения генерации.
Power analysis / EM emanations: Физическое измерение потребления энергии или излучения чипа (актуально для смарт-карт, HSM, IoT).
Cache attacks (Prime+Probe, Flush+Reload): Восстановление ключей/состояния через кэш CPU в облачных средах (multi-tenant).

Атака на «входную» энтропию (Entropy Starvation)

Виртуальные машины и контейнеры часто страдают от нехватки энтропии при первой загрузке (first boot). Если приложение запрашивает случайные байты до накопления достаточной энтропии (в Linux до ядра 5.6 /dev/urandom мог блокироваться или выдавать предсказуемые данные, сейчас getrandom блокируется до готовности), генератор может работать в детерминированном режиме с известным Seed.

Практический пример: Взлом Mersenne Twister (Python `random`)

Допустим, сервер на Python 3.10 использует random.getrandbits(32) для генерации токенов. MT19937 имеет состояние из 624 32-битных слов.

Собираем 624 последовательных 32-битных числа (например, через API, выдающее «случайные» бонусы, ID матчей и т.д.).
Применяем обратное преобразование «tempering» (инвертируем сдвиги и XOR, которые MT применяет к состоянию перед выводом).
Восстанавливаем внутренний массив mt[624] и индекс index.
Клонируем генератор локально. Теперь мы знаем все будущие токены.

Код концепта (Python):

# Требуется библиотека: pip install mersenne-twister-predictor
from mt19937predictor import MT19937Predictor

predictor = MT19937Predictor

for observed_number in observed_numbers_list:
 predictor.setrandbits(observed_number, 32)

next_token = predictor.getrandbits(32)
print(f"Следующий токен: {next_token}")

Психология и когнитивные ошибки: почему нам кажется, что мы видим закономерности

Часто «угадывание», это иллюзия, вызванная особенностями работы мозга:

Ошибка игрока (Gambler’s Fallacy): «Выпало 5 раз черное, значит теперь точно красное». В независимых испытаниях вероятность всегда 50/50 (или 1/37 в рулетке). Генератор не имеет памяти.
Апофения / Паттерн-поиск: Мозг эволюционно запрограммирован искать паттерны даже в белом шуме. Мы запоминаем совпадения и забываем промахи.
Закон больших чисел: В длинной последовательности обязательно встретятся длинные серии одинаковых значений (например, 10 «орлов» подряд). Это не сбой генератора, это норма.
Смещение выжившего (Survivorship Bias): Вы слышите про того, кто «угадал» 10 раз подряд, но не слышите про миллионы, кто проиграл.

Защита: как правильно генерировать числа (Чек-лист для разработчиков)

Если вы пишете код, где от случайности зависит безопасность (токены, ключи, nonce, соли, игровая логика за деньги):

Используйте только CSPRNG:
- Python: secrets.token_bytes, secrets.randbelow
- Node.js / Browser: crypto.randomBytes, crypto.getRandomValues
- Go: crypto/rand
- Java: SecureRandom
- C#: RandomNumberGenerator (не System.Random!)
- PHP: random_bytes, random_int
- Rust: rand::rngs::OsRng (через getrandom crate)
Никогда не сидите генератор вручную (нет srand(time(0)), random.seed(123) в продакшене). ОС делает это лучше вас.
Переинициализируйте после fork: В Python os.urandom безопасен, но если используете пользовательский PRNG — вызывайте reseed в дочернем процессе.
Достаточная длина: Токены сессии — минимум 128 бит энтропии (256 бит для долгосрочных ключей).
Константное время: При сравнении токенов используйте hmac.compare_digest / constant_time_compare, чтобы избежать timing-атак.

Квантовые компьютеры и будущее

Алгоритм Шора ломает RSA/ECC, но не ломает симметричную криптографию и хеш-функции, на которых построены CSPRNG (ChaCha20, AES, SHA-2/3).

Алгоритм Гровера дает квадратичное ускорение брутфорса: 256-битное пространство становится 128-битным. Поэтому стандарт NIST, использовать 256-битные ключи/состояния для пост-квантовой стойкости (AES-256, SHA-384/512, ChaCha20 с 256-битным ключом).

Угадать число в генераторе случайных чисел можно только в двух случаях:

Генератор криптографически слабый (LCG, Mersenne Twister, старый Math.random) и у вас есть доступ к его выходам для восстановления состояния.
Генератор сильный (CSPRNG), но плохо инициализирован (предсказуемый Seed, утечка состояния, форк без ресида, побочные каналы).

В любом другом случае — вы не угадываете, а гадаете. Математика криптографически стойких генераторов гарантирует, что лучшая стратегия атаки — это полный перебор (brute force), который при 256 битах энтропии требует энергии, превышающей выход Солнца на миллиарды лет.

Помните: Если вы не разработчик криптографической библиотеки, не изобретайте велосипед. Используйте системные CSPRNG (/dev/urandom, getrandom, CryptGenRandom, secrets module). Это единственный надежный способ не стать жертвой собственной наивности или чужой атаки.