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

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

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

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

Возможные проблемы с детерминированными генераторами [ править ]

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

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

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

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

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

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

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

Генераторы, основанные на линейных повторениях [ править ]

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

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

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

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

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

Криптографически безопасные генераторы псевдослучайных чисел [ править ]

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

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

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

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

Большинство алгоритмов ГПСЧ создают последовательности, которые равномерно распределяются по любому из нескольких тестов. Это открытый вопрос, который является центральным для теории и практики криптографии , существует ли способ отличить вывод высококачественного 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 \ влево (\ 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}$ - непустое множество (не обязательно борелевское). Часто это набор между «S поддержки и его интерьер ; например, если является равномерным распределением на интервале , может быть . Если не указан, предполагается, что это некоторый набор, содержащийся в опоре и содержащий его внутреннюю часть, в зависимости от контекста. $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 0<\varepsilon \in \mathbb {R} \quad \exists N\in \mathbb {N} _{1}\quad \forall N\leq n\in \mathbb {N} _{1},\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$ $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'

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

F(b)=c

так что

b=F^{-1}(c)

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

^ Баркер, Элейн; Баркер, Уильям; Берр, Уильям; Полк, Уильям; Смид, Майлз (июль 2012 г.). «Рекомендации по управлению ключами» (PDF) . Специальная публикация NIST 800-57 . NIST . Проверено 19 августа 2013 года .
^ "Генераторы псевдослучайных чисел" . Ханская академия . Проверено 11 января 2016 .
^ Фон Нейман, Джон (1951). «Различные методы, используемые в связи со случайными цифрами» (PDF) . Национальное бюро стандартов серии по прикладной математике . 12 : 36–38.
^ Press et al. (2007), глава 7
^ L'Ecuyer, Пьер (2010). «Генераторы единых случайных чисел». В Ловриче, Миодраг (ред.). Международная энциклопедия статистической науки . Springer. п. 1629. ISBN 3-642-04897-8.
^ Random (Java Platform SE 8) , Документация Java Platform Standard Edition 8.
^ Random.java в OpenJDK .
^ Press et al. (2007) §7.1
^ Мацумото, Макото; Нисимура, Такудзи (1998). «Твистер Мерсенна: 623-мерный равномерный генератор однородных псевдослучайных чисел» (PDF) . Транзакции ACM по моделированию и компьютерному моделированию . ACM . 8 (1): 3–30. DOI : 10.1145 / 272991.272995 .
^ Марсалья, Джордж (июль 2003 г.). «Xorshift RNG» . Журнал статистического программного обеспечения . 8 (14).
^ С.Вигна. "xorshift * / xorshift + генераторы и перестрелка ГПСЧ" .
^ Вигна С. (2016), «Экспериментальное исследование генераторов xorshift Марсальи», ACM Transactions on Mathematical Software , 42; DOI : 10.1145 / 2845077 .
↑ Vigna S. (2017), «Дальнейшие расшифровки генераторов xorshift Марсальи», Журнал вычислительной и прикладной математики , 315; DOI : 10.1016 / j.cam.2016.11.006 .
^ Паннетон, Франсуа; Л'Экуайер, Пьер; Мацумото, Макото (2006). «Улучшенные долгопериодические генераторы на основе линейных повторений по модулю 2» (PDF) . Транзакции ACM на математическом ПО . 32 (1): 1–16. DOI : 10.1145 / 1132973.1132974 .
^ Песня Ю. Янь. Криптоаналитические атаки на RSA . Springer, 2007. стр. 73. ISBN 978-0-387-48741-0.
Перейти ↑ Niels Ferguson , Bruce Schneier , Tadayoshi Kohno (2010). «Инженерия криптографии: принципы проектирования и практическое применение, глава 9.4: Генератор» (PDF) . CS1 maint: multiple names: authors list (link)
^ Клаус Поммеренинг (2016). «IV.4 Совершенные генераторы случайных чисел» . Криптология . uni-mainz.de . Проверено 12 ноября 2017 . Генератор MICALI-SCHNORR
^ Пройдите, Рафаэль. «Лекция 11: Теорема Гольдрайха-Левина» (PDF) . COM S 687 Введение в криптографию . Проверено 20 июля +2016 .
↑ Мэтью Грин . «Множество недостатков Dual_EC_DRBG» .
^ Кац, Джонатан; Иегуда, Линделл (2014). Введение в современную криптографию . CRC Press. п. 70.
^ a b Шиндлер, Вернер (2 декабря 1999 г.). «Классы функциональности и методология оценки для детерминированных генераторов случайных чисел» (PDF) . Anwendungshinweise und Interpretationen (AIS) . Bundesamt für Sicherheit in der Informationstechnik . С. 5–11 . Проверено 19 августа 2013 года .
^ «Требования безопасности для криптографических модулей» . FIPS . NIST . 1994-01-11. п. 4.11.1 Тесты при включении. Архивировано из оригинала на 27 мая 2013 года . Проверено 19 августа 2013 года .

