Генератор псевдослучайной функции

Изобретение относится к вычислительной технике, в частности к генераторам псевдослучайных функций (ПСФ), и может быть использовано в цифровых вычислительных устройствах, а также в системах защиты информации. Техническим результатом является повышение скорости вычисления псевдослучайной функции. Устройство содержит два входа для секретного ключа и входных данных, три регистра, сумматор по модулю 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

F N R ( ( h , x 1 , x 2 , , x m ) ( b 1 , , b m ) ) = h П i m = 1 x i b i mod p ( 1 )

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

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

F П С Ф ( ( h , x 1 , x 2 , , x m ) ( u 1 , , u n ) ) = h П i = 2 m 1 ( X i + U i ) mod p ( 2 )

где U=U1,U2… - входной код; X=X1,X2… - ключ; log2X=log2U=m - разрядность двоичного кода; n = m e   - количество блоков; 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).

Получаем

F П С Ф = h П i = 1 2 1 ( X i + U i ) mod p = 2 1 ( 2 + 2 ) 1 ( 2 + 0 ) mod 11 = 2 1 4 1 2 mod 11 = 2 1 8 mod 11 = 2 7 mod 11 = 7

Рассмотрим работу устройства. Перед началом работы генератора в третий регистр 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).

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



 

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

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

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

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

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

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

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

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

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

Изобретение относится к скремблеру, к способу обработки скремблирования, к устройству и способу генерирования сигнала основной полосы. .

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

Изобретение относится к вычислительной технике и может быть использовано для генерации потоков псевдослучайных чисел (ПСЧ). Техническим результатом является возможность генерации N начальных значений и отсутствие корреляций при их использовании между не менее N потоками ПСЧ.

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

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

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

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

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

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

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

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

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

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

Наверх