Как компьютер генерирует «случайные» числа

Компьютер — самый дисциплинированный исполнитель на свете: он всегда делает ровно то, что ему сказали, и ни шагом в сторону. Так откуда же берётся случайность, когда игра кидает кубик, музыка включается «вперемешку», а сайт выдаёт тебе непредсказуемый пароль? Сейчас разберёмся — и окажется, что почти вся «случайность» вокруг тебя на самом деле строго рассчитана.

Почему компьютеру так трудно быть случайным

Представь робота, который умеет идеально печь печенье по рецепту. Дай ему одни и те же ингредиенты и одну и ту же инструкцию — он каждый раз выдаст абсолютно одинаковое печенье. В этом вся суть компьютера: он детерминированная машина. Это умное слово означает простую вещь: при одинаковых входных данных он всегда даёт одинаковый результат.

А теперь попроси этого робота «придумать что-нибудь случайное». Он растеряется. У него нет ни интуиции, ни настроения, ни подброшенной монетки. Всё, что он умеет, — выполнять арифметику: складывать, умножать, делить с остатком. Из чистой арифметики получить настоящую случайность невозможно: формула, которую ты вычислишь дважды, дважды даст один и тот же ответ.

Поэтому программисты пошли на хитрость. Раз настоящей случайности взять негде, давай сделаем числа, которые выглядят случайными, хотя на самом деле получены по строгой формуле. Такие числа называют псевдослучайными — то есть «как бы случайными».

Генератор, который притворяется хаосом

Программа, которая выдаёт такие числа, называется генератором псевдослучайных чисел (по-английски сокращают до PRNG). Работает он на удивление просто. Берётся стартовое число, к нему применяется хитрая формула, получается новое число — оно и есть первый «случайный» результат. Затем эта же формула применяется уже к нему, рождается следующее число, и так далее. Получается длинная цепочка, в которой каждое звено вычислено из предыдущего.

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

Псевдослучайные числа — это не хаос. Это очень-очень запутанный порядок, который человеческий глаз не в силах распутать.

Если выписать такую цепочку, она выглядит как полная неразбериха: 7, 142, 33, 198, 5... Никакого ритма, никакого узора. Но стоит запустить ту же формулу с тем же стартом ещё раз — и ты получишь ровно ту же последовательность, число в число. Хаос только притворяется хаосом.

Магическое слово «seed»

То самое стартовое число называют seed — по-английски «зерно» или «семя». И это не случайное слово: из одного зёрнышка всегда вырастает одно и то же «дерево» чисел. Поменяешь зерно — вырастет совсем другая последовательность.

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

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

• в играх — чтобы сгенерировать один и тот же мир по «коду уровня» (как seed-карты в Minecraft);
• при тестировании программ — чтобы баг, вызванный «случайными» данными, можно было воспроизвести снова и снова;
• в науке — чтобы другой исследователь мог повторить твой эксперимент с теми же числами.

Получается, управляемая случайность иногда ценнее настоящей.

Когда «как бы случайно» — это опасно

Для игр и перемешивания плейлиста псевдослучайности хватает за глаза. Но представь, что сайт банка создаёт тебе пароль или секретный ключ с помощью обычного генератора, у которого зерно — это текущее время. Если злоумышленник примерно знает, когда ты регистрировался, он может перебрать все возможные зёрна за нужную секунду и вычислить твой «случайный» ключ. Вся защита рассыпается.

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

Откуда? Операционная система потихоньку собирает энтропию — крошечные непредсказуемые шумы реальности: микрозадержки между нажатиями твоих клавиш, дрожание движений мышки, моменты прихода сетевых пакетов, тепловой шум внутри самого процессора. По отдельности это мелочь, но вместе они дают по-настоящему непредсказуемое зерно, которое невозможно угадать или повторить.

Есть и совсем экзотика. Некоторые компании ради генерации настоящих случайных чисел снимают на видеокамеры стену из десятков лавовых ламп: пузыри в них колышутся по законам физики, и предсказать их форму нельзя в принципе. Кадр с этими разводами превращают в числа — вот тебе и кусочек живого хаоса для криптографии.

Так это случайность или нет?

Подведём итог. Почти всё, что компьютер называет «случайным», — это псевдослучайность: красиво запутанная, но строго вычисленная по формуле последовательность, выросшая из одного зерна. Её легко получить, легко повторить, и для игр, симуляций и перемешивания она идеальна.

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