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

Алгоритм, который генерирует приближение случайной числовой последовательности

Генератор псевдослучайных чисел ( PRNG ), также известный как детерминированный генератор случайных битов ( DRBG ), ^[1] представляет собой алгоритм для генерации последовательности чисел, свойства которой приближаются к свойствам последовательностей случайных чисел . Последовательность, сгенерированная PRNG, не является истинно случайной , поскольку она полностью определяется начальным значением, называемым семенем PRNG (которое может включать истинно случайные значения). Хотя последовательности, которые ближе к истинно случайным, могут быть сгенерированы с помощью аппаратных генераторов случайных чисел , генераторы псевдослучайных чисел важны на практике из-за их скорости генерации чисел и их воспроизводимости. ^[2]

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

Хорошие статистические свойства являются центральным требованием к выходу PRNG. В общем, требуется тщательный математический анализ, чтобы иметь уверенность в том, что PRNG генерирует числа, которые достаточно близки к случайным, чтобы соответствовать предполагаемому использованию. Джон фон Нейман предостерегал от неправильного толкования PRNG как действительно случайного генератора, шутя, что «Любой, кто рассматривает арифметические методы получения случайных цифр, конечно, находится в состоянии греха». ^[3]

Возможные проблемы

На практике выходные данные многих распространенных PRNG демонстрируют артефакты , из-за которых они не проходят статистические тесты на обнаружение закономерностей. К ним относятся:

• Более короткие, чем ожидалось, периоды для некоторых исходных состояний (такие исходные состояния можно назвать «слабыми» в этом контексте);
• Отсутствие равномерности распределения больших объемов генерируемых чисел;
• Корреляция последовательных значений;
• Плохое размерное распределение выходной последовательности;
• Расстояния между точками, где встречаются определенные значения, распределены иначе, чем в случайном последовательном распределении.

Дефекты, демонстрируемые неисправными PRNG, варьируются от незаметных (и неизвестных) до очень очевидных. Примером может служить алгоритм случайных чисел RANDU , который десятилетиями использовался на мэйнфреймах . Он имел серьезные недостатки, но его неадекватность оставалась незамеченной в течение очень долгого времени.

Во многих областях исследовательская работа до 21-го века, которая опиралась на случайный выбор или моделирование Монте-Карло , или иным образом опиралась на PRNG, была гораздо менее надежной, чем идеальная, в результате использования PRNG низкого качества. ^[4] Даже сегодня иногда требуется осторожность, как показано в следующем предупреждении в Международной энциклопедии статистической науки (2010). ^[5]

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

В качестве иллюстрации рассмотрим широко используемый язык программирования Java . До 2020 года Java по-прежнему полагалась на линейный конгруэнтный генератор (LCG) для своего PRNG, ^{[6] [7]} , который имеет низкое качество (см. далее ниже). Поддержка Java была улучшена с Java 17 .

Одним из известных ГПСЧ, избежавших серьезных проблем и по-прежнему работавших довольно быстро, является Вихрь Мерсенна (обсуждается ниже), опубликованный в 1998 году. Другие ГПСЧ более высокого качества, как с точки зрения вычислительной, так и статистической производительности, были разработаны до и после этой даты; их можно найти в Списке генераторов псевдослучайных чисел .

Генераторы на основе линейных рекуррент

Во второй половине 20-го века стандартный класс алгоритмов, используемых для PRNG, включал линейные конгруэнтные генераторы . Качество LCG было известно как неадекватное, но лучших методов не было. Пресс и др. (2007) описали результат следующим образом: «Если бы все научные статьи, результаты которых сомнительны из-за [LCG и связанных с ними], исчезли с библиотечных полок, на каждой полке образовался бы зазор размером с ваш кулак». ^[8]

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

Изобретение в 1997 году вихря Мерсенна ^[9] в частности позволило избежать многих проблем с более ранними генераторами. У вихря Мерсенна период составляет 2 ^{19 937}  − 1 итераций (≈ 4,3 × 10⁶⁰⁰¹ ), как доказано, равномерно распределен в (до) 623 измерениях (для 32-битных значений) и на момент своего появления работал быстрее, чем другие статистически обоснованные генераторы.

В 2003 году Джордж Марсалья представил семейство генераторов xorshift , ^[10] снова основанных на линейной рекуррентности. Такие генераторы чрезвычайно быстры и, в сочетании с нелинейной операцией, проходят сильные статистические тесты. ^{[11] [12] [13]}

