Как угадать число в генераторе случайных чисел: типы ГСЧ, предсказуемость и методы восстановления seed

Генераторы случайных чисел (ГСЧ) широко используются в программировании, играх, криптографии и статистических моделях.
Несмотря на название, большинство «случайных» чисел генерируются детерминированными алгоритмами, которые при
известном начальном состоянии (seed) воспроизводят одну и ту же последовательность.
Поэтому вопрос «как угадать номер в генераторе случайных чисел» имеет смысл только в контексте
предсказания следующего значения или восстановления seed‑а. В этой статье мы разберём:

• Типы генераторов случайных чисел;
• Почему некоторые из них предсказуемы;
• Методы восстановления seed‑а;
• Практические примеры и рекомендации по защите.

Классификация генераторов случайных чисел

Существует два основных класса:

1.1 Псевдослучайные генераторы (PRNG)

PRNG – это детерминированные алгоритмы, которые используют начальное значение (seed) и математическую функцию,
чтобы выдавать последовательность, выглядящую случайной. Примеры:

• Linear Congruential Generator (LCG)
• Mersenne Twister
• Xorshift, PCG, SplitMix64

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

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

• Fortuna
• Yarrow
• ChaCha20‑based DRBG
• OS‑уровневые источники: /dev/urandom, CryptGenRandom

Почему некоторые генераторы предсказуемы?

Предсказуемость возникает из двух причин:

1. Недостаточная энтропия seed‑а. Если seed выбирается из небольшого диапазона (например, текущий Unix‑время),
   атакующий может перебрать все варианты.
2. Простая математическая структура. Алгоритмы вроде LCG имеют известные формулы, позволяющие восстановить
   параметры генератора, если известны несколько последовательных выходов.

Методы угадывания (предсказания) номера

3.1 Перебор seed‑а (brute‑force)

Если диапазон seed ограничен, можно просто перебрать все варианты и сравнить полученные числа с известными
наблюдениями.

for seed in range(0, 2**32):
 rng = random.Random(seed)
 if rng.random == known_value:
 print("Найден seed:", seed)
 break

3;2 Анализ уравнений LCG

LCG задаётся формулой:

X_n+1 = (a·X_n + c) mod m

Если известны два последовательных значения X_n и X_n+1, можно решить систему
уравнений и найти параметры a, c, m, а затем восстановить предыдущее состояние.

Пример восстановления seed LCG

1. Получаем три последовательных числа: r1, r2, r3.
2. Решаем уравнения:
   • r2 = (a·r1 + c) mod m
   • r3 = (a·r2 + c) mod m
3. Вычисляем a и c через модульную арифметику (используем расширенный алгоритм Евклида).
4. Получаем seed = r1.

3.3 Атака на Mersenne Twister

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

Алгоритм восстановления:

1. Собрать 624 вывода генератора.
2. Обратным преобразованием (untemper) восстановить внутренние слова.
3. Инициализировать новый объект MT19937 этим состоянием.
4. Генерировать дальше – получаем те же числа, что и оригинальный генератор.

3.4 Криптографические генераторы

Для CSPRNG предсказание без доступа к внутреннему секретному ключу практически невозможно. Однако иногда
возможны побочные атаки:

• Side‑channel атаки. Измерение времени, потребления энергии, шумов и т.п. могут раскрыть часть состояния.
• Недостаточная инициализация. Если CSPRNG инициализируется предсказуемым seed‑ом (например, временем),
  атакующий может выполнить перебор.

Практический пример: угадываем номер в простом LCG

Допустим, в игре используется следующий генератор:

seed = int(time.time)
a = 1103515245
c = 12345
m = 2*31
def next_rand:
 global seed
 seed = (a  seed + c) % m
 return seed

Мы знаем, что игрок получил число 12345678 в момент t = 1625078400 (Unix‑время). Как восстановить seed?

1. Перебираем небольшое окно времени (±5 секунд) вокруг известного времени.
2. Для каждого candidate‑seed вычисляем первое значение генератора.
3. Сравниваем с известным числом.

import time

target = 12345678
t0 = 1625078400
window = 5
for delta in range(-window, window+1):
 cand = t0 + delta
 seed = cand
 val = (1103515245 * seed + 12345) % (2**31)
 if val == target:
 print("Найден seed:", cand)
 break

В результате получаем точный seed и можем предсказывать все последующие номера.

Как защититься от угадывания?

• Использовать криптографически стойкие генераторы. В Python – secrets.randbits, в C/C++ – std::random_device + std::mt19937 только после хорошей инициализации.
• Не использовать время как единственный seed. Добавляйте дополнительные источники энтропии (аппаратные датчики, хеши от пользовательского ввода).
• Регулярно перемешивайте состояние. Для PRNG можно периодически «перезапускать» генератор новым seed‑ом.
• Ограничьте количество выдаваемых чисел. Чем меньше наблюдаемых выходов, тем сложнее восстановить состояние.
• Следите за уязвимостями side‑channel. При работе с CSPRNG в критических системах используйте защищённые библиотеки,
  которые минимизируют утечки.

Угадать номер в генераторе случайных чисел возможно, но только при выполнении определённых условий:
низкая энтропия seed‑а, простая структура алгоритма и наличие достаточного количества известных выходов.
Современные криптографические генераторы делают такие атаки практически невозможными, однако
неправильная инициализация или использование устаревших PRNG может открыть двери для предсказания.

Помните, что безопасность случайных чисел – это фундаментальная часть любой системы, где важна
непредсказуемость (игры, шифрование, распределённые протоколы). Выбирайте проверенные решения,
регулярно обновляйте библиотеки и проверяйте, что ваш seed действительно «случайный».

Удачной разработки и безопасных генераций!