close

Вход

Забыли?

вход по аккаунту

?

Патент BY12420

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2009.10.30
(12)
(51) МПК (2006)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
G 06F 7/58
СПОСОБ ГЕНЕРИРОВАНИЯ СЛУЧАЙНОЙ БИНАРНОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ И УСТРОЙСТВО ДЛЯ ЕГО
РЕАЛИЗАЦИИ
(21) Номер заявки: a 20070593
(22) 2007.05.18
(43) 2008.12.30
(71) Заявитель: Государственное научное учреждение "Институт физики
имени Б.И.Степанова Национальной академии наук Беларуси" (BY)
(72) Авторы: Чижевский Вячеслав Николаевич; Хорошко Дмитрий Борисович; Пустоход Дмитрий Игоревич;
Килин Сергей Яковлевич (BY)
BY 12420 C1 2009.10.30
BY (11) 12420
(13) C1
(19)
(73) Патентообладатель: Государственное
научное учреждение "Институт физики имени Б.И.Степанова Национальной академии наук Беларуси" (BY)
(56) ALKASSAR A. et al. Obtaining TrueRandom Binary Numbers from a Weak
Radioactive Source, O. Gervasi et al.
(Eds.), ICCSA 2005, LNCS 3481, 2005.P. 634-646.
RU 2281603, 2006.
US 7167882 B2, 2007.
US 3662337, 1972.
EP 0545183 A1, 1993.
(57)
1. Способ генерирования случайной бинарной последовательности, характеризующийся тем, что измеряют временные интервалы между случайными событиями, принадлежащие заданному закону распределения, например экспоненциальному, преобразуют
каждый измеренный временной интервал в биты двоичного представления, генерируют
последовательность случайных бит, каждый из которых получают путем суммирования по
модулю два бит двоичного представления соответствующего измеренного временного интервала, причем количество упомянутых суммируемых бит выбирают, исходя из требуемой равномерности распределения случайных бит в генерируемой последовательности и
скорости преобразования измеренных временных интервалов в последовательность случайных бит, а измеренные временные интервалы между случайными событиями, не принадлежащие заданному закону распределения, дискриминируют по заданному уровню.
Фиг. 1
BY 12420 C1 2009.10.30
2. Устройство для генерирования случайной бинарной последовательности, содержащее источник случайных временных интервалов, детектор случайных событий, блок измерения временных интервалов, блок преобразования измеренных временных интервалов
в биты двоичного представления, отличающееся тем, что содержит блок дискриминации
измеренных временных интервалов по заданному уровню, включенный между блоком измерения временных интервалов и блоком преобразования измеренных временных интервалов в биты двоичного представления; блок суммирования по модулю два бит двоичного
представления, выход которого является выходом устройства, а входы соединены с соответствующими выходами блока преобразования измеренных временных интервалов в биты двоичного представления.
Изобретение относится к области криптографии, вычислительной техники и может
быть использовано в системах обработки информации и статистическом моделировании.
Известен способ генерации случайной бинарной последовательности, основанный на
сравнении длительности интервалов времени между двумя последовательными случайными событиями, подчиняющихся экспоненциальному закону распределения [1]. По этому способу пара измеренных интервалов t1 и t2 принимается за "1", если при измерении
интервалов времени t1 > t2, и за "0" - если t1 < t2, а при t1 = t2 оба интервала времени отбрасываются. К недостаткам способа относится потеря половины измеренных интервалов
времени, так как один бит определяется по двум интервалам, а также чувствительность
метода генерации к техническим флуктуациям и нестабильностям параметров.
Ближайшим техническим решением к предложенному способу (прототип) является
способ генерирования случайной бинарной последовательности [2], основанный на измерении интервалов времени между последовательными случайными событиями и преобразовании этих интервалов в двоичное представление по определенному правилу [2, 3]: если
число бит (двоичных разрядов) в преобразованном интервале является нечетным, то измеренный интервал интерпретируется как "1", если число бит (двоичных разрядов) -четное,
то измеренный интервал интерпретируется как "0". Хотя способ позволяет удвоить число
генерируемых случайных бит, тем не менее, он не позволяет получить случайную бинарную последовательность с равномерным распределением нулей и единиц и коэффициентами корреляции, необходимыми для криптографических систем. Известно, что безопасность
криптографических систем существенно зависит от качества используемых случайных чисел.
Задачей изобретения является повышение качества генерируемых случайных бит за
счет улучшения равномерности генерируемой случайной бинарной последовательности и
уменьшения корреляции между генерируемыми битами.
Сущность предлагаемого изобретения заключается в следующем. Способ генерирования случайной бинарной последовательности характеризуется тем, что измеряют временные интервалы между случайными событиями, принадлежащие заданному закону
распределения, например экспоненциальному, преобразуют каждый измеренный временной интервал в биты двоичного представления, генерируют последовательность случайных бит, каждый из которых получают путем суммирования по модулю два бит
двоичного представления соответствующего измеренного временного интервала, причем
количество упомянутых суммируемых бит выбирают, исходя из требуемой равномерности распределения случайных бит в генерируемой последовательности и скорости преобразования измеренных временных интервалов в последовательность случайных бит, а
измеренные временные интервалы между случайными событиями, не принадлежащие заданному закону распределения, дискриминируют по заданному уровню.
Устройство для генерирования случайной бинарной последовательности содержит источник случайных временных интервалов, детектор случайных событий, блок измерения
2
BY 12420 C1 2009.10.30
временных интервалов, блок преобразования измеренных временных интервалов в биты
двоичного представления, блок дискриминации измеренных временных интервалов по
заданному уровню, включенный между блоком измерения временных интервалов и блоком преобразования измеренных временных интервалов в биты двоичного представления;
блок суммирования по модулю два бит двоичного представления, выход которого является выходом устройства, а входы соединены с соответствующими выходами блока преобразования измеренных временных интервалов в биты двоичного представления.
Для осуществления способа генерирования случайной бинарной последовательности,
предлагается устройство, блок-схема которого представлена на фиг. 1. Устройство включает в себя источник случайных временных событий с требуемым законом распределения 1,
детектор случайных событий 2, блок измерения временных интервалов 3, блок преобразования измеренных интервалов в биты (разряды) двоичного представления 4, согласно изобретению, после преобразователя измеренных интервалов дополнительно введен блок
суммирования бит (разрядов) двоичного представления по модулю два 5, с выхода которого считывают случайные биты, при этом для дискриминации временных интервалов по
заданному уровню перед блоком преобразователя 4 дополнительно введен блок дискриминации 6.
Рассмотрим последовательность измеренных интервалов времени между случайными
событиями, подчиняющихся, например, экспоненциальному закону распределения. Подобная функция распределения характерна для целого ряда процессов в квантовой оптике.
Для данной частоты дискретизации, число выборочных тактов m между двумя последовательными событиями - случайная величина с экспоненциальным распределением
Рr(m) = pqm, где p = 1-q - вероятность события для данного такта. В этом случае каждый
измеренный случайный интервал m может быть преобразован в биты (разряды) двоичного
представления: m = (аl-1...а1а0)2, где аk принимает значение либо "0", либо "1".
При генерировании случайной бинарной последовательности по способу прототипа
(т.е. по определению четности или нечетности измеренных интервалов), значение разности вероятностей появления нулей и единиц D = Pr(b = 0)-Рr(b = 1) определяется следующим выражением:
1− q
D=
.
1+ q
В частности, для значений q = 0,99, эта величина D ≈ 5 × 10-3.
По предложенному способу, для генерации случайно бинарной последовательности
предлагается проводить суммирование бит (разрядов) двоичного представления
(аl-1...a1a0)2 по модулю 2:
 n −1 
