Введение: «Состояние греха» фон Неймана и парадокс детерминированной случайности

В 1951 году Джон фон Нейман произнёс фразу, навсегда вошедшую в историю информатики: «Всякий, кто рассматривает арифметические методы получения случайных цифр, разумеется, пребывает в состоянии греха (in a state of sin)». Цифровой компьютер — это строго детерминированный конечный автомат: при заданном начальном состоянии и инструкции каждый следующий бит предопределён на 100%. Тем не менее от моделирования методом Монте-Карло в ядерной физике и процедурной генерации миров в играх до ключей TLS, SSH и подписей ECDSA современная цивилизация потребляет триллионы случайных чисел каждую секунду.

Как жёсткий алгоритм может порождать непредсказуемость? И почему статистически безупречный генератор вроде вихря Мерсенна (MT19937) оказывается катастрофически уязвимым при генерации токенов сброса пароля, позволяя атакующему по 624 последовательным выходам на 100% предсказать все будущие и прошлые значения?

Глава 1: Математическая анатомия ГПСЧ ── Зерно (Seed), конечное пространство состояний и принцип Дирихле

Формально генератор псевдослучайных чисел (ГПСЧ / PRNG) — это детерминированный автомат $(\mathcal{S}, \mathcal{O}, f, g, s_0)$ с конечным внутренним пространством состояний $\mathcal{S}$ размера $|\mathcal{S}| = 2^b$, начальным зерном (Seed) $s_0 \in \mathcal{S}$, функцией перехода $f: \mathcal{S} \to \mathcal{S}$ и функцией вывода $g: \mathcal{S} \to \mathcal{O}$:

Как только зерно $s_0$ зафиксировано, вся последовательность $r_0, r_1, r_2, \dots$ полностью предопределена. Эта воспроизводимость бесценна при отладке научных расчётов. Однако по принципу Дирихле (Pigeonhole Principle) автомат неизбежно повторит одно из предыдущих состояний $s_{k+P} = s_k$ не более чем через $2^b$ шагов, замкнувшись в периодический цикл периода $P \le 2^b$.

  flowchart LR
    S0["Начальное зерно s0"] --> S1["Состояние s1 = f(s0)"]
    S1 --> S2["Состояние s2 = f(s1)"]
    S2 -. "Предпериод (Tail)" .-> Sk["Вход в цикл sk"]
    Sk --> Sk1["Состояние s(k+1)"]
    Sk1 -. "Периодический цикл P <= 2^b" .-> Skm1["Состояние s(k+P-1)"]
    Skm1 -- "f(s(k+P-1)) = sk" --> Sk

Предложенный фон Нейманом в 1949 году метод серединных квадратов (Middle-Square Method) (возведение $2k$-значного числа в квадрат и извлечение средних $2k$ цифр) без алгебраической структуры быстро вырождается в 0000 или короткие циклы длины 4.

Глава 2: Линейные конгруэнтные генераторы (LCG) и теорема Марсальи ── Трагедия 15 плоскостей IBM RANDU

В 1949 году Д. Г. Лемер предложил линейный конгруэнтный генератор (LCG): $X_{n+1} = (a X_n + c) \bmod m$. Согласно теореме Халла — Добелла (1962), LCG достигает полного периода $P = m$ тогда и только тогда, когда: (1) $\gcd(c, m) = 1$, (2) каждый простой делитель $p$ числа $m$ делит $a-1$, и (3) если $4 \mid m$, то $4 \mid (a-1)$.

В 1968 году статистик Джордж Марсалья (George Marsaglia) опубликовал знаменитую статью «Random numbers fall mainly in the planes», доказав, что $d$-мерные точки $(X_n, \dots, X_{n+d-1})$ любого LCG ложатся не более чем на $(d! \cdot m)^{1/d}$ параллельных гиперплоскостей кристаллической решётки!

