Энциклопедичный YouTube

1 / 5

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

✪ Генератор псевдослучайных чисел | Криптография | Программирование (часть 8)

✪ Уроки C++ с нуля / Урок #5 - Генератор чисел + строки в C++

✪ rand. srand. rand задать диапазон. srand time null. Генератора случайных чисел. randomize. Урок #29.

✪ Случайные числа, линейный конгруэнтный метод - LNG (Linear Congruential Generator)

Субтитры

Когда мы наблюдаем за физическим миром, мы находим случайные отклонения везде. Мы можем генерировать настоящие случайные величины, измеряя случайные отклонения, называемые шумом. При измерении этого шума (выборке) можно получать числа. Например, если измерить электрический ток статики от телевизора в течении некоторого времени, то получится идеальная случайная последовательность. Можно визуализировать эту случайную последовательность, изобразив путь, направление которого изменяется в зависимости от каждого числа. Это называется случайным блужданием. Нужно отметить отсутствие шаблона любого масштаба в каждой точке последовательности -- следующий шаг всегда непредсказуем. Говорят, что случайные процессы недетерминированные, так как невозможно предсказать их развитие заранее. Машины, с другой стороны, детерминированные. Их операции предсказуемы и повторяемые. В 1946 году Джон фон Нейман был приглашен для проведения вычислений для военных. Особенно активно он участвовал при проектировании водородной бомбы. Используя компьютер ENIAC, он планировал повторяющиеся вычисления приближенных процессов, задействованных при ядерном синтезе. Как бы то ни было, это требовало быстрого доступа к случайно сгенерированным числам, которые возможно воспроизвести при необходимости. Однако, ENIAC имел очень ограниченную внутреннюю память, и хранить длинные случайные последовательности не представлялось возможным. Поэтому Нейман разработал алгоритм для механической симуляции перестановочного аспекта случайности таким образом: Сначала выбирается настоящее случайное число, называемое зерном. Это число можно получить при измерении шумов или взять текущее время в миллисекундах. Далее, выбранное зерно передается на вход для простых вычислений. Зерно умножается само на себя и на выход подаются средние цифры в результирующем числе. Затем, выход итерации передается в качестве зерна на вход для следующей. Этот процесс повторяется так долго, сколько нужно. Этот метод известен как метод серединных квадратов, и это только первый из большого набора генераторов псевдослучайных чисел известных сегодня. Случайность последовательности зависит только от случайности изначального зерна. Одно зерно -- одна последовательность. Итак, какая же разница между случайно сгенерированной и псевдослучайно сгенерированной последовательностями? Представим каждую последовательность в виде случайного блуждания. Они выглядят схожим образом до тех пор, пока мы не ускорим представление. Псевдослучайная последовательность в конечном счете повторяется. Это происходит, когда алгоритм доходит до зерна, которое уже было использовано ранее, и круг замыкается. Длина последовательности до повторения называется периодом. Период четко ограничен длиной изначального зерна. Например, для двузначного зерна алгоритм может породить последовательность длиной до 100 элементов, прежде чем вернется к использованному ранее зерну и начнет циклически повторяться. Трехзначное зерно позволяет растянуть период до 1000 чисел до начала повторений. Четырехзначное зерно расширяет последовательность до 10 000 чисел до начала повторений. Однако, если использовать достаточно большое зерно, можно получать последовательности из триллионов и триллионов элементов до начала повторений. Ключевым же отличием является то, что генерируя последовательность псевдослучайно, из нее исключаются очень многие подпоследовательности, которые просто не могут быть включены в нее. Например, если Алиса генерирует настоящую случайную последовательность из 20 элементов, это эквивалентно произвольной выборке из стопки всех возможных последовательностей этой длины. Эта стопка содержит 26 в степени 20 страниц, что является числом астрономического масштаба. Если встать внизу стопки и посветить фонариком вверх, то человек, стоящий на вершине стопки, не увидит этого света примерно 200 миллионов лет. Сравним это с генерацией 20-элементной псевдослучайной последовательности с использованием 4-значного зерна. Это эквивалентно произвольной выборке из 10 000 возможных начальных зерен. То есть можно сгенерировать лишь 10 000 различных последовательностей, что является исчезающе малой частью всех возможных вариантов последовательностей. Меняя случайные смещения на псевдослучайные, мы сужаем пространство ключей до намного меньшего пространства зерен. Для того, чтобы псевдослучайная последовательность была неотличима от случайно сгенерированной последовательности, нужно, чтобы при помощи компьютера было невозможно перебрать все зерна для нахождения совпадения. Это приводит нас к важному отличию в компьютерной науке между тем, что возможно и тем, что возможно в разумные сроки. Мы применяем ту же логику, когда покупаем замок для велосипеда. Мы знаем, что кто угодно может просто перебрать все возможные комбинации, чтобы найти ту, которая подойдет и откроет замок. Но это займет несколько дней. Поэтому мы предполагаем, что на 8 часов он практически защищен. При использовании генераторов псевдослучайных чисел безопасность возрастает с повышением длины зерна. Самый мощный компьютер будет перебирать все возможные зерна на протяжении многих лет, поэтому мы может спокойно предполагать практическую безопасность вместо идеальной безопасности. При увеличении скорости вычислений длина зерна должна пропорционально увеличиваться. Псевдослучайность освобождает Алису и Боба от необходимости обмениваться полной случайной последовательностью смещений заранее. Вместо этого они обмениваются относительно небольшим случайным зерном и растягивают его в одинаковые подобные случайным последовательности, которые требуются. Но что случится, если они никогда не встретятся для обмена этим случайным зерном.

