СПОСОБ ПОЛУЧЕНИЯ ПОСЛЕДОВАТЕЛЬНОСТИ СЛУЧАЙНЫХ ДВОИЧНЫХ ЧИСЕЛ И УСТРОЙСТВО ДЛЯ ЕГО ОСУЩЕСТВЛЕНИЯ Российский патент 2017 года по МПК G06F7/58 H03K3/84 

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

Известны средства для генерирования случайных чисел на основе диодов-генераторов шума, в частности генератор случайных чисел, содержащий последовательно соединенные источник шума, выполненный на шумовом диоде, дифференцирующую цепочку, компаратор, счетный триггер и стробируемый Д-триггер, синхронизирующий вход которого является синхронизирующим входом генератора, где вход задания уровня срабатывания компаратора подключен к синхронизирующему входу генератора (Авторское свидетельство СССР №840855, G06F 1/02, дата публикации 23.06.1981). Данное изобретение обеспечивает повышение быстродействия по сравнению с существующими на тот период времени аналогичными устройствами.

Также известен способ генерирования случайных чисел, содержащий этапы получения первого шума, имеющего характеристику 1/f, где f является частотой шумовых компонентов, с помощью первой схемы генерирования шума и получения второго шума, имеющего характеристику 1/f, с помощью второй схемы генерирования шума, подачи указанных первого и второго шумов, имеющих характеристики 1/f, полученных с помощью первой и второй схем генерирования шумов соответственно, на дифференциальную схему для получения разностного сигнала между первым шумом и вторым шумом и генерирования из разностного сигнала случайных чисел, которые не имеют периодичности, вызванной характеристиками 1/f, первого и второго шумов, разностный сигнал, полученный с помощью дифференциальной схемы, преобразуют с помощью схемы аналогово-цифрового преобразования в цифровой сигнал и полученный таким образом цифровой сигнал подают на выход в качестве случайных чисел (Патент РФ №2216036, G06F 7/58, дата публикации 10.11.2003). Изобретение направлено на обеспечение возможности генерирования случайных чисел, не имеющих какой-либо периодичности или регулярности.

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

Наиболее близкими аналогами заявленного способа и устройства являются:

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

устройство для получения последовательности случайных чисел, содержащее источник случайных событий, реализованный в виде физического генератора шума, например, шумового диода, использующее фильтрацию, аналого-цифровое преобразование для получения последовательности бит и средство формирования из указанной последовательности бит выходной последовательности случайных двоичных чисел с применением корректора фон Неймана, использующегося для постобработки случайных потоков за счет использования битов данных непересекающихся пар последовательных битов (Заявка США №20060117149, G06F 7/58, дата публикации 28.04.2016). В качестве источника случайных событий используют полупроводниковый шумовой диод.

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

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

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

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

η_j=0, если ξ_2j-1=0, a ξ_2j=1,

η_j=1, если ξ_2j-1=1, а ξ_2j=0,

где η - элемент выходной последовательности случайных двоичных чисел,

ξ - элемент последовательности младших битов чисел знакоперемен (0 и 1),

j - 1, 2, 3, …,

при этом другие сочетания элементов ξ_2j-1 и ξ_2j (ξ_2j-1=0, ξ_2j=0; ξ_2j-1=1, ξ_2j=1) при формировании выходной последовательности случайных двоичных чисел не учитывают.

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

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

При формировании выходной последовательности производят накопление ее элементов до получения последовательности заданной длины.

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

Для получения технического результата устройство для получения последовательности случайных чисел содержит источник случайных событий в виде физического генератора шума, подключенного к входу фильтра высоких частот, выход которого связан с одним из входов компаратора напряжений, выход которого подключен к входу таймера-счетчика импульсов, определяющего число знакоперемен (0 и 1) в течение заданного интервала времени и связанного с цифровым устройством обработки сигналов, последнее выполнено с возможностью выявления и записи младшего бита этого числа и формирования из последовательности указанных младших битов выходной последовательности случайных двоичных чисел, каждый элемент которой равен:

η_j=0, если ξ_2j-1=0, a ξ_2j=1,

η_j=1, если ξ_2j-1=1, а ξ_2j=0,

где η - элемент выходной последовательности случайных двоичных чисел,

ξ - элемент последовательности младших битов чисел знакоперемен (0 и 1),

j - 1, 2, 3, …,

при этом другие сочетания элементов ξ_2j-1 и ξ_2j (ξ_2j-1=0, ξ_2j=0; ξ_2j-1=1, ξ_2j=1) при формировании выходной последовательности случайных двоичных чисел не учитываются.

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

К другому входу фильтра высоких частот подключен другой источник опорного напряжения.

Выход фильтра высоких частот связан с указанным входом компаратора напряжений через усилитель.

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

На чертеже представлена схема устройства для получения последовательности случайных чисел.

Позициями обозначены:

