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


СОДЕРЖАНИЕ:

Документация

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

Числа Pseudorandom сгенерированы детерминированными алгоритмами. Они «случайны» в том смысле, что в среднем они проходят статистические тесты относительно своего распределения и корреляции. Они отличаются от истинных случайных чисел, в которых они сгенерированы алгоритмом, а не действительно вероятностным процессом.

Random number generators (RNG) как те в MATLAB ® является алгоритмами для генерации псевдослучайных чисел с заданным распределением.

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

Общие методы генерации псевдослучайного числа

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

Прямые методы

Прямые методы непосредственно используют определение распределения.

Например, рассмотрите биномиальные случайные числа. Биномиальное случайное число является количеством голов в бросках монеты с вероятностью головы на любом одном броске. Если вы генерируете универсальные случайные числа на интервале (0,1) и считаете номер меньше, чем , то количество является биномиальным случайным числом с параметрами и .

Эта функция является простой реализацией биномиального RNG с помощью прямого подхода:

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

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

Функция poissrnd на самом деле использует два прямых метода:

Метод времени ожидания для маленьких значений

Метод из-за Аренса и Дитера для больших значений

Методы инверсии

Методы инверсии основаны на наблюдении, что непрерывные кумулятивные функции распределения (cdfs) располагаются однородно на интервале (0,1) . Если универсальное случайное число на (0,1) , то использование генерирует случайное число от непрерывного распределения с заданным cdf .

Например, следующий код генерирует случайные числа от определенного Экспоненциального распределения с помощью инверсии cdf и универсального генератора случайных чисел MATLAB® rand :

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

Методы инверсии также работают на дискретные распределения. Чтобы сгенерировать случайное число от дискретного распределения с вектором вероятностной меры где , сгенерируйте универсальное случайное число на (0,1) и затем установите если .

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

Используйте функцию, чтобы сгенерировать случайные числа от любого дискретного распределения:

Методы приемного отклонения

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

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

Непрерывный RNG приемного отклонения продолжает можно следующим образом:

Находит константу таким образом это для всех .

Генерирует универсальное случайное число .

Генерирует случайное число от .

Если , принимает и возвращается . В противном случае отклонения и переходят к шагу 3.

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

Следующая функция реализует метод приемного отклонения для генерации случайных чисел от данного PDF , RNG grnd для , и константа :

Например, функция удовлетворяет условия для PDF на (неотрицательный, и объединяется к 1). Экспоненциальный PDF со средним значением 1 , доминирует для большего, чем приблизительно 2,2. Таким образом можно использовать rand и exprnd , чтобы сгенерировать случайные числа от :

PDF является на самом деле Распределение Релея с параметром формы 1. Этот пример сравнивает распределение случайных чисел, сгенерированных методом приемного отклонения со сгенерированными raylrnd :

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

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

Находит константу таким образом это для всех .

Генерирует универсальное случайное число .

Генерирует случайное число от .

Если , принимает и возвращается . В противном случае отклонения и переходят к шагу 3.

Похожие темы

Документация Statistics and Machine Learning Toolbox
Поддержка

© 1994-2020 The MathWorks, Inc.

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

2. Не дополняйте перевод комментариями “от себя”. В исправлении не должно появляться дополнительных смыслов и комментариев, отсутствующих в оригинале. Такие правки не получится интегрировать в алгоритме автоматического перевода.

3. Сохраняйте структуру оригинального текста — например, не разбивайте одно предложение на два.

4. Не имеет смысла однотипное исправление перевода какого-то термина во всех предложениях. Исправляйте только в одном месте. Когда Вашу правку одобрят, это исправление будет алгоритмически распространено и на другие части документации.

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

Поточные шифры и генераторы псевдослучайных чисел. Часть 1

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

Широкое распространение получил алгоритм генерации псевдослучайных чисел, называемый алгоритмом BBS (от фамилий авторов — L. Blum, M. Blum, M. Shub) или генератором с квадратичным остатком. Для целей криптографии этот метод предложен в 1986 году.

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

На каждом 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 . Вычислим стартовое число генератора х :

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

х1=9 2 mod 209= 81 mod 209= 81 младший бит: 1
х2=81 2 mod 209= 6561 mod 209= 82 младший бит:
х3=82 2 mod 209= 6724 mod 209= 36 младший бит:
х4=36 2 mod 209= 1296 mod 209= 42 младший бит:
х5=42 2 mod 209= 1764 mod 209= 92 младший бит:
х6=92 2 mod 209= 8464 mod 209= 104 младший бит:
х7=104 2 mod 209= 10816 mod 209= 157 младший бит: 1
х8=157 2 mod 209= 24649 mod 209= 196 младший бит:
х9=196 2 mod 209= 38416 mod 209= 169 младший бит: 1
х10=169 2 mod 209= 28561 mod 209= 137 младший бит: 1

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

Простейшими генераторами псевдослучайных чисел являются: линейный конгруэнтный генератор , генератор по методу Фибоначчи с запаздываниями, генератор на основе алгоритма Блюм – Блюма – Шуба ( BBS ).

Генерация случайных чисел

Дата создания: 2009-05-03 15:27:38
Последний раз редактировалось: 2012-02-08 06:53:25

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

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

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

