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

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

Конструктивний підхід к определению случайной последовательности предложили Блюм, Голдвассер, Микалли и Яо. Их определение считает последовательность случайной, если не существует полиномиального (вероятностного) алгоритма, который сможет отличить ее от чисто случайной. Такая последовательность называется полиномиально неразличимой от случайной илипсевдослучайной .

Этот подход позволяет использовать для формирования псевдослучайных последовательностей (ПСП) детерминированные алгоритмы, реализуемые конечными автоматами. Хотя с математической точки зрения такие последовательности не случайны, так как они полностью определяются начальным заполнением, тем не менее, их практическое использование не дает никаких преимуществ криптоаналитику благодаря “неразличимости” со случайными. Поскольку этот подход представляется более конструктивным, остановимся на нем детальнее.

Случайные последовательности в смысле последнего определения также называют “случайными для всех практических применений”. Генераторы таких последовательностей, называют криптографически надежными (cryptographically strong ) или криптографически безопасными (cryptographically secure ). Псевдослучайность в данном случае есть не только свойство последовательности (или генератора), но и свойство наблюдателя, а точнее его вычислительных возможностей.

Для ПСП доказаны два важных утверждения:

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

2. Криптографически сильные генераторы существуют в том и только в том случае, если существуют легко вычислимые функции, но вычислительно сложно обратимые (односторонние функции - one-way functions ). В этом случае каждому генератору ПСП можно поставить во взаимнооднозначное соответствие некоторую одностороннюю функцию, которая зависит от определенных параметров.

Наиболее простым датчиком псевдослучайных чисел является линейный конгруэнтный генератор (ЛКГ), который описывается рекуррентным уравнением вида X n = (aX n -1 +b ) mod N , где X 0 – случайное начальное значение, а – множитель, b – приращение, N – модуль.

Период выходной последовательности такого генератора не превышает N , максимальное значение достигается при правильном выборе параметров a,b, N , а именно, когда

· числа N и b взаимнопросты: НОД(N,b)=1 );

· a-1 кратно любому простому p , делящему N ;

· a-1 кратно 4 , если N кратно 4 .

В приведен список констант для ЛКГ, обеспечивающих максимальный период последовательности и, что не менее важно, соответствующие последовательности проходят статистические тесты.

Для реализации ЛКГ на персональных компьютерах с учетом их разрядной сетки нередко используется модуль N=2 31 -1»2.14×10 9 . При этом наиболее качественные статистические свойства ПСП достигаются для константы a=397204094.

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

Недостатком ЛКГ в плане их использования для создания поточных шифров является предсказуемость выходных последовательностей. Эффективные атаки на ЛКГ были предложены Joan Boyar , ей принадлежат методы атак на квадратичные ‑ X n =(aX n -1 2 +bX n -1 +c)modN и кубические ‑ X n =(aX n -1 3 +bX n -1 2 +cX n -1 +d)modN генераторы.

Другие исследователи обобщили результаты работ Boyar на случай общего полиномиального конгруэнтного генератора. Stern и Boyar показали, как взломать ЛКГ, даже если известна не вся последовательность.

Wishmann и Hill , а позже Pierre L’Ecuger изучили комбинации ЛКГ. Результаты не являются более стойкими криптографически, но имеют большие периоды и лучше ведут себя на некоторых критериях случайности.

Регистры сдвига с линейной обратной связью (Linear Feedback Shift Registers - LFSR ) включают собственно регистр сдвига и схему вычисления функции обратной связи (tap sequence ) – см. рис. 12:

Поток бит

n

∙∙∙

2

1

Рис. 2. Регистр сдвига с линейной обратной связью (LFSR )

На схеме содержимое регистра ‑ последовательность бит – сдвигается с приходом тактового импульса (clock pulse ) на один разряд вправо. Бит самого младшего разряда считается выходом LFSR в данном такте работы. Значение самого старшего разряда при этом является результатом сложения по mod2 (функция XOR) разрядов обратной связи.

