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

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

Иллюстрации

Показать все

Реферат

Область техники, к которой относится изобретение

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

Уровень техники

Существующий уровень техники предоставляет различные способы генерации случайных чисел и технические решения по реализации генераторов случайных чисел: RU 2577201 С2, 22.04.2014; RU 2331916 С1, 20.08.2008; RU 2339073 С2, 20.11.2008; RU 2246129 С2, 10.07.2004; US 2006020647 (А1), 26.01.2006; WO 2010005784 (Al), 14.01.2010. Известны способы генерации случайных и псевдослучайных чисел с помощью компьютера [1, 2]. В способах, где пользователь не участвует, за основу случайности взята нестабильность функционирования некоторых устройств компьютера. Известен программно-аппаратный способ получения случайного числа, в котором источниками случайности являются микроархитектурное состояние процессора, время выполнения последовательности инструкций и неопределенность, вносимая аппаратными прерываниями [3]. Также в качестве источника случайности используется нестабильность таймера, функционирующего независимо от генератора тактовой частоты [4]. Подходы с участием пользователя в процессе генерации (например, с помощью перемещений и кликов мышью или нажатий клавиш на клавиатуре [5]), основаны на различных процессах, реализуемых программно. В этих случаях не представлены обоснованные оценки либо производительности генерации, либо статистических свойств выходных двоичных последовательностей, либо того и другого, что затрудняет оценку этих подходов.

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

Наиболее близким к заявленному техническому решению является способ генерации случайного числа с использованием компьютера (варианты) RU 2577201 С2 (опубл. 22.04.2014), МПК G06F 7/58. Способ генерации случайных чисел с использованием компьютера обеспечивает получение случайного числа с энтропией не меньше заданной величины. Компьютер содержит таймер для формирования значений текущего времени, не связанный с генератором тактовой частоты компьютера, прикладное программное обеспечение, предоставляющее возможности получать из таймера значения текущего времени, выполнять обработку данных в соответствии с заданным алгоритмом, в том числе, с функцией хэширования. Способ реализуется в несколько этапов, в ходе которых задается значение энтропии и определяется в зависимости от характеристик компьютера длина М последовательности D, обработка которой необходима для получения случайного числа со значением энтропии не меньше заданного. Затем в результате обработки элементов последовательности D получается случайное число. Преимуществом способа является получение случайного числа с заданной энтропией с использованием компьютера без применения дополнительных аппаратных средств.

Описанный выше способ принят за прототип.

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

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

Особенности криптографического приложения и среды функционирования определили ряд требований к предлагаемому способу:

1. Генерируемые последовательности должны быть близки по статистическим характеристикам к идеальным случайным последовательностям, в частности, для двоичной последовательности вероятность (относительная частота) p знака «1» или «0» должна быть близка к 1/2, то есть отклонение δ вероятности знака от 1/2 не должно превосходить некоторого фиксированного значения δ₀, близкого к нулю, например, ⎟p-1/2⎢δ≤δ₀, где δ₀≤10^-2.

2. При реализации способа среднестатистическим пользователем скорость генерации должна быть не менее 10 бит/сек.

3. Продолжительность генерации среднестатистическим пользователем 320 бит (которые соответствуют в алгоритмах ГОСТ 28147-89 и «Магма» (ГОСТ Р 34.12-2015)) сумме длины ключа (256 бит) и длины синхропосылки (64 бита) не должна превышать 30 секунд.

4. Удобство для пользователя реализации способа.

Раскрытие изобретения

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

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

Задача, на решение которой направлено данное изобретение, состоит в программной реализации способа генерации случайных двоичных последовательностей с заданными характеристиками производительности и относительной частоты знаков с использованием компьютера и действий пользователя. Реализацию предлагаемого способа назовем биологическим датчиком случайных чисел (БиоДСЧ), то есть датчиком, вырабатывающим случайную последовательность путем реализации случайных испытаний, основанных на случайном характере многократного взаимодействия пользователя с персональным компьютером.

