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

Алгоритм, генерирующий аппроксимацию последовательности случайных чисел

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

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

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

Потенциальные проблемы

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

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

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

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

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

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

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

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

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

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

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

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

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

Криптографические ГПСЧ

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

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

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

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

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

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

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

• K1 – Должна быть высокая вероятность того, что сгенерированные последовательности случайных чисел отличаются друг от друга.
• K2 - Последовательность чисел неотличима от «истинно случайных» чисел согласно указанным статистическим тестам. Тесты представляют собой монобитный тест (равное количество единиц и нулей в последовательности), тест покера (частный экземпляр теста хи-квадрат ), тест прогонов (подсчитывает частоту прогонов различной длины), тест longruns (проверяет, существует любая серия длиной 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}$

Можно показать, что если — генератор псевдослучайных чисел для равномерного распределения на и если — CDF некоторого заданного распределения вероятностей , то — генератор псевдослучайных чисел для , где — процентиль , т.е. Интуитивно понятно, что произвольное распределение можно смоделировать путем моделирования стандартного равномерного распределения. ${\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» и так далее. Фон Нейман использовал десятизначные числа, но процесс был тот же.

Проблема метода «среднего квадрата» заключается в том, что все последовательности в конечном итоге повторяются, некоторые очень быстро, например «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)}$

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

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

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

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

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

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

Рекомендации

1. Баркер, Элейн; Баркер, Уильям; Берр, Уильям; Полк, Уильям; Смид, Майлз (июль 2012 г.). «Рекомендации по управлению ключами» (PDF) . Специальная публикация NIST 800-57 . НИСТ . дои : 10.6028/NIST.SP.800-57p1r3 . Проверено 19 августа 2013 г.
2. «Генератор псевдослучайных чисел» . Ханская академия . Проверено 11 января 2016 г.
3. Фон Нейман, Джон (1951). «Различные методы, используемые со случайными цифрами» (PDF) . Серия Национального бюро стандартов по прикладной математике . 12 : 36–38.
4. Пресс и др. (2007), гл.7
5. Л'Экуайер, Пьер (2010). «Единые генераторы случайных чисел». В Ловрике, Миодраг (ред.). Международная энциклопедия статистических наук . Спрингер. п. 1629. ИСБН 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): 3–30. дои : 10.1145/272991.272995. S2CID  3332028.
10. Марсалья, Джордж (июль 2003 г.). «Xorshift ГСЧ». Журнал статистического программного обеспечения . 8 (14). дои : 10.18637/jss.v008.i14 . S2CID  250501391.
11. С.Вигна. «Генераторы xorshift*/xorshift+ и перестрелка PRNG».
12. Винья С. (2016), «Экспериментальное исследование генераторов xorshift Марсальи», ACM Transactions on Mathematical Software , 42; дои : 10.1145/2845077.
13. Винья С. (2017), «Дальнейшая расшифровка генераторов xorshift Марсальи», Журнал вычислительной и прикладной математики , 315; дои : 10.1016/j.cam.2016.11.006.
14. Паннетон, Франсуа; Л'Экуйер, Пьер; Мацумото, Макото (2006). «Улучшенные долгопериодические генераторы на основе линейных рекуррент по модулю 2» (PDF) . Транзакции ACM в математическом программном обеспечении . 32 (1): 1–16. дои : 10.1145/1132973.1132974. S2CID  7368302.
15. Сон Ю. Ян (7 декабря 2007 г.). Криптоаналитические атаки на RSA . Спрингер, 2007. с. 73. ИСБН 978-0-387-48741-0.
16. Нильс Фергюсон , Брюс Шнайер , Тадаёси Коно (2010). «Криптографическая инженерия: принципы проектирования и практическое применение, глава 9.4: Генератор» (PDF) .{{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )
17. Клаус Поммеренинг (2016). «IV.4 Совершенные генераторы случайных чисел». Криптология . uni-mainz.de . Проверено 12 ноября 2017 г.
18. Пасс, Рафаэль. «Лекция 11: Теорема Гольдрейха-Левина» (PDF) . COM S 687 Введение в криптографию . Проверено 20 июля 2016 г.
19. Мэтью Грин (18 сентября 2013 г.). «Многие недостатки Dual_EC_DRBG».
20. Кац, Джонатан; Иегуда, Линделл (2014). Введение в современную криптографию . ЦРК Пресс. п. 70.
21. Шиндлер, Вернер (2 декабря 1999 г.). «Классы функциональности и методология оценки детерминированных генераторов случайных чисел» (PDF) . Anwendungshinweise und Interpretationen (AIS) . Bundesamt für Sicherheit in der Informationstechnik . стр. 5–11 . Проверено 19 августа 2013 г.
22. «Требования безопасности к криптографическим модулям». ФИПС . НИСТ . 11 января 1994 г. п. 4.11.1 Тесты при включении питания. Архивировано из оригинала 27 мая 2013 года . Проверено 19 августа 2013 г.

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

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

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

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