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

Введение

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

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

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

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

Псевдослучайный процесс и задача пользователя

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

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

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

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

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

Измеряемые величины процесса

Генерация СП выполняется с помощью измерения ряда характеристик описанного псевдослучайного процесса в случайные моменты времени, определяемые реакцией пользователя. Скорость генерации бит тем выше, чем больше независимых характеристик подвергаются измерению. Независимость измеряемых характеристик означает непредсказуемость значения каждой характеристики по известным значениям других характеристик.
Заметим, что каждый круг, движущийся на экране, пронумерован, разделен на 2 k равных невидимых пользователю секторов, пронумерованных числами от 0 до 2 k -1, где k – натуральное и вращается вокруг своего геометрического центра с заданной угловой скоростью. Нумерацию кругов и секторов круга пользователь не видит.
В момент попадания в круг (успешного клика либо нажатия пальцем) измеряется ряд характеристик процесса, так называемые источники энтропии. Обозначим a i точку попадания в i-й круг, i=1,2,… Тогда к измеряемым величинам целесообразно отнести:

• координаты X и Y точки a i ;
• расстояние R от центра круга до точки a i ;
• номер сектора внутри i-го круга, содержащего точку a i ;
• номер круга и др.

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

Результаты экспериментов

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

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

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

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

Считается, что первая попытка создать физический датчик случайных чисел относится к 3500 году до н.э. и связана с настольной игрой сенет, древнеегипетским светским развлечением. Согласно современным реконструкциям правил игры для определения набранного каждым игроком количества очков и очередности ходов в этой игре использовались четыре плоские палочки, одна сторона которых была белой, другая - черной. Палочки бросали одновременно и в зависимости от выпавшей комбинации цветов определяли дополнительные возможности игроков. В начале XX в. последовательности случайных чисел имитировались вручную - с помощью бросаний монеты или игральной кости, раскладывания игральных карт, рулетки, извлечения шаров из урны и т.д. Современные физические (аппаратные) датчики представляют собой специальные устройства, генерирующие случайные числа на основе преобразования случайных шумов естественного или искусственного происхождения (тепловой шум, дробовой эффект в электронных лампах, радиоактивный распад и т.д.). Например, машина ERNIE 4 (electronic random number indicator equipment ),

• 1 Иногда, хотя и редко, к стандартным относят распределение, задаваемое таблицей 0 1 ... 8 9
• 0,1 0,1 ... 0,1 0,1/ с помощью которой определяют выигравшие номера в ежемесячной Британской лотерее, в качестве источника случайных величин использует тепловой шум транзисторов. У физического способа получения последовательности случайных чисел есть особенности, которые для имитационной модели являются недостатками. К ним относятся, в первую очередь, необходимость специальных мер по обеспечению стабильности источника сигнала, преобразуемого в случайные числа, и невозможность воспроизведения полученной последовательности случайных чисел.