Обычно используется генерация псевдослучайных чисел. Т.е. числа не совсем случайные. Мы уже рассматривали функцию rand(). Если Вы напишите программу использующую данную функцию, то при каждом запуске программы, rand() будет генерировать одну и ту же последовательность чисел. Последовательность сгенерированная rand() определяется начальным числом (seed). Сначала задаётся начальное число, затем, по определённой формуле вичисляются все остальные числа последовательности. Зная начальное число и формулу по которой рассчитываются числа, можно вычислить следующее число.

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

Одним из предопределённых (детерминистических) алгоритмов создания случайных чисел является линейно-конгруэнтный.

Установка начального значения (для функции rand(), которую мы использовали до сих пор) выглядит примерно так:

Функция srnd устанавливает начальное значение i.

Линейный конгруэнтный (linear congruential) метод генерации случайных чисел

Существует много методов генерации случайных чисел. Линейно-конгруэнтный лишь один из них. Метод довольно старый — 1950х годов. Разработал его Деррик Лемер.

Для реализации алгоритма необходиом задать четыре параметра:

Диапазон значений m, при этом m > 0.
Множитель a (0 = 2, b >= 1.

Вичислим шестой элемент с помощью этой формулы (мы ведь уже знаем пятый):

X5+1 = (a*1*X5 + (a*1-1)*c/b) % m = (2*1*5 + (2*1-1)*3/1) % 10 = 13 % 10 = 3

Всё росто, правда?

У последовательности созданной с помощью линейного конгруэнтного метода и определённой целыми параметрами m, a, c и X, период равен числу m когда выполняются следующие условия:
1.Наибольший общий делитель c и m равен 1.
2.b — кратно любому простому числу, являющемуся делителем m.
3.Если m кратно 4, тогда b также кратно 4.

Выбор m

Период не может быть больше числа m. Следовательно m должно быть довольно большим.

Примеры (x — целое число):

Очень часто для m выбирают одно из простых чисел Мерсенна [3] . Часто число 2 31 — 1 используется, когда вычисления ведутся с 32-ух битными данными.

Множитель a

Множитель нужно выбирать так, чтобы период был как можно длиннее. Существует серьёзная проблема с данным коэффициентом: при малых значениях a, если текущий элемент последовательности достаточно мал, вполне вероятно, что следующий элемент тоже будет маленьким.

Инкремент c

Данный параметр можно выбирать довольно произвольно. Очень часто его задают в виде нуля, но при этом уменьшается длина периода и X != 0.

Начальное значение (seed)

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

Вот так вот! Генерация последовательных чисел — это самая настоящая мистификация!

Каждый электрик должен знать:  Запах гари от новой люстры в чем причина и что делать

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

Вообще говоря, с помощью арифметических методов нельзя построить по настоящему случайную последовательность чисел. Как невесело шутил наш друг — Джон Фон Нейман:

«Anyone who uses arithmetic methods to produce random numbers is in a state of sin.» (C) Джон Фон Нейман.

Грустно всё это. Вот так живёшь-живёшь. Находясь в состоянии неведения, думаешь: «А вот круто бы было создать генератор случайных чисел на основе линейного когнруэнтного метода!». А оказывается что по настоящему случайную последовательность таким образом создать нельзя. Крах надежд! Депрессия и вот ты уже на пороге первой стадии алкоголизма. Этот груз невозможности реализовать свои желания будет давить на тебя всю оставшуюся жизнь. Что-то я отвлёкся. Продолжим.

Реализация генерации случайных чисел

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

Для последовательности рассмотренной выше, генератор будет выглядеть так:

X объявляется как глобальная переменная:

Это самый примитивный вариант генератора. В реальности такое чудовище использовать нельзя! Но мы будем это делать!

В данной реализации мы никак не отслеживаем возможность переполнения переменных. Вместо типа int используйте тип _int64 — это целый восьмибайтный тип.

Простые числа

Простые числа — числа которые можно разделить без остатка только на единицу и на само число. Например: 11, 3, 7.

Код Грея

[1] Код Грея представляет собой последовательность чисел, где следующее число отличается от предыдущей одним битом. Т.е. чтобы угадать последовательность, нужно смотреть не на десятичные числа, а на их двоичные эквиваленты.

Вот возрастающая последовательность чисел от 0 до 7 в двоичном коде:

Используя код Грея, получим такую последовательность:

Простые числа Мерсенна

[3] На данный момент известно 44 числа Мерсенна. Из названия понятно, что данные числа — простые, т.е. делятся только на единицу и на самих себя. Кроме того данные числа должны подчиняться следующей формуле:

Где n также простое число. Для первых девяти простых чисел Мерсенна n следующие: <2, 3, 5, 7, 13, 17, 19, 31, 61>.

Поразрядные логические операции

[2] Мы уже рассматривали логические операции && (И) и || (ИЛИ). Существуют также поразрядные логические операции & (поразрядное И) и | (поразрядное ИЛИ). Работате операция следующим образом:

То есть в данной операции сравниваются соответствующие позиции двух чисел и если они равны, то в результируюем числе в данной позиции пишется 1, в противном случае — ноль.

Степень числа

Другие генераторы случайных чисел

Кроме линейного конгруэнтного генератора существует множество других. Например Вихрь Мерсенна, изобретённый двумя японскими учёными (непомню как из зовут) в 1997. У него очень большой (очень большой это мягко сказано) период. Кстати, вихрь Мерсенна использует линейный конгруэнтный генератор для установления начального значения (seed).


Генераторы случайных чисел применяются при шифровании. Но здесь используются специальные генераторы — криптографически защищённые генераторы псевдослучайных чисел. Например блочный шифр (block cipher), потоковый шифр (stream cipher), который был разработан на основе шифра Вернама.

Упражнения:

Реализуйте генераторы случайных чисел на основе линейного когруэнтного метода. В качестве параметров воспользуйтесь следующими:

  • m = 2 32 ; a = 1664525; c = 1013904223. Данные параметры использовались в примере реализации генератора в одной старой книжке по Фортрану.
  • m = 2 32 ; a= 214013; c = 2531011; Данные параметры используется в реализации метода в Visual C++. При этом берутся старшие биты 30..16. Берутся именно верхние биты, т.к. в линейном конгруэнтном методе нижние биты гораздо менее случайны. Так как мы пока не умеем брать конкретные биты, можете использовать всё число.
  • В качестве m выберите одно из чисел Мерсенна. Начните с малых (2 3 -1,2 5 -1). Попробуйте подставить 2 31 -1 и 2 61 -1.

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

Как правильно генерировать псевдослучайные числа?

Доброго времени суток.

Из статьи на Хабре можно извлечь одну формулу:

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

Поэтому как правильно генерировать каким-либо алгоритмом псевдослучайные числа ? (Как, например в Питоне при random.randint(arg1, arg2) или как в Java при использовании new Random().nextInt(100)

P.S: В метках указан Python и Java, но на самом деле подойдет любой, желательно си-подобный, язык

  • Вопрос задан более трёх лет назад
  • 1800 просмотров

Судя по Вашему комментарию к ответу Ivan Sokolov Вы несколько не понимайте суть своего же вопроса.

Любое, повторюсь, абсолютно любое, псевдослучайное число будет находиться в какой-то последовательности, причем сама последовательность будет строиться по какой-то формуле.

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

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

Возьмем, например, функцию rand() из любого языка программирования. Она будет генерировать псевдослучайное число основываясь на метки времени в unixtime. На сколько она предсказуема? Хм, думаю не менее чем на 100%. Хорошо, получается что зная приблизительное время запуска функции rand(), скажем, с точностью до 1 минуты, мы можем получить точно такое же псевдослучайное число. Отлично, т.е. вот от этого нужно и копать.

Давайте предположим, что мы вытянули список компаний из ЕГРЮЛ по Москве и взяли их ОРГН. Далее, наша функция генерирует unixtime и из него мы вычитаем этот самый ОГРН, причем последние две цифтры в unixtime и ОГРН должны совпадать(к примеру, условие выбора ОГРН может быть любое). Чего мы добились? Зная время работы функции rand() мы не можем сгенерировать второе точно такое же псевдослучайное число. Вы мне можете сейчас возразить, что давайте возьмем тот же ОГРН и повторим процедуру. На этом месте я хочу задать Вам вопрос: а от кого мы вообще строим защиту? Злоумышленник является создателем системы и знает о ней 100%? Я думаю любая защита в этом случае просто бессмысленна.

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

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

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

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

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

Подробные инструкции смотрите ниже.

Количество чисел:
Диапазон случайных чисел:
от до
Упорядочить:
Разделитель чисел:
исключить повторы

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

По умолчанию выводится 1 число. Изменив настройки Количества цифр можно генерировать до 250 случайных цифр одновременно.

Задайте Диапазон. Максимальное значение — 9 999 999 999.

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

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

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

Скопируйте Ссылку на результат и разместите ее в социальной сети или отправьте другу

ГЕНЕРАТОРЫ ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

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

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

Интересно отметить, что в книге «Незнакомцы на мосту», написанной адвокатом разведчика Абеля, приводится термин «гамма», который специалисты ЦРУ пометили комментарием «музыкальное упражнение?», т.е. в пятидесятые годы они не знали его смысла.

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

Не следует думать, что они нужны лишь криптографам — картографирование Венеры стало возможным^ когда длина периода случайного ряда импульсов превысила 10. Фотографирование этой планеты нельзя было сделать потому, что она всегда закрыта плотным слоем облаков. Локация же ее с Земли затруднена обилием помех и высокими требованиями к разрешению. Поэтому зондирование выполнялось случайной последовательностью импульсов указанного периода. После 300 зондирований, на что ушло более полу- года, была получена карта, где различимы объекты размером около километра, а по высоте разрешение получено такое, какое достигнуто не везде на Земле. Генераторы псевдослучайных чисел используются очень широко в сотнях программных приложений — от конструирования ядерных реакторов и радиолокационных систем раннего обнаружения до поисков нефти и до многоканальной связи.

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

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

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

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

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

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

Если п пробегает значения натурального ряда чисел, то поведение Y(ri) выглядит весьма хаотичным. Еще Карл Якоби доказал, что при рациональном коэффициенте а множество конечно, а при иррациональном — бесконечно и всюду плотно в интервале от 0 до 1. Для многочленов больших степеней такая задача была решена лишь в 1916 г. выдающимся математиком прошедшего века Германом Вейлем. Кроме того, он установил критерий равномерности распределения любой функции от натурального ряда чисел. Небезынтересно привести его в краткой формулировке.

КРИТЕРИЙ ВЕЙЛЯ. Чтобы ряд Х, Xz, Х3, . был распределен равномерно в интервале от 0 до 1, необходимо и достаточно, чтобы для любой интегрируемой по Риману функции Дх) было справедливо соотношение Р <ДМ(х)) = МДх)>= 1.

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

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

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

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