Теоретически, n -битный LFSR может сгенерировать псевдослучайную последовательность с периодом 2 n -1 бит, такие LFSR называются регистрами максимального периода. Для этого регистр сдвига должен побывать во всех 2 n -1 внутренних состояниях (2 n -1 , т.к. нулевое заполнение регистр сдвига, вызовет бесконечную последовательность нулей).

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

Примитивный полином степени n – это неприводимый полином, который делит ,но не делит x d +1 для любого d : (2 n-1 │d)

Теорема (без доказательства): Для того, чтобы LFSR имел максимальный период, необходимо и достаточно, чтобы полином, образованный из элементов обратной связи (tap sequence ) плюс единица был примитивным полиномом по модулю 2. (на самом деле, примитивный полином – это генератор в данном поле).

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

Например, примитивным полиномом является x 32 x 7 x 5 x 3 x 2 x1 . Запись (32,7,5,3,2,1,0 ) означает, что, взяв 32-битный регистр сдвига и генерируя бит обратной связи путем сложения по mod2 7-го, 5-го, 3-го, 2-го и 1-го бита, мы получим LFSR максимальной длины (с 2 32 -1 состояниями).

Заметим, если р(х) – примитивный полином, то x n ×p(1/x) – также примитивный.

Например, если полином (a,b,0) примитивный, то (a,a-b,0) – примитивный. Если полином (a,b,c,d,0) примитивный, то и (a,a-d,a-c,a-b,0) – примитивный и т.д.

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

LFSR – удобны для технической реализации, но имеют неприятные свойства. Последовательные биты линейно зависимы, что делает их бесполезными для шифрования. Даже если схема обратной связи неизвестна, то достаточно 2n выходных бит, чтобы определить ее.

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

Существует еще ряд генераторов ПСП (в т.ч. генераторы чисел Фибоначчи), которые по ряду причин не нашли широкого применения в криптографических системах. Наиболее эффективные решения были получены на основе составных генераторов.

Идея построения составного генератора базируется на том факте, что комбинация двух и более простых генераторов ПСП, в случае правильного выбора объединяющей функции (в т.ч. mod 2 , mod 2 32 -1 и др.), дает генератор с улучшенными свойствами случайности, и, как следствие, с повышенной криптографической стойкостью.

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

Известно 4 подхода к конструированию соответствующих генераторов:

1) системно-теоретический подход;

2) сложностно-теоретический подход;

3) информационно-теоретический подход;

4) рандомизированный подход.

Эти подходы различаются в своих предположениях о возможностях криптоаналитика, определении криптографического успеха и понятия надежности.

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

На основе такого подхода Рюппелем сформулирован следующий набор критериев для потоковых шифров:

1. Большой период выходной последовательности, отсутствие повторений;

2. Высокая линейная сложность, как характеристика нашего генератора через регистр LFSR минимальной длины, который может сгенерировать такой же выход;

3. Неотличимость от РРСП по статистическим критериям;

4. Перемешивание: любой бит ключевого потока должен быть сложным преобразованием всех или большинства бит начального состояния (ключа);

5. Рассеивание: избыточность во всех подструктурах алгоритма работы генератора должна рассеиваться;

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

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

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

Примером удачного построения составного генератора с точки зрения повышения линейной сложности является каскад Голмана (рис. 3).

Каскад Голмана включает несколько регистров LFSR , причем тактирование каждого следующего LSFR управляется предыдущим так, что изменение состояния LFSR -(k+1) в момент времени t происходит, если в предыдущем такте t-1 выход LFSR -k равняется 1, и LFSR -(k+1) не меняет свое состояние в противном случае.

Если все LFSR – длины l, то линейная сложность системы с n регистрами равна l ×(2 l -1) n-1 .

X(t)

LFSR-2

LFSR-3

Такт

Рис. 4. Чередующийся старт-стопный генератор

У этого генератора большой период и большая линейная сложность.

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

