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

Описание патента на изобретение RU2716357C1

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

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

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

где оператор - взятие дробной части числа.

На первой шаге работы алгоритма, значения xi-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.

Похожие патенты RU2716357C1

название год авторы номер документа
ГЕНЕРАТОР СЛУЧАЙНОГО ПРОЦЕССА 1991
  • Гладунов В.Д.
RU2050585C1
Субоптимальный нелинейный фильтр 1990
  • Булычев Юрий Гурьевич
  • Погонышев Сергей Анатольевич
SU1714618A1
Генератор случайных чисел 1975
  • Коорт Антс Альфредович
SU590790A1
Генератор случайных чисел 1988
  • Мартыщенко Леонид Андреевич
  • Воловик Александр Васильевич
  • Степанов Александр Николаевич
  • Гайфутдинов Васых Ахметович
  • Голик Евгений Сергеевич
SU1531094A1
Последовательное множительное устройство 1985
  • Глазачев Александр Юрьевич
SU1307455A1
Генератор широкополосных случайных процессов 1980
  • Ярмолик Вячеслав Николаевич
  • Леусенко Александр Ефимович
SU881743A1
Вероятностный коррелометр 1978
  • Корчагин Владимир Герасимович
  • Кравцов Леонид Яковлевич
  • Садомов Юрий Борисович
  • Хохлов Лев Михайлович
SU942037A1
Устройство для умножения чисел в модулярной системе счисления 1986
  • Коляда Андрей Алексеевич
  • Ревинский Виктор Викентьевич
  • Селянинов Михаил Юрьевич
  • Чернявский Александр Федорович
SU1352483A1
Устройство для контроля качества дискретного канала связи 1990
  • Карпов Вячеслав Николаевич
SU1702533A1
УСТРОЙСТВО ОБРАЩЕНИЯ ЦИКЛИЧЕСКОГО СДВИГА И ОБРАЩЕННОГО ПЕРЕМЕЖЕНИЯ ДАННЫХ 1997
  • Фимофф Марк
  • Спаете Лоренс С. Мл.
RU2189629C2

Иллюстрации к изобретению RU 2 716 357 C1

Реферат патента 2020 года СПОСОБ И УСТРОЙСТВО ГЕНЕРАЦИИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ СЛУЧАЙНЫХ ЧИСЕЛ

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

Формула изобретения RU 2 716 357 C1

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

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

Документы, цитированные в отчете о поиске Патент 2020 года RU2716357C1

СПОСОБ ГЕНЕРАЦИИ СЛУЧАЙНЫХ ЧИСЕЛ 2003
  • Осмоловский С.А.
RU2246129C2
УСТРОЙСТВО ДЛЯ ГЕНЕРИРОВАНИЯ КОРОТКИХ ЭЛЕКТРОМАГНИТНЫХ ВОЛН 1926
  • Миллер Ф.А.
SU24008A1
Колосоуборка 1923
  • Беляков И.Д.
SU2009A1
Станок для изготовления деревянных ниточных катушек из цилиндрических, снабженных осевым отверстием, заготовок 1923
  • Григорьев П.Н.
SU2008A1
Пломбировальные щипцы 1923
  • Громов И.С.
SU2006A1

RU 2 716 357 C1

Авторы

Шакурский Максим Викторович

Даты

2020-03-11Публикация

2018-09-25Подача