×
10.09.2015
216.013.7840

ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНОЙ ФУНКЦИИ

Вид РИД

Изобретение

Юридическая информация Свернуть Развернуть
Краткое описание РИД Свернуть Развернуть
Аннотация: Изобретение относится к вычислительной технике, в частности к генераторам псевдослучайных функций (ПСФ), и может быть использовано в цифровых вычислительных устройствах, а также в системах защиты информации. Техническим результатом является повышение скорости вычисления псевдослучайной функции. Устройство содержит два входа для секретного ключа и входных данных, три регистра, сумматор по модулю p, блок вычисления обратного элемента по модулю p, умножитель по модулю p, блок возведения в степень по модулю p. 1 ил., 1 табл.
Основные результаты: Генератор псевдослучайной функции, отличающийся тем, что генератор содержит первый и второй входы, которые являются входами первого и второго регистров, выходы которых соответственно подключены к первому и второму входам сумматора по модулю р, выходы которого подсоединены ко входу блока вычисления обратного элемента по модулю р, выход блока вычисления обратного элемента по модулю р подсоединен к первому входу умножителя по модулю р, выход умножителя по модулю р соединен со входом третьего регистра, первый выход которого соединен со вторым входом умножителя по модулю р, второй выход третьего регистра соединен со входом блока возведения в степень по модулю р, выход которого является выходом генератора.
Реферат Свернуть Развернуть