1. Источник тока (постоянный резистор);

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

3. Преобразователь напряжения (емкостной умножитель напряжения);

4. Фильтр высокой частоты;

5. Первый источник опорного напряжения;

6. Усилитель;

7. Второй источник опорного напряжения;

8. Компаратор напряжения;

9. Таймер/счетчик импульсов;

10. Цифровое устройство обработки;

(Узлы 7-10 могут входить в состав микросхемы микроконтроллера).

Физический генератор шума 2 соединен с источником тока 1, в простейшем случае постоянным резистором, который питается от преобразователя напряжения 3, представляющем собой емкостной умножитель напряжения. Напряжение с генератора шума 2 подается на фильтр высоких частот 4, отсекающий постоянную и низкочастотную составляющую напряжения шума, и одновременно на фильтр высоких частот подается напряжение смещения от первого источника опорного напряжения 5 для формирования рабочей точки работы компаратора напряжения 8, на который подается сигнал от фильтра высоких частот 4, а на второй вывод компаратора подается постоянное напряжение от второго источника опорного напряжения 7. Выбором напряжения на втором источнике опорного напряжения 7 определяется равновероятность получения нулей и единиц в выходной последовательности с компаратора напряжения 8. Выход компаратора напряжения 8 соединен с входом таймера/счетчика 9, с выхода которого цифровой сигнал подается на цифровое устройство обработки 10. С выхода цифрового устройства обработки 10 выходная последовательность случайных чисел передается на выход устройства посредством имеющихся в микроконтроллере интерфейсов, например, SPI, I2C, USART, USB. Для упрощения конструкции узлы второго источника опорного напряжения 7, компаратор напряжения 8, таймер/счетчик 9 и цифровое устройство обработки 10 объединены в одной микросхеме микроконтроллера.

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

Работающий преобразователь напряжения 3 вырабатывает напряжение около +20 В, и через источник постоянного тока 1 (постоянный резистор), обеспечивающий ток, согласно техническим требованиям, подается на физический генератор шума 2 (диод серии NDxxx или КГ401А). Аналоговый сигнал, получаемый с физического генератора шума 1 через фильтр высоких частот, представляющих собой RC-цепь с частотой среза 50…100 кГц, отсекающий постоянную и низкочастотную составляющие напряжения шума и присоединенный к источнику опорного напряжения 5 с уровнем напряжения, равным половине напряжения питания, подается на вход аналогового компаратора напряжения 8, на второй вход которого подается напряжение со второго источника опорного напряжения 7. Выбором напряжения на втором источнике опорного напряжения 7 определяется равновероятность получения нулей и единиц в выходной последовательности с компаратора напряжения 8. Выходной сигнал компаратора напряжения 8 подается на вход таймера/счетчика 9, работающего в режиме счетчика со стробированием по времени. Таймер производит подсчет импульсов с выхода компаратора на заданном интервале тактов микроконтроллера Т, количество тактов выбирается исходя из критерия:

,

где:

Т - количество тактов микроконтроллера;

f_{микроконтроллера} - частота работы цифрового устройства обработки 10;

f_гр - граничная частота физического генератора шума 2.

В качестве случайного бита принимается младший бит (0 или 1) таймера/счетчика 9 по окончании периода стробирования. Этот бит записывается во внутренний буфер случайной последовательности цифрового устройства обработки 10.

Для повышения равновероятности нолей и единиц полученная битовая последовательность прореживается следующим образом:

η_j=0, если ξ_2j-1=0, a ξ_2j=1,

η_j=1, если ξ_2j-1=1, а ξ_2j=0,

где η - элемент выходной последовательности случайных двоичных чисел,

ξ - элемент последовательности младших битов чисел знакоперемен (0 и 1),

j - 1, 2, 3, …,

при этом другие сочетания элементов ξ_2j-1 и ξ_2j (ξ_2j-1=0, ξ_2j=0; ξ_2j-1=1, ξ_2j=1) при формировании выходной последовательности случайных двоичных чисел не учитывают.

Полученная последовательность является выходной последовательностью генератора случайных чисел.

Предусмотрен контроль выходных последовательностей.

Вырабатываемые аппаратным генератором последовательности проходят контроль (режимы контроля):

- ежесменный контроль: при включении генератора и 1 раз в 24 часа тестируется заранее заданный блок последовательности длиной 4096Байт;

- динамический контроль: тестируется каждая вырабатываемая последовательность длиной 4069 бита;

- регламентный контроль: выполняется один раз в 8760 часов работы устройства для более углубленной проверки ГСЧ.

Критерии тестирования:

- критерий на равновероятность нулей и единиц в последовательности;

- критерий на независимость соседних знаков последовательности (ноль либо единица);

- критерий серий;

- критерий χ2.

При использовании критериев на равновероятность и независимость подсчитывается число нулей m0 и число знакоперемен М (фрагментов вида 0 и 1, 1 и 0) в последовательности.