В 2006 году было разработано семейство генераторов WELL . ^[14] Генераторы WELL в некотором роде улучшают качество Mersenne Twister, который имеет слишком большое пространство состояний и очень медленное восстановление из пространств состояний с большим количеством нулей.

Криптографические PRNG

PRNG, подходящий для криптографических приложений, называется криптографически безопасным PRNG (CSPRNG). Требование к CSPRNG заключается в том, что противник, не знающий начального числа, имеет лишь незначительное преимущество в различении выходной последовательности генератора от случайной последовательности. Другими словами, в то время как PRNG требуется только для прохождения определенных статистических тестов, CSPRNG должен проходить все статистические тесты, которые ограничены полиномиальным временем от размера начального числа. Хотя доказательство этого свойства выходит за рамки текущего состояния теории вычислительной сложности , убедительные доказательства могут быть предоставлены путем сведения к CSPRNG проблемы , которая считается сложной , такой как факторизация целых чисел . ^[15] В общем случае могут потребоваться годы проверки, прежде чем алгоритм может быть сертифицирован как CSPRNG.

Некоторые классы CSPRNG включают следующее:

• потоковые шифры
• блочные шифры, работающие в режиме счетчика ^[16] или обратной связи на выходе
• Генераторы псевдослучайных чисел, специально разработанные для обеспечения криптографической безопасности, такие как функция CryptGenRandom из интерфейса программирования криптографических приложений Microsoft , алгоритм Ярроу (встроенный в Mac OS X и FreeBSD ) и Fortuna
• Комбинированные PRNG, которые пытаются объединить несколько примитивных алгоритмов PRNG с целью устранения любой обнаруживаемой неслучайности
• специальные конструкции, основанные на предположениях о математической прочности: примеры включают генератор Микали–Шнорра , ^[17] псевдослучайную функцию Наора–Рейнгольда и алгоритм Блюма–Блюма–Шуба , которые обеспечивают надежное доказательство безопасности (такие алгоритмы довольно медленные по сравнению с традиционными конструкциями и непрактичные для многих приложений)
• Универсальные ГПСЧ: хотя было показано, что (криптографически) безопасный ГПСЧ может быть сконструирован в общем виде из любой односторонней функции , ^[18] эта универсальная конструкция чрезвычайно медленна на практике, поэтому представляет в основном теоретический интерес.

Было показано, что, скорее всего, АНБ внедрило асимметричный бэкдор в сертифицированный NIST генератор псевдослучайных чисел Dual_EC_DRBG . ^[19]

Большинство алгоритмов PRNG создают последовательности, которые равномерно распределены любым из нескольких тестов. Это открытый вопрос, и один из центральных для теории и практики криптографии , есть ли способ отличить вывод высококачественного PRNG от действительно случайной последовательности. В этой ситуации различающий знает, что использовался либо известный алгоритм PRNG (но не состояние, с которым он был инициализирован), либо использовался действительно случайный алгоритм, и должен различать их. ^[20] Безопасность большинства криптографических алгоритмов и протоколов, использующих PRNG, основана на предположении, что невозможно отличить использование подходящего PRNG от использования действительно случайной последовательности. Простейшими примерами этой зависимости являются потоковые шифры , которые (чаще всего) работают путем исключающего или -инга открытого текста сообщения с выводом PRNG, создавая шифротекст . Разработка криптографически адекватных PRNG чрезвычайно сложна, поскольку они должны соответствовать дополнительным критериям. Размер периода является важным фактором криптографической пригодности ГПСЧ, но не единственным.

Критерии оценки BSI

Федеральное ведомство по информационной безопасности Германии ( нем . Bundesamt für Sicherheit in der Informationstechnik , BSI) установило четыре критерия качества детерминированных генераторов случайных чисел. ^[21] Они обобщены здесь:

