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

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

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

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

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

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

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

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

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

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

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

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

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

Во второй половине 20-го века стандартный класс алгоритмов, используемых для ГПСЧ, включал линейные конгруэнтные генераторы . Было известно, что качество 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 в некотором смысле улучшают качество вихря Мерсенна, который имеет слишком большое пространство состояний и очень медленное восстановление из пространств состояний с большим количеством нулей.

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

ГПСЧ, подходящий для криптографических приложений, называется криптографически безопасным ГПСЧ (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] и НИСТ , ^[22] и автокорреляционный тест. По сути, эти требования являются проверкой того, насколько хорошо последовательность битов: одинаково часто содержит нули и единицы; после последовательности из n нулей (или единиц) следующим битом будет единица (или ноль) с вероятностью, равной половине; и любая выбранная подпоследовательность не содержит информации о следующем элементе(ах) в последовательности.
K3 – Злоумышленнику должно быть невозможно (для всех практических целей) вычислить или иным образом угадать на основе любой данной подпоследовательности, любых предыдущих или будущих значений в последовательности или какого-либо внутреннего состояния генератора.
K4 – Для всех практических целей злоумышленнику должно быть невозможно вычислить или угадать на основе внутреннего состояния генератора любые предыдущие числа в последовательности или любые предыдущие внутренние состояния генератора.

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

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

Данный:

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

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

$f\left(\mathbb {N} _{1}\right)\subseteq A$
$\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$

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

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

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

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

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

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

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

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

Неоднородные генераторы

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

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

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

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

F(b)=c

так что

b=F^{-1}(c)

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

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

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

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

См. также

Ссылки

^ Баркер, Элейн; Баркер, Уильям; Берр, Уильям; Полк, Уильям; Смид, Майлз (июль 2012 г.). «Рекомендации по управлению ключами» (PDF) . Специальная публикация NIST 800-57 . НИСТ . дои : 10.6028/NIST.SP.800-57p1r3 . Проверено 19 августа 2013 г.
^ «Генератор псевдослучайных чисел» . Ханская академия . Проверено 11 января 2016 г.
^ Фон Нейман, Джон (1951). «Различные методы, используемые со случайными цифрами» (PDF) . Серия Национального бюро стандартов по прикладной математике . 12 : 36–38.
^ Пресс и др. (2007), гл.7
^ Л'Экуйер, Пьер (2010). «Единые генераторы случайных чисел». В Ловрике, Миодраг (ред.). Международная энциклопедия статистических наук . Спрингер. п. 1629. ИСБН 978-3-642-04897-5 .
^ Случайный (Java Platform SE 8) , Документация Java Platform Standard Edition 8.
^ Random.java в OpenJDK .
^ Пресс и др. (2007) §7.1
^ Мацумото, Макото; Нисимура, Такудзи (1998). «Твистер Мерсенна: 623-мерный равномерно распределенный генератор псевдослучайных чисел» (PDF) . ACM-транзакции по моделированию и компьютерному моделированию . 8 (1). АКМ : 3–30. дои : 10.1145/272991.272995 . S2CID 3332028 .
^ Марсалья, Джордж (июль 2003 г.). «Xorshift RNG» . Журнал статистического программного обеспечения . 8 (14). дои : 10.18637/jss.v008.i14 . S2CID 250501391 .
^ С.Вигна. «Генераторы xorshift*/xorshift+ и перестрелка PRNG» .
^ Винья С. (2016), «Экспериментальное исследование генераторов xorshift Марсальи», ACM Transactions on Mathematical Software , 42; дои : 10.1145/2845077 .
^ Винья С. (2017), «Дальнейшая расшифровка генераторов xorshift Марсальи», Журнал вычислительной и прикладной математики , 315; дои : 10.1016/j.cam.2016.11.006 .
^ Паннетон, Франсуа; Л'Экуйер, Пьер; Мацумото, Макото (2006). «Улучшенные долгопериодические генераторы на основе линейных рекуррент по модулю 2» (PDF) . Транзакции ACM в математическом программном обеспечении . 32 (1): 1–16. дои : 10.1145/1132973.1132974 . S2CID 7368302 .
^ Сун Ю. Ян (7 декабря 2007 г.). Криптоаналитические атаки на RSA . Спрингер, 2007. с. 73. ИСБН 978-0-387-48741-0 .
^ Нильс Фергюсон , Брюс Шнайер , Тадаёши Коно (2010). «Криптографическая инженерия: принципы проектирования и практическое применение, глава 9.4: Генератор» (PDF) . {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Клаус Поммеренинг (2016). «IV.4 Совершенные генераторы случайных чисел» . Криптология . uni-mainz.de . Проверено 12 ноября 2017 г.
^ Пас, Рафаэль. «Лекция 11: Теорема Гольдрейха-Левина» (PDF) . COM S 687 Введение в криптографию . Проверено 20 июля 2016 г.
^ Мэтью Грин (18 сентября 2013 г.). «Многие недостатки Dual_EC_DRBG» .
^ Кац, Джонатан; Иегуда, Линделл (2014). Введение в современную криптографию . ЦРК Пресс. п. 70.
^ Jump up to: ^а ^б Шиндлер, Вернер (2 декабря 1999 г.). «Классы функциональности и методология оценки детерминированных генераторов случайных чисел» (PDF) . Замечания по применению и интерпретации (AIS) . Федеральное управление информационной безопасности . стр. 5–11 . Проверено 19 августа 2013 г.
^ «Требования безопасности к криптографическим модулям» . ФИПС . НИСТ . 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.

[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 RNG» . Журнал статистического программного обеспечения . 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 г.

[GoldreichLevinNotes-18] Пас, Рафаэль. «Лекция 11: Теорема Гольдрейха-Левина» (PDF) . COM S 687 Введение в криптографию . Проверено 20 июля 2016 г.

[19] Мэтью Грин (18 сентября 2013 г.). «Многие недостатки Dual_EC_DRBG» .

[20] Кац, Джонатан; Иегуда, Линделл (2014). Введение в современную криптографию . ЦРК Пресс. п. 70.

[bsi_ais20-21] Jump up to: ^а ^б Шиндлер, Вернер (2 декабря 1999 г.). «Классы функциональности и методология оценки детерминированных генераторов случайных чисел» (PDF) . Замечания по применению и интерпретации (AIS) . Федеральное управление информационной безопасности . стр. 5–11 . Проверено 19 августа 2013 г.

[22] «Требования безопасности к криптографическим модулям» . ФИПС . НИСТ . 11 января 1994 г. п. 4.11.1 Тесты при включении питания. Архивировано из оригинала 27 мая 2013 года . Проверено 19 августа 2013 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]