Источники случайных чисел

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

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

Генератор псевдослучайных чисел включён в состав многих современных процессоров , например, RdRand входит в набор инструкций IA-32.

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

Детерминированные ГПСЧ

Из современных ГПСЧ широкое распространение также получил «вихрь Мерсенна », предложенный в 1997 году Мацумото и Нисимурой. Его достоинствами являются колоссальный период (2 19937 −1), равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение максимум в 5 измерениях), быстрая генерация случайных чисел (в 2-3 раза быстрее, чем стандартные ГПСЧ, использующие линейный конгруэнтный метод). Однако существуют алгоритмы, распознающие последовательность, порождаемую вихрем Мерсенна, как неслучайную.

ГПСЧ с источником энтропии или ГСЧ

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

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

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

В персональных компьютерах авторы программных ГСЧ используют гораздо более быстрые источники энтропии, такие, как шум звуковой карты или счётчик тактов процессора . Сбор энтропии являлся наиболее уязвимым местом ГСЧ. Эта проблема до сих пор полностью не разрешена во многих устройствах (например, смарт-картах), которые таким образом остаются уязвимыми. Многие ГСЧ используют традиционные испытанные, хотя и медленные, методы сбора энтропии вроде измерения реакции пользователя (движение мыши и т. п.), как, например, в PGP и Yarrow , или взаимодействия между потоками , как, например, в Java SecureRandom.

Пример простейшего ГСЧ с источником энтропии

Если в качестве источника энтропии использовать текущее время, то для получения целого числа от 0 до N достаточно вычислить остаток от деления текущего времени в миллисекундах на число N +1. Недостатком этого ГСЧ является то, что в течение одной миллисекунды он выдает одно и то же число.

Примеры ГСЧ и источников энтропии

ГПСЧ в криптографии

Разновидностью ГПСЧ являются ГПСБ (PRBG) - генераторы псевдо-случайных бит, а также различных поточных шифров . ГПСЧ, как и поточные шифры, состоят из внутреннего состояния (обычно размером от 16 бит до нескольких мегабайт), функции инициализации внутреннего состояния ключом или зерном (англ. seed ), функции обновления внутреннего состояния и функции вывода. ГПСЧ подразделяются на простые арифметические, сломанные криптографические и криптостойкие . Их общее предназначение - генерация последовательностей чисел, которые невозможно отличить от случайных вычислительными методами.

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