Таблицы случайных чисел лишены указанных недостатков. Поясним, что понимается под таблицей случайных чисел. Предположим, что мы осуществили N независимых опытов, в результате которых получили случайные цифры а, а 2 ,осдг. Запись этих цифр (в порядке появления и в форме прямоугольной таблицы) даст так называемую таблицу случайных цифр. Используется она следующим образом. В ходе расчетов нам может потребоваться либо случайная цифра, либо случайное число. Если потребуется случайная цифра, то мы можем взять любую цифру из этой таблицы. То же относится к случаю целого случайного числа - для каждого разряда можно выбрать любую цифру. Если нам понадобится случайное число 0 k очередных цифр сц, а 2 , ос/, и считать, что 8 = (Хоцо^.-.о^. При этом в случае «идеальной» таблицы случайных цифр выбирать цифры из нее можно случайным образом, можно подряд, можно использовать любой алгоритм выбора, не зависящий от значений цифр таблицы, начинать с любого места таблицы, читать в любом направлении.

Первые таблицы случайных чисел были получены с помощью рулеток. Такие таблицы несколько раз издавались в виде книг. Одна из самых известных таблиц , опубликованная в 1927 г., содержала свыше 40 000 случайных цифр, «произвольно взятых из отчетов о переписи».

Историческая справка

Леонард Типпет (Leonard Henry Caleb Tippett , 1902-1985) - английский статистик, ученик К. Пирсона и Р. Фишера. В 1965-1966 гг. - президент Королевского статистического общества. С его именем связаны некоторые важные результаты в теории экстремальных значений, например распределение Фишера - Типпета и теорема Фишера - Типпета - Гнеденко.

Позже были сконструированы специальные устройства (машины), механически вырабатывающие случайные числа. Первую такую машину в 1939 г. использовали М. Дж. Кендалл и Б. Бэбингтон-Смит при создании таблиц, включающих 100 тыс. случайных цифр. В 1955 г. компания RAND Corporation опубликовала хорошо известные таблицы с миллионом случайных цифр, полученных другой машиной такого типа. Практическое применение таблиц случайных чисел ограничивается в настоящее время, как правило, задачами, в которых используются методы случайного отбора

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

Это интересно

В России действует ГОСТ 18321-73 (СТ СЭВ 1934-79), устанавливающий правила отбора единиц продукции в выборку при проведении статистического приемочного контроля качества, статистических методов анализа и регулирования технологических процессов для всех видов штучной продукции производственно-технического назначения и товаров народного потребления. В нем, в частности, указывается, что при отборе единиц продукции в выборку «используют таблицы случайных чисел по СТ СЭВ 546-77».

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

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

• Tippett L. Random sampling numbers. London: Cambridge University Press, 1927.
• См.: Кнут Д. Э. Искусство программирования. 3-е изд. М. : Вильямс, 2000. Т. 2. Гл. 3.Случайные числа.

Заметим, что в идеале кривая плотности распределения случайных чисел выглядела бы так, как показано на рис. 22.3 . То есть в идеальном случае в каждый интервал попадает одинаковое число точек: N i = N /k , где N — общее число точек, k — количество интервалов, i = 1, …, k .

Рис. 22.3. Частотная диаграмма выпадения случайных чисел,
порождаемых идеальным генератором теоретически

Следует помнить, что генерация произвольного случайного числа состоит из двух этапов:

• генерация нормализованного случайного числа (то есть равномерно распределенного от 0 до 1);
• преобразование нормализованных случайных чисел r i в случайные числа x i , которые распределены по необходимому пользователю (произвольному) закону распределения или в необходимом интервале.

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

• физические;
• табличные;
• алгоритмические.

Физические ГСЧ

Примером физических ГСЧ могут служить: монета («орел» — 1, «решка» — 0); игральные кости; поделенный на секторы с цифрами барабан со стрелкой; аппаратурный генератор шума (ГШ), в качестве которого используют шумящее тепловое устройство, например, транзистор (рис. 22.4–22.5 ).

Рис. 22.4. Схема аппаратного метода генерации случайных чисел
Рис. 22.5. Диаграмма получения случайных чисел аппаратным методом

Задача «Генерация случайных чисел при помощи монеты»

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

Первый способ решения задачи Подбросьте монету 9 раз, и если монета упала решкой, то запишите «0», если орлом, то «1». Итак, допустим, что в результате эксперимента получили случайную последовательность 100110100. Начертите интервал от 0 до 1. Считывая числа в последовательности слева направо, разбивайте интервал пополам и выбирайте каждый раз одну из частей очередного интервала (если выпал 0, то левую, если выпала 1, то правую). Таким образом, можно добраться до любой точки интервала, сколь угодно точно. Итак, 1 : интервал делится пополам — и , — выбирается правая половина, интервал сужается: . Следующее число, 0 : интервал делится пополам — и , — выбирается левая половина , интервал сужается: . Следующее число, 0 : интервал делится пополам — и , — выбирается левая половина , интервал сужается: . Следующее число, 1 : интервал делится пополам — и , — выбирается правая половина , интервал сужается: . По условию точности задачи решение найдено: им является любое число из интервала , например, 0.625. В принципе, если подходить строго, то деление интервалов нужно продолжить до тех пор, пока левая и правая границы найденного интервала не СОВПАДУТ между собой с точностью до третьего знака после запятой. То есть с позиций точности сгенерированное число уже не будет отличимо от любого числа из интервала, в котором оно находится. Второй способ решения задачи Разобьем полученную двоичную последовательность 100110100 на триады: 100, 110, 100. После перевода этих двоичных чисел в десятичные получаем: 4, 6, 4. Подставив спереди «0.», получим: 0.464. Таким методом могут получаться только числа от 0.000 до 0.777 (так как максимум, что можно «выжать» из трех двоичных разрядов — это 111 2 = 7 8) — то есть, по сути, эти числа представлены в восьмеричной системе счисления. Для перевода восьмеричного числа в десятичное представление выполним: 0.464 8 = 4 · 8 –1 + 6 · 8 –2 + 4 · 8 –3 = 0.6015625 10 = 0.602 10 . Итак, искомое число равно: 0.602.

Табличные ГСЧ

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

Таблица 22.1. Случайные цифры. Равномерно распределенные от 0 до 1 случайные числа

Случайные цифры								Равномерно распределенные от 0 до 1 случайные числа
9	2	9	2	0	4	2	6	0.929
9	5	7	3	4	9	0	3	0.204
5	9	1	6	6	5	7	6	0.269

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

Находится таблица, содержащая 500 абсолютно случайных проверенных чисел (взято из книги И. Г. Венецкого, В. И. Венецкой «Основные математико-статистические понятия и формулы в экономическом анализе»).

Алгоритмические ГСЧ

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

r i + 1 = f (r i ) .

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

Достоинством данных ГСЧ является быстродействие; генераторы практически не требуют ресурсов памяти, компактны. Недостатки: числа нельзя в полной мере назвать случайными, поскольку между ними имеется зависимость, а также наличие периодов в последовательности квазислучайных чисел.

Рассмотрим несколько алгоритмических методов получения ГСЧ:

• метод серединных квадратов;
• метод серединных произведений;
• метод перемешивания;
• линейный конгруэнтный метод.

Метод серединных квадратов

Имеется некоторое четырехзначное число R 0 . Это число возводится в квадрат и заносится в R 1 . Далее из R 1 берется середина (четыре средних цифры) — новое случайное число — и записывается в R 0 . Затем процедура повторяется (см. рис. 22.6 ). Отметим, что на самом деле в качестве случайного числа необходимо брать не ghij , а 0.ghij — с приписанным слева нулем и десятичной точкой. Этот факт отражен как на рис. 22.6 , так и на последующих подобных рисунках.

Рис. 22.6. Схема метода серединных квадратов

Недостатки метода: 1) если на некоторой итерации число R 0 станет равным нулю, то генератор вырождается, поэтому важен правильный выбор начального значения R 0 ; 2) генератор будет повторять последовательность через M n шагов (в лучшем случае), где n — разрядность числа R 0 , M — основание системы счисления.

