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

Авторы патента:

H04L9/18 - шифрование путем последовательной или непрерывной модификации элементов потока данных, например системы с поточным шифром

G06F7/58 - генераторы случайных или псевдослучайных чисел

G06F1/02 - генераторы дискретных функций

Владельцы патента RU 2562373:

Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Северо-Кавказский федеральный университет" (RU)

Изобретение относится к вычислительной технике, в частности к генераторам псевдослучайных функций (ПСФ), и может быть использовано в цифровых вычислительных устройствах, а также в системах защиты информации. Техническим результатом является повышение скорости вычисления псевдослучайной функции. Устройство содержит два входа для секретного ключа и входных данных, три регистра, сумматор по модулю 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, х₁…x_m) и входные данные в двоичном коде b=b₁, b₂…b_mX{0,l}^m

$F_{N R} ((h, x_{1}, x_{2}, \dots, x_{m}) (b_{1}, \dots, 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}, \dots, x_{m}) (u_{1}, \dots, u_{n})) = h^{П_{i = 2}^{m} \frac{1}{(X_{i} + U_{i})}} \mod p (2)$

где U=U₁,U₂… - входной код; X=X₁,X₂… - ключ; log₂X=log₂U=m - разрядность двоичного кода; $n = \frac{m}{e}$ - количество блоков; l=log₂U_i=log₂X_i - разрядность блока. Применение алгоритма (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. Пусть в качестве секретного ключа используется Х=8₁₀. В качестве входного значения, поступившего в генератор ПСФ, U=10₁₀. Представим эти значения в двоичном коде. Получаем U=10₁₀=1010₂; Х=8₁₀=1000₂.

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

U₁=10₂=2₁₀; U₂=l0₂=2₁₀; Х₁=10₂=2₁₀; Х₂=00₂=0₁₀.

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

Получаем

$\begin{array}{l} F_{П С Ф} = h^{П_{i = 1}^{2} \frac{1}{(X_{i} + U_{i})}} \mod p = 2^{\frac{1}{(2 + 2)} * \frac{1}{(2 + 0)}} \mod 11 = 2^{\frac{1}{4} * \frac{1}{2}} \mod 11 = 2^{\frac{1}{8}} \mod 11 \\ = 2^{7} \mod 11 = 7 \end{array}$

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

Данное значение подается на вход блока 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 соответственно подаются вторые блоки секретного ключа Х₂=00₂=0₁₀ и входных данных U₂=10₂=2₁₀. Данные значения записываются в регистр 3 и регистр 4 соответственно. С входа регистров данные блоки поступают на входы сумматора 5 по модулю 11, где реализуется процедура

(X₂+U₂)modp=(00₂+10₁)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)=2⁷mod11=7

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

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

где - l=log₂U_i=log₂X_t - разность блоков.

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

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

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

Скремблирующее и дескремблирующее устройство для параллельной кадровой синхронизации // 2505932

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

Аппаратный интерфейс для обеспечения возможности прямого доступа и совместного использования оценки безопасности // 2502200

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

Скремблер, способ обработки скремблирования и программа // 2486684

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

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

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

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

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

Способ защиты информации // 2423800

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

Способ формирования общего секретного ключа двух удаленных абонентов телекоммуникационной системы // 2412548

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

Скремблер, способ обработки скремблирования и носитель данных // 2404518

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

Структура поточного шифра с циклическим перемещением буферов // 2390949

Генератор псевдослучайных последовательностей // 2557764

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

Способ генерации параллельных потоков псевдослучайных чисел и устройства для его осуществления (2 варианта) // 2556430

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

Генератор случайных чисел // 2554537

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

Генератор нелинейных псевдослучайных последовательностей // 2549524

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

Генератор коррелированных случайных сигналов // 2546580

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

Способ формирования коррелированных случайных сигналов // 2546579

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

Генератор случайной последовательности // 2542903

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

Способ и устройство детектирования // 2506631

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

Способ нелинейного трехмерного многораундового преобразования данных dozen // 2503994

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

Генератор случайных чисел на основе трехзначной логики // 2495479

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

Генератор коррелированных случайных сигналов // 2546580