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

(51) МПК (2006) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ СПОСОБ ГЕНЕРИРОВАНИЯ СЛУЧАЙНОЙ БИНАРНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ И УСТРОЙСТВО ДЛЯ ЕГО РЕАЛИЗАЦИИ(71) Заявитель Государственное научное учреждение Институт физики имени Б.И.Степанова Национальной академии наук Беларуси(72) Авторы Чижевский Вячеслав Николаевич Хорошко Дмитрий Борисович Пустоход Дмитрий Игоревич Килин Сергей Яковлевич(73) Патентообладатель Государственное научное учреждение Институт физики имени Б.И.Степанова Национальной академии наук Беларуси(57) 1. Способ генерирования случайной бинарной последовательности, характеризующийся тем, что измеряют временные интервалы между случайными событиями, принадлежащие заданному закону распределения, например экспоненциальному, преобразуют каждый измеренный временной интервал в биты двоичного представления, генерируют последовательность случайных бит, каждый из которых получают путем суммирования по модулю два бит двоичного представления соответствующего измеренного временного интервала, причем количество упомянутых суммируемых бит выбирают, исходя из требуемой равномерности распределения случайных бит в генерируемой последовательности и скорости преобразования измеренных временных интервалов в последовательность случайных бит, а измеренные временные интервалы между случайными событиями, не принадлежащие заданному закону распределения, дискриминируют по заданному уровню. 12420 1 2009.10.30 2. Устройство для генерирования случайной бинарной последовательности, содержащее источник случайных временных интервалов, детектор случайных событий, блок измерения временных интервалов, блок преобразования измеренных временных интервалов в биты двоичного представления, отличающееся тем, что содержит блок дискриминации измеренных временных интервалов по заданному уровню, включенный между блоком измерения временных интервалов и блоком преобразования измеренных временных интервалов в биты двоичного представления блок суммирования по модулю два бит двоичного представления, выход которого является выходом устройства, а входы соединены с соответствующими выходами блока преобразования измеренных временных интервалов в биты двоичного представления. Изобретение относится к области криптографии, вычислительной техники и может быть использовано в системах обработки информации и статистическом моделировании. Известен способ генерации случайной бинарной последовательности, основанный на сравнении длительности интервалов времени между двумя последовательными случайными событиями, подчиняющихся экспоненциальному закону распределения 1. По этому способу пара измеренных интервалов 1 и 2 принимается за 1, если при измерении интервалов времени 12, и за 0 - если 12, а при 12 оба интервала времени отбрасываются. К недостаткам способа относится потеря половины измеренных интервалов времени, так как один бит определяется по двум интервалам, а также чувствительность метода генерации к техническим флуктуациям и нестабильностям параметров. Ближайшим техническим решением к предложенному способу (прототип) является способ генерирования случайной бинарной последовательности 2, основанный на измерении интервалов времени между последовательными случайными событиями и преобразовании этих интервалов в двоичное представление по определенному правилу 2, 3 если число бит (двоичных разрядов) в преобразованном интервале является нечетным, то измеренный интервал интерпретируется как 1, если число бит (двоичных разрядов) -четное,то измеренный интервал интерпретируется как 0. Хотя способ позволяет удвоить число генерируемых случайных бит, тем не менее, он не позволяет получить случайную бинарную последовательность с равномерным распределением нулей и единиц и коэффициентами корреляции, необходимыми для криптографических систем. Известно, что безопасность криптографических систем существенно зависит от качества используемых случайных чисел. Задачей изобретения является повышение качества генерируемых случайных бит за счет улучшения равномерности генерируемой случайной бинарной последовательности и уменьшения корреляции между генерируемыми битами. Сущность предлагаемого изобретения заключается в следующем. Способ генерирования случайной бинарной последовательности характеризуется тем, что измеряют временные интервалы между случайными событиями, принадлежащие заданному закону распределения, например экспоненциальному, преобразуют каждый измеренный временной интервал в биты двоичного представления, генерируют последовательность случайных бит, каждый из которых получают путем суммирования по модулю два бит двоичного представления соответствующего измеренного временного интервала, причем количество упомянутых суммируемых бит выбирают, исходя из требуемой равномерности распределения случайных бит в генерируемой последовательности и скорости преобразования измеренных временных интервалов в последовательность случайных бит, а измеренные временные интервалы между случайными событиями, не принадлежащие заданному закону распределения, дискриминируют по заданному уровню. Устройство для генерирования случайной бинарной последовательности содержит источник случайных временных интервалов, детектор случайных событий, блок измерения 2 12420 1 2009.10.30 временных интервалов, блок преобразования измеренных временных интервалов в биты двоичного представления, блок дискриминации измеренных временных интервалов по заданному уровню, включенный между блоком измерения временных интервалов и блоком преобразования измеренных временных интервалов в биты двоичного представления блок суммирования по модулю два бит двоичного представления, выход которого является выходом устройства, а входы соединены с соответствующими выходами блока преобразования измеренных временных интервалов в биты двоичного представления. Для осуществления способа генерирования случайной бинарной последовательности,предлагается устройство, блок-схема которого представлена на фиг. 1. Устройство включает в себя источник случайных временных событий с требуемым законом распределения 1,детектор случайных событий 2, блок измерения временных интервалов 3, блок преобразования измеренных интервалов в биты (разряды) двоичного представления 4, согласно изобретению, после преобразователя измеренных интервалов дополнительно введен блок суммирования бит (разрядов) двоичного представления по модулю два 5, с выхода которого считывают случайные биты, при этом для дискриминации временных интервалов по заданному уровню перед блоком преобразователя 4 дополнительно введен блок дискриминации 6. Рассмотрим последовательность измеренных интервалов времени между случайными событиями, подчиняющихся, например, экспоненциальному закону распределения. Подобная функция распределения характерна для целого ряда процессов в квантовой оптике. Для данной частоты дискретизации, число выборочных тактовмежду двумя последовательными событиями - случайная величина с экспоненциальным распределением Р, где 1- - вероятность события для данного такта. В этом случае каждый измеренный случайный интервалможет быть преобразован в биты (разряды) двоичного представления(а-1 а 1 а 0)2, где а принимает значение либо 0, либо 1. При генерировании случайной бинарной последовательности по способу прототипа(т.е. по определению четности или нечетности измеренных интервалов), значение разности вероятностей появления нулей и единиц(0)-Р(1) определяется следующим выражением 1. 1 В частности, для значений 0,99, эта величина 510-3. По предложенному способу, для генерации случайно бинарной последовательности предлагается проводить суммирование бит (разрядов) двоичного представления 0 с помощью которого каждый интервал времени преобразуется в один случайный бит . При этом число суммируемых бит двоичного представления определяется требуемой равномерностью распределения бит и скоростью преобразования измеренных интервалов в последовательность случайных бит. При 2, т.е. при суммировании двух младших бит(регистров) двоичного отображения (а 1 и а 0), полученный поток бит имеет распределение,близкое к равномерному 12 Для значений 0,99 разностьмежду вероятностью появления нулей (0) и вероятностью появления единиц (1),510-5, что примерно в 100 раз меньше, чем по способу прототипа. При 3, т.е. при суммировании трех и более младших бит (раз 3 12420 1 2009.10.30 рядов) двоичного представления (аа 1 и а 0), полученный поток бит имеет распределение, определяемое следующим выражением 2,3. 121 При суммировании, например, трех младших бит для 0,99 разность 1,810-6,что примерно в 2500 раз меньше, чем по способу прототипа. Еще меньшее значениеможет быть получено при суммировании большего числа бит. Например, при 9 для значения 0,99, разность 7,910-11, что примерно в 107 раз меньше, чем по способу прототипа. На фиг. 2 в логарифмическом масштабе представлены зависимости величиныот числа суммируемых младших бит , показанные для разных значений(0,9 (1) 0,95 (2) 0,97 (3) 0,98 (4) 0,99 (5. Значенияпри 1 соответствует величине неравномерности распределения числа нулей и единиц в последовательности генерируемых бит по способу прототипа. Видно, что для любых значенийувеличение числа суммируемых бит приводит к существенному улучшению равномерности распределения нулей и единиц в генерируемой последовательности по сравнению с прототипом. При этом существует некоторое оптимальное значение числа суммируемых бит , начиная с которого дальнейшее увеличение числа суммируемых битможно не проводить в силу слабой зависимостиот . Эти значенияможно оценить из следующего выражения 1,5-2(1-),где- символ округления к верхнему целому значению. На фиг. 2 значения , рассчитанные из приведенного выражения, показаны кружками. Из приведенных оценок следует, что предложенный способ, при заданной частоте дискретизации, позволяет существенно уменьшить величину , характеризующую неравномерность распределения нулей и единиц в потоке генерируемых бит, по сравнению с прототипом. При этом число суммируемых битопределяется отношением частоты дискретизации к средней частоте появления случайных событий. Для получения такого же эффекта при использовании прототипа необходимо увеличить в 102-107 раз частоту дискретизации (в зависимости от требуемого качества случайных бит и скорости их генерации), что приводит либо к существенному удорожанию аппаратуры, либо практически нереализуемо на существующем уровне развития технических средств. Предложенный способ был экспериментально реализован и статистически протестирован на устройстве, согласно предложенному изобретению. В качестве источника случайных временных интервалов 1 использовался полупроводниковый лазер с вертикальным резонатором, генерирующий в области поляризационной бистабильности. Инжекционный ток и температура лазерного диода были выбраны таким образом, чтобы обеспечить почти симметричную конфигурацию бистабильного квазипотенциала со спонтанными переключениями между двумя поляризационными состояниями. Известно, что в бистабильном полупроводниковом лазере с вертикальным резонатором, переключения между двумя поляризационными состояниями вызываются спонтанной эмиссией 4 и поэтому являются действительно случайными событиями. Интенсивность лазера на выделенной поляризации регистрировалась фотодетектором и цифровымосциллографом,позволяющим реализовать быструю передачу данных на компьютер для обработки данных. Период дискретизациибыл выбран так, чтобы гарантировать 0,99 (0,5 мксек в нашем случае). На фиг. 3 показан фрагмент временного поведения интенсивности лазера на выделенной поляризации, демонстрирующий случайные переключения между двумя поляризационными состояниями, индуцированные спонтанными шумами лазера. В процессе обработки измерялось время между последовательными переключениями. На фиг. 4 показана функция распределения интервалов времени между переключениями, полученная из обработки экспериментальных данных. В такой системе было сгенерировано более 4 12420 1 2009.10.30 2108 интервалов времени между последовательными переключениями (обозначенные здесь, как/, где- время между двумя последовательными переключениями). В определенном диапазоне , экспериментальные данные на кривой (фиг. 4) приблизительно удовлетворяют условиям экспоненциального закона Рехр (-/0), где 0100, за исключением небольшой части при малых значениях . Поэтому как первый шаг в преобразовании , в биты двоичного представления дискриминировались все , имеющие значение меньше, чем некоторое значение . Из анализа данных было найдено, что для данной системы 7. После этого остальная часть экспериментальных данных преобразовывалась в поток случайных бит, как описано выше. С целью подтверждения преимуществ предложенного способа над известными способами, из одного и того же массива экспериментально измеренных временных интервалов были сгенерированы случайные последовательности бит (длиной в 108 бит) тремя различными способами двумя известными способами - по способу аналога - путем сравнения соседних временных интервалов по способу прототипа - выделением четных-нечетных интервалов (что равносильно взятию младшего бита двоичного представления в качестве случайного) и тремя модификациями предложенного способа - суммированием двух младших бит двоичного представления интервалов суммированием трех младших бит суммированием 9 бит двоичного представления временных интервалов. Проверка гипотезы о случайности пяти сгенерированных последовательностей бит производилась с помощью трех наборов статистических тестов, широко используемых на практике при определении качества генерируемых случайных последовательностей. Результаты статистического тестирования приведены в табл. 1-3.-тест 5. В этом наборе тестов вычисляются пять параметров, которые характеризуют как случайность тестируемой последовательности (2 - тест, энтропия/бит), так и ее качество (среднее значение, коэффициент корреляции, моделирование числа ). Более подробное описание тестов можно найти в 5. Из данных, приведенных в табл. 1 видно,что применение предложенного метода позволяет значительно уменьшить коэффициент корреляции и приблизить среднее значение к теоретическому пределу 0,5. Увеличение параметраприводит к лучшему результату 2 - теста, для прохождения которого необходимо получить значение в интервале (0,25 0,75). Использование предложенного способа для статистического моделирования числаметодом Монте-Карло также приводит к существенно меньшей ошибке. Таблица 1 Предложенный способ Способ ана- Способ про- Суммамладших бит Сумма 9 бит (дволога тотипа-0,000063 корреляции 25 0,01 75 50 75 2 - тест,Блок тестов . В соответствии с описанием блока тестов 6, полученные в каждом из 229 тестов р-значения (всего 229 величин) должны быть равномерно распределены на интервале (0,1). Итоговое р-значение есть результат оценки равномерности их распределения. В случае шести и более р-значений, очень близких к 0 или 1 (т.е. 5 12420 1 2009.10.30 меньших 0,025 или больших 0,975), тесты следует считать не пройденными. Результаты,приведенные в табл. 2, свидетельствуют, что предложенный способ позволяет генерировать случайные последовательности из таких исходных данных, из которых ранее известные методы не позволяли получать случайные бинарные последовательности,удовлетворяющие условиям прохождения тестов. Таблица 2 Предложенный способ Интервал р- Способ Способ Суммамладших бит Сумма 9 бит (двоичных значений аналога прототипа (двоичных разрядов) разрядов) 2 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 теста) Тест на непрерывную серию Тест на самую длинную серию единиц в блоке Тест ранга случайной двоичной матрицы Суммамладших Способ Способ Сумма 9 бит бит (двоичных разаналога прототипа 12420 1 2009.10.30 Продолжение таблицы 3 Предложенный способ Название теста Спектральный тест дискретного преобразования Фурье Тест на соответствие неперекрывающегося (апериодического) шаблона (148 тестов) Тест на соответствие перекрывающегося(периодического) шаблона Универсальный статистический тест Морера Тест на приближенную энтропию Тест на случайные отклонения (8 тестов) Вариант теста на случайные отклонения (18 тестов) Серийный тест (2 теста) Линейный тест на сложность Суммамладших Способ Способ Сумма 9 бит бит (двоичных разаналога прототипа Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.