Для примера на рис. 22.6 : если число R 0 будет представлено в двоичной системе счисления, то последовательность псевдослучайных чисел повторится через 2 4 = 16 шагов. Заметим, что повторение последовательности может произойти и раньше, если начальное число будет выбрано неудачно.

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

Метод серединных произведений

Число R 0 умножается на R 1 , из полученного результата R 2 извлекается середина R 2 * (это очередное случайное число) и умножается на R 1 . По этой схеме вычисляются все последующие случайные числа (см. рис. 22.7 ).

Рис. 22.7. Схема метода серединных произведений

Метод перемешивания

В методе перемешивания используются операции циклического сдвига содержимого ячейки влево и вправо. Идея метода состоит в следующем. Пусть в ячейке хранится начальное число R 0 . Циклически сдвигая содержимое ячейки влево на 1/4 длины ячейки, получаем новое число R 0 * . Точно так же, циклически сдвигая содержимое ячейки R 0 вправо на 1/4 длины ячейки, получаем второе число R 0 ** . Сумма чисел R 0 * и R 0 ** дает новое случайное число R 1 . Далее R 1 заносится в R 0 , и вся последовательность операций повторяется (см. рис. 22.8 ).

Рис. 22.8. Схема метода перемешивания

Обратите внимание, что число, полученное в результате суммирования R 0 * и R 0 ** , может не уместиться полностью в ячейке R 1 . В этом случае от полученного числа должны быть отброшены лишние разряды. Поясним это для рис. 22.8 , где все ячейки представлены восемью двоичными разрядами. Пусть R 0 * = 10010001 2 = 145 10 , R 0 ** = 10100001 2 = 161 10 , тогда R 0 * + R 0 ** = 100110010 2 = 306 10 . Как видим, число 306 занимает 9 разрядов (в двоичной системе счисления), а ячейка R 1 (как и R 0 ) может вместить в себя максимум 8 разрядов. Поэтому перед занесением значения в R 1 необходимо убрать один «лишний», крайний левый бит из числа 306, в результате чего в R 1 пойдет уже не 306, а 00110010 2 = 50 10 . Также заметим, что в таких языках, как Паскаль, «урезание» лишних битов при переполнении ячейки производится автоматически в соответствии с заданным типом переменной.

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

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