Изобретение иллюстрируется рисунками.

Фиг. 1 - приведена схема хаотичного движения кругов по рабочей области экрана персонального компьютера.

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

Фиг. 3 - показан независимый от процесса рандомизатор и определение состояния невидимого круга.

Фиг. 4 - показаны измеряемые величины, относящиеся к успешному клику, то есть клику в площадь круга.

Фиг. 5 - блок-схема алгоритма генерации необходимого количества бит случайной двоичной последовательности в соответствии с предлагаемым способом.

Фиг. 6 - приведена таблица с выбранными значениями параметров БиоДСЧ.

Способ заключается в следующем.

Способ генерации случайных двоичных последовательностей, характеризуется тем, что используют персональный компьютер 1 и обеспечивают получение случайного числа с заданной энтропией. В качестве источника случайности используют осмысленные целенаправленные действия пользователя 2, а именно - клики 3 (мышью либо пальцем в случае сенсорного экрана) по экрану 4 персонального компьютера 1, по отношению к наблюдаемому внутри рабочей области 5 экрана 4 псевдослучайному процессу, который состоит в последовательной генерации с помощью кликов 3 пользователя 2 N кругов 6 диаметра d с временными интервалами в доли секунды, где каждый круг 6 начинает прямолинейное движение в различных направлениях движения кругов 7, отражаясь от границ рабочей области 5 и других кругов 6, часто меняя направление движения 7 и имитируя в целом хаотичный процесс движения кругов 6. На фиг. 1 приведена схема хаотичного движения кругов по рабочей области экрана компьютера.

На фиг. 2 изображена блок-схема одного сеанса взаимодействия пользователя 2 с псевдослучайным процессом, отображаемым на экране 4 компьютера 1. В начале процесса (этап 8) пользователь 2 генерирует N кругов 6 диаметра d (этап 9), кликая произвольным образом в площадь прямоугольника рабочей области 5. После появления в рабочей области 5 последнего круга 6 (этап 10) кликают в произвольной последовательности в площадь каждого из N движущихся кругов 6 (этапы 11, 13, 15), при этом после успешного клика 3 (этапы 12, 14, 16) сохраняются характеристики каждого круга 6 (этапы 17, 19, 21), круг 6 становится невидимым и переходит в новое состояние (этапы 18, 20), которое определяется независимым от процесса рандомизатором (показан далее на фиг. 3). Сеанс взаимодействия пользователя 2 с псевдослучайным процессом, отображаемым на экране 4 персонального компьютера 1 завершается (этап 22) после успешного попадания в площадь каждого круга 6.

На фиг. 3 приведен пример независимого от процесса рандомизатора, который иллюстрирует, но не ограничивает настоящего изобретения. В качестве рандомизатора можно использовать линейный регистр сдвига с примитивным характеристическим многочленом (позиция 23) (далее - регистр сдвига). Длина регистра сдвига 23 равна восьми. Вариант состояния невидимого круга 6 определяется выходной 3-граммой (позиция 24) (то есть последовательностью из 3-х элементов) регистра сдвига 23 выработанной при случайном ненулевом состоянии регистра сдвига 23: в случае выработки регистром сдвига 23 3-грамм 24 вида «000», «001», «010», «011» невидимый круг 6 продолжает двигаться и соударяться в рабочей области 5 (позиция 25), в случае «100» невидимый круг 6 останавливается (позиция 26), в случае «101» - невидимый круг 6 останавливается после одного соударения с любыми кругами в рабочей области 5 (позиция 27), в случае «110» - невидимый круг 6 останавливается после двух соударений с любыми кругами в рабочей области 5 (позиция 28), в случае «111» - невидимый круг 6 останавливается после трех соударений с любыми кругами в рабочей области 5 (позиция 29).