Самым печально известным примером стал стандартный генератор RANDU корпорации IBM ($m = 2^{31}, c = 0, a = 65539 = 2^{16} + 3$) на мейнфреймах System/360:

Из-за тождества $X_{n+2} \equiv 6 X_{n+1} - 9 X_n \pmod{2^{31}}$ все 3D-точки RANDU в единичном кубе оказались заперты всего на 15 параллельных плоскостях с огромными пустыми промежутками, что исказило тысячи расчётов методом Монте-Карло в 1960–70-х годах!

Глава 3: Вихрь Мерсенна (MT19937) и современные статистические ГПСЧ (PCG64, Xoshiro256++)

В 1997 году японские математики Макото Мацумото и Такудзи Нисимура создали вихрь Мерсенна (MT19937) на основе скрученного обобщённого регистра сдвига с обратной связью (TGFSR) над полем $\mathbb{F}_2 = \{0, 1\}$ (стандарт в Python random, R, MATLAB, C++ std::mt19937):

1. Гигантский период и 623-мерная равномерность: Массив состояния из $624$ 32-битных слов ($19\,937$ активных бит) обеспечивает период, равный простому числу Мерсенна $P = 2^{19937} - 1 \approx 4{,}315 \times 10^{6001}$, и строгую равномерность распределения вплоть до размерности 623!
2. Закалка (Tempering): Перед выводом каждое слово состояния $x$ умножается на обратимую битовую матрицу $32\times 32$ над $\mathbb{F}_2$:

Чтобы преодолеть большой объём состояния MT19937 ($2{,}5\text{ КБ}$) и провал двух тестов на $\mathbb{F}_2$-линейность в пакете TestU01 (BigCrush), в 2010-х годах были созданы PCG64 (Мелисса О’Нил, 2014: 128-битный LCG с вращением битов, зависящим от данных; стандарт в NumPy) и Xoshiro256++ (Блэкман и Винья, 2018: 256-битное состояние с нелинейным скремблером; используется в Rust и Java), проходящие 100% тестов BigCrush.

Глава 4: Почему статистическое совершенство $\neq$ криптостойкость ── Взлом MT19937 по 624 выходам и КГПСЧ

4.1 Обращение Tempering: клонирование MT19937 по 624 выходам

Использование MT19937 для генерации токенов сессий или паролей — фатальная ошибка: каждый из четырёх шагов Tempering является обратимой линейной биекцией над $\mathbb{F}_2^{32}$ за время $O(1)$!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def untemper(z: int) -> int:
    # Invert MT19937 32-bit output z back to internal state word x in O(1)
    y3 = z ^ (z >> 18)
    y2 = y3 ^ ((y3 << 15) & 0xEFC60000)
    y1 = y2
    for _ in range(4):
        y1 = y2 ^ ((y1 << 7) & 0x9D2C5680)
    x = y1
    for _ in range(2):
        x = y1 ^ (x >> 11)
    return x & 0xFFFFFFFF

Атакующий, увидевший всего 624 последовательных 32-битных выхода ($2\,496\text{ байт}$) сервера на MT19937, применяет untemper(z) к каждому числу и на 100% восстанавливает внутренний массив из 624 слов! С этого момента он может со 100%-ной точностью предсказывать все будущие числа и вычислять прошлые.

4.2 Теорема Эндрю Яо (1982) и криптографически стойкие генераторы (КГПСЧ / CSPRNG)

В криптографии необходим криптографически стойкий ГПСЧ (CSPRNG), удовлетворяющий трём аксиомам:

1. Непредсказуемость следующего бита $\iff$ Вычислительная неотличимость (Теорема Яо, 1982 / Блюм — Микали): Никакой полиномиальный алгоритм $\mathcal{A}$, зная первые $k$ бит, не может угадать бит $r_{k+1}$ существенно лучше, чем подбрасыванием монеты ($1/2$):

