Введение
Алгоритм, генерирующий приближение последовательности случайных чисел. Псевдослучайный генератор чисел (PRNG), также известный как детерминированный генератор случайных бит (DRBG), — это алгоритм для генерации последовательности чисел, свойства которых аппроксимируют свойства последовательностей случайных чисел. Последовательность, генерируемая PRNG, не является истинно случайной, поскольку она полностью определяется начальным значением, называемым начальным зерном PRNG (которое может включать в себя истинно случайные значения). Хотя последовательности, более близкие к истинно случайным, могут быть получены с использованием аппаратных генераторов случайных чисел, псевдослучайные генераторы чисел важны на практике благодаря скорости генерации чисел и их воспроизводимости. PRNG играют центральную роль в таких областях применения, как моделирование (например, для метода Монте-Карло), электронные игры (например, для процедурной генерации) и криптография. Криптографические приложения требуют, чтобы выходные данные не были предсказуемыми на основе предыдущих выходных данных, и для этого требуются более сложные алгоритмы, не наследующие линейность более простых PRNG. Хорошие статистические свойства являются ключевым требованием к выходным данным PRNG. Как правило, необходим тщательный математический анализ, чтобы убедиться, что PRNG генерирует числа, достаточно близкие к случайным для предполагаемого использования. Джон фон Нейман предостерегал от неверной интерпретации PRNG как истинно случайного генератора, шутя, что «любой, кто рассматривает арифметические методы получения случайных цифр, конечно, совершает грех».
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed (which may include truly random values). Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom number generators are important in practice for their speed in number generation and their reproducibility. PRNGs are central in applications such as simulations (e. g. for the Monte Carlo method), electronic games (e. g. for procedural generation), and cryptography. Cryptographic applications require the output not to be predictable from earlier outputs, and more elaborate algorithms, which do not inherit the linearity of simpler PRNGs, are needed. Good statistical properties are a central requirement for the output of a PRNG. In general, careful mathematical analysis is required to have any confidence that a PRNG generates numbers that are sufficiently close to random to suit the intended use. John von Neumann cautioned about the misinterpretation of a PRNG as a truly random generator, joking that "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."
генераторы, основанные на линейных рецидивах
Во второй половине 20-го века стандартный класс алгоритмов, используемых для PRNG, включал линейные конгруэнтные генераторы. Известно, что качество LCG было недостаточным, но более совершенные методы были недоступны. Пресс и др. (2007) описали это следующим образом: «Если бы все научные работы, результаты которых поставлены под сомнение из-за [ЛКГ и связанных с ними], исчезли из библиотечных полок, на каждой полке образовалась бы пустота размером с кулак». Значительным прогрессом в создании псевдослучайных генераторов стало внедрение методов, основанных на линейных рекурренциях в поле из двух элементов; такие генераторы связаны с линейными регистрами сдвига с обратной связью. Изобретение в 1997 году генератора Mersenne Twister, в частности, позволило избежать многих проблем, присущих более ранним генераторам. Mersenne Twister имеет период в 2<sup>19937</sup> − 1 итераций (≈ 4,3), доказано, что он равномерно распределен в (до) 623 измерений (для 32-битных значений), и на момент его появления работал быстрее, чем другие статистически обоснованные генераторы. В 2003 году Джордж Марсалья представил семейство генераторов xorshift, также основанных на линейной рекурренции. Такие генераторы чрезвычайно быстры и, в сочетании с нелинейной операцией, успешно проходят строгие статистические тесты. В 2006 году было разработано семейство генераторов WELL. Генераторы WELL в некоторой степени улучшают качество Mersenne Twister, который характеризуется слишком большим пространством состояний и очень медленным восстановлением из пространств состояний с большим количеством нулей.
Критерии оценки СКБ
Федеральное управление по информационной безопасности Германии (Bundesamt für Sicherheit in der Informationstechnik, BSI) установило четыре критерия качества детерминированных генераторов случайных чисел. Они обобщены здесь:
K1 – Должна быть высокая вероятность того, что генерируемые последовательности случайных чисел различны друг от друга. K2 – Последовательность чисел не должна отличаться от "истинно случайных" чисел согласно заданным статистическим тестам. Эти тесты включают: монобитный тест (равное количество единиц и нулей в последовательности), покерный тест (частный случай теста хи-квадрат), тест серий (подсчитывает частоту серий различной длины), тест длинных серий (проверяет наличие серий длиной 34 или более в 20 000 битах последовательности) – как разработанные BSI, так и тест автокорреляции. По сути, эти требования проверяют, насколько хорошо битовая последовательность: содержит нули и единицы с одинаковой частотой; после последовательности из n нулей (или единиц) следующий бит является единицей (или нулем) с вероятностью 1/2; и любая выбранная подпоследовательность не предоставляет информации о последующих элементах последовательности. K3 – Для злоумышленника (в практическом плане) должно быть невозможно вычислить или иным образом угадать какие-либо предыдущие или будущие значения последовательности, а также любое внутреннее состояние генератора, имея любую заданную подпоследовательность. K4 – В практическом плане злоумышленнику должно быть невозможно вычислить или угадать какие-либо предыдущие числа последовательности или предыдущие внутренние состояния генератора, зная внутреннее состояние генератора. Для криптографических приложений допустимы только генераторы, соответствующие критериям K3 или K4.
Ранние подходы
Ранний компьютерный генератор псевдослучайных чисел (PRNG), предложенный Джоном фон Нейманом в 1946 году, известен как метод среднего квадрата. Алгоритм следующий: возьмите любое число, возведите его в квадрат, извлеките средние цифры полученного числа в качестве "случайного числа", а затем используйте это число как начальное значение для следующей итерации. Например, возведение в квадрат числа "1111" дает "1234321", которое можно записать как "01234321" – восьмизначное число, являющееся квадратом четырехзначного числа. Это дает "2343" в качестве "случайного" числа. Повторение этой процедуры дает "4896" в качестве следующего результата и так далее. Фон Нейман использовал десятизначные числа, но процесс оставался тем же. Проблема метода "среднего квадрата" заключается в том, что все последовательности в конечном итоге повторяются, некоторые – очень быстро, например, "0000". Фон Нейман был осведомлен об этом, но считал этот подход достаточным для своих целей и опасался, что математические "исправления" просто скроют ошибки, а не устранят их. Фон Нейман счел аппаратные генераторы случайных чисел непригодными, поскольку, если они не записывали генерируемый результат, их нельзя было бы впоследствии проверить на наличие ошибок. Если бы они записывали свой результат, они бы исчерпали ограниченную память компьютера, доступную в то время, а следовательно, и способность компьютера читать и записывать числа. Если бы числа записывались на перфокарты, то их запись и чтение заняли бы значительно больше времени. На компьютере ENIAC, который он использовал, метод "среднего квадрата" генерировал числа примерно в сто раз быстрее, чем считывание чисел с перфокарт. С тех пор метод среднего квадрата был заменен более сложными генераторами. Недавним нововведением стало объединение метода среднего квадрата с последовательностью Вейля. Этот метод обеспечивает получение высококачественных результатов в течение длительного периода (см. метод среднего квадрата).