Что такое генератор случайных чисел?
Генератор случайных чисел (RNG) — это система, которая выдает случайные или псевдослучайные числа. Можно ли на самом деле предсказать следующее число, зависит от типа генератора. Одни генераторы опираются на физический процесс, другие вычисляют числа по алгоритму, а некоторые алгоритмы устроены так, что даже тот, кто видел их результаты, не может предсказать, что будет дальше. Выглядеть случайным и быть непредсказуемым — разные свойства, и большая часть этой статьи посвящена разнице между ними.
Аппаратные генераторы случайных чисел
Аппаратный генератор случайных чисел (HRNG), который называют также генератором истинно случайных чисел (TRNG), получает случайные значения из физического процесса. Самые старые такие генераторы можно увидеть своими глазами: подброшенная монета, брошенный игральный кубик, колесо рулетки. Механика описывает каждый из них полностью, и все же хорошо сделанное колесо на практике непредсказуемо: крошечные различия в том, как начинается каждое вращение, вырастают в совершенно разные исходы.
Современные аппаратные генераторы измеряют микроскопические явления: дробовой и тепловой шум в электронных схемах, атмосферный шум, квантовые эффекты. Это хорошие источники энтропии — непредсказуемости, которую можно измерить, — но физический источник не идеален по своей природе: он может давать смещенные результаты, меняться со временем и выходить из строя. Поэтому его качество нужно оценивать и контролировать, а результаты при необходимости дополнительно обрабатывать — именно это описывают стандарты вроде NIST SP 800-90B. Аппаратные источники используют там, где гарантия важнее всего, — прежде всего в криптографии, где они дают непредсказуемый исходный материал для ключей, на которых держатся такие протоколы, как Transport Layer Security (TLS).
Генераторы псевдослучайных чисел
Альтернатива физическому устройству — алгоритм. Генератор псевдослучайных чисел (PRNG) выдает последовательность, которая выглядит случайной, но полностью определяется начальным значением (seed). Дайте одному и тому же алгоритму одно и то же начальное значение — и каждый раз получите одну и ту же последовательность. Это недостаток, когда результат должен быть непредсказуемым, а начальное значение или внутреннее состояние можно угадать или восстановить, и преимущество, когда результат должен быть воспроизводимым: моделирование или тест можно в точности повторить. Кроме того, PRNG быстры, дешевы и просты в реализации, поэтому на них полагается большинство программ. Среди известных алгоритмов — линейный конгруэнтный генератор (LCG), генераторы xorshift и вихрь Мерсенна.
Вихрь Мерсенна
Вихрь Мерсенна, опубликованный в 1997 году Макото Мацумото и Такудзи Нисимурой, — один из самых распространенных генераторов псевдослучайных чисел; во многих языках программирования он используется по умолчанию. Название он получил от своего периода — длины последовательности до ее повторения: в стандартном варианте, MT19937, это простое число Мерсенна 219937 − 1. Он проходит большинство статистических тестов на случайность и хорошо подходит для моделирования. Однако он не создавался для того, чтобы хранить секреты: по 624 последовательным 32-битным значениям кто угодно может восстановить его внутреннее состояние и предсказать все следующие значения, поэтому его нельзя использовать для ключей, паролей и всего остального, что должно оставаться непредсказуемым.
Криптографически стойкие генераторы и энтропия
Многим приложениям нужно и то и другое сразу: скорость алгоритма и непредсказуемость физического источника. Решение — криптографически стойкий генератор псевдослучайных чисел (CSPRNG). Это по-прежнему PRNG, но построенный так, что по части его результатов практически невозможно предсказать остальные; начальное значение он получает и регулярно обновляет из источника настоящей энтропии. Начальное значение из физического источника не делает обычный PRNG стойким: для этого должен быть специально разработан сам алгоритм. Физический источник, например тепловой шум или интервалы между аппаратными событиями, дает небольшое количество истинной случайности, а CSPRNG превращает ее в длинную последовательность значений и выдает их гораздо быстрее. Именно такое сочетание операционная система предоставляет работающим в ней программам, и именно его сегодня на практике обычно называют «генератором случайных чисел». Такой генератор создает ключи шифрования, токены сеансов и пароли.
Случайные числа в браузере
JavaScript дает веб-странице два встроенных способа получить случайные значения, и они относятся к разным классам. Math.random() — обычный PRNG: стандарт языка JavaScript оставляет выбор алгоритма за каждым браузером и ничего не обещает в отношении безопасности. Для анимации этого достаточно, для розыгрыша, результат которого кто-то может оспорить, — нет. Второй способ — Web Crypto API. Его метод crypto.getRandomValues() возвращает криптографически стойкие случайные значения, которые выдает CSPRNG, получающий начальное значение из энтропии операционной системы.
Наш онлайн-генератор случайных чисел обращается к Web Crypto API при каждой генерации, и числа создаются в вашем браузере, а не на сервере. Тот же источник случайности используют и другие генераторы этого сайта — бросаете ли вы кубики, подбрасываете монетку или генерируете пароль.
От случайных битов к числу из вашего диапазона
Криптографически стойкий генератор — только половина честного розыгрыша. Он выдает необработанные биты, а программе еще нужно превратить их в число из вашего диапазона — и здесь может закрасться смещение. Допустим, источник с равной вероятностью выдает значения от 0 до 9, а вам нужно число от 0 до 5. Взять остаток от деления на 6 кажется естественным, но тогда 0, 1, 2 и 3 могут выпасть двумя способами каждое, а 4 и 5 — только одним, поэтому у каждого из чисел от 0 до 3 вероятность 20%, а у 4 и 5 — только по 10%. Один из способов убрать смещение — отбрасывать неподходящие значения и получать новые; подробнее об этом — в материалах о генераторе случайных чисел.
Еще две вещи часто удивляют людей в сгенерированных значениях. Повторы — это нормально: когда целое число от 1 до 10 выбирается независимо и все числа равновероятны, только что выпавшее число имеет тот же шанс 1 из 10 выпасть снова, что и любое другое. Розыгрыш без повторений — это другой вид розыгрыша, а не более случайный. И честный генератор сам по себе не делает честной всю процедуру: список участников и число попыток значат не меньше, о чем рассказывает наша статья о том, как выбрать случайного победителя конкурса.