Однонаправленную функцию f (x ): D→R легко вычислить для всех x Î D , но очень трудно инвертировать для почти всех значений из R . Иначе, если V – вычислительная сложность получения f (x ), а V * – вычислительная сложность нахождения f -1 (x ), то имеет место неравенство V * >>V. Нетрудно видеть, что кандидатом на однонаправленную функцию может быть степенная функция в некотором конечном поле f (x )=a x , где a,xÎGF(q) – поле Галуа из q элементов.

Нетрудно видеть, что умножение, за счет свойства ассоциативности, можно выполнить за меньшее, чем число x-1 шагов. Например, a 9 =a×((a 2) 2) 2 , что позволяет вычислить искомую степень вместо восьми за четыре шага (вначале a 2 =a × a , затем a 4 =a 2 a 2 , a 8 =a 4 a 4 и, наконец, a 9 =a 8 a ).

Обратная операция – нахождение показателя степени по значению степенной функции (логарифмирование) ‑ в конечном поле пока не может быть решена лучше, чем с помощью оптимизированных методов перебора возможных вариантов. В случае большого размера поля (порядка 2 1024 )эта задача при современном развитии компьютерной техники вычислительно неразрешима.

Примером соответствующего генератора может алгоритм RSA . Пусть параметр N=p×q , где p,q – простые числа, начальное значение генератора x 0 N, e: НОД(e,(p-1)×(q-1) )=1.

x i+1 =x e i mod N

Результат генератора – наименьший значимый бит x i+1 . Стойкость этого генератора эквивалентна стойкости RSA . Если N достаточно большое, то генератор обеспечивает практическую стойкость.

Другой пример генератора, построенного на сложностном подходе, предложен Blum , Blum и Shub (BBS ). На данный момент это один из простых и эффективных алгоритмов. Математическая теория этого генератора – квадратичные вычеты по модулю n .

Выберем два больших простых числа p и q, дающих при делении на 4 остаток 3. Произведение n p q назовем числом Блюма. Выберем х : НОД(n,x )=1. Найдем начальное значение генератора: x 0 =x 2 mod n .

Теперь i -ым псевдослучайным числом является наименьший значимый бит x i , где x i =x 2 i -2 mod n .

Заметим, что для получения i- го бита, не требуется вычисления (i-1 ) состояния. Если мы знаем p,q, то мы можем его вычислить сразу: b i есть наименьшее значение бит:

Это свойство позволяет использовать BBS- генератор для работы с файлами произвольного доступа (random-access ).

Число n можно распространять свободно, для того чтобы каждый абонент сети смог самостоятельно сгенерировать необходимые биты. При этом если криптоаналитик не сможет разложить на простые множители число n , он не сможет предсказать следующий бит, даже в вероятностном смысле, например, «с вероятностью 51% следующий бит равен 1».

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

Следующие два подхода информационно-теоретический и рандомизированный не нашли широкого практического применения.

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

В случае рандомизированного подхода задача заключается в том, чтобы увеличить число бит, с которыми необходимо работать криптоаналитику (не увеличивая при этом ключ). Этого можно достичь путем использования больших случайных общедоступных строк. Ключ будет обозначать, какие части этих строк необходимо использовать для зашифрования и расшифрования. Тогда криптоаналитику придется использовать метод тотального перебора вариантов (грубой силы) на случайных строках.

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

Ueli Maurer описал такую схему. Вероятность вскрытия такой криптосистемы зависит от объема памяти, доступного криптоаналитику (но не зависит от его вычислительных ресурсов).

Чтобы эта схема приобрела практический вид, требуется около 100 битовых последовательностей по 10 20 бит каждая. Оцифровка поверхности Луны – один из способов получения такого количества бит.

В заключение отметим, что для построения генератора ПСП необходимо получить несколько случайных бит . Наиболее простой способ ‑ использовать наименьший значимый бит таймера компьютера.

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

Самый лучший способ получить случайное число – это обратиться к естественной случайности реального мира – шумы в результате переходных процессов в полупроводниковых диодах, тепловые шумы высокомных резисторов, радиоактивный распад и т.д. В принципе, элемент случайности есть и в компьютерах:

Время дня;

Загруженность процессора;

Время прибытия сетевых пакетов и т.п.

Проблема не в том, чтобы найти источники случайности, но в том, чтобы сохранить случайность при измерениях.

Например, это можно делать так: найдем событие, случающееся регулярно, но случайно (шум превышает некоторый порог). Измерим время между первым событием и вторым, затем между вторым и третьим. Если t 1,2 t 2,3 , то полагаем выход генератора равным 1; если t 1,2 < t 2,3 , то выход равен 0. Далее процесс продолжим.

Американский национальный институт стандартов (ANSI) разработал метод генерации 64-битных ключей при помощи DES-алгоритма (ANSI X9.17). Его основное назначение состоит в получении большого количества ключей для многократных сеансов связи. Вместо DES-алгоритма можно использовать любой другой стойкий алгоритм шифрования.

Пусть функция Е K (Р) осуществляет шифрование Р по DES-алгоритму на заранее заготовленном ключе К, который используется только для генерации секретных ключей. Пусть далее V 0 является начальным 64-битным значением, которое держится в тайне от противника, а Т i представляет собой отметку даты-времени, когда был сгенерирован i-й ключ. Тогда очередной случайный ключ R i вычисляется с помощью преобразования:

R i = Е К (Е К (Т i) Å V i)

Чтобы получить очередное значение V i , надо вычислить

V i = Е К (Е К (Т i) Å R i)

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

1) Сложением по mod 2 двух независимых последовательностей:если случайный бит смещен к 0 на величину ε , то вероятность появления 0 может быть записана как P(0)=0.5+ε .

Сложение по mod 2: двух одинаково распределенных независимых бит даст: P(0) =(0.5 +ε) 2 +(0.5-ε) 2 =0.5 +2×ε 2 , сложением четырех бит получим: P (0)=0.5+8 ε 4 и т.д. Процесс сходится к равновероятному распределению 0 и 1.

2) Пусть распределение единиц и нулей в последовательности есть величины p и q соответственно. Воспользуемся методом кодирования: рассмотрим два бита:

Если это одинаковые биты, то отбросим их и рассмотрим следующую пару;

Если биты различны, то в качестве выходного значения возьмем первый бит.

Данный метод позволяет решить проблему смещения, сохранив свойства случайности источника (с некоторой потерей в объеме данных).

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

Факт наличия смещения у генератора случайных чисел, вообще говоря, не означает его непригодность. Например, пусть для генерации 112-битного ключа для алгоритма «тройной» DES (Triple DES ) используется генератор со смещением к нулю: P{x t =0}=0.55, Р{x t =1}=0.45 (энтропия Н= 0.99277 на один бит ключа по сравнению с 1 для идеального генератора).

В этом случае нарушитель может оптимизировать процедуру тотального перебора ключей за счет поиска ключа начиная с наиболее вероятного значения (00…0 ) и заканчивая наименее вероятным (11…1 ). Вследствие наличия смещения, можно ожидать нахождения ключа в среднем за 2 109 попыток. Если бы смещения не было, то потребовалось бы 2 111 попыток. Выигрыш есть, но несущественный.

• Tutorial

Вы когда-нибудь задумывались, как работает Math.random()? Что такое случайное число и как оно получается? А представьте вопрос на собеседовании - напишите свой генератор случайных чисел в пару строк кода. И так, что же это такое, случайность и возможно ли ее предсказать?

Меня очень увлекают различные IT головоломки и задачки и генератор случайных чисел - одна из таких задачек. Обычно в своем телеграм канале я разбираю всякие головоломки и разные задачи с собеседований. Задача про генератор случайных чисел набрала большую популярность и мне захотелось увековечить ее в недрах одного из авторитетных источников информации - то бишь здесь, на Хабре.

Данный материал будет полезен всем тем фронтендерам и Node.js разработчикам, кто на острие технологий и хочет попасть в блокчейн проект/стартап, где вопросы про безопасность и криптографию, хотя бы на базовом уровне, спрашивают даже у фронтендеров.

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

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

