Псевдослучайные числа ( ПСЧ ), также известные как детерминированный случайный бит генератор ( DRBG ), [1] представляет собой алгоритм для генерации последовательности чисел, свойства которых аппроксимируют свойство последовательностей случайных чисел . Последовательность ПСЧ-порожденной не является действительно случайным , так как она полностью определяется начальным значением, называется PRNG в семени (которое может включать в себя действительно случайные значения). Хотя последовательности, которые ближе к истинно случайным, могут быть сгенерированы с использованием аппаратных генераторов случайных чисел , псевдослучайныеГенераторы чисел важны на практике из-за их скорости генерации чисел и их воспроизводимости. [2]
ГПСЧ занимают центральное место в таких приложениях, как моделирование (например, для метода Монте-Карло ), электронные игры (например, для процедурной генерации ) и криптография . Криптографические приложения требуют, чтобы выходные данные не были предсказуемыми по сравнению с более ранними выходными данными, и необходимы более сложные алгоритмы , которые не наследуют линейность более простых PRNG.
Хорошие статистические свойства являются центральным требованием для вывода ГПСЧ. В общем, требуется тщательный математический анализ, чтобы быть уверенным в том, что ГПСЧ генерирует числа, достаточно близкие к случайным, чтобы соответствовать предполагаемому использованию. Джон фон Нейман предупредил о неправильной интерпретации ГПСЧ как истинно случайного генератора и пошутил, что «всякий, кто рассматривает арифметические методы получения случайных цифр, конечно, находится в состоянии греха». [3]
Возможные проблемы с детерминированными генераторами
На практике выходные данные многих распространенных ГПСЧ демонстрируют артефакты, которые приводят к тому, что они не проходят статистические тесты обнаружения паттернов. Это включает:
- Более короткие, чем ожидалось, периоды для некоторых начальных состояний (в этом контексте такие начальные состояния можно назвать «слабыми»);
- Отсутствие равномерности распределения для большого количества сгенерированных чисел;
- Соотношение последовательных значений;
- Плохое размерное распределение выходной последовательности;
- Расстояния между местами, где встречаются определенные значения, распределяются иначе, чем в распределении случайной последовательности.
Дефекты, обнаруживаемые некорректными ГПСЧ, варьируются от незаметных (и неизвестных) до очень очевидных. Примером может служить алгоритм случайных чисел RANDU, который десятилетиями использовался на мэйнфреймах . У него был серьезный изъян, но его несоответствие долгое время оставалось незамеченным.
Во многих областях исследования до 21 века, которые основывались на случайном выборе или моделировании Монте-Карло , или иным образом полагались на ГПСЧ, были гораздо менее надежными, чем идеальные, в результате использования некачественных ГПСЧ. [4] Даже сегодня иногда требуется осторожность, о чем свидетельствует следующее предупреждение в Международной энциклопедии статистической науки (2010). [5]
Список широко используемых генераторов, от которых следует отказаться, намного длиннее [, чем список хороших генераторов]. Не доверяйте слепо поставщикам программного обеспечения. Проверьте ГСЧ по умолчанию для вашего любимого программного обеспечения и будьте готовы заменить его при необходимости. Эта последняя рекомендация повторялась снова и снова на протяжении последних 40 лет. Пожалуй, удивительно, но сегодня он остается таким же актуальным, как и 40 лет назад.
В качестве иллюстрации рассмотрим широко используемый язык программирования Java . По состоянию на 2017 год[Обновить], Java по-прежнему полагается на линейный конгруэнтный генератор (LCG) для своего PRNG, [6] [7], который имеет низкое качество - см. Ниже.
Одним из хорошо известных ГПСЧ, позволяющим избежать серьезных проблем и при этом работать достаточно быстро, был Мерсенн Твистер (обсуждается ниже), который был опубликован в 1998 году. До и после этого были разработаны другие ГПСЧ более высокого качества, как с точки зрения вычислительной, так и статистической производительности. Дата; их можно найти в Списке генераторов псевдослучайных чисел .
Генераторы на основе линейных повторений
Во второй половине 20 века стандартный класс алгоритмов, используемых для ГПСЧ, состоял из линейных конгруэнтных генераторов . Было известно, что качество LCG неудовлетворительное, но более эффективных методов не было. Press et al. (2007) так описали результат: «Если все научные статьи, результаты которых вызывают сомнения из-за [LCG и связанных с ними], исчезнут с полок библиотеки, на каждой полке останется пробел размером с ваш кулак». [8]
Основным достижением в создании генераторов псевдослучайных явлений было введение методов, основанных на линейных повторениях в двухэлементном поле; такие генераторы относятся к регистрам сдвига с линейной обратной связью .
Изобретение 1997 Вихрь Мерсенна , [9] , в частности, избежать многих проблем с более ранними генераторами. Mersenne Twister имеет период в 2 19 937 -1 итераций (≈4,3 × 10 6001 ), доказано, что он равнораспределен в (до) 623 измерениях (для 32-битных значений), и на момент его появления работал быстрее, чем другие статистически обоснованные генераторы.
В 2003 году Джордж Марсалья представил семейство генераторов xorshift [10], снова основанных на линейной рекуррентности. Такие генераторы чрезвычайно быстры и в сочетании с нелинейной работой они проходят строгие статистические тесты. [11] [12] [13]
В 2006 году было разработано семейство генераторов WELL . [14] Генераторы WELL в некотором смысле улучшают качество Mersenne Twister, у которого слишком большое пространство состояний и очень медленное восстановление из пространств состояний с большим количеством нулей.
Криптографически безопасные генераторы псевдослучайных чисел
PRNG, подходящий для криптографических приложений, называется криптографически безопасным PRNG (CSPRNG). Требование для CSPRNG состоит в том, чтобы злоумышленник, не знающий начального числа, имел лишь незначительное преимущество в различении выходной последовательности генератора от случайной последовательности. Другими словами, в то время как PRNG требуется только для прохождения определенных статистических тестов, 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]
Большинство алгоритмов ГПСЧ создают последовательности, которые равномерно распределяются по любому из нескольких тестов. Это открытый вопрос, который является центральным для теории и практики криптографии , есть ли способ отличить вывод высококачественного ГПСЧ от действительно случайной последовательности. В этой настройке отличитель знает, что использовался либо известный алгоритм ГПСЧ (но не состояние, с которым он был инициализирован), либо был использован действительно случайный алгоритм, и должен различать два. [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.
Математическое определение
Дано
- - распределение вероятностей на (где стандартное множество Бореля на действительной прямой)
- - непустой набор борелевских множеств , например . Если не указано, это может быть либо или же , в зависимости от контекста.
- - непустое множество (не обязательно борелевское). Часто это набор между «S поддержка и его интерьер ; например, если - равномерное распределение на интервале , возможно . Если не указан, предполагается, что это некоторый набор, содержащийся в поддержке и содержащий его интерьер, в зависимости от контекста.
Мы называем функцию (где - множество натуральных чисел) генератор псевдослучайных чисел для дано принимая ценности в если и только если
( обозначает количество элементов в конечном множестве .)
Можно показать, что если генератор псевдослучайных чисел для равномерного распределения на и если является CDF некоторого заданного распределения вероятностей, тогда генератор псевдослучайных чисел для , где это процентиль , т.е. . Интуитивно, произвольное распределение может быть смоделировано путем моделирования стандартного равномерного распределения.
Ранние подходы
Ранний компьютерный ГПСЧ, предложенный Джоном фон Нейманом в 1946 году, известен как метод среднего квадрата . Алгоритм следующий: возьмите любое число, возведите его в квадрат, удалите средние цифры полученного числа как «случайное число», затем используйте это число в качестве начального числа для следующей итерации. Например, возведение числа «1111» в квадрат дает «1234321», которое можно записать как «01234321», где 8-значное число является квадратом 4-значного числа. Это дает «2343» как «случайное» число. Повторение этой процедуры дает следующий результат «4896» и так далее. Фон Нейман использовал 10-значные числа, но процесс был таким же.
Проблема с методом «среднего квадрата» заключается в том, что все последовательности в конечном итоге повторяются, некоторые очень быстро, например, «0000». Фон Нейман знал об этом, но он нашел подход достаточным для своих целей и был обеспокоен тем, что математические «исправления» просто скроют ошибки, а не устранят их.
Фон Нейман счел аппаратные генераторы случайных чисел непригодными, поскольку, если они не записывали сгенерированный вывод, их нельзя было впоследствии проверить на наличие ошибок. Если бы они действительно записали свой результат, они исчерпали бы ограниченную память компьютера, которая тогда была доступна, и, таким образом, способность компьютера читать и записывать числа. Если бы числа были записаны на карточки, их написание и чтение заняло бы намного больше времени. На компьютере ENIAC, который он использовал, метод «среднего квадрата» генерировал числа в несколько сотен раз быстрее, чем считывание чисел с перфокарт .
С тех пор метод среднего квадрата был вытеснен более сложными генераторами.
Недавнее нововведение - объединить средний квадрат с последовательностью Вейля . Этот метод обеспечивает высококачественный результат в течение длительного периода (см. ГПСЧ последовательности Вейля в среднем квадрате ).
Неоднородные генераторы
Числа, выбранные из неравномерного распределения вероятностей, могут быть сгенерированы с использованием ГПСЧ равномерного распределения и функции, которая связывает два распределения.
Во-первых, нужна кумулятивная функция распределения целевого распределения :
Обратите внимание, что . Используя случайное число c из равномерного распределения в качестве плотности вероятности «пройти мимо», мы получаем
чтобы
число, случайно выбранное из распределения .
Например, обратное кумулятивному распределению Гаусса с идеальным однородным ГПСЧ с диапазоном (0, 1) в качестве входных данных произвел бы последовательность (только положительных) значений с распределением Гаусса; тем не мение
- При использовании практических представлений чисел бесконечные «хвосты» распределения должны быть усечены до конечных значений.
- Повторный пересчет следует уменьшить с помощью таких средств, как алгоритм зиккурата для более быстрой генерации.
Аналогичные соображения применимы к генерации других неоднородных распределений, таких как Рэлея и Пуассона .
Смотрите также
- Список генераторов псевдослучайных чисел
- Применение случайности
- Последовательность с низким расхождением
- Псевдослучайная двоичная последовательность
- Псевдослучайный шум
- Генерация случайных чисел
- Атака генератора случайных чисел
- Случайность
- Статистическая случайность
Рекомендации
- ^ Баркер, Элейн; Баркер, Уильям; Берр, Уильям; Полк, Уильям; Смид, Майлз (июль 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.
- ^ Случайное (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).
- ^ S.Vigna. "xorshift * / xorshift + генераторы и перестрелка ГПСЧ" .
- ^ Вигна С. (2016), «Экспериментальное исследование генераторов xorshift Марсальи», Транзакции ACM по математическому программному обеспечению , 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.
- ^ Нильс Фергюсон , Брюс Шнайер , Тадаёши Коно (2010). «Инженерия криптографии: принципы проектирования и практическое применение, глава 9.4: Генератор» (PDF) .CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Клаус Поммеренинг (2016). «IV.4 Совершенные генераторы случайных чисел» . Криптология . uni-mainz.de . Проверено 12 ноября 2017 .
Генератор MICALI-SCHNORR
- ^ Проходи, Рафаэль. «Лекция 11: Теорема Гольдрайха-Левина» (PDF) . COM S 687 Введение в криптографию . Проверено 20 июля +2016 .
- ^ Мэтью Грин . «Множество недостатков Dual_EC_DRBG» .
- ^ Кац, Джонатан; Иегуда, Линделл (2014). Введение в современную криптографию . CRC Press. п. 70.
- ^ а б Шиндлер, Вернер (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), Numerical Recipes ( 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.