В военных целях и в полевых условиях применяются только засекреченные синхронные криптостойкие ГПСЧ (поточные шифры), блочные шифры не используются. Примерами известных криптостойких ГПСЧ являются RC4 , ISAAC , SEAL , Snow , совсем медленный теоретический алгоритм Блюм - Блюма - Шуба , а также счётчики с криптографическими хеш-функциями или криптостойкими блочными шифрами вместо функции вывода.

Примеры криптостойких ГПСЧ

Циклическое шифрование

В данном случае используется способ генерации ключа сессии из мастер-ключа. Счетчик с периодом N используется в качестве входа в шифрующее устройство. Например, в случае использования 56-битного ключа DES может использоваться счетчик с периодом 256. После каждого созданного ключа значение счетчика повышается на 1. Таким образом, псевдослучайная последовательность, полученная по данной схеме, имеет полный период: каждое выходное значение Х0, Х1,…XN-1 основано на разных значениях счетчика, поэтому Х0 ≠ X1 ≠ XN-1. Так как мастер-ключ является секретным, легко показать, что любой секретный ключ не зависит от знания одного или более предыдущих секретных ключей.

ANSI X9.17

ГПСЧ из стандарта ANSI X9.17 используется во многих приложениях финансовой безопасности и PGP . В основе этого ГПСЧ лежит тройной DES . Генератор ANSI X9.17 состоит из следующих частей:

1. Вход: генератором управляют два псевдослучайных входа. Один является 64-битным представлением текущих даты и времени, которые меняются каждый раз при создании числа. Другой является 64-битным исходным значением. Оно инициализируется некоторым произвольным значением и изменяется в ходе генерации последовательности псевдослучайных чисел.
2. Ключи: генератор использует три модуля тройного DES. Все три используют одну и ту же пару 56-битных ключей, которая держится в секрете и применяется только при генерации псевдослучайного числа.
3. Выход: выход состоит из 64-битного псевдослучайного числа и 64-битного значения, которое будет использоваться в качестве начального значения при создании следующего числа.

• DTi - значение даты и времени на начало i-ой стадии генерации.
• Vi - начальное значение для i-ой стадии генерации.
• Ri - псевдослучайное число, созданное на i-ой стадии генерации.
• K1, K2 - ключи, используемые на каждой стадии.

1 Ri = EDEK1,K2 [ EDEK1,K2 [ DTi] Vi ] 2 Vi+1 = EDEK1,K2 [ EDEK1,K2 [ DTi] Ri]

Схема включает использование 112-битного ключа и трех EDE-шифрований. На вход даются два псевдослучайных значения: значение даты и времени и начальное значение текущей итерации, на выходе получаются начальное значение для следующей итерации и очередное псевдослучайное значение. Даже если псевдослучайное число Ri будет скомпрометировано, вычислить Vi+1 из Ri не является возможным за разумное время, и, следовательно, следующее псевдослучайное значение Ri+1, так как для получения Vi+1 дополнительно выполняются три операции EDE.

Аппаратные ГПСЧ

Кроме устаревших, хорошо известных LFSR-генераторов, широко применявшихся в качестве аппаратных ГПСЧ в XX веке, к сожалению, очень мало известно о современных аппаратных ГПСЧ (поточных шифрах), так как большинство из них разработано для военных целей и держатся в секрете. Почти все существующие коммерческие аппаратные ГПСЧ запатентованы или держатся в секрете . Аппаратные ГПСЧ ограничены строгими требованиями к расходуемой памяти (чаще всего использование памяти запрещено), быстродействию (1-2 такта) и площади (несколько сотен FPGA - или ASIC -ячеек). Из-за таких строгих требований к аппаратным ГПСЧ очень трудно создать криптостойкий генератор, поэтому до сих пор все известные аппаратные ГПСЧ были взломаны. Примерами таких генераторов являются Toyocrypt и LILI-128, которые оба являются LFSR-генераторами, и оба были взломаны с помощью алгебраических атак.