Генератор последовательности Фибоначчи. Интересные классы генераторов случайных чисел неоднократно предлагались многими специалистами по целочисленной арифметике. В частности, Джордж Марсалиа и Ариф Зейман предложили класс генераторов псевдослучайных последовательностей, основанный на использовании последовательностей Фибоначчи, — в этой последовательности каждый последующий член, за исключением первых двух ее членов, равен сумме двух предыдущих:

Если эта последовательность применяется для начального заполнения массива большой длины, то, используя этот массив, можно создать генератор случайных чисел Фибоначчи с запаздыванием, где складываются не соседние, а удаленные числа. Марсалиа и Зейман предложили ввести в схему Фибоначчи «бит переноса», который может иметь начальное значение 0 или 1. Построенный на этой основе генератор «сложения с переносом» приобретает интересные свойства, на их основе можно создавать последовательности, период которых значительно больше, чем у применяемых в настоящее время конгруэнтных генераторов. По образному выражению Марсалиа, генераторы этого класса можно рассматривать как усилители случайности: «Вы берете случайное заполнение длиной в несколько тысяч бит и генерируете длинные последовательности случайных чисел».

Один из вариантов генератора последовательности Фибоначчи показан на рис. 16.1:

Рис. 16.1. Генератор последовательности Фибоначчи