Способ характеризуется также тем, что в момент успешного клика α_i (позиция 30) в i-й круг 6 измеряют характеристики процесса (фиг. 4), то есть измеряемые величины, относящиеся к успешному клику 3 (клику в площадь круга 6), к которым при i=1, …, N относят, но не ограничиваются: координаты по осям X и Y соответственно x_i и y_i (позиция 31) точки клика α_i 30 попадания в i-й круг 6; расстояние r_i (позиция 32) от центра 33 i-го круга 6 до точки клика α_i 30; номер μ_i (позиция 34) сектора 35 внутри i-го круга 6, содержащего точку клика α_i 30 (если расстояние 32 от центра 33 до точки клика α_i 30 превышает три пикселя); время t_i (позиция 36) реагирования пользователя 2 на i-й круг 6, i>1, вычисляемое как разность между моментами попадания в i-й круг и в (i-1)-й круг, вычисляемыми с помощью счетчика тактов процессора RDTSC, обеспечивающего высокую точность (находится в процессоре компьютера 1).

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

На фиг. 5 представлена блок-схема алгоритма генерации необходимого количества бит случайной двоичной последовательности в соответствии с предлагаемым способом. В начале алгоритма (этап 37) происходит сеанс взаимодействия пользователя 2 с компьютером 1 (этап 38), в результате которого осуществляется генерация бит случайной последовательности (этап 39), к элементам которой применяется функция хэширования (этап 40). Если полученного количества бит недостаточно (этап 41), то сеанс повторяется столько раз, сколько необходимо для генерации нужного количества бит (этап 42).

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

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

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

- регистрируемые события независимы во времени, то есть реакцию пользователя 2 на процесс, наблюдаемый на экране 4, сложно тиражировать с высокой точностью как ему самому, так и любому другому пользователю;

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

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

Формула для вычисления энтропии (по Шеннону):

где p_i - вероятность появления i-го значения (значения отсортированы по убыванию вероятностей).

Энтропия Н (в битах) для известных предельных распределений имеет вид [5]:

1. Для нормального распределения N(μ, σ²): , где μ - математическое ожидание случайной величины, σ² - дисперсия случайной величины, π≈3,14, e≈2,718;

2. Для распределения Рэлея R(θ): , где θ - параметр масштаба, γ≈0,577 - постоянная Эйлера;

3. Для дискретного равномерного распределения R[a, b] на отрезке [a, b]:

Известно [6], что энтропия Н_∑ системы, состоящей из Т независимых источников, есть сумма энтропии каждого источника:

.

Получим оценку энтропии для модели БиоДСЧ с параметрами, указанными на фиг. 6, где приведена таблица с выбранными значениями параметров БиоДСЧ.

Координаты x_i и y_i 31 точки клика α_i 30 в рабочей области 1 размером 800 на 600 точек распределены по нормальному закону с математическим ожиданием, равным 400 и 300 соответственно, и с эмпирической верхней границей для дисперсии, равной 27800 и 16400 соответственно. Следовательно,

,

.

Расстояния r_i 32 от центра 33 i-го круга 6 до точки клика α_i 30 распределены по закону Рэлея с эмпирической верхней границей для масштаба, равной 21. Следовательно,

.

Номера μ_i 34 сектора 35 внутри i-го круга 6, содержащего точку клика α_i 30 в случае восьми секторов распределены равномерно. Следовательно,

.

Значения времени t_i 36 реагирования пользователя 2 на i-й круг 6, i>1, определяемые значением младшего байта разностей значений счетчика RDTSC, распределены равномерно. Следовательно,

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

.

В результате удаления двенадцати кругов (N=12) за один сеанс работы БиоДСЧ можно получить случайную последовательность s длины 408 бит, элементы которой преобразуются с использованием функции хэширования.

Приведем пример применения предлагаемого способа для генерации ключа К и вектора инициализации IV алгоритма ГОСТ 28147-89.