r i + 1 = mod(k · r i + b , M ) .

Последовательность случайных чисел, полученных с помощью данной формулы, называется линейной конгруэнтной последовательностью . Многие авторы называют линейную конгруэнтную последовательность при b = 0 мультипликативным конгруэнтным методом , а при b ≠ 0 — смешанным конгруэнтным методом .

Для качественного генератора требуется подобрать подходящие коэффициенты. Необходимо, чтобы число M было довольно большим, так как период не может иметь больше M элементов. С другой стороны, деление, использующееся в этом методе, является довольно медленной операцией, поэтому для двоичной вычислительной машины логичным будет выбор M = 2 N , поскольку в этом случае нахождение остатка от деления сводится внутри ЭВМ к двоичной логической операции «AND». Также широко распространен выбор наибольшего простого числа M , меньшего, чем 2 N : в специальной литературе доказывается, что в этом случае младшие разряды получаемого случайного числа r i + 1 ведут себя так же случайно, как и старшие, что положительно сказывается на всей последовательности случайных чисел в целом. В качестве примера можно привести одно из чисел Мерсенна , равное 2 31 – 1 , и таким образом, M = 2 31 – 1 .

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

Теорема . Линейная конгруэнтная последовательность, определенная числами M , k , b и r 0 , имеет период длиной M тогда и только тогда, когда:

• числа b и M взаимно простые;
• k – 1 кратно p для каждого простого p , являющегося делителем M ;
• k – 1 кратно 4, если M кратно 4.

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

Было установлено, что ряд псевдослучайных чисел, генерируемых на основе данных из примера 1, будет повторяться через каждые M /4 чисел. Число q задается произвольно перед началом вычислений, однако при этом следует иметь в виду, что ряд производит впечатление случайного при больших k (а значит, и q ). Результат можно несколько улучшить, если b нечетно и k = 1 + 4 · q — в этом случае ряд будет повторяться через каждые M чисел. После долгих поисков k исследователи остановились на значениях 69069 и 71365 .

Генератор случайных чисел, использующий данные из примера 2, будет выдавать случайные неповторяющиеся числа с периодом, равным 7 миллионам.

Мультипликативный метод генерации псевдослучайных чисел был предложен Д. Г. Лехмером (D. H. Lehmer) в 1949 году.

Проверка качества работы генератора

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

Осуществляемые проверки бывают двух типов:

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

Проверки на равномерность распределения

1) ГСЧ должен выдавать близкие к следующим значения статистических параметров, характерных для равномерного случайного закона:

2) Частотный тест

Частотный тест позволяет выяснить, сколько чисел попало в интервал (m r – σ r ; m r + σ r ) , то есть (0.5 – 0.2887; 0.5 + 0.2887) или, в конечном итоге, (0.2113; 0.7887) . Так как 0.7887 – 0.2113 = 0.5774 , заключаем, что в хорошем ГСЧ в этот интервал должно попадать около 57.7% из всех выпавших случайных чисел (см. рис. 22.9 ).

Рис. 22.9. Частотная диаграмма идеального ГСЧ
в случае проверки его на частотный тест

Также необходимо учитывать, что количество чисел, попавших в интервал (0; 0.5) , должно быть примерно равно количеству чисел, попавших в интервал (0.5; 1) .

3) Проверка по критерию «хи-квадрат»

Критерий «хи-квадрат» (χ 2 -критерий) — это один из самых известных статистических критериев; он является основным методом, используемым в сочетании с другими критериями. Критерий «хи-квадрат» был предложен в 1900 году Карлом Пирсоном. Его замечательная работа рассматривается как фундамент современной математической статистики.

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

Частотная диаграмма эталонного ГСЧ представлена на рис. 22.10 . Так как закон распределения эталонного ГСЧ равномерный, то (теоретическая) вероятность p i попадания чисел в i -ый интервал (всего этих интервалов k ) равна p i = 1/k . И, таким образом, в каждый из k интервалов попадет ровно по p i · N чисел (N — общее количество сгенерированных чисел).

Рис. 22.10. Частотная диаграмма эталонного ГСЧ

Реальный ГСЧ будет выдавать числа, распределенные (причем, не обязательно равномерно!) по k интервалам и в каждый интервал попадет по n i чисел (в сумме n 1 + n 2 + … + n k = N ). Как же нам определить, насколько испытываемый ГСЧ хорош и близок к эталонному? Вполне логично рассмотреть квадраты разностей между полученным количеством чисел n i и «эталонным» p i · N . Сложим их, и в результате получим:

χ 2 эксп. = (n 1 – p 1 · N ) 2 + (n 2 – p 2 · N ) 2 + … + (n k – p k · N ) 2 .

Из этой формулы следует, что чем меньше разность в каждом из слагаемых (а значит, и чем меньше значение χ 2 эксп. ), тем сильнее закон распределения случайных чисел, генерируемых реальным ГСЧ, тяготеет к равномерному.

В предыдущем выражении каждому из слагаемых приписывается одинаковый вес (равный 1), что на самом деле может не соответствовать действительности; поэтому для статистики «хи-квадрат» необходимо провести нормировку каждого i -го слагаемого, поделив его на p i · N :

Наконец, запишем полученное выражение более компактно и упростим его:

Мы получили значение критерия «хи-квадрат» для экспериментальных данных.

В табл. 22.2 приведены теоретические значения «хи-квадрат» (χ 2 теор. ), где ν = N – 1 — это число степеней свободы, p — это доверительная вероятность, задаваемая пользователем, который указывает, насколько ГСЧ должен удовлетворять требованиям равномерного распределения, или p — это вероятность того, что экспериментальное значение χ 2 эксп. будет меньше табулированного (теоретического) χ 2 теор. или равно ему .

Таблица 22.2. Некоторые процентные точки χ 2 -распределения

	p = 1%	p = 5%	p = 25%	p = 50%	p = 75%	p = 95%	p = 99%
ν = 1	0.00016	0.00393	0.1015	0.4549	1.323	3.841	6.635
ν = 2	0.02010	0.1026	0.5754	1.386	2.773	5.991	9.210
ν = 3	0.1148	0.3518	1.213	2.366	4.108	7.815	11.34
ν = 4	0.2971	0.7107	1.923	3.357	5.385	9.488	13.28
ν = 5	0.5543	1.1455	2.675	4.351	6.626	11.07	15.09
ν = 6	0.8721	1.635	3.455	5.348	7.841	12.59	16.81
ν = 7	1.239	2.167	4.255	6.346	9.037	14.07	18.48
ν = 8	1.646	2.733	5.071	7.344	10.22	15.51	20.09
ν = 9	2.088	3.325	5.899	8.343	11.39	16.92	21.67
ν = 10	2.558	3.940	6.737	9.342	12.55	18.31	23.21
ν = 11	3.053	4.575	7.584	10.34	13.70	19.68	24.72
ν = 12	3.571	5.226	8.438	11.34	14.85	21.03	26.22
ν = 15	5.229	7.261	11.04	14.34	18.25	25.00	30.58
ν = 20	8.260	10.85	15.45	19.34	23.83	31.41	37.57
ν = 30	14.95	18.49	24.48	29.34	34.80	43.77	50.89
ν = 50	29.71	34.76	42.94	49.33	56.33	67.50	76.15
ν > 30	ν + sqrt(2ν ) · x p + 2/3 · x 2 p – 2/3 + O (1/sqrt(ν ))
x p =	–2.33	–1.64	–0.674	0.00	0.674	1.64	2.33

Приемлемым считают p от 10% до 90% .

Если χ 2 эксп. много больше χ 2 теор. (то есть p — велико), то генератор не удовлетворяет требованию равномерного распределения, так как наблюдаемые значения n i слишком далеко уходят от теоретических p i · N и не могут рассматриваться как случайные. Другими словами, устанавливается такой большой доверительный интервал, что ограничения на числа становятся очень нежесткими, требования к числам — слабыми. При этом будет наблюдаться очень большая абсолютная погрешность.

Еще Д. Кнут в своей книге «Искусство программирования» заметил, что иметь χ 2 эксп. маленьким тоже, в общем-то, нехорошо, хотя это и кажется, на первый взгляд, замечательно с точки зрения равномерности. Действительно, возьмите ряд чисел 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, … — они идеальны с точки зрения равномерности, и χ 2 эксп. будет практически нулевым, но вряд ли вы их признаете случайными.

Если χ 2 эксп. много меньше χ 2 теор. (то есть p — мало), то генератор не удовлетворяет требованию случайного равномерного распределения, так как наблюдаемые значения n i слишком близки к теоретическим p i · N и не могут рассматриваться как случайные.

