Вычислительный метод использующий датчик случайных чисел называется

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

где ф означает совокупность операций, которые необходимо проделать над числами х_п, x_n__v . х_{п г}, чтобы получитьх_и+1. При этом качество последовательности х_г+1, . х_п в значительной мере зависит от начальных (исходных) чисел х, х_х. х_г.

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

Конгруэнтный (линейный) метод

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

где а, a_v . а_г, р и т, а также числау, y_v . являются целыми числами. Образование равномерно распределенных псевдослучайных чисел на интервале [0; 1) реализуется с помощью выражения

Формулы (2.4) и (2.5) определяют линейный конгруэнтный метод, частные случаи которого задают тот или иной датчик случайных чисел.

Алгоритм Лемера (мультипликативный датчик)

Датчик случайных чисел, основанный на использовании алгоритма Лемера, является частным случаем линейного конгруэнтного метода. Подставляя в (2.4)

и полагая, что а = а> 0, получаем

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

• 1. Число у. известно с предыдущего шага. Вычисляется произведение а • у_г
• 2. Получается остатокy_j+l от деления а • у₍. на т.

3. Так каку_/+| является целым числом из интервала [0; т), то нужно его разделить на т, чтобы получить число из интервала [0; 1), т.е.

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

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

Например, если т = 2 1 , где / > 2 — число двоичных разрядов для задания максимального значения целой константы в ЭВМ (например, / может быть равно 15 или 31). Данный выбор определяется тем, что при таком т вычислительно легко получить остаток от деления по модулю т. Максимальный период в этом случае достигается при нечетном у и значении a mod 8, равном 3 или 5, что выполняется, когда а = 5 2р+ р = 0, 1,2, . (или а = 2 s + 3, 5 = 3, 4, 5, . ). Значение максимально достижимого периода в данном случае Г_макс = 2 /_2 = т/4.

В том случае, если в качестве т выбрать наибольшее простое число, меньшее 2 1 , можно получить генератор с периодом т — 1. Такой генератор называется мультипликативным линейным конгруэнтным генератором с простым модулем. Например, если b = 31, то т = 2 31 — 1 = 2 147 483 647. Для такого т можно получить период т-1, если а — это первообразный элемент по модулю т, т.е. наименьшее целое число /, для которого а’ — 1 делится на т, составляет 1-т — 1.

Заметим, что при построении такого генератора сложно выбирать параметр а. Хорошие свойства имеют генераторы с т = 2 31 — 1 = = 2 147 483 647 и а = а_< = 16 807 или а = а₂ = 630 360 016, причем генератор с а = а₂ лучше [4]. Также отметим, что данный генератор работает несколько медленнее из-за более сложного получения остатка от деления на т — 1.

В качестве примера приведем консольную программу на языке С#, реализующую и использующую функцию для генерации случайных чисел. Данная функция реализует мультипликативный генератор с параметрами: у = 2451, т = 4096, а = 5.

// Количество случайных чисел private const int N = 1500;

// Параметр мультипликативного генератора private const int А = 5;

private static int _Mm;

// Случайное число private static int Y;

III Генератор случайных чисел III Случайное значение private static double Rnd()

_Y = (A * _Y) % _Mm; return (double)_Y / _Mm;

III Основная программа

static void Main(string[] args)

// Массив для случайных чисел double[] х = new double[N]; for (int i = 0; i

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

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

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

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

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

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

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

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

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

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

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

Несколько примеров ГСЧ с их источниками энтропии и генераторами:

Источник энтропии	ГПСЧ	Достоинства	Недостатки
/dev/random в Linux	Счётчик тактов процессора, однако собирается только во время аппаратных прерываний	LFSR, с хешированием выхода через	Очень долго «нагревается», может надолго «застревать», либо работает как ГПСЧ (/dev/urandom)
Yarrow от Брюса Шнайера [3]	Традиционные (устаревшие) методы	AES-256 и	Гибкий криптостойкий дизайн	Долго «нагревается», очень маленькое внутреннее состояние, слишком сильно зависит от криптостойкости выбранных алгоритмов, медленный, применим исключительно для генерации ключей
Генератор Леонида Юрьева [4]	Шум звуковой карты	?	Скорее всего, хороший и быстрый источник энтропии	Нет независимого, заведомо криптостойкого ГПСЧ, доступен исключительно в виде Windows
Microsoft		Встроен в Windows, не «застревает»	Маленькое внутреннее состояние, легко предсказуем
	Взаимодействие между потоками		В Java другого выбора пока нет, большое внутреннее состояние	Медленный сбор энтропии