• K1 – Должна быть высокая вероятность того, что сгенерированные последовательности случайных чисел будут отличаться друг от друга.
• K2 – Последовательность чисел неотличима от «истинно случайных» чисел согласно указанным статистическим тестам. Тесты — это тест монобита (равное количество единиц и нулей в последовательности), тест покера (особый случай теста хи-квадрат ), тест серий (подсчитывает частоту серий различной длины), тест длинных серий (проверяет , существует ли какая-либо серия длиной 34 или более в 20 000 бит последовательности) — оба из BSI ^[21] и NIST ^[22] и тест автокорреляции . По сути, эти требования являются тестом того, насколько хорошо последовательность бит: имеет нули и единицы одинаково часто; после последовательности из n нулей (или единиц) следующий бит — единица (или ноль) с вероятностью одна половина; и любая выбранная подпоследовательность не содержит информации о следующем элементе (элементах) в последовательности.
• K3 – Злоумышленник (для всех практических целей) не должен иметь возможности вычислить или иным образом угадать на основе любой заданной подпоследовательности любые предыдущие или будущие значения в последовательности, а также любое внутреннее состояние генератора.
• K4 – Для всех практических целей злоумышленнику должно быть невозможно вычислить или угадать на основе внутреннего состояния генератора любые предыдущие числа в последовательности или любые предыдущие внутренние состояния генератора.

Для криптографических приложений приемлемы только генераторы, соответствующие стандартам K3 или K4.

Математическое определение

Данный:

• ${\displaystyle P}$– распределение вероятностей на (где находится стандартное борелевское множество на действительной прямой) ${\displaystyle \left(\mathbb {R} ,{\mathfrak {B}}\right)}$ ${\displaystyle {\mathfrak {B}}}$
• ${\displaystyle {\mathfrak {F}}}$– непустая коллекция борелевских множеств , например . Если не указано, это может быть либо , либо , в зависимости от контекста. ${\displaystyle {\mathfrak {F}}\subseteq {\mathfrak {B}}}$ ${\displaystyle {\mathfrak {F}}=\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}}$ ${\displaystyle {\mathfrak {F}}}$ ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle \left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}}$
• ${\displaystyle A\subseteq \mathbb {R} }$– непустое множество (не обязательно борелевское множество). Часто является множеством между носителем и его внутренностью ; например, если – равномерное распределение на интервале , может быть . Если не указано, предполагается, что это некоторое множество, содержащееся в носителе и содержащее его внутренность, в зависимости от контекста. ${\displaystyle A}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle \left(0,1\right]}$ ${\displaystyle A}$ ${\displaystyle \left(0,1\right]}$ ${\displaystyle A}$ ${\displaystyle P}$

Мы называем функцию (где — множество положительных целых чисел) генератором псевдослучайных чисел для заданного принимающего значения тогда и только тогда, когда : ${\displaystyle f:\mathbb {N} _{1}\rightarrow \mathbb {R} }$ ${\displaystyle \mathbb {N} _{1}=\left\{1,2,3,\dots \right\}}$ ${\displaystyle P}$ ${\displaystyle {\mathfrak {F}}}$ ${\displaystyle A}$