Обозначим: V_n - множество всех n-мерных двоичных векторов, n - натуральное число; MSB_n:V_k→V_n - отображение множества k-битовых векторов во множество n-битовых векторов, k≥n, ⎟а⎢ - размерность двоичного вектора а, а⎪⎪b - конкатенация двоичных векторов a и b, т.е. двоичный вектор из V_{⎪a⎪+⎪b⎪}, в котором слева записаны координаты вектора а, а справа - координаты вектора b.

Пусть s=s₁⎪⎪s₂, где ⎪s₁⎪=280, ⎪s₂⎪=128. Тогда 256 бит ключа K и 64 бита вектора инициализации IV получаются в соответствии с формулами:

K=hash(s₁),

IV=MSB₆₄(hash(s₂)),

где hash есть функция хэширования с длиной хэш-кода 256 бит.

Таким образом, для генерации ключа и вектора инициализации алгоритма ГОСТ 28147-89 среднестатистическому пользователю 2 достаточно одного сеанса работы БиоДСЧ продолжительностью не более 30 секунд.

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

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

Источники информации

1. Фомичев В.М. Методы дискретной математики в криптологии / В.М. Фомичев. - М.: Диалог-МИФИ, 2010. - 424 с.

2. Кнут Д. Искусство программирования. Том 2. Получисленные алгоритмы / Д. Кнут; пер. с англ. - 3-е изд. - М.: «Вильямс», 2007. - 832 с.

3. Seznec A., Sendrier N. HAVEGE: a user-level software heuristic for generating empirically strong random numbers, ACM Transaction on Modeling and Computer Simulations (TOMACS), Volume 13, Issue 4, October 2003.

4. Патент RU 2577201 C2, МПК G06F 7/58, 22.04.2014. - Способ генерации случайных чисел с использованием компьютера (варианты).

5. Фергюсон Н. Практическая криптография / Н. Фергюсон, Б. Шнайер Б. - М.: Издательский дом «Вильямс», 2005. - 424 с.

6. Вентцель Е.С. Теория вероятностей: Учеб. для вузов. - 6-е изд. стер. - М.: Высш. шк., 1999. - 576 с.

1. Способ генерации случайных двоичных последовательностей, характеризующийся тем, что используют персональный компьютер и обеспечивают получение случайного числа с заданной энтропией, отличающийся тем, что в качестве источника случайности используют осмысленные целенаправленные действия пользователя, а именно - клики мышью либо клики пальцем в случае сенсорного экрана, по отношению к наблюдаемому внутри рабочей области экрана псевдослучайному процессу, который состоит в последовательной генерации N кругов диаметра d с временными интервалами в доли секунды, и каждый круг начинает прямолинейное движение в различных направлениях из центра рабочей области, отражаясь от границ рабочей области и других кругов, часто меняя направление движения и имитируя в целом хаотичный процесс движения кругов, и после появления в рабочей области последнего круга кликают в произвольной последовательности в площадь каждого из N движущихся кругов, при этом после успешного клика круг переходит в следующее состояние: становится невидимым для пользователя и впоследствии либо продолжает двигаться и соударяться в рабочей области, либо останавливается после h соударений с любыми кругами в рабочей области, h∈{0,1,2,3}, причем вариант состояния невидимого круга определяется независимым от процесса рандомизатором.

2. Способ по п. 1, отличающийся тем, что в момент успешного клика измеряют характеристики процесса, к которым при i=1, …, N относят: координаты x_i и y_i (по осям X и Y соответственно) точки α_i попадания в i-й круг; расстояние r_i от центра i-го круга до точки клика α_i; номер μ_i сектора внутри i-го круга, содержащего точку α_i (если расстояние от центра до α_i превышает три пикселя); время t_i реагирования пользователя на i-й круг, i>1, вычисляемое как разность между моментами попадания в i-й круг и в (i-1)-й круг, вычисляемыми с помощью счетчика тактов процессора RDTSC, обеспечивающего высокую точность.

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