b =  ∑ a k  mod 2, n ≤ l ,
 k =0 
с помощью которого каждый интервал времени преобразуется в один случайный бит b.
При этом число суммируемых бит двоичного представления определяется требуемой равномерностью распределения бит и скоростью преобразования измеренных интервалов в
последовательность случайных бит. При n = 2, т.е. при суммировании двух младших бит
(регистров) двоичного отображения (а1 и а0), полученный поток бит имеет распределение,
близкое к равномерному:
D=
(1 − q )2 .
1 + q2
Для значений q = 0,99 разность D между вероятностью появления нулей Pr(b = 0) и вероятностью появления единиц Pr(b = 1), D ≈ 5 × 10-5, что примерно в 100 раз меньше, чем
по способу прототипа. При n ≥ 3, т.е. при суммировании трех и более младших бит (раз-
3
BY 12420 C1 2009.10.30
рядов) двоичного представления (аk,...,а1 и а0), полученный поток бит имеет распределение, определяемое следующим выражением:
n −2
D = (1 − q) n
∏ (1 + q 2
k =1
k −1
) n − k −1
, n ≥ 3.
1 + q 2 n −1
При суммировании, например, трех младших бит для q = 0,99 разность D ≈ 1,8 × 10-6,
что примерно в 2500 раз меньше, чем по способу прототипа. Еще меньшее значение D
может быть получено при суммировании большего числа бит. Например, при n = 9 для
значения q = 0,99, разность D ≈ 7,9 × 10-11, что примерно в 107 раз меньше, чем по способу
прототипа. На фиг. 2 в логарифмическом масштабе представлены зависимости величины
D от числа суммируемых младших бит n, показанные для разных значений q (q = 0,9 (1)
0,95 (2); 0,97 (3); 0,98 (4); 0,99 (5)). Значения D при n = 1 соответствует величине неравномерности распределения числа нулей и единиц в последовательности генерируемых бит
по способу прототипа. Видно, что для любых значений q увеличение числа суммируемых
бит приводит к существенному улучшению равномерности распределения нулей и единиц
в генерируемой последовательности по сравнению с прототипом. При этом существует
некоторое оптимальное значение числа суммируемых бит N, начиная с которого дальнейшее увеличение числа суммируемых бит n можно не проводить в силу слабой зависимости D от n. Эти значения N можно оценить из следующего выражения:
N ≈ 1,5-log2(1-q),
где N - символ округления к верхнему целому значению. На фиг. 2 значения N, рассчитанные из приведенного выражения, показаны кружками.
Из приведенных оценок следует, что предложенный способ, при заданной частоте
дискретизации, позволяет существенно уменьшить величину D, характеризующую неравномерность распределения нулей и единиц в потоке генерируемых бит, по сравнению с
прототипом. При этом число суммируемых бит N определяется отношением частоты дискретизации к средней частоте появления случайных событий. Для получения такого же
эффекта при использовании прототипа необходимо увеличить в 102-107 раз частоту дискретизации (в зависимости от требуемого качества случайных бит и скорости их генерации), что приводит либо к существенному удорожанию аппаратуры, либо практически
нереализуемо на существующем уровне развития технических средств.
Предложенный способ был экспериментально реализован и статистически протестирован на устройстве, согласно предложенному изобретению. В качестве источника случайных временных интервалов 1 использовался полупроводниковый лазер с
вертикальным резонатором, генерирующий в области поляризационной бистабильности.
Инжекционный ток и температура лазерного диода были выбраны таким образом, чтобы
обеспечить почти симметричную конфигурацию бистабильного квазипотенциала со спонтанными переключениями между двумя поляризационными состояниями. Известно, что в
бистабильном полупроводниковом лазере с вертикальным резонатором, переключения
между двумя поляризационными состояниями вызываются спонтанной эмиссией [4] и поэтому являются действительно случайными событиями. Интенсивность лазера на выделенной поляризации регистрировалась фотодетектором и цифровым USB осциллографом,
позволяющим реализовать быструю передачу данных на компьютер для обработки данных. Период дискретизации ts был выбран так, чтобы гарантировать q ≥ 0,99 (ts = 0,5 мксек
в нашем случае). На фиг. 3 показан фрагмент временного поведения интенсивности лазера
на выделенной поляризации, демонстрирующий случайные переключения между двумя
поляризационными состояниями, индуцированные спонтанными шумами лазера. В процессе обработки измерялось время между последовательными переключениями. На фиг. 4
показана функция распределения интервалов времени между переключениями, полученная из обработки экспериментальных данных. В такой системе было сгенерировано более
4
BY 12420 C1 2009.10.30
2 × 108 интервалов времени между последовательными переключениями (обозначенные
здесь, как nk = tk/ts, где tk - время между двумя последовательными переключениями). В
определенном диапазоне tk, экспериментальные данные на кривой (фиг. 4) приблизительно удовлетворяют условиям экспоненциального закона: Р (nk) ∞ехр (-nk/n0), где n0 ≈ 100, за
исключением небольшой части при малых значениях nk. Поэтому как первый шаг в преобразовании nk, в биты двоичного представления дискриминировались все nk, имеющие
значение меньше, чем некоторое значение nth. Из анализа данных было найдено, что для
данной системы nth = 7. После этого остальная часть экспериментальных данных преобразовывалась в поток случайных бит, как описано выше.
С целью подтверждения преимуществ предложенного способа над известными способами, из одного и того же массива экспериментально измеренных временных интервалов
были сгенерированы случайные последовательности бит (длиной в 108 бит) тремя различными способами: двумя известными способами - по способу аналога - путем сравнения
соседних временных интервалов; по способу прототипа - выделением четных-нечетных
интервалов (что равносильно взятию младшего бита двоичного представления в качестве
случайного); и тремя модификациями предложенного способа - суммированием двух
младших бит двоичного представления интервалов; суммированием трех младших бит;
суммированием 9 бит двоичного представления временных интервалов.
Проверка гипотезы о случайности пяти сгенерированных последовательностей бит
производилась с помощью трех наборов статистических тестов, широко используемых на
практике при определении качества генерируемых случайных последовательностей. Результаты статистического тестирования приведены в табл. 1-3.
ENT-тест [5]. В этом наборе тестов вычисляются пять параметров, которые характеризуют как случайность тестируемой последовательности (χ2 - тест, энтропия/бит), так и ее
качество (среднее значение, коэффициент корреляции, моделирование числа π). Более
подробное описание тестов можно найти в [5]. Из данных, приведенных в табл. 1 видно,
что применение предложенного метода позволяет значительно уменьшить коэффициент
корреляции и приблизить среднее значение к теоретическому пределу 0,5. Увеличение параметра n приводит к лучшему результату χ2 - теста, для прохождения которого необходимо получить значение в интервале (0,25; 0,75). Использование предложенного способа
для статистического моделирования числа π методом Монте-Карло также приводит к существенно меньшей ошибке.
Таблица 1
Предложенный способ
Способ ана- Способ про- Сумма n младших бит
Сумма 9 бит (дволога
тотипа
(двоичных разрядов)
ичных разрядов)
n=2
n=3
Энтропия/бит
1,000000
0,999950
1,000000
1,000000
1,000000
Среднее зна0,5001
0,5041
0,500009
0,500024
0,5000025
чение
π, метод Мон3,118326259 3,117756019 3,141172343 3,1426949
3,141306743 (0,01)
те-Карло
(0,74)
(0,76)
(0,01)
03 (0,04)
(ошибка, %)
Коэффициент
0,016496
0,000122
0,000084
-0,000006
-0,000063
корреляции
25
0,01
75
50
75
χ2 - тест, %
Блок тестов DIEHARD. В соответствии с описанием блока тестов DIEHARD [6], полученные в каждом из 229 тестов р-значения (всего 229 величин) должны быть равномерно
распределены на интервале (0,1). Итоговое р-значение есть результат оценки равномерности их распределения. В случае шести и более р-значений, очень близких к 0 или 1 (т.е.
5
BY 12420 C1 2009.10.30
меньших 0,025 или больших 0,975), тесты следует считать не пройденными. Результаты,
приведенные в табл. 2, свидетельствуют, что предложенный способ позволяет генерировать случайные последовательности из таких исходных данных, из которых ранее известные методы не позволяли получать случайные бинарные последовательности,
удовлетворяющие условиям прохождения тестов.
Таблица 2
Предложенный способ
Интервал р- Способ
Способ
Сумма n младших бит
Сумма 9 бит (двоичных
значений
аналога прототипа (двоичных разрядов)
разрядов)
n=2
n=3
0,0-0,1
15
20
29
16
26
0,1-0,2
6
8
17
17
22
0,2-0,3
6
13
20
19
26
0,3-0,4
14
16
15
20
20
0,4-0,5
5
21
37
28
26
0,5-0,6
3
19
25
28
27
0,6-0,7
7
19
23
22
19
0,7-0,8
8
20
29
28
16
0,8-0,9
8
23
13
26
24
0,9-1,0
157
70
21
25
23
Итоговое р0,000000 0,000000
0,442689
0,064345
0,675203
значение
Комплекс тестов Национального Института Стандартов и Технологий (НИСТ, США).
Данные и параметры этого набора тестов выбирались в соответствии с рекомендациями,
изложенными в [7]. В процессе тестирования исходная последовательность разбивалась на
100 частей, по 106 бит в каждой. Результатом прохождения каждого теста, таким образом,
было 100 р-значений. Эти сто величин должны, во-первых, быть равномерно распределены на интервале (0,1) и, во-вторых, не менее 96,015 % из них должны превышать пороговое значение α = 0,01, где параметр α определяет качество генерируемой случайной
последовательности. Для каждого из трех способов в двух столбцах отражается соответствие этим двум критериям (см. табл. 3). Результаты этого тестирования также свидетельствуют о преимуществах предложенного способа по сравнению с известными способами
генерации случайных бинарных последовательностей.
Таблица 3
Предложенный способ
Название теста
Частотный тест
Частотный тест внутри блока
Тест на кумулятивную сумму (2
теста)
Тест на непрерывную серию
Тест на самую длинную серию
единиц в блоке
Тест ранга случайной двоичной
матрицы
Сумма n младших
Способ Способ
Сумма 9 бит
бит (двоичных разаналога прототипа
(двоичных
рядов)
разрядов)
n=2
n=3
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-
+
+
+
+
+
+
-
-
-
-
+
+
+
+
+
+
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
6
BY 12420 C1 2009.10.30
Продолжение таблицы 3
Предложенный способ
Название теста
Спектральный тест дискретного
преобразования Фурье
Тест на соответствие неперекрывающегося (апериодического)
шаблона (148 тестов)
Тест на соответствие перекрывающегося(периодического)
шаблона
Универсальный статистический
тест Морера
Тест на приближенную энтропию
Тест на случайные отклонения (8
тестов)
Вариант теста на случайные отклонения (18 тестов)
Серийный тест (2 теста)
Линейный тест на сложность
Сумма n младших
Способ Способ
Сумма 9 бит
бит (двоичных разаналога прототипа
(двоичных
рядов)
разрядов)
n=2
n=3
+
-
+
+
+
+
+
+
+
+
-
-
-
-
+
+
+
+
+
+
-
-
-
-
+
+
+
+
+
+
-
-
+
+
+
+
+
+
+
+
-
-
-
-
+
+
+
+
+
+
+
-
+
-
+
+
+
+
+
+
+
+
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
Источники информации:
1. Stipcevic М., Rogina В.М. Quantum random number generator, http://arXiv:quantph/0609043.
2. Alkassar A., Nicolay T., Rohe M. Obtaining True-Random Binary Numbers from a Weak
Radioactive Source, O. Gervasi et al. (Eds.): ICCSA 2005, LNCS. V. 3481.- P. 634-646, 2005.
3. Патент США 7167882, МПК8 G 06F 1/02, 2007.
4. Willemsen М.В. et al. Polarization Switching of a Vertical-Cavity Semiconductor Laser
as a Kramers Hopping Problem. Phys. Rev. Lett. 82, 1999.- P. 4115-4118.
5. John Walker. ENT - a pseudorandom sequence test program. http://www.fourmilab.ch/random/.
6. George Marsaglia. Diehard: a battery of tests for random number generators.
http://stat.fsu.edu/~geo/diehard.html.
7.National Institute of Standards and Technology. Random number generation and testing.
http://csrc.nist.gov/rng/.
7
BY 12420 C1 2009.10.30
Фиг. 2
Фиг. 3
Фиг. 4
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
8
Документ
Категория
Без категории
Просмотров
0
Размер файла
374 Кб
Теги
by12420, патент
1/--страниц
Пожаловаться на содержимое документа