Этот источник используется для накопления энтропии с последующим получением из неё начального значения (initial value, seed), которое необходимо генераторам случайных чисел (ГСЧ) для формирования случайных чисел.

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

Энтропия - это мера беспорядка. Информационная энтропия - мера неопределённости или непредсказуемости информации.

Выходит, что чтобы создать псевдослучайную последовательность нам нужен алгоритм, который будет генерить некоторую последовательность на основании определенной формулы. Но такую последовательность можно будет предсказать. Тем не менее, давайте пофантазируем, как бы могли написать свой генератор случайных чисел, если бы у нас не было Math.random()

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

Придумываем свой алгоритм ГПСЧ

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

Мы можем взять последовательность каких-то чисел и брать от них модуль числа. Самый простой пример, который приходит в голову. Нам нужно подумать, какую последовательность взять и модуль от чего. Если просто в лоб от 0 до N и модуль 2, то получится генератор 1 и 0:

Function* rand() { const n = 100; const mod = 2; let i = 0; while (true) { yield i % mod; if (i++ > n) i = 0; } } let i = 0; for (let x of rand()) { if (i++ > 100) break; console.log(x); }
Эта функция генерит нам последовательность 01010101010101… и назвать ее даже псевдослучайной никак нельзя. Чтобы генератор был случайным, он должен проходить тест на следующий бит. Но у нас не стоит такой задачи. Тем не менее даже без всяких тестов мы можем предсказать следующую последовательность, значит такой алгоритм в лоб не подходит, но мы в нужном направлении.

А что если взять какую-то известную, но нелинейную последовательность, например число PI. А в качестве значения для модуля будем брать не 2, а что-то другое. Можно даже подумать на тему меняющегося значения модуля. Последовательность цифр в числе Pi считается случайной. Генератор может работать, используя числа Пи, начиная с какой-то неизвестной точки. Пример такого алгоритма, с последовательностью на базе PI и с изменяемым модулем:

Const vector = [...Math.PI.toFixed(48).replace(".","")]; function* rand() { for (let i=3; i<1000; i++) { if (i > 99) i = 2; for (let n=0; n Но в JS число PI можно вывести только до 48 знака и не более. Поэтому предсказать такую последовательность все так же легко и каждый запуск такого генератора будет выдавать всегда одни и те же числа. Но наш генератор уже стал показывать числа от 0 до 9.

Мы получили генератор чисел от 0 до 9, но распределение очень неравномерное и каждый раз он будет генерировать одну и ту же последовательность.

Мы можем взять не число Pi, а время в числовом представлении и это число рассматривать как последовательность цифр, причем для того, чтобы каждый раз последовательность не повторялась, мы будем считывать ее с конца. Итого наш алгоритм нашего ГПСЧ будет выглядеть так:

Function* rand() { let newNumVector = () => [...(+new Date)+""].reverse(); let vector = newNumVector(); let i=2; while (true) { if (i++ > 99) i = 2; let n=-1; while (++n < vector.length) yield (vector[n] % i); vector = newNumVector(); } } // TEST: let i = 0; for (let x of rand()) { if (i++ > 100) break; console.log(x) }
Вот это уже похоже на генератор псевдослучайных чисел. И тот же Math.random() - это ГПСЧ, про него мы поговорим чуть позже. При этом у нас каждый раз первое число получается разным.

Собственно на этих простых примерах можно понять как работают более сложные генераторы случайных числе. И есть даже готовые алгоритмы. Для примера разберем один из них - это Линейный конгруэнтный ГПСЧ(LCPRNG).

Линейный конгруэнтный ГПСЧ

Линейный конгруэнтный ГПСЧ(LCPRNG) - это распространённый метод для генерации псевдослучайных чисел. Он не обладает криптографической стойкостью. Этот метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой формулой. Получаемая последовательность зависит от выбора стартового числа - т.е. seed. При разных значениях seed получаются различные последовательности случайных чисел. Пример реализации такого алгоритма на JavaScript:

Const a = 45; const c = 21; const m = 67; var seed = 2; const rand = () => seed = (a * seed + c) % m; for(let i=0; i<30; i++) console.log(rand())
Многие языки программирования используют LСPRNG (но не именно такой алгоритм(!)).

Как говорилось выше, такую последовательность можно предсказать. Так зачем нам ГПСЧ? Если говорить про безопасность, то ГПСЧ - это проблема. Если говорить про другие задачи, то эти свойства - могут сыграть в плюс. Например для различных спец эффектов и анимаций графики может понадобиться частый вызов random. И вот тут важны распределение значений и перформанс! Секурные алгоритмы не могут похвастать скоростью работы.

Еще одно свойство - воспроизводимость. Некоторые реализации позволяют задать seed, и это очень полезно, если последовательность должна повторяться. Воспроизведение нужно в тестах, например. И еще много других вещей существует, для которых не нужен безопасный ГСЧ.

Как устроен Math.random()

Метод Math.random() возвращает псевдослучайное число с плавающей запятой из диапазона = crypto.getRandomValues(new Uint8Array(1)); console.log(rvalue)
Но, в отличие от ГПСЧ Math.random(), этот метод очень ресурсоемкий. Дело в том, что данный генератор использует системные вызовы в ОС, чтобы получить доступ к источникам энтропии (мак адрес, цпу, температуре, etc…).

Первой широко используемой технологией создания случайного числа был алгоритм, предложенный Лехмером, который известен как метод линейного конгруента. Этот алгоритм параметризуется четырьмя числами следующим образом:

Последовательность случайных чисел {X n } получается с помощью следующего итерационного равенства:

X n +1 = (a X n + c) mod m

Если m, а и с являются целыми, то создается последовательность целых чисел в диапазоне 0 X n < m.

Выбор значений для а, с и m является критичным для разработки хорошего генератора случайных чисел.

Очевидно, что m должно быть очень большим, чтобы была возможность создать много случайных чисел. Считается, что m должно быть приблизительно равно максимальному положительному целому числу для данного компьютера. Таким образом, обычно m близко или равно 2 31 .

Существует три критерия, используемые при выборе генератора случайных чисел:

1. Функция должна создавать полный период, т.е. все числа между 0 и m до того, как создаваемые числа начнут повторяться.

2. Создаваемая последовательность должна появляться случайно. Последовательность не является случайной, так как она создается детерминированно, но различные статистические тесты, которые могут применяться, должны показывать, что последовательность случайна.

3. Функция должна эффективно реализовываться на 32-битных процессорах.

Значения а, с и m должны быть выбраны таким образом, чтобы эти три критерия выполнялись. В соответствии с первым критерием можно показать, что если m является простым и с = 0, то при определенном значении а период, создаваемый функцией, будет равен m-1. Для 32-битной арифметики соответствующее простое значение m = 2 31 - 1. Таким образом, функция создания псевдослучайных чисел имеет вид:

X n +1 = (a X n) mod (2 31 - 1)

Только небольшое число значений а удовлетворяет всем трем критериям. Одно из таких значений есть а = 7 5 = 16807, которое использовалось в семействе компьютеров IBM 360. Этот генератор широко применяется и прошел более тысячи тестов, больше, чем все другие генераторы псевдослучайных чисел.

Сила алгоритма линейного конгруента в том, что если сомножитель и модуль (основание) соответствующим образом подобраны, то результирующая последовательность чисел будет статистически неотличима от последовательности, являющейся случайной из набора 1, 2, ..., m-1. Но не может быть случайности в последовательности, полученной с использованием алгоритма, независимо от выбора начального значения Х 0 . Если значение выбрано, то оставшиеся числа в последовательности будут предопределены. Это всегда учитывается при криптоанализе.

Если противник знает, что используется алгоритм линейного конгруента, и если известны его параметры (а = 7 5 , с = 0, m = 2 31 - 1), то, если раскрыто одно число, вся последовательность чисел становится известна. Даже если противник знает только, что используется алгоритм линейного конгруента, знания небольшой части последовательности достаточно для определения параметров алгоритма и всех последующих чисел. Предположим, что противник может определить значения Х 0 , Х 1 , Х 2 , Х 3 . Тогда:

Х 1 = (а Х 0 + с) mod mХ 2 = (а Х 1 + с) mod mХ 3 = (а Х 2 + с) mod m

Эти равенства позволяют найти а, с и m.

Таким образом, хотя алгоритм и является хорошим генератором псевдослучайной последовательности чисел, желательно, чтобы реально используемая последовательность была непредсказуемой, поскольку в этом случае знание части последовательности не позволит определить будущие ее элементы. Эта цель может быть достигнута несколькими способами. Например, использование внутренних системных часов для модификации потока случайных чисел. Один из способов применения часов состоит в перезапуске последовательности после N чисел, используя текущее значение часов по модулю m в качестве нового начального значения. Другой способ состоит в простом добавлении значения текущего времени к каждому случайному числу по модулю m.

В компьютерных программах нередко требуется эмуляция случайности. Например, при разработке игр. Если в программе имеется некий генератор, т. е. производитель, случайного числа, то, используя полученное таким образом число, можно выбирать ту или иную ветку выполнения программы, или произвольный объект из коллекции. Другими словами, главное – сгенерировать число. Эмуляция случайности иного рода основывается на нем.

Мы наверняка не знаем, есть ли в природе случайность, или она нам только кажется из-за ограниченности наших знаний. Мы только знаем, что в программировании настоящей случайности нет. Неоткуда взяться произвольному числу, нельзя запрограммировать его появление из ниоткуда. Можно лишь создать программу, которая в результате применения сложной формулы к "зерну" будет выдавать число, и нам будет казаться, что это число случайно.

"Зерно" – это исходные данные для формулы. Им может быть, например, системное время в миллисекундах, которое постоянно меняется. Следовательно, "зерно" будет постоянно разным. Или программист может задавать его самостоятельно.

Подобную программу (в реальности модуль или функцию) называют генератором псевдослучайных чисел. В состав стандартной библиотеки языка Python входит модуль random. Он содержит множество функций, связанных с эмуляцией случайности (например, "перемешивание" элементов последовательности), а не только функции генерации псевдослучайных чисел.

В этом уроке будут рассмотрены функции random(), randrange() и randint() из модуля random. Обратите внимание, что модуль random содержит одноименную функцию random(). Так бывает.

Чтобы обращаться к функциям, надо импортировать модуль random:

>>> import random

Или импортировать отдельные функции из него:

>>> from random import random , randrange, randint

Функции для получения целых "случайных" чисел – randint() и randrange()

Функции randint() и randrange() генерируют псевдослучайные целые числа. Первая из них наиболее простая и всегда принимает только два аргумента – пределы целочисленного диапазона, из которого выбирается любое число:

>>> random .randint (0 , 10 ) 6

или (если импортировались отдельные функции):

>>> randint(100 , 200 ) 110

В случае randint() обе границы включаются в диапазон, т. е. на языке математики отрезок описывается как .

Числа могут быть отрицательными:

>>> random .randint (-100 , 10 ) -83 >>> random .randint (-100 , -10 ) -38

Но первое число всегда должно быть меньше или, по-крайней мере, равно второму. То есть a <= b.

Функция randrange() сложнее. Она может принимать один аргумент, два или даже три. Если указан только один, то она возвращает случайное число от 0 до указанного аргумента. Причем сам аргумент в диапазон не входит. На языке математики – это }

Поделись статьей:

Похожие статьи

17 апреля 2015
Соляная лампа «Каменный цветок

17 апреля 2015
Продуктивные способы потратить время в интернете

17 апреля 2015
Как установить приложение плей маркет на ноутбук

17 апреля 2015
Спрайты для игр - что это такое?