Как компьютеры выбирают «случайные» числа? Магия рандома

Мы любим её в играх и научных экспериментах. Речь о случайности, конечно. Но вот незадача: в мире компьютеров чистая случайность — это (почти) миф. Когда вы просите компьютер выбрать случайное число, он подходит к задаче с удивительной изобретательностью, но без спонтанности. Заинтригованы? 

Давайте разберемся, как же всё-таки работает этот «случайный» выбор в машинах, которые не умеют играть в «угадай, какое число я загадал». И как случайно сгенерированный пароль можно… восстановить! 

Случайность? Не в моём алгоритме!

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

Псевдослучайные числа

Основной инструмент в арсенале компьютера для создания иллюзии случайности — это псевдослучайный генератор чисел (ПСЧГ). 

Этот алгоритм берет начальное значение (известное как «семя» или seed) и применяет к нему серию математических операций для генерации числа, которое выглядит для нас случайным.

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

В этом году мы все порадовались за мужчину, который более 10 лет назад положил на свой криптокошелек несколько биткоинов, защитил его случайным паролем, а потом... забыл его. За это время стоимость биткоина выросла многократно. Обидно? Да. Но мужчину спасли хакеры. 

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

За мужчину радостно. А вот за безопасность обидно.

• Предсказуемость. Если «семя» для генератора псевдослучайных чисел известно или может быть предсказано, результаты генерации тоже становятся предсказуемыми. Это очень критично в криптографии, где от уникальности и «случайности» ключей зависит безопасность.

• Временные метки. Системные часы компьютеров могут быть относительно доступны или предсказаны на основе анализа контекста (например, из логов серверов, метаданных файлов и т.д.).

Так что в идеале для криптографических приложений следует использовать источники аппаратной случайности, которые генерируют числа на основе непредсказуемых физических процессов.

И это возвращает нас обратно к теме случайных чисел.

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

Алгоритмов для генерации псевдослучайных чисел несколько. Их выбор зависит от нужной степени «случайности» и предназначения чисел. 

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

Сейчас объясним сложное простым языком, чтобы был повод удивить ребёнка и даже друзей.

Линейный конгруэнтный метод 

• Начальное число («семя») — стартовая точка, от которой всё начинается. Можно выбрать любое число, и оно определяет всю последующую последовательность чисел.

• Множитель (a) — это число, на которое мы умножаем наше текущее число.

• Приращение (с) — это число, которое мы добавляем после умножения.

• Модуль (m) — это число, которое определяет «рамки» для нашей последовательности. Когда наше новое число достигает этого значения или превышает его, мы начинаем считать сначала (так же, как часы начинают отсчет заново после 12). 

Внимание: формула, которая может напугать.

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

Вихрь Мерсенна

Как это работает?

1. Наш воображаемый шкаф Мерсенна содержит большой список (или массив) из сотен чисел. Начинаем мы с того, что заполняем этот список начальными числами, которые называются «семенами».

2. Теперь берем особую математическую формулу MT19937, чтобы «перемешать» числа в этом списке таким образом, чтобы они выглядели совершенно случайными. Формула берет одно число из списка, сочетает его с другими числами по определенным правилам и создает новое число, которое заменяет одно из старых. Что за формула? Вот тут простым языком уже не получится: в ход идёт темперирование каждого значения массива, битовые сдвиги и битовые операции.

3. Одна из особенностей «Вихря» в том, что алгоритм может создать просто огромное количество чисел, прежде чем начнёт повторяться. 

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

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

Настоящая случайность из виртуальной реальности

Для задач, где требуется настоящая случайность (например, в криптографии), компьютеры могут использовать генераторы аппаратных случайных чисел. Эти устройства генерируют числа, исходя из непредсказуемых физических процессов, таких как радиоактивный распад или тепловой шум. Эти числа действительно случайны, но генерировать их сложнее и дороже.

Хаос в мире порядка

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

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