Способ и устройство генерации последовательностей случайных чисел - RU2716357C1

Чертежи

Описание

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

В качестве аналога изобретения может быть рассмотрен известный способ генерации случайных чисел [1] с использованием n-разрядного регистра сдвига с обратной связью, разрядом которого выбран q-ичный символ (q=2^l, l=8, 16 бит), в цепях обратной связи осуществляют не менее трех двухпараметрических операций над q-ичными символами на основе случайных таблиц замены Т_к, каждая из которых содержит 2^l неповторяющихся значений двоичных комбинаций длиной l, начальное заполнение регистра сдвига с обратной связью и таблиц случайной замены выполняют от физического датчика случайных чисел неповторяющимися значениями случайных чисел, для чего сравнивают очередное значение случайного числа с ранее записанными значениями случайных чисел, при совпадении нового значения числа с любым из ранее записанных, новое значение отбрасывают, при несовпадении - записывают в очередной разряд регистра сдвига и очередную строку таблицы замены, для генерации очередного случайного числа выбирают пять значений, указывающих номера разрядов регистра сдвига, первая и вторая пары значений указывают номера разрядов регистра сдвига для выполнения соответственно первой и второй операций, операндами третьей операции являются результаты выполнения первых двух операций, операндами которых являются значения q-ичных символов, записанные в данном такте в разрядах регистра сдвига с указанными номерами, для выполнения всех операций находят в используемой таблице Т_к значение первого операнда и считывают из таблицы Т_к значение, которое отстоит на число строк используемой таблицы Т_к, совпадающее с двоичным значением второго операнда, результат выполнения третьей операции, являющийся очередным результатом генерации, записывают в последний выбранный разряд регистра сдвига, после чего производят сдвиг содержимого регистра сдвига на один q-ичный разряд.

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

Известен способ (прототип) алгоритмической генерации последовательности случайных чисел Блюм - Блюма - Шуба [2], описываемый выражением:

где М=pq является произведением двух больших простых p и q. Ha каждом шаге алгоритма выходные данные получаются из

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

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

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

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

На фиг. 1 изображена структурная схема устройства.

Устройство содержит два идентичных функциональных блока.

На фиг. 2 изображена структурная схема первого функционального блока.

Функциональный блок содержит блок 1 памяти коэффициентов, блоки 2, 3 и 4 умножения, блоки 5 и 7 суммирования, блок 6 деления, блок 8 исключения целой составляющей, блок 9 задержки, блок 10 коммутирующего устройства.

На фиг. 3 показан генерируемый одним из функциональных блоков сигнал.

На фиг. 4 показана гистограмма сигнала, приведенного на фиг. 3.

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

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

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

где оператор

На первой шаге работы алгоритма, значения x_i-1 являются задаваемыми начальными значениями.

На фиг. 2 приведена структурная схема устройства, реализующего первый функциональный блок. Каждый функциональный блок имеет два входа и два выхода и имеет блок 1 памяти, первый выход которого подключен к первому входу блока 10 коммутирующего устройства, второй выход блока 1 памяти подключен к первому входу блока 2 умножения, третий выход блока 1 памяти подключен к первому входу блока 3 умножения, четвертый выход блока 1 памяти подключен к первому входу блока 4 умножения, первый вход функционального блока подключен ко второму входу блока 2 умножения и ко второму входу блока 6 деления, второй вход функционального блока подключен ко второму входу блока 3 умножения и ко второму входу блока 4 умножения, выход блока 2 умножения подключен к первому входу блока 5 суммирования, выход блока 3 умножения подключен ко второму входу блока 5 суммирования, выход блока 4 умножения подключен к первому входу блока 6 деления, выход блока 5 суммирования подключен к первому входу блока 7 суммирования, выход блока 6 деления подключен ко второму входу блока 7 суммирования, выход блока 7 суммирования подключен к блоку 8 исключения целой части, выход блока 8 исключения целой части подключен ко входу блока 9 линии задержки, а также является вторым выходом устройства, выход блока 9 линии задержки подключен ко второму входу блока 10 коммутирующего устройства, выход блока 10 коммутирующего устройства является первым выходом устройства.

Устройство работает следующим образом.

Каждый из двух функциональных блоков работает идентично. На первом шаге блок 10 коммутирующего устройства передает на первый выход функционального блока начальное значение генерируемого ряда с первого выхода блока 1 памяти, которое по линии обратной связи передается на первый вход блока генерации случайной последовательности, на второй вход функционального блока передается начальное значение со следующего по порядку функционального блока. Начиная со второго шага работы устройства, блок 10 коммутации передает на первый выход функционального блока значение с блока 9 линии задержки на один отсчет. Работа функционального блока основана на выражениях (3), умножители 2, 3 и 4 формируют произведения трех слагаемых в выражениях (3), причем значения коэффициентов а, b и с берутся, соответственно, со второго, третьего и четвертого выходов блока 1 памяти. Блок 6 деления реализует деление в третьем слагаемом, блоки 5 и 7 осуществляют сложение трех слагаемых. Блок 8 исключает целую составляющую из полученного в блоке 7 значения, после чего результат передается на второй выход функционального блока и на блок 9 линии задержки, для последующего использования результата на следующем шаге.

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

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

Список источников

1. Патент на изобретение №2246129. Российская федерация, МПК G06F 7/58, G09C 1/02, H04L 9/20. Способ генерации случайных чисел / С.А. Осмоловский // (Россия).; заявл. 13.01.2003; опубл. 10.07.2004.

2. Википедия - свободная энциклопедия [Электронный ресурс]. - https://ru.wikipedia.org/ - (дата обращения: 10.04.2018).

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

Реферат

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

Формула