Chaos от Ruptor [5]	Счётчик тактов процессора, собирается непрерывно	Хеширование 4096-битового внутреннего состояния на основе нелинейного варианта Marsaglia-генератора	Пока самый быстрый из всех, большое внутреннее состояние, не «застревает»
RRAND от Ruptor [6]	Счётчик тактов процессора	Зашифровывание внутреннего состояния поточным шифром	Очень быстр, внутреннее состояние произвольного размера по выбору, не «застревает»

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

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

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

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

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

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

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

Примечания

1. ↑Дональд Кнут. Глава 3.3. Спектральный критерий // Искусство программирования. Указ. соч. — С. 129—130.
2. ↑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
3. ↑ 12http://www.schneier.com/yarrow.html
4. ↑http://leo.yuriev.ru/random
5. ↑http://cryptolib.com/crypto/chaos/
6. ↑http://cryptolib.com/crypto/rrand/

См. также

• NIST STS — пакет статистического тестирования
• CryptX — пакет статистического тестирования
• Тесты DIEHARD
• Метод Монте-Карло
• Случайное простое число
• Линейный конгруэнтный метод

Ссылки

• Андрей Зубинский. В поисках случайности Компьютерное обозрение № 29 (2003)
• Юрий Лифшиц. Курс «Современные задачи криптографии» Лекция 9: Псевдослучайные генераторы
• Л. Бараш. Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел
• noonv. Старый взгляд на новые вещи
• Жельников Владимир. Псевдослучайные последовательности чисел // Криптография от папируса до компьютера М.: ABF, 1996.
• random.org (англ.) — онлайновый сервис для генерации случайных чисел
• 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

Литература

• Дональд Кнут. Глава 3. Случайные числа // Искусство программирования = The Art of Computer Programming. — 3-е изд. — М.: «Вильямс», 2007. — Т. 2. Получисленные алгоритмы. — 832 с. — ISBN 5-8459-0081-6 (русс.) ISBN 0-201-89684-2 (англ.)

Wikimedia Foundation . 2010 .

Смотреть что такое "Датчик случайных чисел" в других словарях:

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

датчик случайных чисел — Узел вычислительной машины, который служит для выработки случайных чисел … Политехнический терминологический толковый словарь