При использовании критерия серий подсчитывается длина максимальной серии Smax нулей и единиц.

Если исходная последовательность случайная и равновероятная, то значения m0, М, Smax должны удовлетворять условиям:

,

,

,

где t_α/2 - квантиль нормального распределения. Функция распределения случайной величины:

,

Из таблицы можно определить, что

В качестве рабочих параметров рассмотрим значение t_α/2=2,32, что обеспечивает значение ошибки первого рода α=0,01.

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

1. R:=(r₁, r₂, …, r₅₁₂) - полученная последовательность длиной 4096 бита;

2. проверяются условия 962<⎪⎪m0⎪⎪<1085;

3. проверяется условие 962<⎪⎪M⎪⎪<1085;

4. проверяется условие 1<Smax<17 для последовательности нулей;

5. проверяется условие 1<Smax<17 для последовательности единиц;

6. проверяется условие χ2<312,586.

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

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

Изобретение относится к области и предназначено для получения последовательности случайных чисел с заданными статистическими характеристиками. Технический результат - повышение независимости вырабатываемой последовательности случайных чисел от параметров источника шума и получение последовательности случайных чисел с заданными статистическими характеристиками. В способе для получения последовательности случайных двоичных чисел используют источник случайных событий - полупроводниковый шумовой диод. Формируют аналоговый сигнал, характеризующий наступление указанных событий, производят обработку сформированного аналогового сигнала и преобразование его в цифровую форму. Задают интервал времени, в течение которого определяют число знакоперемен (0 и 1). В полученном числе выявляют младший бит и записывают его. Из последовательности указанных младших битов формируют выходную последовательность случайных двоичных чисел. 2 н. и 9 з.п. ф-лы, 1 ил.

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

η_j=0, если ξ_2j-1=0, a ξ_2j=1,

η_j=1, если ξ_2j-1=1, а ξ_2j=0,

где η - элемент выходной последовательности случайных двоичных чисел,

ξ - элемент последовательности младших битов чисел знакоперемен (0 и 1),

j - 1, 2, 3, …,

при этом другие сочетания элементов ξ_2j-1 и ξ_2j (ξ_2j-1=0, ξ_2j=0; ξ_2j-1=1, ξ_2j=1) при формировании выходной последовательности случайных двоичных чисел не учитывают.

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

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

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

5. Способ по любому из пп. 1-4, отличающийся тем, что полученную выходную последовательность случайных двоичных чисел тестируют на равновероятность и независимость нулей и единиц путем вычисления статистики χ2 и сравнения с допустимым распределением, сравнения числа знакоперемен (0 и 1) с допустимым и сравнения максимального числа подряд идущих нулей и максимального числа подряд идущих единиц с допустимым и отбраковывают последовательность, если не выполнено хотя бы одно указанное условие.

6. Устройство для получения последовательности случайных чисел, содержащее физический генератор шума, подключенный к входу фильтра высоких частот, выход которого связан с одним из входов компаратора напряжений, выход которого подключен к входу таймера-счетчика импульсов, определяющего число знакоперемен (0 и 1) в течение заданного интервала времени и связанного с цифровым устройством обработки сигналов, выполненным с возможностью выявления и записи младшего бита этого числа и формирования из последовательности указанных младших битов выходной последовательности случайных двоичных чисел, каждый элемент которой равен:

η_j=0, если ξ_2j-1=0, а ξ_2j=1,

η_j=1, если ξ_2j-1=l, а ξ_2j=0,

где η - элемент выходной последовательности случайных двоичных чисел,

ξ - элемент последовательности младших битов чисел знакоперемен (0 и 1),

j - 1, 2, 3, …,

при этом другие сочетания элементов ξ_2j-1 и ξ_2j (ξ_2j-1=0, ξ_2j=0; ξ_2j-i=1,

ξ_2j=1) при формировании выходной последовательности случайных двоичных чисел не учитываются.

7. Устройство по п. 6, отличающееся тем, что физический генератор шума представляет собой полупроводниковый шумовой диод.

8. Устройство по п. 6, отличающееся тем, что к другому входу фильтра высоких частот подключен другой источник опорного напряжения.

9. Устройство по п. 6, отличающееся тем, что выход фильтра высоких частот связан с указанным входом компаратора напряжений через усилитель.

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

11. Устройство по любому из пп. 6-10, отличающееся тем, что цифровое устройство обработки сигналов содержит средство тестирования полученной выходной последовательности случайных двоичных чисел на равновероятность и независимость нулей и единиц путем вычисления статистики χ2 и сравнения с допустимым распределением, сравнения числа знакоперемен (0 и 1) с допустимым и сравнения максимального числа подряд идущих нулей и максимального числа подряд идущих единиц с допустимым для отбраковки последовательности, если не выполнено хотя бы одно указанное условие.