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

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

 

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

В настоящее время известны три класса датчиков случайных чисел:

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

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

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

При использовании в средствах защиты информации ко всем указанным типам датчиков случайных чисел предъявляется требование равновероятности знаков вырабатываемой последовательности и их статистическая независимость [1, 2]. При этом все указанные классы датчиков случайных чисел обладают преимуществами и недостатками.

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

К аппаратным датчикам, например, относятся следующие способы.

Известны способы, описанные в патентах RU 2103725 G06F 7/58, 1998.01.27, RU 2103726 G06F 7/58, 1998.01.27, RU 93031409, G06F 7/58, 1996.08.27, позволяющие генерировать равномерно распределенные случайные числа и состоящие из генератора исходной последовательности и дополнительного устройства, осуществляющего преобразование выходной последовательности генератора в выходную последовательность датчика случайных чисел. Наличие дополнительного устройства позволяет улучшить статистические характеристики выходной последовательности датчика случайных чисел. Указанные способы имеют недостаток - для их реализации необходим генератор исходной равномерно распределенной последовательности, т.е. известные способы позволяют только улучшить качество уже равномерно распределенной последовательности. Также для их реализации требуется дополнительное устройство, что влечет дополнительные аппаратные затраты.

Известны способы, описанные в патентах RU 2150140, G06F 3/00, 2000.05.27, RU 2190872, G06F 7/58, G02F 3/00, 2002.10.10, позволяющие генерировать случайные числа со степенью «случайности» и законом распределения, аппроксимируемым равномерным. Для осуществления указанных способов используется специализированная оптическая схема, содержащая такие элементы, как оптический генератор, содержащий источник излучения, оптические ответвители, электрооптический модулятор, оптические волноводы, оптические фазовые модуляторы, оптический усилитель. Недостатком указанных способов является использование специализированной оптической схемы. При использовании приведенных методов в вычислительной технике дополнительно потребуется аппаратное устройство съема параметров хаотического оптического процесса.

Известны способы, описанные в патентах RU 2003132421, G06F 7/58, 20.08.2005, US 6571263, G06J 001/00, G06F 007/58, G06G 007/00, 27.05.2003, US 6763364, G06F 007/58, 13.07.2004, позволяющие генерировать случайные числа из физических источников шума. Известные способы основаны на преобразовании электрических параметров случайного сигнала в соответствующие цифровые значения в специализированной схеме. При этом используется устройство, формирующее случайный электрический сигнал (например, шумовой диод), и схема съема и преобразования случайного сигнала в случайные цифровые значения. Основным недостатком этих способов является необходимость использования специализированного устройства генерации случайных сигналов.

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

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

Решение этой задачи возможно путем использования аппаратного датчика случайных чисел, что сопряжено с уже перечисленными выше проблемами, или использованием источника случайности, естественным образом присутствующего в проектируемой системе. Так, телекоммуникационные средства имеют в своем составе различные источники случайных величин. Например, время выхода абонентов сети (радио или вычислительной) на связь, работа оператора с клавиатурой устройства управления, время приема пакетов из сети связи, шум микрофонов акустических приборов вычислительных средств и т.п. являются случайными величинами, что отмечено в [3], [4], [5].

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

Известны различные способы приведения исходной последовательности случайных знаков к равномерному виду. В источниках [3], [4], [5] предлагаются несколько способов приведения закона распределения к равномерному виду:

1. Сложение нескольких идущих подряд битов источника.

2. Использование последовательностей несовпадающих пар.

3. Использование быстрого преобразования Фурье.

4. Использование сжатия выходной последовательности.

Все перечисленные способы обладают определенными недостатками и требуют некоторых допущений для своего применения. Первый и второй способы при наличии корреляции между соседними битами увеличивают смещение выходной последовательности [3]. Осуществление быстрого преобразования Фурье на универсальных вычислительных средствах требует значительных вычислительных затрат [6], и применение данного метода требует допущения о соответствии источника белому шуму [3]. Второй метод значительно понижет объем выходной последовательности датчика. Использование сжатия сопряжено со значительным расходом вычислительного ресурса [6].

