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

 

 

Содержание

 

 

 

      1.Введение

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

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

         3.1. Регистр сдвига с обобщённой обратной связью

         3.2. RANDU

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

         3.4. Метод Фибоначчи с запаздываниями

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

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

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

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

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

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

              5.1.2. ANSI X9.17

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

7. Литература

 

 

 

 

 

 

 

 

 

Введение

 

Все процессы в мире происходят либо по воле случая, либо же по заранее  предусмотренному плану или закономерности.  
Фактически в любой сфере нашей жизни мы используем случайные числа. Подкидывая монетку, играя в покер или лотерею, придумывая числовой пароль, или же создавая игру, вы используете случайные числа или специально придуманный генератор случайных чисел.  
Генератор случайных чисел (ГСЧ) – это алгоритм, который генерирует практически независимые друг от друга числа в последовательность. Объединяет их разве что заданное распределение.  
Работа ГСЧ зависит от заранее написанного алгоритма. Исходя из этого, можно говорить о псевдо случайности этих чисел. Поэтому бытует выражение, что в нашем мире ничто не случайно, каким бы случайным оно не казалось.  
Согласно всем научным статьям, генератор случайных чисел имеет более правильное название – генератор псевдослучайных чисел. Просто для удобства использование слова "псевдо" опускается.  
Фактически все алгоритмы ГСЧ сильно зависят от языка программирования и вычислительной платформы.  
Принцип работы всех видов генераторов достаточно простой – применяется внутренняя функция, которая выбирает случайные значения в пределах установленного диапазона.  
Но есть ещё одна сфера деятельности, где используются такие алгоритмы – криптография. Для создания абсолютно новых и недоступных паролей и ещё целого множества функций генераторы случайных чисел предназначены как нельзя кстати.  

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

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

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

Генератор псевдослучайных  чисел включён в состав многих современных процессоров (напр., семейства x86).

 

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

 

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

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

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

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

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

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

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

 

Регистр сдвига с обобщённой обратной связью

Регистр сдвига с обобщённой обратной связью (англ. Generalized feedback shift register (GFSR)) - вариант генератора псевдослучайных чисел (ГПСЧ) Таусворта, предложенный Льюисом и Пейном в 1973 году.

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

Каждый столбец последовательности подчиняется рекурсии

,

где   - XOR, или аналог сложения по модулю 2, а  , каждое слово также должно подчиняться рекурсии

.

 

Содержание  1 Алгоритм GFSR 2 Пример 3 Среднее значение, дисперсия и корреляция 4 Плюсы и минусы

Алгоритм GFSR 

1. Если  , переходите к пункту 2 (  изначально ноль).
2. Изначально   используют задержанную базовую последовательность  , для получения каждого столбца  .
3. .
4. Если  , установить  .
5. .
6. Если  , установить  .
7. EXCLUSIVE-OR,  ,
8. Запомнить,  .

Пример 

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

Каждое  , появляется только один раз в течение всего периода из   числа.

Сопровождающая матрица для полинома  :

Составим матрицу, столбцами  которой являются слова  , обозначим её   и перемножим на матрицу  :

Мы получили матрицу, столбцами  которой являются слова  . В матричном виде  . После   применения этой матрицы  .

Среднее значение, дисперсия и корреляция 

Теоретическое среднее значение и дисперсия алгоритма гарантируются его периодичностью.

В общем случае:

, где 

Для L-битной машины:

.

На нормализованном (0, 1) интервале:  .

Дисперсия:

,

и на нормализованном интервале (0, 1):  .

Корреляция получается усреднением по всему периоду:

.

Плюсы и минусы 

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

Минусом алгоритма является то, что во многих областях требуется  значительно больший период генерируемой последовательности, чем может дать алгоритм РСсООС.

Вихрь Мерсенна (англ. Mersenne twister, MT) — генератор псевдослучайных чисел (ГПСЧ), разработанный в 1997 году японскими учёными Макото Мацумото (яп. 松本 眞) и Такудзи Нисимура (яп. 西村 拓士). Вихрь Мерсенна основывается на свойствах простых чисел Мерсенна (отсюда название) и обеспечивает быструю генерацию высококачественных псевдослучайных чисел. Вихрь Мерсенна лишен многих недостатков, присущих другим ГПСЧ, таких как малый период, предсказуемость, легко выявляемая статистическая зависимость. Тем не менее этот генератор не является крипто стойким, что ограничивает его использование в криптографии.

RANDU

 

 

Распределение в трёхмерном пространстве 100 000 точек, полученных алгоритмом RANDU. Можно видеть, что точки расположены на 15 плоскостях.

RANDU — печально известный линейный конгруэнтный генератор псевдослучайных чисел, вошедший в употребление в 1960-х. Он определяется рекуррентным соотношением:

где   нечётное.

Псевдослучайные числа вычисляются  следующим образом:

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

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

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

что, в свою очередь, показывает наличие  линейной зависимости (а следовательно, и полной корреляции) между тремя соседними элементами последовательности:

Как следствие корреляции, точки  в трёхмерном пространстве, координаты которых получены по данному алгоритму, располагаются на сравнительно небольшом  количестве плоскостей (в приведённом  примере — на 15 плоскостях).

Пример 

Пример псевдослучайной последовательности, порождаемой алгоритмом RANDU при начальном  значении  :

            1

        65539

       393225

      1769499

      7077969

     26542323

     95552217

    334432395

   1146624417

   1722371299

     14608041

          ...

    134633675

   1893599841

   1559961379

    907304297

   2141591611

    388843697

    238606867

     79531577

    477211307

            1

 

 

 

 

 

 

 

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

 

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

Содержание  1 Описание 2 Свойства 3 Часто используемые параметры 4 Крипто анализ

Описание 

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

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

Свойства 

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

1. НОД(c,m) = 1 (то есть, c и m взаимно просты);
2. a-1 кратно p для всех простых делителей p числа m;
3. a-1 кратно 4, если m кратно 4.

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