Генерация случайных чисел: методы и применение

Генерация случайных чисел — это фундаментальный процесс в информатике и криптографии, обеспечивающий создание непредсказуемых последовательностей. От защиты данных до компьютерного моделирования, случайные числа играют критическую роль в современных технологиях. Разберёмся, как работают различные методы генерации и где они применяются.

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

Различные применения случайности привели к развитию разных методов генерации случайных данных. Некоторые из них известны с древних времён: бросание костей, подбрасывание монет, тасование карт, использование палочек ярроу в И Цзин (гадании), и множество других техник. Из-за механической природы этих методов создание больших количеств достаточно случайных чисел (важное в статистике) требовало значительных усилий и времени. Поэтому результаты часто собирались и распространялись в виде таблиц случайных чисел.

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

Практические применения

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

Генераторы псевдослучайных чисел очень полезны при разработке симуляций методом Монте-Карло (Monte Carlo), так как отладка облегчается возможностью повторного запуска одной и той же последовательности случайных чисел, начиная с одного и того же начального значения. Они также используются в криптографии — при условии, что начальное значение остаётся секретным. Отправитель и получатель могут автоматически генерировать одинаковый набор чисел для использования в качестве ключей.

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

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

Истинные и псевдослучайные числа

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

Скорость получения энтропии из естественных источников зависит от измеряемых физических явлений. Таким образом, источники естественной энтропии называют блокирующими — они ограничены по скорости до накопления достаточной энтропии. На некоторых Unix-подобных системах, включая большинство дистрибутивов Linux, псевдоустройство /dev/random будет блокироваться до накопления достаточной энтропии из окружения. Из-за этого поведения большие операции чтения из /dev/random, такие как заполнение жёсткого диска случайными битами, могут быть медленными на системах, использующих этот тип источника энтропии.

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

Стандартные криптографические конструкции используют гибридный подход, применяя энтропию из естественных источников для инициализации криптографически стойких генераторов псевдослучайных чисел (КСПСГ). Аппаратные генераторы случайных чисел обычно производят ограниченное количество случайных битов в секунду. Чтобы увеличить доступную скорость вывода, они часто используются для генерации начального значения более быстрого ПСГ. ПСГ также помогает с «анонимизацией» источника шума и извлечением энтропии. При выборе надлежащего алгоритма ПСГ (криптографически стойкого генератора псевдослучайных чисел) комбинация может удовлетворять требованиям стандартов Federal Information Processing Standards и Common Criteria.

Методы генерации

Физические методы

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

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

Аппаратный генератор случайных чисел должен выдавать почти идеальные случайные числа («полная энтропия»). Физический процесс обычно не обладает этим свойством, и практический АГСЧ обычно включает несколько блоков:

• источник шума, реализующий физический процесс, производящий энтропию. Обычно этот процесс аналоговый, поэтому используется цифровой преобразователь для преобразования выхода аналогового источника в двоичное представление;
• кондиционер (экстрактор случайности), улучшающий качество случайных битов;
• тесты здоровья. АГСЧ в основном используются в криптографических алгоритмах, которые полностью нарушаются, если случайные числа имеют низкую энтропию, поэтому функция тестирования обычно включена.

Вычислительные методы

По соображениям производительности и безопасности большинство генераторов случайных чисел используют ПСГ в своей конструкции (эта архитектура фактически предписана промышленными стандартами, такими как NIST SP 800-90A).

Генератор псевдослучайных чисел (ПСГ), также известный как детерминированный генератор случайных битов (ДГСБ), — это алгоритм для генерации последовательности чисел, свойства которых приблизительно соответствуют свойствам последовательностей случайных чисел. Последовательность, генерируемая ПСГ, не является истинно случайной, потому что она полностью определяется начальным значением, называемым начальным значением ПСГ (которое может включать истинно случайные значения). Хотя последовательности, более близкие к истинно случайным, могут быть сгенерированы с использованием аппаратных генераторов случайных чисел, генераторы псевдослучайных чисел важны на практике благодаря скорости генерации чисел и их воспроизводимости.

ПСГ являются центральными в приложениях, таких как симуляции (например, для метода Монте-Карло), электронные игры (например, для процедурной генерации) и криптография. Криптографические приложения требуют, чтобы выход был непредсказуем из предыдущих выходов, и необходимы более сложные алгоритмы, которые не наследуют линейность более простых ПСГ.

Хорошие статистические свойства — центральное требование для выхода ПСГ. В целом, требуется тщательный математический анализ, чтобы иметь какую-либо уверенность в том, что ПСГ генерирует числа, достаточно близкие к случайным для предполагаемого использования. Джон фон Нейман (John von Neumann) предостерегал от неправильного толкования ПСГ как истинно случайного генератора, шутя, что «Тот, кто рассматривает арифметические методы производства случайных цифр, конечно же, находится в состоянии греха».

Людьми

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

Постобработка и статистические проверки

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