Здесь квадратами обозначены разряды генератора, треугольниками — умножение на коэффициенты (на практике в зависимости от коэффициента там либо есть соединение с последующей логикой, либо его нет). Плюсы в кружках — это операция XOR: 0 + 0 = 0,

Рекуррентные двоичные последовательности. Линейные последовательности максимальной длины в основном получают с помощью генераторов, использующих в качестве основных элементов TV- каскадные регистры сдвига и сумматоры по модулю 2 (фильтр Хаффмана). Генератор состоит из хорошо отработанных стандартных импульсных элементов и при минимальном их числе обеспечивает получение последовательности с максимальным периодом (М-последова- тельность). Достоинствами такого типа генератора являются фиксированная амплитуда, легко и в весьма широком диапазоне регулируемая ширина спектра сигнала, а также возможность путем небольших усложнений получать сдвинутые по шкале времени сигналы.

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

  • — должно быть задано правило подключения сумматоров (осо, 0С2, . ад);
  • — ао и aN всегда равны 1 (поэтому на схеме их можно не указывать);
  • — из всех а„ /е <1, 2, . N — 1>, хотя бы одно должно иметь значение ‘Г.

Рис. 16.2. Фильтр Хаффмана


Циклические свойства генератора последовательности определяются так называемым характеристическим полиномом

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

ГППМД составляют основу так называемых генераторов псевдослучайных чисел. Для этого к регистру сдвига добавляются сумматоры по модулю 2. При работе регистра сдвига на выходе этих элементах образуются М-последовательности <а*+Л, задержанные относительно исходной последовательности <а>>, полученной на выходе цепи обратной связи, на определенное число тактов. Величину задержки можно регулировать в пределах от N + 1 до Т = 2 Л — 1. При этом на выходе данного генератора получаются равномерно распределенные псевдослучайные числа.

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

Метод линейного сравнения (конгруэнтные генераторы). Безусловно, самым популярным алгоритмом для генерирования псевдослучайных чисел является алгоритм, предложенный Д.Х. Лемером (Lehmer) и называемый методом линейного сравнения (конгруэнтным способом).

Этот алгоритм имеет четыре следующих параметра:

т модуль сравнения т > 0,

а множитель 0 31 .

Кроме значений т — 2″ широко используются выборы простыхш, например, простого числа т = 2 31 — 1, известного со времен Эйлера (это число «плохо» тем, что в двоичной записи содержит лишь единицы. Однако оно может использоваться, если вычисления выполняются в десятичной арифметике).

Для иллюстрации важности выбора «хороших» параметров алгоритма рассмотрим, например, случай а = с = 1. Порождаемая при этом последовательность, очевидно, не будет удовлетворительной. Теперь рассмотрим значения а — 7, с — 0, т = 32 и Хо = 1. В этом случае генерируется последовательность <7, 17, 23, 1, 7, . >, которая также, очевидно, не будет удовлетворительной. Из 32 возможных значений здесь оказываются задействованными только 4 (в данном случае говорят, что последовательность имеет период 4). Если же, оставив другие значения прежними, изменить значение а и положить а = 5, то результирующей последовательностью будет <1, 5, 25, 29, 17, 21,9, 13, 1. >и ее период будет равен уже 8.

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

  • 1. Генерирующая функция должна быть функцией полного периода, т.е. функция должна порождать все числа от 0 до т, прежде чем числа начнут повторяться.
  • 2. Генерируемая последовательность должна вести себя как случайная. На самом деле эта последовательность не будет случайной, поскольку генерируется детерминированным алгоритмом, но существует множество статистических тестов, которые можно использовать, чтобы оценить степень случайности поведения последовательности.
  • 3. Генерирующая функция должна эффективно реализовываться в рамках 32-битовой арифметики.