Известен способ, описанный в патенте US 6298360, G06F 007/58, 02.10.2001, использующий для генерации случайных чисел источники неопределенности, естественным образом присутствующие в вычислительной технике и системах, построенных на ее основе. В известном способе в качестве случайных чисел используется комбинация значений времени переповтора пакетов в вычислительной сети, после коллизии, значения контрольных сумм сетевых пакетов и некоторого начального случайного значения. Недостатком известного способа являются: применимость только в устройствах, подключенных к вычислительным сетям, так как источником случайных значений является неопределенность передачи сетевых пакетов, и способ не гарантирует равномерный закон распределения выходных случайных чисел, равномерное распределение случайных чисел должно обеспечиваться некоторыми дополнительными преобразованиями.

Наиболее близким по технической сущности к заявленному способу является способ, описанный в патенте US 6369727, Н03М 001/20, 09.04.2002, позволяющий генерировать равномерно распределенные случайные числа с использованием устройства аналого-цифрового преобразования. Способ прототип использует аналого-цифровое преобразование сигнала от источника шума, с дальнейшим понижением разрядности выходных случайных значений, полученных от аналого-цифрового преобразователя. При этом понижение разрядности осуществляется с использованием съема значений нескольких младших разрядов и отбрасывания значений оставшихся старших разрядов. Для обоснования равномерной распределенности получившихся значений в способе-прототипе вводится ряд ограничений на источник шума. В частности, требуется, чтобы источник шума имел нормальное распределения и схема усиления поддерживала значение сигнала на входе аналого-цифрового преобразователя на уровне, обеспечивающем перекрытие аналого-цифровым преобразователем диапазона около восьми среднеквадратических отклонений измеряемого случайного сигнала.

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

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

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

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

Изобретение иллюстрируется следующими чертежами:

фиг.1 - процесс измерения случайной величины;

фиг.2 - разбиение носителя Р_ζ(t) на равные интервалы;

фиг.3 - устройство, реализующее заявленный способ.

Заявленный способ основывается на следующих свойствах случайных величин.

Пусть ζ - наблюдаемая случайная величина, имеющая плотность распределения P_ζ(t). Процесс измерения ζ условно представлен на фиг.1 [7].

С математической точки зрения процесс измерения величины ζ с n-значными (верными) битами означает, что ошибка измерения не превосходит половины цены последней сохраненной цифры [7], [8].

- имеет n-значных (верных) бит.

есть двоичный вектор ζ_n...ζ_Sζ_S-1...ζ₁ζ₀. Рассмотрим S младших бит ζ_S-1...ζ₁ζ₀. Разобьем интервал измерения наблюдаемой случайной величины ζ на подынтервалы длины h (см. фиг.2).

Введем в рассмотрение случайную величину ξ, определяемую условием ξ≡ζ (mod h).

Величина ξ характеризуется следующим:

- случайная величина ξ изменяется в пределах 0≤ξ<h;

- всякое значение случайной величины ξ связано с некоторым значением случайной величины ζ равенством ζ=k·h+ξ, где k - некоторое целое число.

Согласно этому определению функция плотности вероятности P_ξ(t) случайной величины ξ имеет вид:

Пусть - характеристическая функция случайной величины ζ. Согласно формуле суммирования Пуассона [9] имеет место равенство:

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

Разложим сумму в правой части равенства (3) на две составляющие:

Пусть h выбираем так, что π/h>ν₀(ζ), где ν₀(ζ) - частота, за пределами которой характеристическая функция имеет пренебрежимо малое абсолютное значение (ν₀(ζ) - частота Найквиста). Последнее означает: величина π/р не менее частоты Найквиста сигнала P_ζ(t).

В этих предположениях формула (4) принимает вид:

Следовательно, P_ξ(t)=1/h при 0≤t<h, то есть ξ - равномерно распределенная величина, при условии, что и характеристическая функция случайной величины ζ быстро стремится к нулю при ω, стремящемся к бесконечности.

На основании приведенных выше рассуждений сформулируем практические требования к приведению плотности вероятности P_ξ(t) величины ξ к равномерному виду:

1. Спектр функции Р_ξ(t) должен быть конечным, т.е. при -ν₀(P_ζ)<ω<+ν₀(P_ζ), и стремиться к нулю вне этого интервала, где ν₀(P_ζ) - частота Найквиста.

2. Ряд, образующий функцию P_ξ(t), сходится абсолютно и равномерно.

На основании приведенных выше рассуждений делаются следующие выводы.

