Нейронная сеть для определения координат точек на эллиптической кривой

Нейронная сеть для определения координат точек на эллиптической кривой

Иллюстрации

Показать все

Реферат

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

Известно устройство для вычисления сумм попарных произведений в системе классов вычетов - СОК (патент РФ №2012041, G06F 7/72, 1994 г.), которое содержит входной регистр, блок коррекции ошибки, модульный сумматор, блок вычисления сумм парных произведений, блок памяти, матричный умножитель, счетчик тактов. Недостатком устройства является сложность аппаратной реализации и низкая скорость сложения чисел в СОК.

Целью изобретения является повышение скорости суммирования чисел в СОК и, как следствие, определения координат точек эллиптической кривой, которые используются в системе защиты информации. Поставленная цель достигается тем, что в нейронную сеть введен блок извлечения квадратного корня на просмотровых таблицах (памяти). Таким образом, нейронная сеть для определения координат точек на эллиптической кривой на фиг.1 будет состоять из конвейерной нейронной сети конечного кольца (КНСКК) 2, имеющей входную шину данных 1, являющуюся входом нейронной сети для определения координат симметричных точек на эллиптической кривой и выход которой, шина 5, является выходом нейронной сети для определения абсциссы симметричных точек на эллиптической кривой и соединен шиной 6 с умножителем 10 и шиной 7 с умножителем 11, который шиной 8 соединен с постоянным запоминающим устройством (ПЗУ) 3, при этом умножитель 10 шиной 12 и умножитель 11 шиной 13 соединен с НСКК 14, которая также соединена шиной 9 с ПЗУ 4 и выход которой шиной 15 соединен с блоком извлечения квадратного корня 16, имеющим выходные шины для определения ординат симметричных точек на эллиптической кривой 17 и 18, являющиеся также выходными шинами нейронной сети для определения координат точек на эллиптической кривой.

В эллиптической криптографии используются эллиптические кривые, которые согласно стандарту ANSI X9.62 задаются уравнением Ньютона

где y и х - координаты симметричных точек кривой Р(х, y) и -Р(х, -y) (фиг.3), a,b∈F(p) - параметры кривой и являются ключом шифрования, F(p)≠2, 3 - конечное поле.

Для достижения требуемого уровня безопасности используются ключи шифрования (а,b) размером 100-250 бит, т.е. 2¹⁰⁰-2²⁵⁰. Большая размерность обрабатываемых данных обуславливает низкую скорость определения точек и в целом скорости шифрования на современной вычислительной базе. Для уменьшения размерности обрабатываемых данных и повышения скорости определения точек предлагается применить СОК. В СОК, имея набор взаимно-простых чисел или модулей р₁, р₂, …, р_n, любое число С представляется в виде кортежа небольших вычетов

Сложение и умножение двух кортежей С=(с₁,c₂,…,с_n) и М=(m₁,m₂,…,m_n) в СОК производится по правилам

На основе (2) параметры кривой а и b и шифруемые данные х, которые являются абсциссой точки (например, символ текстового сообщения, которому поставлен в соответствие цифровой код), представляются в виде

Вычислительные модели (13), (14) для определения координат точек кривой реализует нейронная сеть для определения координат точек на кривой, представленная на фиг.2, состоящая из n одинаковых нейронных сетей 2, представленных на фиг.1, каждая из которых функционирует по установленному модулю p_i, где i=1, 2, …, n, входной шины данных 1 и выходных шин данных 3.

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

Для перевода переменной х по i-му модулю из позиционной системы счисления в СОК согласно (7) в изобретении используется КНСКК 2 (патент №2317584). Для хранения заранее вычисленных констант и согласно (5), (6) используется ПЗУ 3 и 4 соответственно.

В первом цикле синхронизации переменная х поступает по входной шине данных 1 на КНСКК 2, где за четыре цикла синхронизации вычисляется вычет согласно (2).