Все эти три критерия могут быть удовлетворены при подходящем выборе значений а, с и т. Относительно первого критерия можно доказать, что если т является простым и с = 0, то для определенных значений а период генерируемой функцией последовательности оказывается равным т — 1, и в этой последовательности будет отсутствовать только значение 0.

В 32-битовой арифметике удобным простым значением для т является значение 2 31 — 1 (см. его недостатки выше). В этом случае генерирующая функция принимает вид

Из более чем двух миллионов возможных значений а только горстке множителей соответствуют функции, выдерживающие все три теста. Одним из них является значение а = 7 — 16 807, которое было найдено и использовано для семейства компьютеров IBM/360. Соответствующий генератор находит очень широкое применение, и поэтому он был подвергнут более тщательному анализу, чем любой другой генератор псевдослучайных чисел. Он нередко рекомендуется для статистического и имитационного моделирования различных процессов.

Преимуществом алгоритма линейного сравнения является то, что если выбрать подходящие множитель и модуль сравнения, то генерируемая последовательность чисел оказывается статистически неотличимой от последовательности чисел, выбираемых случайно (но безвозвратно) из множества чисел 1, 2, . т — 1. Но в самом алгоритме нет ничего случайного вообще, кроме выбора начального значения Xq. Если это значение выбрано, остальные числа последовательности определяются им однозначно. Это оказывается очень важным с позиций криптоанализа.

Если противник знает, что используется алгоритм линейного сравнения, и если к тому же ему известны параметры алгоритма (например, а = 7 5 , с = 0, т = 2 31 — 1), то, открыв всего одно число, противник сможет получить и все последующие. Но даже если оппонент знает только то, что выбран алгоритм линейного сравнения, знания небольшой части последовательности уже достаточно для того, чтобы определить все параметры алгоритма.

Предположим, например, что противник сможет определить значения Xq, Х, Х2 и A3. Тогда

Эти уравнения могут быть решены относительно а, с и т.

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

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

Линейный конгуэнтный генератор псевдослучайных чисел (ЛКГ ПСЧ)

  • x — начальное значение (инициализирующий вектор)
  • a — множитель
  • b — приращение
  • m — модуль

Нелинейные конгуэнтные генераторы псевдослучайных чисел (НКГ ПСЧ)

Физические датчики случайных процессов

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

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

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

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

Современная информатика широко использует псевдослучайные числа в самых разных приложениях — от метода Монте-Карло и имитационного моделирования до криптографии. При этом от качества используемых ГПСЧ напрямую зависит качество получаемых результатов. Это обстоятельство подчёркивает известный афоризм математика ORNL Роберта Кавью : «генерация случайных чисел слишком важна, чтобы оставлять её на волю случая».

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

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

У физических источников случайных чисел существует ряд недостатков:

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

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

Качественные требования, предъявляемые к ГПСЧ

  • Достаточно длинный период, гарантирующий отсутствие зацикливания последовательности в пределах решаемой задачи. Длина периода должна быть математически доказана;
  • Эффективность — быстрота работы алгоритма и малые затраты памяти;
  • Воспроизводимость — возможность заново воспроизвести ранее сгенерированную последовательность чисел любое количество раз;
  • Портируемость — одинаковое функционирование на различном оборудовании и операционных системах;
  • Быстрота получения X n + i <\displaystyle X_> элемента последовательности чисел, при задании X n <\displaystyle X_> элемента, для i <\displaystyle i>любой величины; это позволяет разделять последовательность на несколько потоков (последовательностей чисел). [3]

Ранние подходы к формированию ПСЧ

Джон фон Нейман считал неприемлемым использование физических генераторов случайных чисел в вычислительной технике, так как при возникновении необходимости проверки вычислений повтор предыдущих действий требовал бы воспроизведение случайного числа, в то время как генерация нового случайного числа недопустима. Предварительная запись и хранение сгенерированных случайных чисел предполагало бы возможность их считывания. Механизм считывания данных являлся одним из самых слабых звеньев вычислительных машин 1940-х годов. Джон фон Нейман привёл следующий метод «середины квадрата» (англ. middle-square method ) [4] получения десятизначных псевдослучайных чисел:

Десятизначное число возводится в квадрат, затем из середины квадрата числа берётся десятизначное число, которое снова возводится в квадрат, и так далее.

В 1951 году Д. Г. Лемер предложил линейный конгруэнтный метод, [5] суть которого заключается в задании последовательности целых чисел рекурсивной формулой X n + 1 = ( a X n + c ) mod m , <\displaystyle X_=(aX_+c)