Генерируемые случайные числа иногда подвергаются статистическим тестам перед использованием, чтобы убедиться, что базовый источник всё ещё работает, а затем постобрабатываются для улучшения их статистических свойств. Примером может служить аппаратный генератор случайных чисел TRNG9803, который использует измерение энтропии в качестве аппаратного теста, а затем постобрабатывает случайную последовательность с помощью потокового шифра со сдвиговым регистром. Обычно сложно использовать статистические тесты для проверки сгенерированных случайных чисел. Ван и Никол предложили технику статистического тестирования на основе расстояния, которая используется для выявления слабостей нескольких генераторов случайных чисел. Ли и Ван предложили метод тестирования случайных чисел на основе источников хаотической энтропии лазера, используя свойства броуновского движения.

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

Другие соображения

Изменение распределения

Равномерные распределения

Большинство генераторов случайных чисел работают с целыми числами или отдельными битами, поэтому требуется дополнительный шаг для достижения канонического равномерного распределения между 0 и 1. Реализация не так тривиальна, как деление целого числа на его максимальное возможное значение. Конкретно:

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

Основной алгоритм, используемый OpenJDK, Rust и NumPy, описан в предложении для C++ STL. Он не использует дополнительную точность и страдает от смещения только в последнем бите из-за округления половины к чётному. Другие численные соображения оправданы при сдвиге этого канонического равномерного распределения в другой диапазон. Предложенный метод для языка программирования Swift утверждает, что использует полную точность везде.

Равномерно распределённые целые числа обычно используются в алгоритмах, таких как тасование Фишера-Йетса (Fisher–Yates shuffle). Опять же, наивная реализация может внести смещение модуля в результат, поэтому должны использоваться более сложные алгоритмы. Метод, который почти никогда не выполняет деление, был описан в 2018 году Даниэлем Лемиром (Daniel Lemire), с текущим передовым методом, являющимся вдохновлённым арифметическим кодированием оптимальным алгоритмом 2021 года Стивена Кэнона (Stephen Canon) из Apple Inc.

Большинство генераторов от 0 до 1 включают 0, но исключают 1, в то время как другие включают или исключают оба.

Другие распределения

Учитывая источник равномерно распределённых случайных чисел, существует несколько методов для создания нового источника случайных чисел, соответствующего функции плотности вероятности. Один метод, называемый методом инверсии, включает интегрирование до площади, большей или равной случайному числу (которое должно быть сгенерировано между 0 и 1 для надлежащих распределений). Второй метод, называемый методом принятия-отклонения, включает выбор значений x и y и проверку того, больше ли функция x значения y. Если это так, значение x принимается. В противном случае значение x отклоняется и алгоритм повторяется.

В качестве примера выборки отклонения для генерации пары статистически независимых стандартно нормально распределённых случайных чисел (x, y) можно сначала сгенерировать полярные координаты (r, θ), где r~χ и θ~UNIFORM(0,2π) (см. преобразование Бокса-Мюллера (Box–Muller transform)).

Отбеливание

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

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

Последовательности с низкой дискрепантностью как альтернатива

Некоторые вычисления, использующие генератор случайных чисел, можно резюмировать как вычисление общего или среднего значения, такого как вычисление интегралов методом Монте-Карло. Для таких задач может быть возможно найти более точное решение, используя так называемые последовательности с низкой дискрепантностью, также называемые квазислучайными числами. Такие последовательности имеют определённый паттерн, который равномерно заполняет пробелы; истинно случайная последовательность может и обычно оставляет более крупные пробелы.

Задние ходы

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

Сообщается, что АНБ (NSA) вставило задний ход в сертифицированный NIST криптографически стойкий генератор псевдослучайных чисел Dual EC DRBG. Если, например, SSL-соединение создано с использованием этого генератора случайных чисел, то, по словам Мэтью Грина (Matthew Green), это позволило бы АНБ определить состояние генератора случайных чисел и, таким образом, в конечном итоге иметь возможность читать все данные, отправляемые по SSL-соединению. Хотя было очевидно, что Dual EC DRBG был очень плохим и, возможно, имел задний ход генератором псевдослучайных чисел задолго до подтверждения заднего хода АНБ в 2013 году, он получил значительное практическое применение до 2013 года, например, компанией RSA Security. Впоследствии были высказаны обвинения в том, что RSA Security сознательно вставила задний ход АНБ в свои продукты, возможно, в рамках программы Bullrun. RSA отрицает сознательное внедрение заднего хода в свои продукты.

Также было высказано предположение, что аппаратные генераторы случайных чисел могут быть тайно модифицированы, чтобы иметь меньше энтропии, чем указано, что сделает шифрование с использованием аппаратного генератора уязвимым для атак. Один опубликованный метод работает путём изменения маски примеси чипа, что было бы невозможно обнаружить при оптическом обратном проектировании. Например, для генерации случайных чисел в Linux считается неприемлемым использовать аппаратный генератор RDRAND от Intel без смешивания выхода RDRAND с другими источниками энтропии для противодействия любым задним ходам в аппаратном генераторе, особенно после раскрытия программы АНБ Bullrun.

В 2010 году розыгрыш американской лотереи был сфальсифицирован директором по информационной безопасности Ассоциации многогосударственной лотереи (MUSL), который тайно установил вредоносное ПО с задним ходом на защищённый компьютер генератора случайных чисел MUSL во время плановой профилактики. Во время взломов мужчина выиграл в общей сложности 16 500 000 долларов в течение нескольких лет.

Генерация случайных чисел: истинные и псевдослучайные генераторы