датчик случайных величин — датчик случайных чисел генератор случайных чисел Устройство или программа, предназначенные для выработки последовательности случайных чисел по заданному закону распределения вероятностей их значений. [http://slovar lopatnikov.ru/] Тематики… … Справочник технического переводчика

Датчик случайных величин — [random number generator] то же: датчик случайных чисел, генератор случайных чисел устройство или программа, предназначенные для выработки последовательности случайных чисел по заданному закону распределения вероятностей их значений … Экономико-математический словарь

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

СЛУЧАЙНЫХ ЧИСЕЛ ДАТЧИК — устройство для выработки случайных чисел, равномерно распределённых в заданном диапазоне. Применяется для имитации реальных условий функционирования систем автоматич. управления, при решении на ЭВМ задач методом статистич. испытаний (т. н.… … Большой энциклопедический политехнический словарь

генератор случайных чисел — датчик случайных чисел — [[http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23]] Тематики защита информации Синонимы датчик случайных чисел EN random number generatorrandom number generator … Справочник технического переводчика

Датчик — первичный преобразователь, элемент измерительного, сигнального, регулирующего или управляющего устройства системы, преобразующий контролируемую величину (давление, температуру, частоту, скорость, перемещение, напряжение, электрический ток … Большая советская энциклопедия

Аппаратное шифрование — Аппаратное шифрование процесс шифрования, производимый при помощи специализированных вычислительных устройств. Содержание 1 Введение 2 Достоинства и недостатки аппаратного шифрования … Википедия

Метод Фибоначчи с запаздываниями — (Lagged Fibonacci generator) один из методов генерации псевдослучайных чисел. Особенности распределения случайных чисел, генерируемых линейным конгруэнтным алгоритмом, делают невозможным их использование в статистических алгоритмах, требующих… … Википедия

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

Таблица 1. Подходы к определению случайности

Название подхода	Авторы	Суть подхода
Частотный	фон Мизес (Mises), Чёрч (Church), Колмогоров, Ловеланд (Loveland)	В СП должна наблюдаться устойчивость частот встречаемости элементов. Например, знаки 0 и 1 должны встречаться независимо и с равными вероятностями не только в двоичной СП, но и в любой ее подпоследовательности, выбранной случайно и независимо от исходных условий генерации.
Сложностной	Колмогоров, Чейтин (Chaitin)	Любое описание реализации СП не может быть существенно короче самой этой реализации. То есть СП должна иметь сложное строение, и энтропия ее начальных элементов должна быть велика. Последовательность случайна, если ее алгоритмическая сложность близка к длине последовательности.
Количественный	Мартин-Лёф (Martin-Lof)	Разбиение вероятностного пространства последовательностей на неслучайные и случайные, то есть на последовательности, «не проходящие» и «проходящие» набор определенных тестов, предназначенных для выявления закономерностей.
Криптографический	Современный подход	Последовательность считается случайной, если вычислительная сложность поиска закономерностей не меньше заданной величины.

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

Известны различные варианты генерации случайных чисел на компьютере, предполагающие использование осмысленных и неосмысленных действий пользователя в качестве источника случайности. К таким действиям можно отнести, например, нажатия клавиш на клавиатуре, перемещения либо клики мышью и др. Мерой случайности генерируемой последовательности является энтропия. Недостатком многих известных подходов является сложность оценки количества получаемой энтропии. Подходы, связанные с измерением характеристик неосмысленных движений человека, позволяют получать в единицу времени относительно небольшую долю случайных бит, что накладывает определенные ограничения на использование генерируемых последовательностей в криптографических приложениях.
Рассмотрим генерацию СП с помощью осмысленных реакций пользователя на некоторый достаточно сложно устроенный псевдослучайный процесс. А именно: в случайные моменты времени измеряются значения определенного набора меняющихся во времени величин. Затем случайные значения величин процесса представляются в виде случайной последовательности бит. Особенности криптографического приложения и среды функционирования определили ряд требований к БиоДСЧ:

1. Генерируемые последовательности должны быть близки по статистическим характеристикам к идеальным случайным последовательностям, в частности, для двоичной последовательности вероятность p знака «1» или «0» должна быть близка к 1/2, то есть отклонение b вероятности от 1/2 не должно превосходить некоторого фиксированного значения b0, близкого к нулю, например, |p-1/2|=b≤b0, где b0≤10 -2 .
2. В ходе реализации процесса среднестатистическим пользователем скорость генерации должна быть не менее 10 бит/сек.
3. Продолжительность генерации среднестатистическим пользователем 320 бит (которые соответствуют в алгоритме ГОСТ 28147-89 сумме длины ключа (256 бит) и длины синхропосылки (64 бита)) не должна превышать 30 секунд.
4. Удобство работы пользователя с программой БиоДСЧ.

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

Рисунок 1. Траектории движения центров кругов внутри рабочей области

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

С целью определения параметров приоритетной реализации БиоДСЧ было проведено разными исполнителями порядка 10 4 сеансов. Реализованные эксперименты позволили определить области подходящих значений для параметров модели БиоДСЧ: размеры рабочей области, количество, размеры и скорость движения фигур и др.
При анализе результатов работы БиоДСЧ сделаны следующие допущения:

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

Оценка доверительных интервалов для значений вычисляемых величин процесса соответствует уровню значимости 0,05. Для распознавания равномерности распределения знаков полученной выборки (после приведения к двоичному виду) применялся критерий хи-квадрат согласия с равномерным распределением.
Количество бит, получаемых из значений измеряемых величин процесса (источников энтропии), определялось эмпирическим путем на основе анализа информационной энтропии значений ряда характеристик процесса. Эмпирически установлено, что успешное попадание в площадь фигуры позволяет получить порядка 30 бит случайной последовательности. Следовательно, для генерации ключа и вектора инициализации алгоритма ГОСТ 28147-89 за 1-2 сеанса работы БиоДСЧ достаточно использования 10-12 фигур.
Направления улучшения характеристик биологических генераторов следует связать как с оптимизацией рассмотренного подхода, так и с исследованием других подходов к построению БиоДСЧ.