>>m> , а также то, что ПСЧ зацикливается.

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

Алгоритм

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

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

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

Одноразовый блокнот

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

Недостатки ГПСЧ

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

Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается — начинает повторять одну и ту же последовательность чисел. Длина циклов ГПСЧ зависит от самого генератора и составляет около 2 n 2 <\displaystyle 2^<\frac <2>>> , где n <\displaystyle n>— размер внутреннего состояния в битах, хотя линейные конгруэнтные и РСЛОС-генераторы обладают максимальными циклами порядка 2 n <\displaystyle 2^> [7] . Если порождаемая последовательность ГПСЧ сходится к слишком коротким циклам, то такой ГПСЧ становится предсказуемым и непригодным для практических приложений.


Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков:

  • Слишком короткий период/периоды.
  • Последовательные значения не являются независимыми.
  • Некоторые биты «менее случайны», чем другие.
  • Неравномерное одномерное распределение.
  • Обратимость.

В частности, алгоритм RANDU, десятилетиями использовавшийся на мейнфреймах, оказался очень плохим [8] [9] , что вызвало сомнения в достоверности результатов многих исследований, использовавших этот алгоритм.

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

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

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

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

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

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

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

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

Источник энтропии ГПСЧ Достоинства Недостатки
/dev/random в UNIX/Linux Счётчик тактов процессора, однако собирается только во время аппаратных прерываний РСЛОС, с хешированием выхода через SHA-1 Есть во всех Unix, надёжный источник энтропии Очень долго «нагревается», может надолго «застревать», либо работает как ГПСЧ (/dev/urandom)
Yarrow от Брюса Шнайера [12] Традиционные методы AES-256 и SHA-1 маленького внутреннего состояния Гибкий криптостойкий дизайн Медленный
Microsoft CryptoAPI Текущее время, размер жёсткого диска, размер свободной памяти, номер процесса и NETBIOS-имя компьютера MD5-хеш внутреннего состояния размером в 128 бит Встроен в Windows, не «застревает» Сильно зависит от используемого криптопровайдера (CSP).
Java SecureRandom Взаимодействие между потоками SHA-1-хеш внутреннего состояния (1024 бит) Большое внутреннее состояние Медленный сбор энтропии
RdRand от intel [13] Шумы токов Построение ПСЧ на основе «случайного» битового считывания значений от токов [13] Очень быстр, не «застревает» Оригинальная разработка, свойства приведены только по утверждению разработчиков.

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

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

Примерами известных криптостойких ГПСЧ являются RC4 [7] , ISAAC [14] , SEAL [15] , SNOW [16] , совсем медленный теоретический алгоритм Блюм — Блюма — Шуба [7] , а также счётчики с криптографическими хеш-функциями или криптостойкими блочными шифрами вместо функции вывода [7] .

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

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

ANSI X9.17

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

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

Кроме устаревших, хорошо известных РСЛОС-генераторов, широко применявшихся в качестве аппаратных ГПСЧ в XX веке, очень мало известно о современных аппаратных ГПСЧ, так как большинство из них разработано для военных целей или запатентованы и держатся в секрете. Аппаратно реализуемые РСЛОС-генераторы Toyocrypt и LILI-128, были взломаны с помощью алгебраических атак [19] [20] .

В настоящее время известно о применении аппаратных ГПСЧ, реализуемых на основе маломощных шумов в электросхемах. [21]

Применение ГПСЧ в лотереях

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

Попытки создать генератор случайных чисел относятся к 3500 году до н. э. и связаны с древнеегипетской настольной игрой Сенет. В Сенете два игрока играют за две стороны. Ходы определяются с помощью 4 плоских палочек, что и может считаться генератором случайных чисел того времени. Бросают все четыре палочки сразу. Подсчёт очков происходит следующим образом: 1 палочка упала белой стороной вверх — 1 очко и дополнительный бросок; 2 — 2 очка; 3 — 3 очка, 4 — 4 и дополнительный бросок. Одна из сторон палочки чёрная и если все четыре палочки падали чёрной стороной вверх — это максимальный результат — 5 очков и дополнительный бросок.

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

Основные требования к программному обеспечению и оборудованию, используемому для проведения розыгрышей в Российской Федерации, устанавливаются Федеральным законом от 11.11.2003 № 138-ФЗ «О лотереях»:

  • Технические характеристики лотерейного оборудования должны обеспечивать случайность распределения выигрышей при розыгрыше призового фонда тиражных лотерей.
  • Не должны использоваться процедуры, реализующие алгоритмы, которые позволяли бы предопределять результат розыгрыша призового фонда до начала такого розыгрыша.
  • Лотерейное оборудование, используемое при проведении тиражной лотереи, должно обеспечивать защиту информации от утраты, хищения, искажения, несанкционированных действий по её уничтожению, модификации, копированию и иных подобных действий и несанкционированного доступа по сети передачи данных. [22]

В российских государственных лотереях («Гослото «5 из 36», «Гослото «6 из 36», «Гослото «6 из 45», «Гослото «7 из 49», «Гослото «4 из 20», «Спортлото 6 из 49») [23] для определения победителей используются самозаряжающиеся лототроны. Трансляция розыгрышей ведется в прямом эфире. [24]