2. Прямая секретность (Forward Secrecy / Защита от ретроспективного взлома): После каждой выдачи внутренний ключ немедленно перезаписывается односторонней функцией (Fast-Key-Erasure), поэтому даже при утечке текущего состояния невозможно восстановить прошлые ключи.
3. Обратная секретность (Backward Secrecy / Защита от предсказания): Периодическое подмешивание свежей аппаратной энтропии (Reseeding) восстанавливает безопасность после компрометации.

  flowchart TD
    subgraph Insecure ["Статистический ГПСЧ (LCG / MT19937 / Xoshiro)"]
        StateM["Внутреннее состояние s_i (624 слова)"] -- "Обратимый F2-линейный Tempering" --> OutM["Выход r_i"]
        OutM -- "untemper() клонирует состояние по 624 выходам!" --> StateM
    end
    subgraph Secure ["Криптостойкий КГПСЧ (ChaCha20 / AES-CTR_DRBG)"]
        Entropy["Аппаратные источники энтропии<br/>(Тепловой шум / RDSEED)"] -- "Периодический Reseeding (Backward Secrecy)" --> StateC["256-битный секретный ключ и счётчик"]
        StateC -- "Односторонний шифр (ChaCha20 / AES)<br/>[Обращение требует 2^256 операций!]" --> OutC["Криптостойкий поток r_i"]
        StateC -- "Fast-Key-Erasure Key' = PRF(Key)<br/>[Forward Secrecy!]" --> StateC_Next["Обновлённый ключ Key'"]
    end

Современные CSPRNG строятся на потоковых и блочных шифрах ChaCha20-RNG (ядро Linux, OpenBSD, Rust) и AES-CTR_DRBG (NIST SP 800-90A), либо на теоретико-числовой задаче факторизации в Blum-Blum-Shub ($x_{n+1} = x_n^2 \bmod M$). Напротив, стандартизированный NIST в 2006 году генератор на эллиптических кривых Dual_EC_DRBG содержал клептографический бэкдор АНБ (подтверждённый документами Сноудена в 2013 году: знание секретного дискретного логарифма $d$ в $P = d \cdot Q$ позволяло по 32 байтам выхода вычислить внутреннее состояние и расшифровать TLS-трафик).

Глава 5: Физические генераторы (TRNG), мин-энтропия ($H_\infty$) и пулы энтропии ОС

Начальное зерно CSPRNG поступает от аппаратных генераторов истинно случайных чисел (TRNG / HRNG), улавливающих физический хаос: тепловой шум Джонсона — Найквиста в проводниках, квантовый дробовой шум лавинного пробоя стабилитронов и фазовый джиттер кольцевых осцилляторов (инструкции RDSEED/RDRAND в процессорах Intel/AMD). В криптографии (NIST SP 800-90B) непредсказуемость в худшем случае оценивается через мин-энтропию ($H_\infty$), а не среднюю энтропию Шеннона $H_1$:

«Сырой» физический шум проходит отбеливание (Whitening) методом фон Неймана или криптографическими хеш-экстракторами (BLAKE2s в ядре Linux согласно Leftover Hash Lemma) перед подачей в CSPRNG.

В современном Linux (5.6+) /dev/random и /dev/urandom используют один и тот же ядерный CSPRNG на базе ChaCha20; разработчикам следует всегда вызывать getrandom(2) (или Python secrets, JS crypto.getRandomValues(), Rust OsRng/ThreadRng, Go crypto/rand). Катастрофа Debian OpenSSL 2008 года (CVE-2008-0166) — когда из-за закомментированной ради Valgrind строки энтропия всех генерируемых в мире ключей RSA/SSH на два года сжалась до 15-битного идентификатора процесса PID ($32\,768$ вариантов!) — и ошибка со статическим одноразовым числом $k$ в ECDSA на Sony PlayStation 3 (2010) напоминают железный закон: стойкость любой криптосистемы никогда не превышает энтропию генератора случайных чисел, создавшего её ключи.