На пятом цикле синхронизации по шине 6 вычет подается на умножитель 10, который реализует модель Умножитель 10 реализован на просмотровых таблицах. Входы просмотровых таблиц, на которые по шине 6 подаются вычеты являются адресами хранимых заранее рассчитанных результатов возведения в третью степень вычета в конечном поле. Параллельно с этим вычет по шине 7 и константа от ПЗУ 3 по шине 8 подаются на умножитель 11, который реализует модель

На шестом цикле синхронизации результаты вычислений по шине 12, по шине 13 и константа от ПЗУ 4 по шине 9 подаются на НСКК 14, которая работает в режиме сложения модулярных чисел и реализует вычислительную модель по i-му модулю

На седьмом цикле синхронизации результат вычислений по шине 15 подается на вход блока извлечения квадратного корня 16. Этот блок реализован на просмотровых таблицах (памяти), предназначенных для хранения результатов извлечения корня в конечном поле

Входы просмотровых таблиц являются адресами хранимых результатов. На выходе блок 17 имеет две шины 18 и 19 для выдачи на выход нейронной сети двух результатов и

Пример

Необходимо разместить на эллиптической кривой Е вида

E:y² =(x³+34x+33)mod1309,

где a=37, b=33, F(q)=1309, сообщение 100010₂=34₁₀.

Тогда в обычной системе счисления

Симметричная ордината находится из выражения 1309 - 752 = 557. Имеем две точки на кривой Р(34,752) и -Р(34, 557).

Выберем систему модулей СОК р₁=7, р₂=11, p₃=17 и представим в СОК а, b, х.

Диапазон представления данных Р=р₁·р₂·р₃=1309=F(q).

Определим ортогональные базисы из выражения

для i=1, 2, …, n.

B₁=561, В₂=595, B₃=154.

Согласно (2)

а=37=(2,4,3)

b=33=(5,0,16)

x=34=(6,1,0)

Тогда для трех нейронных сетей имеем следующие модели вычисления

После этого, используя полученные значения в качестве адресных, из просмотровой таблицы для каждой нейронной сети получаем хранящиеся в памяти на основании (11) и (12) значения

и точки P((6,1,0), (3,4,4)) и -P((6,1,0), (4,7,13)).

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

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

Для проверки

Таким образом, с помощью изобретения при использовании n параллельных нейронных сетей за семь циклов синхронизации вычисляются две точки на эллиптической кривой (13) и (14).

Нейронная сеть для определения координат точек на эллиптической кривой, содержащая конвейерную нейронную сеть конечного кольца и нейронную сеть конечного кольца, отличающаяся тем, что в нее введены просмотровые таблицы в виде памяти, реализующие вычислительные модели и где х - шифруемые данные, которые являются абсциссой симметричных точек на эллиптической кривой, а и b - параметры уравнения эллиптической кривой или ключ шифрования, у - ордината симметричных точек на эллиптической кривой, p_i - модуль системы остаточных классов, i=1,2,…, n, причем упомянутая конвейерная нейронная сеть предназначена для реализации вычислительной модели входная шина данных конвейерной нейронной сети конечного кольца является входом нейронной сети для определения координат точек на эллиптической кривой, выход конвейерной нейронной сети конечного кольца является выходом конвейерной нейронной сети конечного кольца, причем выход конвейерной нейронной сети конечного кольца соединен с умножителем, реализующим вычислительную модель а также соединен с умножителем, реализующим модель и соединенным с выходом первого постоянного запоминающего устройства, хранящего при этом выходы умножителей, реализующих модели и соединены с нейронной сетью конечного кольца, соединенной с выходом второго постоянного запоминающего устройства, хранящего при этом нейронная сеть конечного кольца предназначена для реализации модели выход упомянутой нейронной сети конечного кольца соединен с упомянутыми просмотровыми таблицами, выходы которых являются выходом нейронной сети для определения координат точек на эллиптической кривой.