В российских государственных лотереях («Рапидо», «Кено-Спортлото», «Топ-3», «12/24», «Всё по сто») для определения победителей используется генератор случайных чисел — аппаратно-программный комплекс, сертифицированный АНО «МИЦ» и отвечающий рекомендациям ФГУП ВНИИМС. Аппарат формирует непрерывный поток случайных шумов, которые преобразуются в числа. В заданный момент времени из потока выхватываются текущие значения, которые и являются выигрышной лотерейной комбинацией. [25]

В 2015 году бывшему директору по безопасности US Multi-State Lottery Association после выигрыша в 16.5 млн. долларов, имевшему доступ к программному обеспечению, используемому при розыгрышах лотерей, было предъявлено обвинение в использовании специальных алгоритмов, позволяющих определять выигрышную комбинацию лотереи в течение нескольких дней в году. [26]

См. также

Примечания

  1. N.G. Bardis, A.P. Markovskyi, N. Doukas, N. V. Karadimas.True Random Number Generation Based on Environmental Noise Measurements for Military Applications // Proceedings of the 8th WSEAS International Conference on SIGNAL PROCESSING, ROBOTICS and AUTOMATION. — 2009. — С. 68-73 . — ISBN 978-960-474-054-3. — ISSN1790-5117.
  2. ↑Random.org .
  3. 123456L’Ecuyer, Pierre.Random Number Generation // Springer Handbooks of Computational Statistics : Глава. — 2007. — С. 93 — 137 . — DOI:10.1002/9780470172445.ch4.
  4. Von Neumann, John.Various techniques used in connection with random digits // National Bureau of Standards Applied Mathematics Series. — 1951. — № 12 . — С. 36-38 .
  5. Lehmer, D.H.Mathematical Methods in Large-Scale Computing Units // Ann, Comput Lab. Harvard Univ.. — 1951. — Vol. 26. — С. 141-146 . (недоступная ссылка)
  6. ↑Intel Digital Random Number Generator (DRNG): Software Implementation Guide, Revision 1.1 (PDF). Intel Corporation (7 августа 2012). Дата обращения 25 ноября 2012.Архивировано 18 мая 2013 года.
  7. 12345Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И., Владимиров С. М.Защита информации. Учебное пособие. — С. 100-113.
  8. Дональд Кнут. Глава 3.3. Спектральный критерий // Искусство программирования. Указ. соч. — С. 129—130.
  9. William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numerical Recipes in C: The Art of Scientific Computing. — 2nd ed. — Cambridge University Press, 1992. — P. 277. — ISBN 0-521-43108-5.
  10. ↑Из квантового вакуума получили случайные числа
  11. Jovan Dj. Goli ́c.Cryptanalytic Attacks on MIFARE >№ 7779 . — С. 239-259 . — DOI:10.1007/978-3-642-36095-4_16.
  12. 12Yarrow
  13. 12Intel DRNG Software Implementation Guide . Intel.
  14. J.-P. Aumasson.On the pseudo-random generator ISAAC // Cryptology ePrint Archive. — 2006.
  15. H. Chen, K. Laine, R. Player. [https://eprint.iacr.org/2020/224.pdf Simple Encrypted Arithmetic Library — SEAL v2.1] // Cryptology ePrint Archive. — 2020.
  16. A. Kircanski and A. M. Youssef. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.301.2615&rep=rep1&type=pdf On the Sl >№ 5(4) . — С. 199-206 .
  17. Лапонина О. Р.Алгоритмы симметричного шифрования . НОУ ИНТУИТ.
  18. Kelsey J., Schneier B., Wagner D., Hall C.Cryptanalytic Attacks on Pseudorandom Number Generators // Fast Software Encryption. FSE 1998. Lecture Notes in Computer Science. — Springer, Berlin, Heidelberg, 1998. — Vol. 1372. — DOI:10.1007/3-540-69710-1_12.
  19. N. T. Courtois.Higher Order Correlation Attacks, XL Algorithm and Cryptanalysis of Toyocrypt // Cryptology ePrint Archive. — 2002.
  20. Ed Dawson, Andrew Clark, J Golic, W Millan, L Penna.The LILI-128 Keystream Generator. — 2000-12-13.
  21. C. S. Petrie, J. A. Connelly.A noise-based IC random number generator for applications in cryptography // IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications. — May 2000. — Vol. 47, № 5 . — С. 615–621 . — ISSN1057-7122. — DOI:10.1109/81.847868.
  22. ↑Статья 12.1. Требования к лотерейному оборудованию и лотерейным терминалам .
  23. ↑Ответы на вопросы о «Столото» . Сто Лото.
  24. ↑Трансляции розыгрышей государственных лотерей . Сто Лото.
  25. ↑Генератор случайных чисел . Сто Лото.
  26. ↑Man hacked random-number generator to rig lotteries, investigators say, The Guardian.

Литература

  • Дональд Э. Кнут. Глава 3. Случайные числа // Искусство программирования = The Art of Computer Programming. — 3-е изд. — М. : Вильямс, 2000. — Т. 2. Получисленные алгоритмы. — 832 с. — 7000 экз. — ISBN 5-8459-0081-6 (рус.) ISBN 0-201-89684-2 (англ.).
  • Кельтон В., Лоу А. Имитационное моделирование. Классика CS. — 3-е изд.. — СПб. : Питер, 2004. — С. 465, 466. — 487 с. — ISBN 0070592926. — ISBN 5-94723-981-7.
  • L’Ecuyer, Pierre.Random Number Generation // Springer Handbooks of Computational Statistics : Глава. — 2007. — С. 93 — 137 . — DOI:10.1002/9780470172445.ch4.

Ссылки

  • В. А. Успенский.Четыре алгоритмических лица случайности. — МЦНМО, 2006. — 48 с. — ISBN 978-5-94057-485-9.
  • Юрий Лифшиц. Лекция 9: Псевдослучайные генераторы // Современные задачи криптографии. — Курс лекций.
  • Л. Бараш.Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел // Безопасность информационных технологий. — 2005. — № 2 . — С. 27-38 . Архивировано 18 октября 2014 года.
  • Жельников В. Псевдослучайные последовательности чисел // Кpиптография от папируса до компьютера. — М. : ABF, 1996. — 335 с. — ISBN 5-87484-054-0.
  • Cryptographic Random Numbers (англ.)
  • Theory and Practice of Random Number Generation (англ.)
  • Zvi Gutterman, Benny Pinkas, Tzachy Reinman. Analysis of the Linux Random Number Generator (англ.)
  • A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (англ.) NIST SP 800-22

На других языках

This page is based on a Wikipedia article written by authors (here).
Text is available under the CC BY-SA 3.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

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

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

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

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

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

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

Детерминированные генераторы простых случайных чисел достаточно распространены, хоть никакой детерминированный алгоритм и не может генерировать полностью случайные числа, он может только аппроксимировать некоторые их свойства. Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается — начинает повторять одну и ту же последовательность чисел. Длина циклов ГПСЧ зависит от самого генератора и составляет около 2п/2, где п — размер внутреннего состояния в битах, хотя линейные конгруэнтные и LFSR-генераторы обладают максимальными циклами порядка 2п. Если порождаемая ГПСЧ последовательность сходится к слишком коротким циклам, то такой ГПСЧ становится предсказуемым и непригодным для практических приложений. Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков:

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

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

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

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

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

  • 1) Назовите основные недостатки простых генераторов случайных чисел.
  • 2) Назовите основные виды генераторов псевдослучайных чисел.
  • 3) Что такое генератор случайных чисел.
  • 4) Назовите отличие псевдослучайных чисел ог истинно случайных.
  • 5) Охарактеризуйте аппаратный генератор случайных чисел.
  • 6) Чем отличается детерминированные ГПСЧ от ГПСЧ с источником энтропии?

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

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

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

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

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

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

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

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