А вот если χ 2 эксп. лежит в некотором диапазоне, между двумя значениями χ 2 теор. , которые соответствуют, например, p = 25% и p = 50%, то можно считать, что значения случайных чисел, порождаемые датчиком, вполне являются случайными.

При этом дополнительно надо иметь в виду, что все значения p i · N должны быть достаточно большими, например больше 5 (выяснено эмпирическим путем). Только тогда (при достаточно большой статистической выборке) условия проведения эксперимента можно считать удовлетворительными.

Итак, процедура проверки имеет следующий вид.

Проверки на статистическую независимость

1) Проверка на частоту появления цифры в последовательности

Рассмотрим пример. Случайное число 0.2463389991 состоит из цифр 2463389991, а число 0.5467766618 состоит из цифр 5467766618. Соединяя последовательности цифр, имеем: 24633899915467766618.

Понятно, что теоретическая вероятность p i выпадения i -ой цифры (от 0 до 9) равна 0.1.

2) Проверка появления серий из одинаковых цифр

Обозначим через n L число серий одинаковых подряд цифр длины L . Проверять надо все L от 1 до m , где m — это заданное пользователем число: максимально встречающееся число одинаковых цифр в серии.

В примере «24633899915467766618» обнаружены 2 серии длиной в 2 (33 и 77), то есть n 2 = 2 и 2 серии длиной в 3 (999 и 666), то есть n 3 = 2 .

Вероятность появления серии длиной в L равна: p L = 9 · 10 –L (теоретическая). То есть вероятность появления серии длиной в один символ равна: p 1 = 0.9 (теоретическая). Вероятность появления серии длиной в два символа равна: p 2 = 0.09 (теоретическая). Вероятность появления серии длиной в три символа равна: p 3 = 0.009 (теоретическая).

Например, вероятность появления серии длиной в один символ равна p L = 0.9 , так как всего может встретиться один символ из 10, а всего символов 9 (ноль не считается). А вероятность того, что подряд встретится два одинаковых символа «XX» равна 0.1 · 0.1 · 9, то есть вероятность 0.1 того, что в первой позиции появится символ «X», умножается на вероятность 0.1 того, что во второй позиции появится такой же символ «X» и умножается на количество таких комбинаций 9.

Частость появления серий подсчитывается по ранее разобранной нами формуле «хи-квадрат» с использованием значений p L .

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

В заключение отметим, что третья глава книги Дональда Э. Кнута «Искусство программирования» (том 2) полностью посвящена изучению случайных чисел. В ней изучаются различные методы генерирования случайных чисел, статистические критерии случайности, а также преобразование равномерно распределенных случайных чисел в другие типы случайных величин. Изложению этого материала уделено более двухсот страниц.

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

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

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

Вычислительной эффективностью – это как можно меньшее время вычисления очередного цикла и объём памяти для работы генератора.

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

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

Для надёжного, в статистическом смысле, вычисления этой вероятности число повторений опыта можно оценить по формуле:

где
- функция, обратная функции нормального распределения,- доверительная вероятность ошибкиизмерения вероятности.

Следовательно, для того чтобы ошибка не выходила за доверительный интервал   с доверительной вероятностью, например =0,95 надо, чтобы число повторений опыта было не меньше:

(2.2)

Например, для 10% ошибки ( =0,1) получим
, а для 3% ошибки ( =0,03) уже получим
.

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

где K - число исходных условий (точек на кривой определяемой методом Монте-Карло), N - число повторений модельного опыта при заданных исходных условиях,L - длина псевдослучайной последовательности.

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

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

Хорошими статистическими свойствами. Это наиболее важный показатель качества генератора случайных чисел. Однако его нельзя оценить каким-либо одним критерием или тестом, т.к. не существует необходимых и достаточных критериев случайности конечной последовательности чисел. Самое большее, что можно сказать о псевдослучайной последовательности чисел это то, что она “выглядит” как случайная. Никакой один статистический критерий не является надёжным индикатором точности. По меньшей мере, необходимо использовать несколько тестов, отражающих наиболее важные стороны качества генератора случайных чисел, т.е. степени его приближения к идеальному генератору.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Юрий Лифшиц. Курс «Современные задачи криптографии» Лекция 9: Псевдослучайные генераторы

Л. Бараш. Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел

Жельников Владимир. Псевдослучайные последовательности чисел // Криптография от папируса до компьютера М.: 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