Из-за недостатка хороших аппаратных ГПСЧ производители вынуждены применять имеющиеся под рукой гораздо более медленные, но широко известные блочные шифры (DES , AES) и хеш-функции (SHA-1) в поточных режимах.

Он заключается в следующем. Вначале выбираются два больших простых 1 Целое положительное число большее единицы называется простым , если оно не делится ни на какое другое число, кроме самого себя и единицы. Подробнее о простых числах см. в "Основные положения теории чисел, используемые в криптографии с открытым ключом" . числа p и q . Числа p и q должны быть оба сравнимы с 3 по модулю 4, то есть при делении p и q на 4 должен получаться одинаковый остаток 3. Далее вычисляется число M = p* q , называемое целым числом Блюма. Затем выбирается другое случайное целое число х , взаимно простое (то есть не имеющее общих делителей, кроме единицы) с М . Вычисляем х0= х 2 mod M . х 0 называется стартовым числом генератора.

На каждом n-м шаге работы генератора вычисляется х n+1 = х n 2 mod M . Результатом n-го шага является один (обычно младший) бит числа х n+1 . Иногда в качестве результата принимают бит чётности, то есть количество единиц в двоичном представлении элемента. Если количество единиц в записи числа четное – бит четности принимается равным 0 , нечетное – бит четности принимается равным 1 .

Например , пусть p = 11, q = 19 (убеждаемся, что 11 mod 4 = 3, 19 mod 4 = 3 ). Тогда M = p* q = 11*19=209 . Выберем х , взаимно простое с М : пусть х = 3 . Вычислим стартовое число генератора х 0 :

х 0 = х 2 mod M = 3 2 mod 209 = 9 mod 209 = 9.

Вычислим первые десять чисел х i по алгоритму BBS . В качестве случайных бит будем брать младший бит в двоичной записи числа х i :

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

Например, вычислим х 10 сразу из х 0 :

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

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

Безопасность алгоритма BBS основана на сложности разложения большого числа М на множители. Утверждается, что если М достаточно велико, его можно даже не держать в секрете; до тех пор, пока М не разложено на множители, никто не сможет предсказать выход генератора ПСЧ. Это связано с тем, что задача разложения чисел вида n = pq (р и q - простые числа) на множители является вычислительно очень трудной, если мы знаем только n , а р и q - большие числа, состоящие из нескольких десятков или сотен бит (это так называемая задача факторизации ).

Кроме того, можно доказать, что злоумышленник , зная некоторую последовательность, сгенерированную генератором BBS , не сможет определить ни предыдущие до нее биты, ни следующие. Генератор BBS непредсказуем в левом направлении и в правом направлении . Это свойство очень полезно для целей криптографии и оно также связано с особенностями разложения числа М на множители.

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

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

Ключевые термины

Stream cipher – поточный шифр .

Алгоритм BBS – один из методов генерации псевдослучайных чисел. Название алгоритма происходит от фамилий авторов - L. Blum, M. Blum, M. Shub. Алгоритм может использоваться в криптографии. Для вычислений очередного числа x n+1 по алгоритму BBS используется формула х n+1 = х n 2 mod M , где M = pq является произведением двух больших простых p и q .

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

Линейный конгруэнтный генератор псевдослучайных чисел – один из простейших ГПСЧ, который для вычисления очередного числа k i использует формулу k i =(a*k i-1 +b)mod c , где а, b, с - некоторые константы , a k i-1 - предыдущее псевдослучайное число .

Метод Фибоначчи с запаздываниями – один из методов генерации псевдослучайных чисел. Может использоваться в криптографии.

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

Краткие итоги

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