Библиография [ править ]

Баркер Э., Келси Дж. , Рекомендации по генерации случайных чисел с использованием детерминированных генераторов случайных битов , NIST SP800-90A, январь 2012 г.
Брент Р.П. , «Некоторые генераторы долгопериодических случайных чисел, использующие сдвиги и xors», ANZIAM Journal , 2007; 48: C188 – C202
Gentle JE (2003), Генерация случайных чисел и методы Монте-Карло , Springer.
Хёрманн В., Лейдольд Дж., Дерфлингер Г. (2004, 2011), Автоматическая генерация неоднородной случайной величины , Springer-Verlag.
Knuth DE . Искусство компьютерного программирования , Том 2: получисловые алгоритмы , третье издание. Аддисон-Уэсли, 1997. ISBN 0-201-89684-2 . Глава 3. [Обширный охват статистических тестов на неслучайность.]
Люби М., Псевдослучайность и криптографические приложения , Princeton Univ Press, 1996. ISBN 9780691025469
фон Нейман Дж., «Различные методы, используемые в связи со случайными цифрами», в AS Householder, GE Forsythe и HH Germond, ред., Метод Монте-Карло , Серия прикладной математики Национального бюро стандартов, 12 (Вашингтон, округ Колумбия: Правительство США Типография, 1951): 36–38.
Петерсон, Иварс (1997). Джунгли случайности: математическое сафари . Нью-Йорк: Джон Вили и сыновья. ISBN 0-471-16449-6.
Press WH, Teukolsky SA, Vetterling W.T., Flannery BP (2007), Численные рецепты ( Cambridge University Press ).
Вьега Дж. " Практическая генерация случайных чисел в программном обеспечении ", в 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 . NIST . Проверено 19 августа 2013 года .

[2] "Генераторы псевдослучайных чисел" . Ханская академия . Проверено 11 января 2016 .

[3] Фон Нейман, Джон (1951). «Различные методы, используемые в связи со случайными цифрами» (PDF) . Национальное бюро стандартов серии по прикладной математике . 12 : 36–38.

[4] Press et al. (2007), глава 7

[5] L'Ecuyer, Пьер (2010). «Генераторы единых случайных чисел». В Ловриче, Миодраг (ред.). Международная энциклопедия статистической науки . Springer. п. 1629. ISBN 3-642-04897-8.

[6] Random (Java Platform SE 8) , Документация Java Platform Standard Edition 8.

[7] Random.java в OpenJDK .

[8] Press et al. (2007) §7.1

[9] Мацумото, Макото; Нисимура, Такудзи (1998). «Твистер Мерсенна: 623-мерный равномерный генератор однородных псевдослучайных чисел» (PDF) . Транзакции ACM по моделированию и компьютерному моделированию . ACM . 8 (1): 3–30. DOI : 10.1145 / 272991.272995 .

[10] Марсалья, Джордж (июль 2003 г.). «Xorshift RNG» . Журнал статистического программного обеспечения . 8 (14).

[11] С.Вигна. "xorshift * / xorshift + генераторы и перестрелка ГПСЧ" .

[12] Вигна С. (2016), «Экспериментальное исследование генераторов xorshift Марсальи», ACM Transactions on Mathematical Software , 42; DOI : 10.1145 / 2845077 .

[13] Vigna S. (2017), «Дальнейшие расшифровки генераторов xorshift Марсальи», Журнал вычислительной и прикладной математики , 315; DOI : 10.1016 / j.cam.2016.11.006 .

[14] Паннетон, Франсуа; Л'Экуайер, Пьер; Мацумото, Макото (2006). «Улучшенные долгопериодические генераторы на основе линейных повторений по модулю 2» (PDF) . Транзакции ACM на математическом ПО . 32 (1): 1–16. DOI : 10.1145 / 1132973.1132974 .

[15] Песня Ю. Янь. Криптоаналитические атаки на RSA . Springer, 2007. стр. 73. ISBN 978-0-387-48741-0.

[16] Перейти ↑ Niels Ferguson , Bruce Schneier , Tadayoshi Kohno (2010). «Инженерия криптографии: принципы проектирования и практическое применение, глава 9.4: Генератор» (PDF) . CS1 maint: multiple names: authors list (link)

[17] Клаус Поммеренинг (2016). «IV.4 Совершенные генераторы случайных чисел» . Криптология . uni-mainz.de . Проверено 12 ноября 2017 . Генератор MICALI-SCHNORR

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

[19] Мэтью Грин . «Множество недостатков Dual_EC_DRBG» .

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

[bsi_ais20-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 года .

[1]