Pull to refresh

Как построить датчик случайных чисел с участием человека?

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

Введение


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

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


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

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

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

Articles

Information

Website
www.securitycode.ru
Registered
Founded
2008
Employees
201–500 employees
Location
Россия