Изобретение относится к вычислительной технике, в частности к генераторам псевдослучайных функций (ПСФ), и может быть использовано в цифровых вычислительных устройствах, а также в системах защиты информации. В работе [1] (Naor M., Reingold О. Constructing Pseudo-Random Permutations with a Prescribed Structure // Journal of Cryptology. 2002. №15. P. 97-102) представлен алгоритм вычисления псевдослучайной функции Naor-Reingold, которая в качестве аргументов использует ключ (h, х1…xm) и входные данные в двоичном коде b=b1, b2…bmX{0,l}m

где h - первообразной элемент мультипликативной группы, порожденный простым числом р: m - разность двоичный кода.

С целью сокращения времени вычисления значений псевдослучайной функции в работе [2] (Калмыков И.А. Разработка псевдослучайных функций повышенной эффективности [Текст] / И.Л. Калмыков, О.И. Дагаева // Известия ЮФУ Технические науки. Тематический выпуск «Информационная безопасность». 2011. Вып. 12. С. 160-169) был предложен алгоритм получения ПСФ

где U=U1,U2… - входной код; X=X1,X2… - ключ; log2X=log2U=m - разрядность двоичного кода; - количество блоков; l=log2Ui=log2Xi - разрядность блока. Применение алгоритма (2) позволяет сократить время вычисления ПСФ в l раз, по сравнению с классической реализацией (1).

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

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

Пример. Пусть р=11. В качестве первообразного элемента выбираем h=2. Пусть в качестве секретного ключа используется Х=810. В качестве входного значения, поступившего в генератор ПСФ, U=1010. Представим эти значения в двоичном коде. Получаем U=1010=10102; Х=810=10002.

Разобьем эти значения на 2 блока, по 2 бит каждый. Имеем

U1=102=210; U2=l02=210; Х1=102=210; Х2=002=010.

Воспользуемся выражением (2).

Получаем

Рассмотрим работу устройства. Перед началом работы генератора в третий регистр 8 записывается единица. На первый вход 1 подается в двоичном коде первый блок секретного ключа X1=102, который записывается в первый регистр 3. На второй вход 2 поступает первый блок входного кода U1=102, который записывается в о второй регистр 4. С выходов регистров 3 и 4 значение Х1 и U1 поступают на входы сумматора 5 по модулю р=11, на входе которого появляется результат (Х1+U1)mod р=(102+102) mod 11=410.

Данное значение подается на вход блока 6 вычисления обратного элемента по модулю р=11. Работа этого блока представлена в таблице 1.

Таблица 1
Элемент а 1 2 3 4 5 6 7 8 9 10
Обратный элемент по модулю p=11, a-1 1 6 4 3 9 2 8 7 5 10

С выхода блока 6 снимается значение 3, которое поступает на первый вход умножителя 7 по модулю р=11, на второй вход которого поступает 1 с первого выхода третьего регистра 8. Умножитель 7 выполняет вычисления

3∗1mod11=3

и полученный результат записывается в регистр 8.

Затем па первый и второй входы 1 и 2 соответственно подаются вторые блоки секретного ключа Х2=002=010 и входных данных U2=102=210. Данные значения записываются в регистр 3 и регистр 4 соответственно. С входа регистров данные блоки поступают на входы сумматора 5 по модулю 11, где реализуется процедура

(X2+U2)modp=(002+101)mod11=2

Вычисленное значение подается на вход блока 6 вычисления обратного элемента по модулю р=11. Согласно таблице 1 с выхода блока 6 будет снято число 6, которое поступит на первый вход умножителя 7 по модулю р=11. На второй вход подается число 3 с первого выхода третьего регистра 8, который используется в качестве хранилища промежуточных результатов. На выходе умножителя 7 по модулю р=11 появляется результат

(6∗3)mod 11=18mod11=7

Вычисленное значение поступает в третий регистр 8. Так как вычисления закончены, то что значение со второго выхода регистра 8 подается на вход блока 8 возведения в степень по модулю р=11, который реализует процедуру (2). В результате имеем

F(2,8,10)=27mod11=7

Проведем сравнительную оценку времени вычисления ПСФ согласно алгоритму, задаваемому выражением (1), и алгоритму (2). Анализ этих выражений показывает, что основным фактором, от которого будет зависеть время характеристики генератора ПСФ, будут вычисления показателя степени. Из выражения (1) наглядно видно, чтобы реализовать эту процедуру необходимо выполнить (m-1) умножений данных размером ]log2p[.

При использовании выражения (2) число таких умножений сокращается в L раз.

где - l=log2Ui=log2Xt - разность блоков.

Таким образом, очевидно, что применение выражения (2) позволяет повысить быстродействие генератора ПСФ в l раз по сравнению с вычислением ПСФ согласно (1).

Генератор псевдослучайной функции, отличающийся тем, что генератор содержит первый и второй входы, которые являются входами первого и второго регистров, выходы которых соответственно подключены к первому и второму входам сумматора по модулю р, выходы которого подсоединены ко входу блока вычисления обратного элемента по модулю р, выход блока вычисления обратного элемента по модулю р подсоединен к первому входу умножителя по модулю р, выход умножителя по модулю р соединен со входом третьего регистра, первый выход которого соединен со вторым входом умножителя по модулю р, второй выход третьего регистра соединен со входом блока возведения в степень по модулю р, выход которого является выходом генератора.
ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНОЙ ФУНКЦИИ
Источник поступления информации: Роспатент

Showing 31-40 of 66 items.
20.04.2015
№216.013.443f

Способ смешивания компонентов и устройство для его осуществления

Изобретение относится к сельскому хозяйству и может найти применение для приготовления смеси сыпучих материалов. Также изобретение можно использовать в пищевой промышленности и строительстве. Устройство для смешивания компонентов состоит из корпуса, в котором двумя оболочками образованы...
Тип: Изобретение
Номер охранного документа: 0002548969
Дата охранного документа: 20.04.2015
10.06.2015
№216.013.5149

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

Изобретение относится к фармацевтической промышленности, а именно к способу получения препарата для регенерации тканей ротовой полости. Способ получения поликомпонентного мелатонинсодержащего препарата для регенерации тканей ротовой полости, включающий инкубирование яиц с последующим...
Тип: Изобретение
Номер охранного документа: 0002552330
Дата охранного документа: 10.06.2015
20.06.2015
№216.013.5708

Металлическая ферма

Предложенное техническое решение относится к области строительства и предназначено для применения в качестве несущих конструкций покрытий зданий и сооружений. Металлическая ферма включает верхние пояса из парных уголков, нижний пояс из одиночного уголка и пространственно расположенные раскосы...
Тип: Изобретение
Номер охранного документа: 0002553810
Дата охранного документа: 20.06.2015
20.07.2015
№216.013.64a1

Способ производства низкокалорийного пивного напитка

Изобретение относится к способу производства пивного напитка. Способ, предусматривающий очистку солода и несоложеного материала, взвешивание, дробление солода и несоложеного материала, получение пивного сусла настойным способом путем приготовления и фильтрования затора, кипячения сусла с...
Тип: Изобретение
Номер охранного документа: 0002557308
Дата охранного документа: 20.07.2015
10.08.2015
№216.013.6b99

Топка с неподвижной колосниковой решеткой

Изобретение относится к области энергетики. Топка с неподвижной колосниковой решеткой и подвижным слоем топлива с наклонным зеркалом горения для сжигания агропеллет, включающая топку водотрубного или жаротрубного котла и чугунную колосниковую решетку, при этом 1/3 колосников, расположенных в...
Тип: Изобретение
Номер охранного документа: 0002559103
Дата охранного документа: 10.08.2015
10.08.2015
№216.013.6e35

Устройство для основного деления модулярных чисел

Изобретение относится к вычислительной технике и может быть использовано в вычислительных системах, функционирующих в системе остаточных классов. Техническим результатом является повышение скорости деления чисел, сокращение оборудования и повышение функциональных возможностей устройства за счет...
Тип: Изобретение
Номер охранного документа: 0002559771
Дата охранного документа: 10.08.2015
10.08.2015
№216.013.6e36

Устройство для основного деления модулярных чисел в формате системы остаточных классов

Изобретение относится к вычислительной технике и может быть использовано в арифметико-логических устройствах вычислительных систем, функционирующих в системе остаточных классов. Техническим результатом является повышение быстродействия и упрощение устройства. Устройство содержит регистры,...
Тип: Изобретение
Номер охранного документа: 0002559772
Дата охранного документа: 10.08.2015
20.08.2015
№216.013.704c

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

Изобретение относится к способам кондиционирования воздуха чистых помещений. Способ кондиционирования воздуха чистых помещений с использованием прямоточной схемы кондиционирования характеризуется тем, что нагрев воздуха осуществляется холодильной машиной, работающей в режиме теплового насоса, в...
Тип: Изобретение
Номер охранного документа: 0002560318
Дата охранного документа: 20.08.2015
20.08.2015
№216.013.7245

Устройство для коррекции ошибок в полиномиальной системе классов

Изобретение относится к области вычислительной техники и может быть использовано для обнаружения и коррекции ошибок при передаче информации. Техническим результатом является обеспечение возможности исправлять двухкратные ошибки в комбинациях модулярного кода. Устройство для коррекции ошибок в...
Тип: Изобретение
Номер охранного документа: 0002560823
Дата охранного документа: 20.08.2015
20.08.2015
№216.013.7246

Устройство имитозащиты контролируемых объектов с повышенной структурной скрытностью сигналов-переносчиков

Изобретение относится к технике охранно-пожарной сигнализации. Технический результат заключается в уменьшении возможности перехвата и подмены псевдослучайных последовательностей за счет использования накопителей хаотических сигналов. Устройство имитозащиты контролируемых объектов с повышенной...
Тип: Изобретение
Номер охранного документа: 0002560824
Дата охранного документа: 20.08.2015
Showing 31-40 of 70 items.
20.03.2015
№216.013.33d9

Накапливающий сумматор

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах цифровой обработки сигналов и в криптографических приложениях. Техническим результатом является повышение быстродействия устройства за счет параллельного...
Тип: Изобретение
Номер охранного документа: 0002544748
Дата охранного документа: 20.03.2015
20.04.2015
№216.013.443f

Способ смешивания компонентов и устройство для его осуществления

Изобретение относится к сельскому хозяйству и может найти применение для приготовления смеси сыпучих материалов. Также изобретение можно использовать в пищевой промышленности и строительстве. Устройство для смешивания компонентов состоит из корпуса, в котором двумя оболочками образованы...
Тип: Изобретение
Номер охранного документа: 0002548969
Дата охранного документа: 20.04.2015
10.06.2015
№216.013.5149

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

Изобретение относится к фармацевтической промышленности, а именно к способу получения препарата для регенерации тканей ротовой полости. Способ получения поликомпонентного мелатонинсодержащего препарата для регенерации тканей ротовой полости, включающий инкубирование яиц с последующим...
Тип: Изобретение
Номер охранного документа: 0002552330
Дата охранного документа: 10.06.2015
20.06.2015
№216.013.5708

Металлическая ферма

Предложенное техническое решение относится к области строительства и предназначено для применения в качестве несущих конструкций покрытий зданий и сооружений. Металлическая ферма включает верхние пояса из парных уголков, нижний пояс из одиночного уголка и пространственно расположенные раскосы...
Тип: Изобретение
Номер охранного документа: 0002553810
Дата охранного документа: 20.06.2015
20.07.2015
№216.013.64a1

Способ производства низкокалорийного пивного напитка

Изобретение относится к способу производства пивного напитка. Способ, предусматривающий очистку солода и несоложеного материала, взвешивание, дробление солода и несоложеного материала, получение пивного сусла настойным способом путем приготовления и фильтрования затора, кипячения сусла с...
Тип: Изобретение
Номер охранного документа: 0002557308
Дата охранного документа: 20.07.2015
10.08.2015
№216.013.6b99

Топка с неподвижной колосниковой решеткой

Изобретение относится к области энергетики. Топка с неподвижной колосниковой решеткой и подвижным слоем топлива с наклонным зеркалом горения для сжигания агропеллет, включающая топку водотрубного или жаротрубного котла и чугунную колосниковую решетку, при этом 1/3 колосников, расположенных в...
Тип: Изобретение
Номер охранного документа: 0002559103
Дата охранного документа: 10.08.2015
10.08.2015
№216.013.6e35

Устройство для основного деления модулярных чисел

Изобретение относится к вычислительной технике и может быть использовано в вычислительных системах, функционирующих в системе остаточных классов. Техническим результатом является повышение скорости деления чисел, сокращение оборудования и повышение функциональных возможностей устройства за счет...
Тип: Изобретение
Номер охранного документа: 0002559771
Дата охранного документа: 10.08.2015
10.08.2015
№216.013.6e36

Устройство для основного деления модулярных чисел в формате системы остаточных классов

Изобретение относится к вычислительной технике и может быть использовано в арифметико-логических устройствах вычислительных систем, функционирующих в системе остаточных классов. Техническим результатом является повышение быстродействия и упрощение устройства. Устройство содержит регистры,...
Тип: Изобретение
Номер охранного документа: 0002559772
Дата охранного документа: 10.08.2015
20.08.2015
№216.013.704c

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

Изобретение относится к способам кондиционирования воздуха чистых помещений. Способ кондиционирования воздуха чистых помещений с использованием прямоточной схемы кондиционирования характеризуется тем, что нагрев воздуха осуществляется холодильной машиной, работающей в режиме теплового насоса, в...
Тип: Изобретение
Номер охранного документа: 0002560318
Дата охранного документа: 20.08.2015
20.08.2015
№216.013.7245

Устройство для коррекции ошибок в полиномиальной системе классов

Изобретение относится к области вычислительной техники и может быть использовано для обнаружения и коррекции ошибок при передаче информации. Техническим результатом является обеспечение возможности исправлять двухкратные ошибки в комбинациях модулярного кода. Устройство для коррекции ошибок в...
Тип: Изобретение
Номер охранного документа: 0002560823
Дата охранного документа: 20.08.2015
+ добавить свой РИД