Для формирования равномерно распределенной случайной величины ξ по результатам измерения наблюдаемой случайной величины ζ форма ее функции плотности распределения несущественна, существенную роль играет информация о полосе частот, в которой сосредоточена характеристическая функция функции P_ζ(t). И если наблюдаемая случайная величина ζ имеет частоту Найквиста v, то базовые ограничения на выбор шага дискретизации имеют следующий вид:

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

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

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

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

Техническая возможность реализации заявленного способа иллюстрируется устройством, реализующим заявленный способ (Фиг.3), которое состоит из блока 1 источника шума (ИШ), блока 2 поддержания параметров источника шума (БПП), блока 3 аналого-цифрового преобразования (АЦП), блока 4 измерения характеристической функции (ИХФ) и блока 5 преобразования выходных значений к равномерному виду (ПРР).

Устройство, реализующее заявленный способ, работает следующим образом.

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

Как было показано выше, устройство, реализующее заявленный способ, содержит (Фиг.3) блок 1 источника шума, выход которого предназначен для выдачи аналогового случайного процесса и связан с входом блока 2 поддержания параметров источника шума, выход которого предназначен для выдачи «усиленного» сигнала аналогового случайного процесса и соединен с входами блока 3 аналого-цифрового преобразования и блока 4 измерения характеристической функции, выход блока 3 предназначен для выдачи цифровых значений результата измерения случайного процесса и соединен с первым входом блока 5 преобразования выходных значений к равномерному виду, выход блока 4 предназначен для выдачи значения числа разрядов, съем которых дает равномерно распределенные случайные числа и соединен со вторым входом блока 5, выход блока 5 предназначен для выдачи равномерно распределенных случайных чисел и соединен с выходом устройства, реализующего заявленный способ.

В устройстве, реализующем заявленный способ, в качестве блока 1 источника шума может использоваться произвольный источник шума, например, это может быть источник шума, используемый в изобретении-прототипе. В качестве блока 1 поддержания параметров источника шума должно использоваться устройство, обеспечивающее поддержание сигнала аналогового случайного процесса, поступающего на вход блока 3 аналого-цифрового преобразования в рабочем интервале блока 3. В качестве блока 3 может использоваться устройство аналого-цифрового преобразования. В качестве блока 4 измерения характеристической функции должно использоваться устройство, осуществляющее измерение значения ширины носителя характеристической функции случайного процесса, поступающего с входа блока 2, и с использованием этого значения вычисляющее по формуле (8) число младших разрядов, дающее равномерное распределение. Блок 4 может быть реализован, например, с использованием метода, изложенного в [10]. Блок 5 преобразования выходных значений к равномерному виду может быть реализован на элементах цифровой логики, осуществляющих выдачу младших разрядов значения, поступившего на первый вход в зависимости от значения, поступившего на второй вход.

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

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

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

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

1. Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. / Под. ред. В.Ф.Шаньгина. - 2-е изд., перераб. доп. - М.: Радио и связь, 2001. - 376 с.: ил.

2. Домашев А.В., Грунтович М.М., Попов В.О., Правиков Д.И., Прокофьев И.В., Щербаков А.Ю. Программирование алгоритмов защиты информации. Учебное пособие. Издание второе, исправленное и дополненное. - М.: Издатель Молгачева С.В., Издательство «Нолидж», 2002. - 552 с.

3. Б.Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. - М.: Издательство ТРИУМФ, 2002. - 816 с.: ил.

4. J. von Neumann. Various techniques used in connection with randomdigits (notes by G.E.Forsythe). Applied Math. Series, vol.12, p.36-38, 1951, NBS, Washington, D.C., reprinted in "CollectedWorks", vol.5, p.768-770, Pergamon, N-Y, 1963.

5. D.Eastlake, S.Crocker, J.Schiller. Randomness Recommendations for Security, Network Working Group, Request for Comments: 1750, December 1994.

6. А.Б.Сергиенко. Цифровая обработка сигналов. - СПб.: Питер, 2003. - 608 с.: ил.

7. Розенберг В.Я. Введение в теорию точности измерительных систем. М.: Советское радио, 1975.

8. Новицкий П.Ф., Зограф И.Д. Оценка погрешностей средств измерения. Л.: Энергоатомиздат, 1985.

9. Владимиров B.C. Уравнения математической физики. 5-е издание. М.: Наука, 1985, 512 стр.

10. Патент RU 2261451, G01R 25/00, 27.09.2005. Анализатор характеристической функции сигнала. / Вешкурцев Ю.М. и др.

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

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