• ${\displaystyle f\left(\mathbb {N} _{1}\right)\subseteq A}$
• ${\displaystyle \forall E\in {\mathfrak {F}}\quad \forall \varepsilon >0\quad \exists N\in \mathbb {N} _{1}\quad \forall n\geq N,\quad \left|{\frac {\#\left\{i\in \left\{1,2,\dots ,n\right\}:f(i)\in E\right\}}{n}}-P(E)\right|<\varepsilon }$

( обозначает количество элементов в конечном множестве .) ${\displaystyle \#S}$ ${\displaystyle S}$

Можно показать, что если — генератор псевдослучайных чисел для равномерного распределения на и если — функция распределения некоторого заданного распределения вероятностей , то — генератор псевдослучайных чисел для , где — процентиль , т. е . . Интуитивно, произвольное распределение можно смоделировать из моделирования стандартного равномерного распределения. ${\displaystyle f}$ ${\displaystyle \left(0,1\right)}$ ${\displaystyle F}$ ${\displaystyle P}$ ${\displaystyle F^{*}\circ f}$ ${\displaystyle P}$ ${\displaystyle F^{*}:\left(0,1\right)\rightarrow \mathbb {R} }$ ${\displaystyle P}$ ${\displaystyle F^{*}(x):=\inf \left\{t\in \mathbb {R} :x\leq F(t)\right\}}$

Ранние подходы

Один из первых компьютерных ГПСЧ, предложенный Джоном фон Нейманом в 1946 году, известен как метод среднего квадрата . Алгоритм выглядит следующим образом: берем любое число, возводим его в квадрат, удаляем средние цифры полученного числа как «случайное число», затем используем это число в качестве начального числа для следующей итерации. Например, возведение в квадрат числа «1111» дает «1234321», что можно записать как «01234321», причем 8-значное число является квадратом 4-значного числа. Это дает «2343» в качестве «случайного» числа. Повторение этой процедуры дает «4896» в качестве следующего результата и так далее. Фон Нейман использовал 10-значные числа, но процесс был тем же самым.

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

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

Метод среднего квадрата с тех пор был вытеснен более сложными генераторами.

Недавнее новшество — объединение среднего квадрата с последовательностью Вейля . Этот метод обеспечивает высококачественный вывод в течение длительного периода (см. метод среднего квадрата ).

Неравномерные генераторы

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

Во-первых, нужна кумулятивная функция распределения целевого распределения : ${\displaystyle F(b)}$ ${\displaystyle f(b)}$

${\displaystyle F(b)=\int _{-\infty }^{b}f(b')\,db'}$

Обратите внимание, что . Используя случайное число c из равномерного распределения в качестве плотности вероятности «пройти мимо», получаем ${\displaystyle 0=F(-\infty )\leq F(b)\leq F(\infty )=1}$

${\displaystyle F(b)=c}$

так что

${\displaystyle b=F^{-1}(c)}$

это число, случайно выбранное из распределения . Это основано на обратном преобразовании выборки . ${\displaystyle f(b)}$

Например, инверсия кумулятивного гауссовского распределения с идеальным равномерным PRNG с диапазоном (0, 1) в качестве входных данных даст последовательность (только положительных) значений с гауссовым распределением; однако ${\displaystyle \operatorname {erf} ^{-1}(x)}$ ${\displaystyle x}$

• При использовании практических числовых представлений бесконечные «хвосты» распределения приходится усекать до конечных значений.
• Повторные пересчеты следует сократить с помощью таких средств, как алгоритм зиккурата для более быстрой генерации. ${\displaystyle \operatorname {erf} ^{-1}(x)}$

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

Смотрите также

• Математический портал

• Список генераторов псевдослучайных чисел
• Применение случайности
• Линейный конгруэнтный генератор
• Последовательность с низким расхождением
• Псевдослучайная бинарная последовательность
• Псевдослучайный шум
• Псевдослучайность
• Генерация случайных чисел
• Атака с использованием генератора случайных чисел
• Случайность
• Статистическая случайность

Ссылки

1. Баркер, Элейн; Баркер, Уильям; Берр, Уильям; Полк, Уильям; Смид, Майлз (июль 2012 г.). "Рекомендация по управлению ключами" (PDF) . Специальная публикация NIST 800-57 . NIST . doi :10.6028/NIST.SP.800-57p1r3 . Получено 19 августа 2013 г. .
2. "Генератор псевдослучайных чисел". Khan Academy . Получено 2016-01-11 .
3. Фон Нейман, Джон (1951). «Различные методы, используемые в связи со случайными цифрами» (PDF) . Серия «Прикладная математика» Национального бюро стандартов . 12 : 36–38.
4. Пресс и др. (2007), гл.7
5. L'Ecuyer, Pierre (2010). "Генератор случайных чисел с равномерным распределением". В Lovric, Miodrag (ред.). Международная энциклопедия статистической науки . Springer. стр. 1629. ISBN 978-3-642-04897-5.
6. Случайный (Java Platform SE 8), Документация Java Platform Standard Edition 8.
7. Random.java в OpenJDK .
8. Пресс и др. (2007) §7.1
9. Мацумото, Макото; Нисимура, Такудзи (1998). «Вихрь Мерсенна: 623-мерно равномерный генератор псевдослучайных чисел» (PDF) . Труды ACM по моделированию и компьютерному моделированию . 8 (1). ACM : 3–30. doi :10.1145/272991.272995. S2CID  3332028.
10. Марсалья, Джордж (июль 2003 г.). "Xorshift RNGs". Журнал статистического программного обеспечения . 8 (14). doi : 10.18637/jss.v008.i14 . S2CID  250501391.
11. С.Вигна. «Генератор xorshift*/xorshift+ и перестрелка PRNG».
12. Винья С. (2016), «Экспериментальное исследование генераторов ксоршифта Марсальи», ACM Transactions on Mathematical Software , 42; doi : 10.1145/2845077.
13. Винья С. (2017), «Дальнейшие скремблирования генераторов ксоршифта Марсальи», Журнал вычислительной и прикладной математики , 315; doi : 10.1016/j.cam.2016.11.006.
14. Паннетон, Франсуа; Л'Экуайе, Пьер; Мацумото, Макото (2006). «Улучшенные генераторы длинных периодов на основе линейных рекуррент по модулю 2» (PDF) . ACM Transactions on Mathematical Software . 32 (1): 1–16. doi :10.1145/1132973.1132974. S2CID  7368302.
15. Song Y. Yan (7 декабря 2007 г.). Криптоаналитические атаки на RSA . Springer, 2007. стр. 73. ISBN 978-0-387-48741-0.
16. Нильс Фергюсон ; Брюс Шнайер ; Тадаёси Коно (2010). «Криптографическая инженерия: принципы проектирования и практическое применение, глава 9.4: Генератор» (PDF) .
17. Клаус Поммеренинг (2016). "IV.4 Идеальные генераторы случайных чисел". Криптология . uni-mainz.de . Получено 12.11.2017 .
18. Пасс, Рафаэль. "Лекция 11: Теорема Голдрайха-Левина" (PDF) . COM S 687 Введение в криптографию . Получено 20 июля 2016 г. .
19. Мэтью Грин (18 сентября 2013 г.). «Множество недостатков Dual_EC_DRBG».
20. Кац, Джонатан; Йехуда, Линделл (2014). Введение в современную криптографию . CRC press. стр. 70.
21. Шиндлер, Вернер (2 декабря 1999 г.). «Классы функциональности и методология оценки детерминированных генераторов случайных чисел» (PDF) . Anwendungshinweise und Interpretationen (AIS) . Bundesamt für Sicherheit in der Informationstechnik . стр. 5–11 . Проверено 19 августа 2013 г.
22. "Требования безопасности для криптографических модулей". FIPS . NIST . 1994-01-11. стр. 4.11.1 Тесты при включении питания. Архивировано из оригинала 27 мая 2013 г. Получено 19 августа 2013 г.

Библиография

• Баркер Э., Келси Дж. , Рекомендации по генерации случайных чисел с использованием детерминированных генераторов случайных битов, NIST SP800-90A, январь 2012 г.
• Брент РП , «Некоторые генераторы случайных чисел с большим периодом, использующие сдвиги и исключающие операции», ANZIAM Journal , 2007; 48:C188–C202
• Gentle JE (2003), Генерация случайных чисел и методы Монте-Карло , Springer.
• Херманн В., Лейдольд Й., Дерфлингер Г. (2004, 2011), Автоматическая генерация неравномерных случайных величин , Springer-Verlag.
• Кнут Д. Э. Искусство программирования , том 2: Получисленные алгоритмы , третье издание. Addison-Wesley, 1997. ISBN 0-201-89684-2 . Глава 3. [Расширенный охват статистических тестов на неслучайность.] 
• Луби М., Псевдослучайность и криптографические приложения , Princeton Univ Press, 1996. ISBN 9780691025469 
• фон Нейман Дж., «Различные методы, используемые в связи со случайными цифрами», в книге А. С. Хаусхолдера, Дж. Э. Форсайта и Х. Х. Джермонда, ред., Метод Монте-Карло , Серия «Прикладная математика» Национального бюро стандартов, 12 (Вашингтон, округ Колумбия: Типография правительства США, 1951): 36–38.
• Петерсон, Иварс (1997). Джунгли случайности: математическое сафари . Нью-Йорк: John Wiley & Sons. ISBN 0-471-16449-6.
• Press WH, Teukolsky SA, Vetterling WT, Flannery BP (2007), Numerical Recipes ( Cambridge University Press ).
• Виега Дж. , «Практическая генерация случайных чисел в программном обеспечении», в трудах 19-й ежегодной конференции по приложениям компьютерной безопасности, декабрь 2003 г.

Внешние ссылки

• TestU01: бесплатный, современный ( GPL ) набор тестов случайных чисел на C++ .
• DieHarder: бесплатный ( GPL ) набор тестов случайных чисел на языке C.
• «Генерация случайных чисел» (во встроенных системах ) Эрика Юнера (2004)
• «Анализ генератора случайных чисел Linux» Цви Гуттермана, Бенни Пинкаса и Цахи Рейнмана (2006)
• «Лучшие генераторы псевдослучайных чисел», Парикшит Гопалан, Рагху Мека, Омер Рейнгольд , Лука Тревисан и Салил Вадхан ( Microsoft Research , 2012).
• rand() считается вредоносным на YouTube Стефаном Лававеем (Microsoft, 2013)
• Wsphynx — простой онлайн-генератор случайных чисел. Случайные числа генерируются с помощью алгоритмов генераторов псевдослучайных чисел (ГПСЧ) Javascript