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

 

 

Содержание

 

 

 

      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. Для этих констант выписаны^[кем?] условия, гарантирующие удовлетворительное качество получаемых случайных чисел.

Часто используемые параметры 

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

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

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

 

 

 

 

 

 

 

Source	m	a	c	выдаваемые биты результата в rand() /  Random(L)
Numerical Recipes (англ.)	232	1664525	1013904223
MMIX Д. Кнута	264	6364136223846793005	1442695040888963407
Borland C/C++	232	22695477	1	биты 30..16 в rand(), 30..0 в lrand()
GNU Compiler Collection	232	69069	5	биты 30..16
ANSI C: Open Watcom, Digital Mars, Metrowerks, IBM VisualAge C/C++	232	1103515245	12345	биты 30..16
Borland Delphi, Virtual Pascal	232	134775813	1	биты 63..32 числа (seed * L)
Microsoft Visual/Quick C/C++	232	214013	2531011	биты 30..16
Apple CarbonLib	231 - 1	16807	0	см. Метод Лемера (англ.)

 

Крипто анализ 

Особенностью линейного  конгруэнтного метода является то, что если сомножитель и модуль соответствующим образом подобраны, то результирующая последовательность чисел будет статистически неотличима от случайной последовательности элементов  множества { 0, 1, 2, …, m-1 }. Однако, все элементы этой последовательности однозначно определяются четырьмя параметрами: X₀, a, c, m.

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

из которой можно получить значения параметров а, с и m.

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

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

 

Метод Фибоначчи с запаздываниями (Lagged Fibonacci generator) — один из методов генерации псевдослучайных чисел.

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

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

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

Формулы 

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

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

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

,

где   — число битов в мантиссе вещественного числа.

Выбор параметров 

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

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

 

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

 

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

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

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

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

 

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

 

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

 

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

 

	Источник энтропии	ГПСЧ	Достоинства	Недостатки
/dev/random вUNIX/ Linux	Счётчик тактов процессора, однако собирается только во время аппаратных прерываний	LFSR, с хешированием выхода через SHA-1	Есть во всех Unix, надёжный источник энтропии	Очень долго «нагревается», может надолго «застревать», либо работает как ГПСЧ (/dev/urandom)
Yarrow отБрюса Шнайера[4]	Традиционные методы	AES-256 и  SHA-1 маленького внутреннего состояния	Гибкий крипто стойкий дизайн	Медленный
MicrosoftCryptoAPI	Текущее время, размер жёсткого диска, размер свободной памяти, номер  процесса и NETBIOS-имя компьютера	MD5-хеш внутреннего состояния размером в 128 бит	Встроен в Windows, не «застревает»	Сильно зависит от используемого  криптопровайдера (CSP).
JavaSecureRandom	Взаимодействие между  потоками	SHA-1-хеш внутреннего состояния (1024 бит)	Большое внутреннее состояние	Медленный сбор энтропии
Chaos от Ruptor	Счётчик тактов процессора, собирается непрерывно	Хеширование 4096-битового внутреннего  состояния на основе нелинейного  варианта Marsaglia-генератора	Пока самый быстрый  из всех, большое внутреннее состояние, не «застревает»	Оригинальная разработка, свойства приведены только по утверждению  автора
RRAND от Ruptor[6]	Счётчик тактов процессора	Зашифровывание внутреннего  состояния поточным шифром EnRUPT в authenticated encryption режиме (aeRUPT)	Очень быстр, внутреннее состояние произвольного размера по выбору, не «застревает»	Оригинальная разработка, свойства приведены только по утверждению  автора. Шифр EnRUPT не является криптостойким.

 

 

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

 

Основная статья: Криптографически стойкий генератор псевдослучайных чисел

Разновидностью ГПСЧ являются ГПСБ (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 — ключи, используемые на каждой стадии.