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

Введение

Актуальность для криптографических приложений проблематики, связанной с генерацией случайных последовательностей (СП), обусловлена их использованием в криптографических системах для выработки ключевой и вспомогательной информации. Само понятие случайности имеет философские корни, что свидетельствует о его сложности. В математике существуют различные подходы к определению термина «случайность», их обзор дан, например, в нашей статье «Случайности не случайны?» . Сведения об известных подходах к определению понятия «случайность» систематизированы в таблице 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⁴ сеансов. Реализованные эксперименты позволили определить области подходящих значений для параметров модели БиоДСЧ: размеры рабочей области, количество и диаметр кругов, скорость движения кругов, скорость вращения «вектора вылета кругов», количество секторов, на которые разделены круги, угловая скорость вращения кругов и др.
При анализе результатов работы БиоДСЧ сделаны следующие допущения:

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

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