Генерирование случайных последовательностей с заданным вероят­ностным законом и проверка их адекватности - одни из важнейших проблем современной криптологии. Генераторы случайных последова­тельностей используются в существующих криптосистемах для генера­ции ключевой информации и задания ряда параметров криптосистем. Научная и практическая значимость этой проблемы настолько велика, что ей посвящены отдельные монографии в области криптологии, орга­низуются разделы в научных журналах "Journal of Cryptology", "Cryptologia" и специальные заседания на международных научных конфе­ренциях "Eurocrypt", "Asiacrypt", "Crypto" и др.

В начале XX века случайные последовательности имитировались с помощью простейших случайных экспериментов: бросание монеты или игральной кости, извлечение шаров из урны, раскладывание карт, рулетка и т. д. В 1927 г. Л. Типпетом впервые были опубликованы та­блицы, содержащие свыше 40000 случайных цифр, "произвольно из­влечённых из отчётов о переписи населения". В 1939 г. с помощью специально сконструированного механического устройства - генера­тора случайных чисел, М. Дж. Кендалл и Б. Бэбингтон-Смит создали таблицу, включающую 10 5 случайных цифр. В 1946 г. американский математик Джон фон Нейман впервые предложил компьютерный алго­ритм генерации случайных чисел. В 1955 г. компания RAND Corpora­tion опубликовала получившие широкую популярность таблицы, содер­жащие 10 6 случайных цифр, сгенерированных на ЭВМ.

В настоящее время спрос на генераторы случайных последователь­ностей с заданными вероятностными распределениями, а также на сами случайные последовательности настолько возрос, что за рубежом появи­лись научно-производственные фирмы, занимающиеся производством и продажей больших массивов случайных чисел. Например, с 1996 г. в мире распространяется компакт-диск "The Marsaglia random number CDROM", который содержит 4,8 млрд. "истинно случайных" бит.

Подавляющее большинство современных криптографических систем используют либо поточные, либо блочные алгоритмы, базирующиеся на различных типах шифрах замены и перестановки. К сожалению, практически все алгоритмы, используемые в поточных криптосистемах, ориентированных на использование в военных и правительственных системах связи, а также, в некоторых случаях, для защиты информации коммерческого характера, что вполне естественно делает их секретными и недоступными для ознакомления. Единственными стандартными алгоритмами поточного симметричного шифрования являются американский стандарт DES (режимы CFB и OFB) и российский стандарт ГОСТ 28147-89 (режим гаммирования).

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

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

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

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

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

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

1. Период гаммы должен быть достаточно большим для шифрования сообщений различной длины.

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

3. Генерирование гаммы не должно быть связано с большими техническими и организационными трудностями.

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

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

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

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

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

3.1 Линейный конгруэнтный метод

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

Этот алгоритм заключается в итеративном применении следующей формулы:

где a>0, c>0, m>0 - некоторые целочисленные константы. Получаемая последовательность зависит от выбора стартового числа X 0 и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства последовательности X j определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа. Ясно, что последовательность чисел, генерируемая таким алгоритмом, периодична с периодом, не превышающим m . При этом длина периода равна m тогда и только тогда, когда:

· НОД (c, m) = 1 (то есть c и m взаимно просты);

· a - 1 кратно p для всех простых p - делителей m;

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

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

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

3.2 Метод Фибоначчи

Интересный класс генераторов псевдослучайных последовательностей основан на использовании последовательностей Фибоначчи. Классический пример такой последовательности {0,1,1,2,3,5,8,13,21,34 …} - за исключением первых двух ее членов, каждый последующий член равен сумме двух предыдущих.

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

В связи с этим линейный конгруэнтный алгоритм постепенно потерял свою популярность, и его место заняло семейство фибоначчиевых алгоритмов, которые могут быть рекомендованы для использования в алгоритмах, критичных к качеству случайных чисел. В англоязычной литературе фибоначчиевы датчики такого типа называют обычно «Subtract-with-borrow Generators» (SWBG).

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

Один из широко распространённых фибоначчиевых датчиков основан на следующей итеративной формуле:

где X k - вещественные числа из диапазона ; 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).

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

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.