3) a — 1 кратно 4, если m кратно 4.

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

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

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

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

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

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

где — вещественные числа из диапазона [0,1), a,b — целые положительные числа, называемые лагами. Для работы фибоначчиеву датчику требуется знать max предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел используется конечная циклическая очередь на базе массива. Для старта фибоначчиевому датчику требуется max случайных чисел, которые могут быть сгенерированы простым конгруэнтным датчиком.

Лаги a и b — «магические» и их не следует выбирать произвольно. Рекомендуются следующие значения лагов: (a, b) = (55,24), (17,5) или (97,33). Качество получаемых случайных чисел зависит от значения константы, a чем оно больше, тем выше размерность пространства, в котором сохраняется равномерность случайных векторов, образованных из полученных случайных чисел. В то же время, с увеличением величины константы a увеличивается объём используемой алгоритмом памяти.

Значения (a,b) = (17,5) можно рекомендовать для простых приложений, не использующих векторы высокой размерности со случайными компонентами. Значения (a,b) = (55,24) позволяют получать числа, удовлетворительные для большинства алгоритмов, требовательных к качеству случайных чисел. Значения (a,b) = (97,33) позволяют получать очень качественные случайные числа и используются в алгоритмах, работающих со случайными векторами высокой размерности. Получаемые случайные числа обладают хорошими статистическими свойствами, причём все биты случайного числа равнозначны по статистическим свойствам.

Вихрь Мерсенна (Mersenne twister) — это генератор псевдослучайных чисел, основанный на свойствах простых чисел Мерсенна и обеспечивает быструю генерацию высококачественных псевдослучайных чисел. Вихрь Мерсенна лишен многих недостатков присущих другим ГПСЧ таких как малый период, предсказуемость, легко выявляемая статистическая зависимость.

Вихрь Мерсенна является витковым регистром сдвига с обобщённой отдачей (twisted generalised feedback shift register, TGFSR). «Вихрь» — это преобразование, которое обеспечивает равномерное распределение генерируемых псевдослучайных чисел в 623 измерениях (для линейных конгруэнтных генераторов оно ограничено 5-ю измерениями). Поэтому корреляция между последовательными значениями в выходной последовательности Вихря Мерсенна пренебрежимо мала.

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

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

где n — целое, которое обозначает степень рекуррентности,

Каждый электрик должен знать:  Чем опасна контрольная лампа и почему она запрещена правилами
Добавить комментарий