Датчики случайных чисел и псевдослучайные последовательности
Генератор псевдослучайных чисел — алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).Источники настоящих случайных чисел найти крайне трудно. Физические шумы, такие, как детекторы событий ионизирующей радиации, дробовой шум в резисторе или космическое излучение, могут быть такими источниками. Однако применяются такие устройства в приложениях сетевой безопасности редко. Сложности также вызывают грубые атаки на подобные устройства.
У физических источников случайных чисел существует ряд недостатков:
Время и трудозатраты при установке и настройке по сравнению с программными ГПСЧ;
Дороговизна;
Генерация случайных чисел происходит медленнее, чем при программной реализации ГПСЧ;
Невозможность воспроизведения ранее сгенерированной последовательности случайных чисел.
В то же время случайные числа, получаемые из физического источника могут использоваться в качестве порождающего элемента для программных ГПСЧ. Такие комбинированные генераторы применяются в криптографии, лотереях, игровых автоматах.
Качественные требования, предъявляемые к ГПСЧ
Достаточно длинный период, гарантирующий отсутствие зацикливания последовательности в пределах решаемой задачи. Длина периода должна быть математически доказана;
Эффективность — быстрота работы алгоритма и малые затраты памяти;
Воспроизводимость — возможность заново воспроизвести ранее сгенерированную последовательность чисел любое количество раз;
Портируемость — одинаковое функционирование на различном оборудовании и операционных системах;
Быстрота получения
элемента последовательности чисел, при задании 
элемента, для 
любой величины; это позволяет разделять последовательность на несколько потоков (последовательностей чисел).
Десятизначное число возводится в квадрат, затем из середины квадрата числа берётся десятизначное число, которое снова возводится в квадрат, и так далее.
Например, для 4-значных чисел, начиная с 1234, получаем
, где берём средние 4 цифры 
(дописав ноль в начале, если это необходимо). Затем возводим полученное число в квадрат 
, и так далее. Недостатком данного метода является ограниченность множества ПСЧ из-за того, что последовательность зацикливается — 
.
В 1951 году Д. Г. Лемер предложил линейный конгруэнтный метод, суть которого заключается в задании последовательности целых чисел рекурсивной формулой
где 
— целые и удовлетворяют следующим условиям: 
. Недостатком данного метода является зависимость 
от 
, так как 
, а также то, что ПСЧ зацикливается.
Большинство детерминированных ГПСЧ соответствуют структуре, предложенной П. Лекуером в 1994 году:
, где 
— это конечный набор состояний, 
— вероятностное распределение в пространстве состояний , используемое для выбора начального состояния 
, }
— функция перехода, 
— пространство выходных значений, 
. Обычно 
, а состояние генератора задается рекуррентной формулой 
для 
. Выходное значение генератора
; 
— последовательность псевдослучайных чисел. Так как конечно, то должны существовать некоторые конечные 
и 
такие, что 
. Значит, для всех
будут выполняться условия 
и 
, потому что функции 
и 
детерминированные. Таким образом, получается, что последовательность периодическая. Периодом ГПСЧ называется минимальное положительное 
.
Наиболее распространены линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, регистр сдвига с линейной обратной связью, регистр сдвига с обобщённой обратной связью.
Из современных ГПСЧ широкое распространение также получил «вихрь Мерсенна», предложенный в 1997 году Мацумото и Нисимурой. Его достоинствами являются колоссальный период (219937−1), равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение максимум в 5 измерениях), быстрая генерация случайных чисел (в 2-3 раза быстрее, чем стандартные ГПСЧ, использующие линейный конгруэнтный метод). Однако существуют алгоритмы, распознающие последовательность, порождаемую вихрем Мерсенна, как неслучайную.
Генератор псевдослучайных чисел включён в состав многих современных процессоров, например, RdRand входит в набор инструкций IA-32.
Разновидностью ГПСЧ являются ГПСБ (PRBG) — генераторы псевдо-случайных бит, а также различных поточных шифров.
Эффективность — быстрота работы алгоритма и малые затраты памяти;
Воспроизводимость — возможность заново воспроизвести ранее сгенерированную последовательность чисел любое количество раз;
Портируемость — одинаковое функционирование на различном оборудовании и операционных системах;
Быстрота получения
элемента последовательности чисел, при задании элемента, для любой величины; это позволяет разделять последовательность на несколько потоков (последовательностей чисел).Ранние подходы к формированию ПСЧ
Джон фон Нейман считал неприемлемым использование физических генераторов случайных чисел в вычислительной технике, так как при возникновении необходимости проверки вычислений повтор предыдущих действий требовал бы воспроизведение случайного числа, в то время как генерация нового случайного числа недопустима. Предварительная запись и хранение сгенерированных случайных чисел предполагало бы возможность их считывания. Механизм считывания данных являлся одним из самых слабых звеньев вычислительных машин 1940-х годов. Джон фон Нейман привёл следующий метод «середины квадрата» получения десятизначных псевдослучайных чисел:Десятизначное число возводится в квадрат, затем из середины квадрата числа берётся десятизначное число, которое снова возводится в квадрат, и так далее.
Например, для 4-значных чисел, начиная с 1234, получаем
, где берём средние 4 цифры (дописав ноль в начале, если это необходимо). Затем возводим полученное число в квадрат , и так далее. Недостатком данного метода является ограниченность множества ПСЧ из-за того, что последовательность зацикливается — .В 1951 году Д. Г. Лемер предложил линейный конгруэнтный метод, суть которого заключается в задании последовательности целых чисел рекурсивной формулой
где — целые и удовлетворяют следующим условиям: . Недостатком данного метода является зависимость от , так как , а также то, что ПСЧ зацикливается.Детерминированные ГПСЧ
АлгоритмБольшинство детерминированных ГПСЧ соответствуют структуре, предложенной П. Лекуером в 1994 году:
, где — это конечный набор состояний, — вероятностное распределение в пространстве состояний , используемое для выбора начального состояния , } — функция перехода, — пространство выходных значений, . Обычно , а состояние генератора задается рекуррентной формулой для . Выходное значение генератора; — последовательность псевдослучайных чисел. Так как конечно, то должны существовать некоторые конечные и такие, что . Значит, для всех будут выполняться условия и , потому что функции и детерминированные. Таким образом, получается, что последовательность периодическая. Периодом ГПСЧ называется минимальное положительное .Наиболее распространены линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, регистр сдвига с линейной обратной связью, регистр сдвига с обобщённой обратной связью.
Из современных ГПСЧ широкое распространение также получил «вихрь Мерсенна», предложенный в 1997 году Мацумото и Нисимурой. Его достоинствами являются колоссальный период (219937−1), равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение максимум в 5 измерениях), быстрая генерация случайных чисел (в 2-3 раза быстрее, чем стандартные ГПСЧ, использующие линейный конгруэнтный метод). Однако существуют алгоритмы, распознающие последовательность, порождаемую вихрем Мерсенна, как неслучайную.
Генератор псевдослучайных чисел включён в состав многих современных процессоров, например, RdRand входит в набор инструкций IA-32.
Разновидностью ГПСЧ являются ГПСБ (PRBG) — генераторы псевдо-случайных бит, а также различных поточных шифров.
Примеры ГСЧ и источников энтропии
| Источник энтропии | ГПСЧ | Достоинства | Недостатки | |
|---|---|---|---|---|
| /dev/random в UNIX/Linux | Счётчик тактов процессора, однако собирается только во время аппаратных прерываний | РСЛОС, с хешированием выхода через SHA-1 | Есть во всех Unix, надёжный источник энтропии | Очень долго «нагревается», может надолго «застревать», либо работает как ГПСЧ (/dev/urandom) |
| Yarrow от Брюса Шнайера | Традиционные методы | AES-256 и SHA-1 маленького внутреннего состояния | Гибкий криптостойкий дизайн | Медленный |
| Microsoft CryptoAPI | Текущее время, размер жёсткого диска, размер свободной памяти, номер процесса и NETBIOS-имя компьютера | MD5-хеш внутреннего состояния размером в 128 бит | Встроен в Windows, не «застревает» | Сильно зависит от используемого криптопровайдера (CSP). |
| JavaSecureRandom | Взаимодействие между потоками | SHA-1-хеш внутреннего состояния (1024 бит) | Большое внутреннее состояние | Медленный сбор энтропии |
| RdRand от intel | Шумы токов | Построение ПСЧ на основе «случайного» битового считывания значений от токов | Очень быстр, не «застревает» | Оригинальная разработка, свойства приведены только по утверждению разработчиков. |