Зачем компьютеру случайность

Компьютер — воплощение предсказуемости: одна и та же программа с одними входами даёт один и тот же результат. И всё же буквально каждую секунду он делает вид, что умеет бросать монетку: перемешивает очереди, раздаёт случайные порты, шифрует сессии, рандомизирует выборки в экспериментах. Откуда в идеально детерминированной машине берётся случайность — и почему «просто random()» подчас опасно?

Зачем случайность, если всё детерминировано

Без случайных чисел нельзя почти ничего из того, что мы считаем данностью:

Особенно показательно последнее: добавь в тесты немного «настоящего рандома» — и баги, зависящие от порядка, начинают вылезать. Случайность как инструмент неприятных сюрпризов для выявления неприятных сюрпризов.

Псевдо: почти случайно, но предсказуемо

Самый простой способ сделать «случайность» — взять формулу. Классика — линейный конгруэнтный генератор (LCG):

def lcg(seed, a=137, c=187, m=256):
    x = seed
    while True:
        x = (a * x + c) % m
        yield x

Последовательность выглядит случайной, но ровно настолько, насколько хватает воображения посмотреть одним глазом. Посмотрите на неё иначе: нарисуйте пары $(x_n,\ x_{n+1})$ для нашего маленького $m=256$ — все точки выстроились в строгие диагональные линии:

Это не рисунок — это структура генератора. Любая пара последовательных значений LCG лежит на одной из параллельных гиперплоскостей (Марсалья, «гиперплоскости Марсальи»). В 256 точках это милые диагонали — а в реальном 32-битном генераторе та же схема прячет ортогональную структуру, которую статистические тесты рано или поздно ловят. Псевдослучайность конечна и периодична — вопрос лишь в том, насколько период велик и насколько хорошо скрыта закономерность.

Самый позорный пример: генератор фон Неймана

Джон фон Нейман придумал «метод середины квадрата»: возьми число, возведи в квадрат, вырежи «середину» — и это новое число:

def middle_square(seed, digits=4):
    x = seed
    while True:
        s = str(x * x).zfill(8)
        x = int(s[2:6])
        yield x

Посмотрите, что происходит с последовательностью, если начать с 5432:

Она застревает на 2500. 5432 → 5066 → 6643 → … → 3500 → 2500 → 2500 → 2500 — «случайный» генератор ведёт себя так, будто у него кончилось вдохновение. Именно так выглядит плохой генератор: случайность в начале, труп в конце. Это поучительная история о том, почему генераторы проверяют статистически, а не глазами.

Настоящий хаос: откуда его берёт машина

Псевдослучайные генераторы — это детерминизм с большим периодом. Для криптографии этого мало: угадал seed — угадал всё. Настоящую случайность машина собирает из шума физического мира:

Intel/AMD RDRAND — аппаратный генератор на тепловых шумах транзисторов.

Циклические вариации таймингов — прерывания клавиатуры, перемещения мыши, сетевые пакеты, время между кешами.

Энтропийные пулы ядра — Linux копит перемешивающийся шум и «выдаёт» его через /dev/urandom и getrandom().

flowchart LR
    A[Физический шум · мышь · сеть · тайминги · чипы] --> B[Энтропийный пул ядра]
    B --> C[Аппаратный или ядерный шум mix]
    C --> D[CSPRNG · криптостойкий генератор]
    D --> E[Ключи · токены · nonce · соли]

Ключевой термин — CSPRNG (криптографически стойкий PRNG). Он смешивает реальную энтропию с детерминированным расширением: немного настоящего хаоса — и можно «раздуть» его в длинную непредсказуемую последовательность, не гоняя миллионы событий на каждый бит.

Почему seed — это и ключ

Любой PRNG детерминирован: одни и те же seed и сама функция дают одну и ту же последовательность. Это свойство — фича для симуляций (воспроизводимость эксперимента) и приговор для криптографии:

Правило простое: если результат «угадывается» — это не случайность. Угадал seed (а seed нередко числовой и маленький) — угадал и весь «случайный». Поэтому для ключей никогда не используют PRNG «как на симуляциях».

import secrets
token = secrets.token_hex(16)   # криптостойкий токен

а не random.randint(...), который при известном seed вычисляем.

Как отличить хороший генератор от плохого

Хороший PRNG проверяют статистически, и это целая наука — но три простых ориентира работают надёжно:

• Тест на равномерность — 100 000 чисел генератора должны равномерно заполнять диапазон (гистограмма без дыр).
• Тест на корреляцию — соседние числа не должны «склеиваться» в линии и плоскости (вспомним гиперплоскости Марсальи).
• Тест на период — последовательность не должна повториться слишком рано; у хорошего генератора период огромен.

Забавно, что идеального консенсуса между «случайностью» и «проверяемостью» не бывает: мы умеем определять «сюрпризность» только статистически, а значит, злодея из числа псевдослучайных не поймаешь одним взглядом — только набором тестов. Именно поэтому криптография полагается не на «странный на вид» шум, а на строго определённые CSPRNG.

Итог

• Компьютер детерминирован, поэтому случайность в нём — либо модель (PRNG), либо заимствованный физический шум (энтропия)
• Псевдослучайные генераторы периодичны и структурны — гиперплоскости Марсальи видны даже глазами
• Плохой генератор может выглядеть случайным, а «застрять» на одной точке (метод середины квадрата — классика)
• Для криптографии используют CSPRNG на энтропии ядра или железа — детерминированный random() туда не годится
• Seed — это ключ: известен seed — вычисляемы все «случайные» числа
• Сим-сим: мало настоящего хаоса, а хороший генератор «раздувает» его в длинную непредсказуемую последовательность

В следующий раз, когда код напишет x = rand() % 100, вспомните: это не бросок монетки. Это детерминированная формула, у которой кончилось воображение где-то в гиперплоскостях. Настоящая случайность так не выглядит — но именно поэтому она так дорога.