СПОСОБ ГЕНЕРАЦИИ И ПРОВЕРКИ ПОДЛИННОСТИ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ, ЗАВЕРЯЮЩЕЙ ЭЛЕКТРОННЫЙ ДОКУМЕНТ Российский патент 2010 года по МПК H03M5/04 

Изобретение относится к области электросвязи и вычислительной техники, а конкретнее к области криптографических способов аутентификации электронных сообщений, передаваемых по телекоммуникационным сетям и сетям ЭВМ, и может быть использовано в системах передачи электронных сообщений (документов), заверенных электронной цифровой подписью (ЭЦП), представленной в виде битовой строки (БС) или нескольких БС. Здесь и далее под БС понимается электромагнитный сигнал в двоичной цифровой форме, параметрами которого являются: число битов и порядок следования их единичных и нулевых значений.

Известен способ генерации и проверки ЭЦП, предложенный в патенте США №4405829 от 20.09.1983 и детально описанный также и в книгах [1. М.А.Иванов. Криптография. М., КУДИЦ-ОБРАЗ, 2001; 2. А.Г.Ростовцев, Е.Б.Маховенко. Введение в криптографию с открытым ключом. С-Петербург, Мир и семья, 2001. - с.43]. Известный способ заключается в следующей последовательности действий:

формируют секретный ключ в виде трех простых многоразрядных двоичных чисел (МДЧ) p, q и d, представленных тремя БС;

формируют открытый ключ (n, е) в виде пары МДЧ n и е, где n - число, представляющее собой произведение двух простых МДЧ p и q, и е - МДЧ, удовлетворяющее условию ed=1 mod (р-1)(q-1),

принимают электронный документ (ЭД), представленный БС Н,

в зависимости от значения Н, под которым понимается значение МДЧ, представленное БС H, и значения секретного ключа формируют ЭЦП в виде МДЧ Q=s=H^d mod n;

формируют первое проверочное МДЧ А=Н;

формируют второе проверочное МДЧ В, для чего МДЧ s возводят в целочисленную степень е по модулю n: В=s^e mod n;

сравнивают сформированные проверочные МДЧ А и В;

при совпадении параметров сравниваемых МДЧ А и В делают вывод о подлинности ЭЦП.

Недостатком известного способа является относительно большой размер подписи и необходимость увеличения размера подписи при разработке новых более эффективных методов разложения числа n на множители или при росте производительности современных вычислительных устройств. Это объясняется тем, что значение элемента подписи s вычисляется путем выполнения арифметических операций по модулю n, а стойкость ЭЦП определяется сложностью разложения модуля n на множители р и q.

Известен также способ генерации и проверки подлинности ЭЦП Эль-Гамаля, описанный в книге [Молдовян А.А., Молдовян Н.А., Советов Б.Я. Криптография. - СПб., Лань, 2000. - с.156-159], который включает следующие действия:

формируют простое МДЧ р и двоичное число g, являющееся первообразным корнем по модулю р, генерируют секретный ключ в виде МДЧ k, в зависимости от секретного ключа формируют открытый ключ в виде МДЧ ψ=g^k mod p, принимают ЭД, представленный в виде МДЧ Н, в зависимости от Н и секретного ключа формируют ЭЦП Q в виде двух МДЧ s и r, то есть Q=(s, r);

осуществляют процедуру проверки подлинности ЭЦП, включающую вычисление двух контрольных параметров с использованием исходных МДЧ р, g, ψ, H, r и s путем возведения МДЧ g, r и ψ в дискретную степень по модулю р и сравнение вычисленных контрольных параметров;

при совпадении значений контрольных параметров делают вывод о подлинности ЭЦП.

Недостатком данного способа также является относительно большой размер ЭЦП. Это объясняется тем, что значения элементов подписи s и r вычисляют путем выполнения арифметических операций по модулю р-1 и по модулю p соответственно.

Известен также способ генерации и проверки ЭЦП, предложенный в патенте США №4995089 от 19.02.1991. Известный способ заключается в следующей последовательности действий:

формируют простое МДЧ p, такое что р=Nq+1, где q - простое МДЧ;

формируют простое МДЧ a, такое что a≠1 и a^q mod p=1;

методом генерации случайной равновероятной последовательности формируют секретный ключ в виде МДЧ k;

формируют открытый ключ в виде МДЧ ψ по формуле ψ=a^k mod p;

принимают ЭД, представленный МДЧ М;

формируют ЭЦП в виде пары МДЧ (е, s), для чего генерируют случайное МДЧ t, формируют МДЧ R по формуле R= a^t mod р, формируют МДЧ е=ƒ(M║R), где знак ║ обозначает операцию присоединения двух МДЧ и f - некоторая специфицированная хэш-функция, значение которой имеет фиксированную длину (обычно 160 или 256 бит), независимую от размера аргумента, т.е. от размера МДЧ M║R, а затем формируют МДЧ s по формуле s=(t+ek) mod q;

формируют первое проверочное МДЧ А, для чего генерируют МДЧ R′ по формуле R′=a^sy^-e mod р и формируют МДЧ е′=ƒ(M║R′);

формируют второе проверочное МДЧ В путем копирования МДЧ е: В=е;

сравнивают сформированные проверочные МДЧ А и В;

при совпадении параметров сравниваемых МДЧ А и В делают вывод о подлинности ЭЦП.

Недостатком способа по патенту США является относительно высокая вычислительная сложность процедуры генерации и проверки ЭЦП, что связано с тем, что для обеспечения минимально требуемого уровня стойкости требуется использовать простой модуль p разрядностью не менее 1024 бит.

Наиболее близким по своей технической сущности к заявленному является известный способ генерации и проверки подлинности ЭЦП, предлагаемый российским стандартом ГОСТ Р 34.10-2001 и описанный, например, в книге [Б.Я.Рябко, А.Н.Фионов. Криптографические методы защиты информации. М., Горячая линия - Телеком, 2005. - 229 с.(см. с.110-111)], согласно которому ЭЦП формируется в виде пары МДЧ r и s, для чего генерируют эллиптическую кривую (ЭК) в виде совокупности точек, каждая из которых определяется парой элементов простого конечного поля GF(p), где р - простое число, называемое характеристикой поля. Элементы поля GF(p) представляют собой МДЧ, принадлежащие множеству {0,1,2,...,р-1}. Пара элементов поля GF(p), задающих точку ЭК, представляет собой две координаты точки ЭК, заданные в декартовой системе координат. Первая и вторая координата точки ЭК называется соответственно абсциссой (х) и ординатой (у) данной точки ЭК. Затем осуществляют операции генерации точек ЭК, сложения точек ЭК и умножения точки ЭК на число, а также арифметические операции над МДЧ, после чего в результате выполненных операций формируются МДЧ r и s. Указанные операции над точками выполняются как операции над МДЧ, являющимися координатами точек, по известным формулам [Б.Я.Рябко, А.Н.Фионов. Криптографические методы защиты информации. М., Горячая линия - Телеком, 2005. - 229 с.(см. с.110-111)]. Операция сложения двух точек А и В с координатами (x_A,y_A) и (x_B,y_B), соответственно, выполняется по формулам:

x_C=k²-x_A-x_B mod p и y_C=k(x_A-x_C)-y_A mod p,

где если точки А и В не равны, и если точки А и В равны. При вычислении значения k выполняется операция деления МДЧ по модулю простого МДЧ, что ограничивает производительность генерации и проверки подлинности ЭЦП по стандарту ГОСТ Р 34.10-2001. Операция умножения точки А на натуральное число n определяется как многократное сложение токи А: nA=А+А+…+А (n раз).

Результатом умножения любой точки ЭК на нуль определяется точка, называемая бесконечно удаленной точкой и обозначаемой буквой О. Две точки А=(х, у) и -А=(х, -у) называются противоположными. Умножение на целое отрицательное число -n определяется следующим образом: (-n)А=n(-А). По

определению принимают, что сумма двух противоположных точек равна бесконечно удаленной точке О.

В прототипе, т.е. в способе генерации и проверки подлинности ЭЦП по стандарту ГОСТ Р 34.10-2001 генерируют ЭК, описываемую уравнением у²=х³+ax+b mod p, причем генерация ЭК состоит в генерации чисел a, b и р, являющихся параметрами ЭК и однозначно задающих множество точек ЭК, абсцисса и ордината каждой из которых удовлетворяет указанному уравнению. Под процедурой генерации ЭК понимают процедуру генерации коэффициентов, входящих в уравнение, описывающее ЭК как совокупность точек, координаты которых удовлетворяют уравнению ЭК. Ближайший аналог (прототип) заключается в выполнении следующей последовательности действий:

генерируют эллиптическую кривую (ЭК) над простым конечным полем GF(p), которая представляет собой совокупность пар МДЧ, называемых точками ЭК и обладающих определенными свойствами;

методом генерации случайной равновероятной последовательности формируют секретный ключ в виде МДЧ k;

формируют открытый ключ Р в виде двух МДЧ, являющихся координатами точки ЭК Р, для чего генерируют точку G, имеющую значение порядка, равное q (порядком точки ЭК называется наименьшее положительное целое число q, такое что результатом умножения данной точки на число q является так называемая бесконечно удаленная точка О; результатом умножения любой точки ЭК на нуль по определению является точка О [Б.Я.Рябко, А.Н.Фионов. Криптографические методы защиты информации. М., Горячая линия - Телеком, 2005. - 229 с.(см. с.97-130)]; и генерируют открытый ключ путем умножения точки G на МДЧ k, т.е. формируют открытый ключ по формуле Р=kG;

принимают ЭД, представленный МДЧ Н;

генерируют случайное МДЧ 0<t<q; по которому формируют точку R по формуле R=tG;

формируют ЭЦП Q в виде пары МДЧ (r, s), для чего генерируют МДЧ r по формуле r=x_R mod q, где x_R - абсцисса точки R, а затем генерируют МДЧ s по формуле s=(tH+rk) mod q;

формируют первую проверочную БС А, для чего генерируют МДЧ ν по формуле ν=sH^-1 mod q и МДЧ w по формуле w=(q-rH^-1) mod q, затем генерируют точку R′ по формуле R′=νG+wP, после чего БС А получают в виде МДЧ А, вычисляемого по формуле А=x_R'mod q, где x_R' - абсцисса точки R′;

формируют вторую проверочную БС в виде МДЧ В, генерируемого путем копирования МДЧ r: В=r;

сравнивают сформированные проверочные БС А и В;

при совпадении параметров сравниваемых БС А и В делают вывод о подлинности ЭЦП.

Недостатком ближайшего аналога является относительно высокая сложность параллельной реализации процедур генерации и проверки ЭЦП, что связано с тем, что выполнение операций над точками ЭК, заданной над простым конечным полем GF(p), включает операцию умножения в поле GF(p) которая в свою очередь включает операцию арифметического умножения двух |p|-разрядных двоичных чисел и операцию деления 2|р|-разрядного двоичного на МДЧ p.

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

Поставленная цель достигается тем, что в известном способе генерации и проверки подлинности электронной цифровой подписи, заверяющей электронный документ, заключающийся в том, что генерируют ЭК над конечным полем в виде совокупности точек, каждая из которых определяется парой элементов конечного поля, являющихся соответственно абсциссой и ординатой данной точки эллиптической кривой, формируют секретный ключ в виде многоразрядного двоичного числа k, по секретному ключу формируют открытый ключ в виде точки Р эллиптической кривой, принимают электронный документ, представленный битовой строкой Н, в зависимости от принятого электронного документа и от значения секретного ключа формируют электронную цифровую подпись Q, формируют первое А и второе В проверочные битовые строки, сравнивают их и при совпадении их параметров делают вывод о подлинности электронной цифровой подписи, новым в заявленном изобретении является то, что генерируют ЭК над конечным полем, являющимся векторным конечным полем.

Существование векторных конечных полей впервые показано в работе [П.А.Молдовяну, Е.С.Дернова, Д.Н.Молдовян. Синтез конечных расширенных полей для криптографических приложений // Вопросы защиты информации. 2008. №3(82). С.2-7]. В этой же работе описаны способы формирования векторных конечных полей. Операция умножения в векторном конечном поле является эффективной для параллельной реализации, благодаря чему процедуры генерации и проверки подлинности ЭЦП могут быть эффективно распараллелены, что существенно повышает производительность процедур генерации и проверки подлинности ЭЦП, заверяющей ЭД. Кроме того, сложность операции умножения в векторном конечном поле в 2 и более раза ниже сложности умножения в простом конечном поле или конечном поле многочленов, что обеспечивает дополнительное повышение производительности алгоритмов ЭЦП при задании ЭК над векторным конечным полем, которое представляет собой новую форму реализации конечных полей.

Новым является также и то, что генерируют ЭК над конечным полем, являющимся векторным конечным полем, заданным над простым конечным полем GF(p), где р - характеристика поля, причем р>3.

Использование ЭК над конечным полем, являющимся векторным конечным полем, заданным над простым конечным полем GF(p), где р - характеристика поля, при простом МДЧ р>3 позволяет эффективно реализовать заявленный способ в программах для ЭВМ.

Новым является также и то, что генерируют ЭК над конечным полем, являющимся векторным конечным полем, заданным над конечным полем многочленов GF(p^s), где s - степень расширения поля и р - характеристика поля, причем р=3.

Новым является также и то, что генерируют ЭК над конечным полем, являющимся векторным конечным полем, заданным над конечным полем многочленов GF(p^s), где s - степень расширения поля и р - характеристика поля, причем р=2.

Использование ЭК, заданных над полями многочленов характеристики р=2 и характеристики р=3, обеспечивает дополнительное повышение производительности процедур генерации и проверки подлинности ЭЦП при аппаратной реализации заявленного способа.

Новым является также и то, что генерируют ЭК над конечным полем, являющимся векторным конечным полем, заданным над конечным полем многочленов GF(p^s), где s - степень расширения поля и р - характеристика поля, причем р>3.

Использование ЭК, заданных над полями многочленов характеристики р>3, обеспечивает дополнительное повышение производительности процедур генерации и проверки подлинности ЭЦП при микропрограммной реализации заявленного способа, т.е. при аппаратной реализации с использованием микроконтроллеров - специализированных микропроцессоров.

Возможность эффективного распараллеливания операции умножения в векторных конечных полях связана с тем, что элементами векторного конечного поля являются m-мерные вектора, координаты которых являются элементами конечного простого поля или конечного поля многочленов при задании векторного конечного поля над простым конечным полем GF(p) или конечным полем многочленов GF(p^s) соответственно. Причем операция умножения m-мерных векторов определяется таким образом, что координаты m-мерного вектора, являющегося результатом выполнения операции умножения m-мерных векторов, являющихся операндами, вычисляются по координатам векторов-операндов независимо друг от друга, благодаря чему имеется возможность распараллелить операцию умножения векторов БС на m независимых процессов и выполнять их параллельно. Благодаря последнему уменьшается время выполнения операции сложения точек ЭК, что дает существенное повышение скорости процедур генерации и проверки подлинности ЭЦП.

Известно, что ЭК могут быть заданы над любым полем, в том числе и над любым конечным полем (см., например, книги [Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы. - М.: КомКнига/URSS, 2006. - 324 с.] и [Болотов А.А., Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. - М.: КомКнига/URSS, 2006. - 274 с.]). Изобретательский замысел заявленного нового технического решения состоит в применении векторных конечных полей, в которых операция умножения является эффективной для параллельной реализации, для генерации на их основе ЭК, используемых в способах генерации и проверки подлинности ЭЦП, заверяющей ЭД. Рассмотрим варианты задания векторных конечных полей. Вектор - это набор из двух или более БС, называемых координатами вектора. Вектор записывается различными способами, требование к которым состоит в том, чтобы они идентифицировали позиции координат вектора. Например, вектор можно записать в виде (a₁, a₂, …, a_m), где m≥2 - это размерность вектора, равная числу координат в векторе. В качестве разделителя может быть использован знак операции сложения векторов, определенной как сложение одноименных координат двух векторов, являющихся слагаемыми. При использовании такого разделителя координаты вектора идентифицируются указанием формального базисного вектора (устанавливаемого после соответствующей координаты) в виде буквы латинского алфавита. Формальными базисные вектора называются потому, что им не приписывается никакого физического смысла. Они служат только для того, чтобы идентифицировать координаты вектора, независимо от последовательности их записи. Так, например, вектора Z₁=523425e+3676785i+53453453j и Z₂=3676785i+523425e+53453453j, где е, i, j - формальные базисные вектора, в которых координатами являются МДЧ, рассматриваются как равные, т.е. Z₁=Z₂. Отдельные слагаемые в такой записи векторов называются компонентами вектора и представляют собой вектора с одной ненулевой координатой. Размерность вектора - это количество, входящих в вектор координат. В данной заявке рассматриваются конечные поля векторов, т.е. алгебраические поля, элементами которых являются вектора вида Z=ae+bi+…+tw, где e, i, …, w - формальные базисные вектора и a, b, …, t - элементы конечного поля, над которым определены вектора, а операции сложения и умножения векторов определены через операции умножения и сложения координат векторов, являющихся операндами. При этом операции умножения и сложения координат представляют собой операции в конечном поле, над которым заданы вектора. Построение векторного конечного поля является расширением конечного поля, над которым заданы вектора.

Сложение векторов выполняется по правилу сложения одноименных координат как элементов поля, над которым заданы вектора, т.е. по формуле: (aе+bi+…+tw)+(хе+yi+…+zw)=(a+x)e+(b+y)i+…+(t+z)w или равносильной ей формуле (a,b,…,t)+(х,у,…,z)=(a+x,b+y,…,t+z).

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

где µ - элемент конечного поля, над которым задано множество векторов.

Такие таблицы будем называть таблицами умножения базисных векторов. Например, пусть Z₁=a₁ е+b₁ i+c₁ j и Z₂=a₂ е+b₂ i+c₂ j, тогда операция умножения векторов Z₁ и Z₂ (обозначим ее знаком «о») выполняется следующим образом:

Элементами векторных конечных полей, заданных над простым полем GF(p), являются вектора, координатами которых являются элементы конечного поля GF(p), задаваемого в виде поля чисел, являющихся остатками от деления всех целых чисел на некоторое простое число р, называемое характеристикой поля. Число элементов конечного поля называется порядком поля. Порядок простого поля GF(p) равен р. Значение р может быть только простым, т.е. не существуют поля со значением характеристики отличным от простого. В другом практически важном случае задания векторных конечных полей вектора задаются над конечными полями многочленов. Такие поля называются расширенными конечными полями и обозначаются следующим образом GF(p^s), где s - натуральное число, называемое степенью расширения простого поля характеристики р. В расширенных полях МДЧ р также является простым МДЧ. Понятие расширенного конечного поля хорошо известно в научно-технической литературе [см., например, А.И.Кострикин. Введение в алгебру. Основы алгебры. М.: Физматлит.1994. - 320 с.]. В технике расширенные конечные поля широко применяются в виде конечных полей многочленов. Многочлен - это последовательность коэффициентов (например, МДЧ, являющихся элементами поля GF(p)) при различных степенях формальной переменной z. Над многочленами определены операции сложения многочленов и умножения многочленов, которые сводятся к выполнению действий с коэффициентами многочленов, являющихся операндами. Многочлены и правила действия над ними подробно рассмотрены в книгах [А.И.Кострикин. Введение в алгебру. Основы алгебры. М.: Физматлит.1994. - 320 с.] и [Курош А.Г. Курс высшей алгебры. - М., Наука, 1971. - 431 с.]. В вычислительных устройствах многочлены представляются в виде БС, в которых каждый бит или каждая подстрока битов фиксированной длины интерпретируется как один из коэффициентов многочлена, над которыми определены операции сложения и умножения коэффициентов. Элементами конечного поля многочленов являются все возможные многочлены, коэффициентами которых являются элементы простого поля GF(p) для некоторого заданного значения простого числа р. Операция умножения в поле многочленов состоит в умножении многочленов-сомножителей и взятии остатка от деления полученного произведения на некоторый заданный неприводимый многочлен. Число элементов конечного поля многочленов (порядок поля) равно p^s, где s - степень неприводимого многочлена, которая совпадает с максимальным числом ненулевых коэффициентов в многочленах, получаемых в качестве остатка от деления на неприводимый многочлен.

Вектора, в которых БС являются элементами конечного простого поля, т.е. многоразрядными двоичными числами, будем называть векторами МДЧ. Вектора, в которых БС являются элементами конечного расширенного поля многочленов, будем называть векторами многочленов. Действия над конечными множествами векторов МДЧ и конечными множествами векторов многочленов описываются одинаково, за исключением того, что действия над координатами векторов относятся к полям различного типа, а потому отличаются в этих двух случая. Действия над координатами векторов МДЧ можно описать как выполнение операций сложения и умножения по модулю простого числа р. Действия над координатами векторов многочленов можно описать как выполнение операций сложения и умножения по модулю неприводимого многочлена р. Размер модуля в обоих случаях выбирается таким, чтобы обеспечить достаточно большой порядок векторных конечных полей. В обоих случаях формула, описывающая операцию умножения векторов, например умножения векторов Z₁=(a₁ e+b₁ i+c₁ j) и Z₂=a₂ e+b₂ i+c₂ j по таблице 1 имеет одинаковый вид:

где в случае векторов МДЧ параметры a₁, b₁, c₁, a₂, b₂, с₂, р и µ - это МДЧ, а в случае векторов многочленов параметры a₁, b₁, c₁, a₂, b₂, с₂, р и µ - это многочлены.

В зависимости от размерности векторов, над которыми определяются операции умножения, и конкретного варианта задания операции умножения векторов могут быть использованы различные таблицы умножения базисных векторов, например, для векторов размерности m=2 приемлемая таблица имеет вид таблицы 2, где 0<ε<р, а для векторов размерности m=3 - вид таблицы 3, где 0<ε<р. Значение параметра ε, называемого коэффициентом растяжения, выбирают таким образом, что множество всех m -мерных векторов, заданных над конечным полем GF(p) или GF(p^s), образует конечное поле, являющееся расширением конечного поля GF(p) или GF(p^s) соответственно. Конечное векторное поле будем записывать в виде GF(p^m), если оно задано над полем GF(p), или СF((p^s)^m), если оно задано над полем GF(p^s). Для заданного варианта таблицы умножения базисных векторов существует большое число значений коэффициента растяжения, при котором образуется векторное конечное поле. При этом для формирования векторного конечного поля следует выбрать размерность векторов и характеристику поля, над которым задаются вектора, таким образом, чтобы порядок поля делился нацело на значение размерности. Ниже будут построены векторные конечные поля, иллюстрирующие различные конкретные варианты задания векторных полей.

Таблицы умножения базисных векторов для случая векторов МДЧ и векторов многочленов имеют одинаковый вид, за исключением того, что в случае векторов МДЧ коэффициент растяжения ε представляет собой некоторое МДЧ, а в случае векторов многочленов коэффициент растяжения ε представляет собой некоторый многочлен ε=ε(z).

Аналогичным способом могут быть определены операции умножения над векторами размерностей m=4, m=5 и т.д. Например, правила умножения базисных векторов для случая m=7 приведены в следующей таблице 4, где в качестве коэффициентов растяжения p, τ, λ, ε, µ и τ могут быть использованы произвольные шесть значений, являющихся многочленами в случае, когда вектора представляют собой вектора многочленов, или являющихся МДЧ в случае, когда вектора представляют собой вектора МДЧ. В случае задания векторов над простым конечным полем GF(p) для произвольного значения размерности векторов m при соответствующем выборе таблицы умножения базисных векторов и простого значения p множество векторов МДЧ является векторным конечным полем GF(p^m), единичным элементом которого является вектор МДЧ Е=1e+0i+…+0w=(1,0,0,…,0), а нулевым элементом является вектор МДЧ Е=0е+0i+…+0w=(0,0,0,…,0), где 1 и 0 - это единица и нуль в поле GF(p). Векторное конечное поле GF(p^m) является расширением конечного простого поля GF(p). В случае задания векторов над конечным полем многочленов CF(p^s) для произвольного значения размерности векторов m при соответствующем выборе таблицы умножения базисных векторов и простого значения p множество векторов многочленов является векторным конечным полем GF((p^s)^m), единичным элементом которого является вектор многочленов Е=1e+0i+…+0w=(1,0,0,…,0), а нулевым элементом является вектор многочленов Е=0е+0i+…+0w=(0,0,0,…,0), где 1 и 0 - это единица и нуль в поле GF(p^s). Векторное конечное поле GF((p^s)^m) является расширением конечного поля многочленов GF(p^s).

Детальное обоснование и описание условий формирования векторных конечных полей, заданных над простыми конечными полями и полями многочленов, приведено в приводимых ниже примерах, а также в статьях [П.А.Молдовяну, Е.С.Дернова, Д.Н.Молдовян. Синтез конечных расширенных полей для криптографических приложений // Вопросы защиты информации. 2008. №3(82). С.2-7] и [Д.Н.Молдовян, П.А.Молдовяну. Задание умножения в полях векторов большой размерности // Вопросы защиты информации. 2008. №3(82). С.12-17]. Ниже приводятся примеры реализации заявленного способа генерации и проверки подлинности ЭЦП, заверяющей ЭД. При этом в примерах, приводимых ниже, используются параметры с искусственно уменьшенной разрядностью, чтобы уменьшить размер примеров и сделать их более наглядными.

Пример 1

Данный пример иллюстрирует частный вариант реализации заявленного способа, соответствующий пп.1 и 2 формулы изобретения. В этом примере при формировании и проверке подлинности ЭЦП реализуется та же последовательность действий, что и в случае с прототипом, за исключением того, что генерируется ЭК, заданная над векторным конечным полем GF(p^m), где p>3 и m - значение размерности векторов. При этом генерируется ЭК в виде множества точек, координаты которых Х и Y удовлетворяют уравнению Y²=Х³+Z_aX+Z_b, где X, Y, Z_a и Z_b - вектора, принадлежащие векторному полю GF(p^m), которое аналогично уравнению ЭК в случае прототипа. Данное уравнение задает ЭК над любым конечным полем, характеристика которого равна простому числу p>3. Формулы для вычисления суммы двух точек ЭК А и В с координатами соответственно (X_A, Y_A) и (X_B, Y_B), где X_A, Y_A, X_B и Y_B вектора, принадлежащие векторному полю GF(p^m), также являются аналогичными и имеют вид:

X_C=K²-X_A-X_B и Y_C=K(X_A-X_C)-Y_A,

где если точки А и В не равны, и если точки А и В равны. В приведенных в этом примере формулах операции сложения, вычитания, умножения и деления являются операциями сложения, вычитания, умножения и деления m-мерных векторов, а координаты точек ЭК и коэффициенты Z_a, Z_b и К уравнения ЭК являются m-мерными векторами, т.е. элементами векторного конечного поля GF(p^m). Используя хорошо известный метод задания точек ЭК в проективных координатах [Болотов А.А., Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. - М.: КомКнига/URSS, 2006. - 274 с. (см. с.35-45)] сумма двух точек может быть вычислена только с использованием операций умножения, сложения и вычитания, что является общим методом уменьшения времени выполнения операции сложения точек ЭК.

Рассмотрим варианты векторных конечных полей, которые могут быть использованы в рассматриваемом примере частной реализации заявленного способа. При m=3 общие правила умножения базисных векторов, обеспечивающие свойства коммутативности и ассоциативности операции умножения векторов, представлены в таблице 5, где ε и µ - коэффициенты растяжения, ε, µ ∈ GF(p). В зависимости от конкретной пары значений ε и µ множество трехмерных векторов является конечным полем или конечной группой. Поскольку определенные нами операции сложения и умножения векторов являются коммутативными и ассоциативными, а операция умножения дистрибутивна по отношению к операции умножения, то конечное пространство трехмерных векторов будет образовывать расширенное поле GF(p³), если для каждого трехмерного вектора, отличного от (0,0,0), существует вектор, являющийся обратным к нему. В противном случае будем иметь группу, порядок которой определяется числом векторов, для которых существуют соответствующие обратные элементы. Решение этого вопроса связано с анализом характеристического уравнения третьей степени, возникающего из условия существования вектора (xe+yi+zj), являющегося обратным значением к векторам вида aе+bi+cj, где хотя бы одна из координат a, b, с отлична от нуля. Исходя из условия существования обратных значений, запишем в соответствии с таблицей 5 и общим определением операции умножения векторов следующее соотношение

(aе+bi+cj)o(xe+yi+zj)=(ax+εµcy+µεbz)e+(bx+ay+µcz)i+(az+εby+az)j,

из которого видно, что вопрос существования обратных значений сводится к вопросу существования решений системы уравнений вида:

Равенство нулю главного определителя этой системы для некоторых троек значений (a, b, с) задает вектора aе+bi+cj, для которых не существуют обратных элементов. Таким образом, получаем следующее характеристическое уравнение

a³-3εµbc a+ε²µb³+εµ²с³≡0 mod р.

Используя формулу Кардано [Курош А.Г. Курс высшей алгебры.- М., Наука, 1971. - 431 с.] и обозначение В=(ε²µb³+εµ²с³)/2, решение последнего уравнения относительно неизвестного а можно записать в виде a₀=А'+А'', где

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

Случай 1. Число 3 не делит p-1. Существует единственное значение кубичного корня для всех значений подкоренного выражения. В этом случае число корней характеристического уравнения определяется значением его детерминанта

D=-27(ε²µb³-εµ²с³)²(mod p).

Если то D=0 и существует два разных корня a₀' и a₀'', поэтому для 2(p-1) векторов вида (a'₀,b,b mod p) и (a''₀,b,b mod p, где b ∈ {1,2,…,p-1}, не существует обратных значений. Если c≠b mod p, то D≠0 и существует только один корень а₀, поэтому для p(p-1) векторов вида (a₀ b, с), где b, с ∈ {1,2,…,p-1} не существует обратных значений. Учитывая также, что не существует обратного значения для вектора (0,0,0), и вычитая из полного числа трехмерных векторов число векторов, для которых не существует обратных значений, получаем порядок группы трехмерных векторов, равный Ω=р³-2(р-1)-p(р-1)-1=(p-1)²(p+1).

Случай 2. Число 3 делит p-1 и каждое из произведений ε²µ и εµ² является кубичным вычетом в поле GF(p). Анализ дискриминанта характеристического уравнения показывает, что для h=6(р-1)-3(р²+9(р-1)+2 векторов не существует обратных значений. Вычитая из полного числа векторов значение h, получаем порядок группы, равный Ω=p³-h=(p-1)³.

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

Случай 3. Число 3 делит р-1 и каждое из произведений ε²µ и εµ² является кубичным невычетом в поле GF(p). Это может иметь место, например, в случае, когда ε - кубичный вычет, а µ - кубичный невычет, или наоборот. Тогда существует единственная пара значений b и с, а именно b=с=0, для которой имеется решение a₀=0 характеристического уравнения. Это означает, что в этом случае каждому ненулевому вектору можно сопоставить обратный вектор. Следовательно, в рассматриваемом случае совокупность всех трехмерных векторов образует поле GF(p³), мультипликативная группа которого является циклической и имеет порядок Ω=р³-1.

Например, при просто p=604884627778815030120967 и коэффициентах растяжения µ=1 и ε=3048145277787150301203 (кубичный невычет) образуется векторное конечное поле GF(p³), генератором мультипликативной группы которого является вектор G_Ω=2е+3i+5j.

Аналогично построению конечных полей трехмерных векторов можно построить поля многомерных векторов. Для того чтобы множество m-мерных векторов составляло поле GF(p^m), следует выбирать поле GF(p), для характеристики которого выполняется условие делимости m|р-1 (т.е. значение m делит нацело значение р-1). Кроме того, в соответствующую таблицу умножения базисных векторов надо ввести коэффициент растяжения ε, значение которого является невычетом степени m в поле GF(p), т.е такое значение ε, которое не может быть представлено в виде 4-й степени какого-либо другого элемента поля GF(p). В этом случае многомерные векторные пространства (для m≥4), над которыми заданы принятые выше операции сложения и умножения, составляют векторное конечное поле GF(p^m). Рассмотрим некоторые частные варианты.

Случай m=4. Определим операцию умножения четырехмерных векторов aе+bi+cj+dk с помощью таблицы 6, которая обеспечивает свойство коммутативности и ассоциативности. Задавая различные конкретные значения коэффициентов растяжения, можно задавать различные варианты полей GF(p⁴). Для простого p=670657405878917 и коэффициента растяжения ε=33322555333777 (такое значение ε не может быть представлено в виде 4-й степени какого-либо другого элемента поля GF(p)), формируется векторное поле GF(p⁴), генератором мультипликативной группы которого является вектор G_Ω=2е+5i+7j+11k.

Случай m=5. Определим операцию умножения пятимерных векторов aе+bi+cj+dk+gu с помощью таблицы 7. При простом р=268675256028581 и коэффициенте растяжения ε=3048145277787 (это значение ε является невычетом 5-й степени) образуется векторное конечное поле GF(p⁵), генератором мультипликативной группы которого является вектор G_Ω=2e+5i+7j+11k+13u.

Таким образом, мы показали способ построения векторных конечных полей GF(p^m) для различных значений р и m, что обосновывает отличительный признак заявленного изобретения, заключающийся в том, что генерируют ЭК над конечным полем, являющимся векторным конечным полем.

В примере 1 последовательность действия по генерации и проверке ЭЦП в соответствии с заявленным способом имеет следующий вид:

генерируют ЭК, которая представляет собой совокупность точек ЭК, заданных в виде пар векторов, принадлежащих векторному конечному GF(p⁵), описанному выше (см. случай m=5) и удовлетворяющих уравнению Y²=Х³+Z_aX+Z_b (генерация ЭК состоит в задании векторов Z_a и Z_b);

методом генерации случайной равновероятной последовательности формируют секретный ключ в виде МДЧ k;

формируют открытый ключ Р в виде двух векторов X_P и Y_P, являющихся координатами точки Р, принадлежащей ЭК, для чего генерируют точку G, принадлежащую ЭК и имеющую значение порядка, равное q, и затем генерируют точку Р по формуле Р=kG;

принимают ЭД, представленный МДЧ Н;

генерируют случайное МДЧ 0<t<q, по которому формируют точку R по формуле R=tG;

формируют ЭЦП Q в виде пары МДЧ (r, s), для чего генерируют МДЧ r по формуле r=F(R), где F(R) - некоторая функция с целочисленными значениями, аргументом которой являются координаты точки ЭК (например, r=F(R)=x_R1x_R2x_R3x_R4x_R5 mod q, где X_R=(x_R1,x_R2,x_R3,x_R4,x_R5) - абсцисса точки R, представляющая собой пятимерный вектор МДЧ с координатами x_R1, x_R2, x_R3, x_R4 и x_R5);

генерируют МДЧ s по формуле s=(tH+rk) mod q;

формируют первую проверочную БС А, для чего генерируют МДЧ (по формуле ν=sH^-1 mod q и МДЧ w по формуле w=(q-rH^-1) mod q, затем генерируют точку R' по формуле R'=νG+wP, после чего БС А получают в виде МДЧ А, вычисляемого по формуле А=x_R' mod q, где x_R' - абсцисса точки R';

формируют вторую проверочную БС в виде МДЧ В, генерируемого путем копирования МДЧ r: В=r;

сравнивают сформированные проверочные БС А и В;

при совпадении параметров сравниваемых БС А и В делают вывод о подлинности ЭЦП.

Пример 2

Данный пример иллюстрирует частный вариант реализации заявленного способа, соответствующий пп.1 и 3 формулы изобретения. В этом примере при формировании и проверке подлинности ЭЦП реализуется та же последовательность действий, что и в случае с прототипом, за исключением того, что генерируется ЭК, заданная над векторным конечным полем GF((3^s)^m), где s - степень неприводимого многочлена, задающего конечное поле многочленов GF(p^s), где р=3, над которым заданы вектора и m - значение размерности векторов. Конечное поле многочленов имеет характеристику 3 и конечное векторное поле GF((3^s)^m) также имеет характеристику 3. Степень расширения векторного поля равна sm, т.е. в m раз больше, чем степень расширения поля многочленов. При задании ЭК над конечным полем характеристики р=3 может быть использовано уравнение ЭК вида Y²=Х³+Z_aX²+Z_b или уравнение вида Y²=X³+Z_aX+Z_b, где X, Y, Z_a и Z_b, - вектора, принадлежащие векторному полю GF((3^s)^m). Пусть в примере 2 ЭК генерируется по последнему уравнению, тогда формулы для вычисления суммы С=(X_C, Y_C)=А+В двух точек ЭК А=(X_A, Y_A) и В=(X_B, Y_B), где координаты точек X_A, Y_A, X_B и Y_B - это вектора, принадлежащие векторному полю GF((3^s)^m), имеют вид:

X_C=K²-X_A-X_B и Y_C=K(X_A-X_C)-Y_A,

где если точки А и В не равны, и если точки А и В равны. В приведенных в этом примере формулах операции сложения, вычитания, умножения и деления являются операциями сложения, вычитания, умножения и деления m-мерных векторов многочленов. Используя хорошо известный метод задания точек ЭК в проективных координатах [Болотов А.А., Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. - М.: КомКнига/URSS, 2006. - 274 с.(см. с.35-45)] сумма двух точек может быть вычислена только с использованием операций умножения, сложения и вычитания, что является общим методом уменьшения времени выполнения операции сложения точек ЭК.

Векторные конечные поля GF((3^s)^m) над конечными полями многочленов GF(3^s) задаются следующим образом. Выбирают значения m и s такими, что выполняется условие делимости m|3^s-1 (т.е. значение m делит нацело значение 3^s-1). Затем в качестве коэффициента растяжения, присутствующего в соответствующих клетках таблицы умножения базисных векторов, берется многочлен ε степени не более s-1, такой, что он не может быть представлен в виде m-й степени какого-либо другого многочлена (при m≥2 такие многочлены ε всегда существуют и их легко вычислить). Приведем примеры построения векторных конечных полей вида GF((3^s)^m), заданные над троичными многочленами. Троичными многочленами называются многочлены, заданные над полем GF(3).

Случай m=4, р=3 и s=12. Определим операцию умножения четырехмерных векторов aе+bi+cj=dk, где координаты a, b, с и d представляют собой многочлены над простым полем GF(3), с помощью таблицы 6 и коэффициента растяжения ε=ε(z)=z²+1. В качестве неприводимого многочлена возьмем троичный многочлен η(z)=z¹²+2z¹¹+z¹⁰+2z⁹+2z⁸+z⁷+z⁶+z⁵+z³+1, который можно также представить в хорошо известной форме записи троичных многочленов η(z)=(1212211101001), в которой троичный многочлен представлен последовательностью его коэффициентов. Выбранные параметры задают векторное конечное поле GF((3¹²)⁴), генератором мультипликативной группы которого является вектор G_Ω=(1101)е+(2011)i+(112)j+(121)k.

Случай m=5,p=3 и s=8. Определим операцию умножения пятимерных векторов aе+bi+cj+dk+hu, где координаты а, b, с, d и h представляют собой многочлены над полем GF(3), с помощью таблицы 6 и коэффициента растяжения ε=ε(z)=z²+1. В качестве неприводимого многочлена возьмем троичный многочлен η(z)=z⁸+z⁷+2z⁶+z⁵+z³+z²+1, который можно также представить в хорошо известной форме записи троичных многочленов η(z)=(112101101), в которой троичный многочлен представлен последовательностью его коэффициентов. Выбранные параметры задают векторное конечное поле GF((3⁸)⁵), генератором мультипликативной группы которого является вектор G_Ω=(120l)e+(2011)i+(112)j+(121)k+(12)u.

Таким образом, мы показали способ построения векторных конечных полей GF((3^s)^m), заданных над конечным полем GF(p^s) многочленов для значения р=3 и различных значений s, что обосновывает отличительный признак п.3 формулы изобретения, заключающийся в том, что генерируют ЭК над конечным полем, являющимся векторным конечным полем, заданным над конечным полем многочленов GF(p^s), где s - степень расширения поля и р - характеристика поля, причем р=3. В примере 2 последовательность действия по генерации и проверке ЭЦП в соответствии с заявленным способом имеет вид последовательности действий примера 1, за исключением того, что первый шаг последовательности действий в примере 1 заменяется следующим действием: генерируют ЭК, которая представляет собой совокупность пар векторов, принадлежащих векторному конечному полю GF((3⁸)⁵), описанному выше (см. случай m=5,р=3 и s=8) и удовлетворяющих уравнению Y²=Х³+Z_aX+Z_b.

Пример 3

Данный пример иллюстрирует частный вариант реализации заявленного способа, соответствующий пп.1 и 4 формулы изобретения. В этом примере при формировании и проверке подлинности ЭЦП реализуется та же последовательность действий, что и в случае с прототипом, за исключением того, что генерируется ЭК, заданная над векторным конечным полем GF((2^s)^m), где s - степень неприводимого многочлена, задающего конечное поле многочленов GF(p^s), где р=2, над которым заданы вектора и m - значение размерности векторов (конечное поле многочленов имеет характеристику 2 и конечное векторное поле также имеет характеристику 2). При р=2 для генерации ЭК используются уравнения следующих двух видов Y²+XY=X³+Z_aX²+Z_b

и Y²+Z_cY=X³+Z_aX+Z_b, где X, Y, Z_a, Z_b и Z_c - вектора, принадлежащие векторному полю GF((2^s)^m). Будем предполагать, что в примере 3 генерируют ЭК в соответствии со вторым уравнением. Тогда формулы для вычисления суммы двух точек ЭК А и В с координатами соответственно (X_A, Y_A) и (X_B, Y_B) где X_A, Y_A, X_B и Y_B вектора, принадлежащие векторному полю GF((2^s)^m) имеют вид [A.J.Menezes, S.A.Vanstone. Elliptic curve cryptosystems and their implementation // Journal of cryptology. 1993. Vol.6. No 4. P.209-224]:

и

В приведенных в этом примере формулах операции сложения, вычитания, умножения и деления являются операциями сложения, вычитания, умножения и деления m-мерных векторов, являющихся элементами векторного конечного поля GF(2^s)^m). Используя хорошо известный метод задания точек ЭК в проективных координатах, сумма двух точек может быть вычислена только с использованием операций умножения, сложения и вычитания, что является общим методом уменьшения времени выполнения операции сложения точек ЭК (см., например, статью [A.J.Menezes, S.A.Vanstone. Elliptic curve cryptosystems and their implementation // Journal of cryptology. 1993. Vol.6. No 4. P. 209-224] и книгу [Болотов А.А., Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. - М.: КомКнига/URSS, 2006. - 274 с.; см. с.35-45]).

Векторные конечные поля GF((2^s)^m) над конечными полями многочленов GF(2^s) задаются следующим образом. Выбирают значения m и s такими, что выполняется условие делимости m|2^s-1 (т.е. значение m делит нацело значение 2^s-1). Затем в качестве коэффициента растяжения, присутствующего в соответствующих клетках таблицы умножения базисных векторов, берется многочлен ε степени не более s - 1, такой, что он не может быть представлен в виде m-й степени какого-либо другого многочлена (при m≥2 такие многочлены ε всегда существуют и их легко вычислить). Приведем примеры построения векторных конечных полей вида GF((2^s)^m).

Случай m=3, р=2 и s=16. Определим операцию умножения трехмерных векторов aе+bi+cj, где координаты a, b и с представляют собой многочлены над полем GF(2) (такие многочлены называются двоичными многочленами), с помощью таблицы 3 и коэффициента растяжения ε=ε(z)=z³+1. В качестве неприводимого многочлена возьмем двоичный многочлен η(z)=z¹⁶+z¹⁵+z¹⁴+z^l2+z¹¹+z¹⁰+z⁹+z²+1, который можно также представить в хорошо известной форме записи двоичных многочленов η(z)=(11101111000000101), в которой двоичный многочлен представлен последовательностью его коэффициентов. Выбранные параметры задают векторное конечное поле GF((2¹⁶)³), генератором мультипликативной группы которого является вектор G_Ω=(1101)е+(1001)i+(110)j.

Случай m=5, р=2 и s=12. Определим операцию умножения пятимерных векторов aе+bi+cj+dk+gu, где координаты a, b, с, d и g представляют собой многочлены над полем GF(2) (такие многочлены называются двоичными многочленами), с помощью таблицы 3 и коэффициента растяжения ε=ε(z)=z²+1. В качестве неприводимого многочлена возьмем двоичный многочлен η(z)=z¹²+z¹⁰+z⁵+z⁴+z²z+1, который можно также представить в хорошо известной форме записи двоичных многочленов η(z)=(1010000110111), в которой двоичный многочлен представлен последовательностью его коэффициентов. Выбранные параметры задают векторное конечное поле GF((2¹²)⁵), генератором мультипликативной группы которого является вектор G_Ω=(1101)е+(1011)i+(110)j+(101)k+(10)u.

Таким образом, мы показали способ построения векторных конечных полей GF((2^s)^m), заданных над конечным полем GF(p^s) многочленов для значения р=2 и различных значений s, что обосновывает отличительный признак п.4 формулы изобретения, заключающийся в том, что генерируют ЭК над конечным полем, являющимся векторным конечным полем, заданным над конечным полем многочленов GF(p^s), где s - степень расширения поля и р - характеристика поля, причем р=2. В примере 3 последовательность действия по генерации и проверке ЭЦП в соответствии с заявленным способом имеет вид последовательности действий примера 1, за исключением того, что первый шаг последовательности действий в примере 1 заменяется следующим действием: генерируют ЭК, которая представляет собой совокупность пар векторов, принадлежащих векторному конечному полю GF((2¹²)⁵), описанному выше (см. случай m=5, p=2 и s=12) и удовлетворяющих уравнению Y²+Z_cY=Х³+Z_aX+Z_b.

Пример 4

Данный пример иллюстрирует частный вариант реализации заявленного способа, соответствующий пп.1 и 5 формулы изобретения. В этом примере при формировании и проверке подлинности ЭЦП реализуется та же последовательность действий, что и в случае с прототипом, за исключением того, что генерируется ЭК, заданная над векторным конечным полем GF((p^s)^m), где р>3 и m - значение размерности векторов, заданным над конечным полем многочленов GF(p^s). При этом генерируется ЭК, описываемая уравнением Y²=Х³+Z_aX+Z_b, где Z_a и Z_b - вектора, принадлежащие векторному полю GF((p^s)^m), аналогичным уравнению ЭК в случае примера 1. Формулы для вычисления суммы двух точек ЭК А и В с координатами соответственно (X_A, Y_A) и (X_B,Y_B), где X_A, Y_A, X_B и Y_B - вектора, принадлежащие векторному полю GF((p^s)^m), имеют вид: X_C=К²-X_A-X_B и Y_C=K(X_A-X_C)-Y_A, где если точки А и В не равны, и если точки А и В равны. В приведенных в этом примере формулах операции сложения, вычитания, умножения и деления являются операциями сложения, вычитания, умножения и деления m-мерных векторов, а координаты точек ЭК и коэффициенты Z_a, Z_b и К уравнения ЭК являются m-мерными векторами многочленов степени s, т.е. элементами векторного конечного поля GF((p^s)^m). При задании точек ЭК в проективных координатах сумма двух точек может быть вычислена только с использованием операций умножения, сложения и вычитания [Молдовян Н.А., Молдовян А.А., Еремеев М.А. Криптография: от примитивов к синтезу алгоритмов. - СПб., БХВ-Петербург, 2004. 446 с. (см. с.126-128)], что является общим методом уменьшения времени выполнения операции сложения точек ЭК. Благодаря тому, что операция умножения в конечных полях, заданных в векторной форме, эффективно распараллеливается, использование ЭК, заданных над векторными полями, позволяет существенно повысить производительность процедур формирования и проверки ЭЦП в способах, основанных на выполнении операций над точками ЭК.

Рассмотрим конкретные примеры векторных конечных полей GF((p^s)^m), где р>3 и m - значение размерности векторов, заданных над конечными полями многочленов вида GF(p^s).

Случай m=5, р=991 и s=2. Этот случай относится к пространству пятимерных векторов aе+bi+cj+dk+hu, где координаты a, b, с, d и h представляют собой многочлены первой или нулевой степени над полем GF(991). Все возможные значения многочленов степени, меньшей чем s=2 (т.е. многочленов первой и нулевой степени), образуют поле GF(991²), в котором умножение задано как умножение многочленов по модулю неприводимого многочлена второй степени (s=2), например по модулю неприводимого многочлена η(z)=z²+373z+601. Определим операцию умножения пятимерных векторов с помощью таблицы 7 и коэффициента растяжения ε=ε(z)=3z²+2z. Выбранные параметры задают векторное конечное поле GF((991²)⁵), генератором мультипликативной группы которого является вектор многочленов G_Ω=(3z+1)е+(5z+7)i+(3z+2)j+(z+l)k+(3z+l)u.

Случай m=3, р=127 и s=5. Рассмотрим пространство трехмерных векторов aе+bi+cj, где координаты a, b, и с представляют собой многочлены над полем GF(127). Все возможные значения многочленов степени не выше четвертой образуют поле GF(127⁵), в котором умножение задано как умножение многочленов по модулю неприводимого многочлена, например η(z)=z⁵+120z⁴+16z³+114z²+69z+34. Определим операцию умножения трехмерных векторов с помощью таблицы 3 и коэффициента растяжения ε=ε(z)=z²+5z+2. Выбранные параметры задают векторное конечное поле GF((127⁵)³), генератором мультипликативной группы которого является вектор G_Ω=(z³+2z²+z)e+(7z³+5z²+3z+2)i+(z³+3z²+5z+l)j.

Выполнение операций сложения, умножения и деления многочленов, а также операций умножения и сложения по модулю неприводимого многочлена широко описано в научно-технической литературе. Также широко представлена реализация конечных полей многочленов и основные их свойства (см., например, книги [Курош А.Г. Курс высшей алгебры.- М., Наука, 1971. - 431 с.], [Кострикин А.И. Введение в алгебру. Основы алгебры. М.: Физматлит.1994. - 320 с], [А.Акритас. Основы компьютерной алгебры с приложениями. М., Мир, 1994. - 544 с.] и [Л.Б.Шнеперман. Курс алгебры и теории чисел в задачах и упражнениях.- Минск, Вышэйшая школа, 1986. - 272 с.]).

Таким образом, в примере 4 мы показали способ построения векторных конечных полей GF((p^s)^m) для различных значений p>3, s≥2 и m≥2, что обосновывает отличительный признак п.5 формулы изобретения, заключающийся в том, что генерируют ЭК над конечным полем, являющимся векторным конечным полем, заданным над конечным полем многочленов GF(p^s), где s - степень расширения поля и р - характеристика поля, причем р>3. В примере 4 последовательность действия по генерации и проверке ЭЦП в соответствии с заявленным способом имеет следующий вид:

генерируют ЭК, которая представляет собой совокупность пар векторов, принадлежащих векторному конечному полю GF((127⁵)³), описанному выше (см. случай m=3, р=127 и s=5) и удовлетворяющих уравнению Y²=Х³+Z_aX+Z_b (генерация ЭК состоит в задании векторов Z_a и Z_b);

формируют случайный секретный ключ в виде МДЧ k;

формируют открытый ключ Р в виде двух векторов X_P и Y_P векторному конечному полю GF((127⁵)³) и являющихся координатами точки Р, принадлежащей ЭК, для чего генерируют точку G, имеющую значение порядка равное q;

принимают ЭД, представленный МДЧ Н;

генерируют случайное МДЧ 0<t<q, по которому формируют точку R по формуле R=tG;

формируют ЭЦП Q в виде пары МДЧ (r, s), для чего генерируют МДЧ r по формуле r=Н+{X_R} mod q, где X_R=(x_R1,x_R2,x_R3) - абсцисса точки R, представляющая собой трехмерный вектор многочленов с координатами x_R1=x_R1(z), X_R2=x_R2(z) x_R3=x_R3(z) и {X_R} - МДЧ, полученное подстановкой в многочлен x(z)=x_R1x_R2x_R3=x_R1(z)x_R2(z)x_R3(z) значения z=1;

генерируют МДЧ s по формуле s=(t+rk) mod q;

формируют первую проверочную БС А, для чего генерируют точку R' по формуле R'=sG-rP, после чего БС А получают в виде МДЧ А, вычисляемого по формуле А=Н+{X_R'} mod q, где x_R' - абсцисса точки R';

формируют вторую проверочную БС в виде МДЧ В, генерируемого путем копирования МДЧ r: В=r;

сравнивают сформированные проверочные БС А и В;

при совпадении параметров сравниваемых БС А и В делают вывод о подлинности ЭЦП.

Корректность процедур генерации и проверки ЭЦП в последнем примере доказывается в общем случае путем доказательства того, что точка R' совпадает с точкой R, а значит, значение проверочной БС А совпадает со значением r, поскольку r и А вычисляются по одной и той же формуле H+{X_R∗} mod q при параметре R*=R и R*=R'=R соответственно. Действительно, имеем:

R'=sG-rP=(t+rk)G-r(kG)=tG+rkG-rkG)=tG=R⇒A=H+{X_R'}modq=H+{X_R}modq=r=B,

т.е., если параметры подписи (r, s) сформированы с использованием подлинного секретного ключа, то при выполнении процедуры проверки подлинности ЭЦП получим совпадение первой и второй проверочных БС: А=В.

Для практики представляют интерес различные варианты значений размерности m векторов. Выбор соответствующей размерности m зависит от требований конкретных применений заявленного способа генерации и проверки ЭЦП. Например, при использовании 32-разрядных процессоров для выполнения вычислений интерес представляют простые значения размерности m=5, m=7, m=11 и m=13. При аппаратной реализации в виде специализированных вычислительных устройств высокая производительность процедур генерации проверки ЭЦП может быть достигнута при значениях размерности векторов m=8, m=9, m=16 и m=32. Наиболее высокая производительность при аппаратной реализации может быть достигнута при использовании заявленного способа для случая использования векторов двоичных многочленов. Это объясняется тем, что операции сложения и умножения и двоичных многочленов в конечных полях двоичных многочленов являются наиболее эффективными с точки зрения получения высокого быстродействия и уменьшения сложности аппаратной реализации. Таблицы умножения базисных векторов, пригодные для задания векторных конечных полей для различных значений размерности m приведены в статьях [П.А.Молдовяну, Е.С.Дернова, Д.Н.Молдовян. Синтез конечных расширенных полей для криптографических приложений // Вопросы защиты информации. 2008. №3(82). С.2-7] и [Д.Н.Молдовян, П.А.Молдовяну. Задание умножения в полях векторов большой размерности // Вопросы защиты информации. 2008. №3(82). С.12-17].

Приведенные выше примеры показывают принципиальную реализуемость векторных конечных полей различных значений характеристики поля и размерности векторов, а также реализуемость ЭК над конечными векторными полями, и способов генерации и проверки подлинности ЭЦП, основанных на выполнении операций сложения точек ЭК, заданной над векторным конечным полем. Переход к использованию ЭК, заданных над векторными полями, обеспечивает возможность эффективного распараллеливания процедур генерации и проверки ЭЦП, за счет чего достигается существенный выигрыш в производительности. Кроме того, применение ЭК над векторными конечными полями обеспечивает дополнительный рост производительности за счет снижения сложности умножения при заданном размере порядка поля. Рассмотрим вопрос снижения сложности умножения элементов конечного поля GF(p^m), заданного в векторной форме при фиксированном размере порядка поля. Сравним сложность операции умножения в поле такого типа со сложностью умножения в простом поле GF(p'), где |р'|=m|р| (здесь и далее |р| обозначает битовую длину числа р). Операция умножения элементов в векторном конечном поле GF(p^m) включает m² операций умножения в поле GF(p), причем сложность операции умножения в поле GF(p) пропорциональна |p|², поэтому при прямолинейном выполнении операции умножения в поле GF(p^m), представленном в векторной форме, ее сложность примерно равна сложности умножения в поле Z _p' (сложностью операций арифметического сложения мы пренебрегаем ввиду их относительной малости). Однако имеется следующий способ снижения операции умножения в векторном конечном поле. При умножении m-мерных векторов осуществляются обычные арифметические операции умножения соответствующих пар координат векторов-сомножителей, результаты суммируются, а затем выполняется операция арифметического деления полученного результата на значение р. При этом число арифметических умножений остается равным m², а число делений уменьшается в m раз, становясь равным m. При этом сложность операции деления возрастает за счет увеличения делимого несущественно, так как размер последнего увеличивается всего лишь на несколько битов. Это не вносит существенного увеличения сложности операции деления в случае практически значимых размеров значений координат, которые определяются размерами модуля и равны от |р|=16 до |р|=200 бит для значений размерности от m=13 до m=3 соответственно. Поскольку сложность операции деления значительно превосходит сложность операции умножения, то сложность операции умножения элементов поля GF(p^m) снижается примерно пропорционально значению m. Наличие дополнительных операций умножения на коэффициенты растяжения, используемые для создания условия формирования полей в конечных векторных пространствах, не вносят существенного вклада в общую сложность всех операций арифметического умножения, поскольку в качестве таких коэффициентов растяжения можно подобрать значения размером в два-три бита.

Рассмотрим сложность умножения в поле GF(p^s), заданном в виде конечного кольца многочленов степени s - 1. Операция умножения двух многочленов включает s² операций арифметического умножения |p|-битовых чисел и s операций деления 2|р|-битовых чисел на модуль р (операциями сложения пренебрегаем ввиду их низкой сложности). В результате выполнения этих операций получаем многочлен степени 2s - 2, который далее делится на неприводимый многочлен. Наличие этой операции не допускает эффективного распараллеливания операции умножения в поле многочленов. Наиболее эффективная реализация деления на неприводимый многочлен требует выполнения примерно s² операций арифметического умножения |р|-битовых чисел и m операций деления 2|p|-битовых чисел на модуль p. Видим, что в целом операция умножения в поле многочленов, по крайней мере, в два раза сложнее операции умножения в поле GF(p^m), заданном в векторном пространстве, при m=s.

Таким образом, переход к векторной форме задания расширенных конечных полей дает выигрыш в вычислительной эффективности даже в случае использования однопроцессорного вычислительного устройства, т.е. в даже случае, когда распараллеливание выполняемых процедур не может быть реализовано. При возможности распараллеливания операции умножения на m процессов использование векторного конечного поля GF(p^m) обеспечивает возможность сокращения времени выполнения умножения в поле GF(p^m) примерно до m² раз в сравнении с простым полем и до 2m раз в сравнении с конечным полем многочленов (при заданном размере порядка поля, над которым задается ЭК).

Общая схема синтеза алгоритмов ЭЦП на основе ЭК над векторными конечными полями остается такой же, как и в случае задания ЭК над простыми полями или полями многочленов. Изменяется только форма представления конечного поля, над которым задаются ЭК. Ввиду известного факта об изоморфизме всех конечных полей заданного порядка [А.Акритас. Основы компьютерной алгебры с приложениями. М., Мир, 1994. - 544 с.], использование конечного поля в векторной форме представления не приводит к изменению структурных свойств ЭК и к изменению сложности задачи дискретного логарифмирования на ЭК, которая определяет безопасность способов генерации и проверки ЭЦП, построенных с использованием ЭК. При заданном размере поля, над которым задается ЭК, уровень стойкости способов генерации и проверки ЭЦП с использованием векторных конечных полей не ниже стойкости способов генерации и проверки ЭЦП с использованием простых конечных полей и расширенных конечных полей. Таким образом, заявленный технический результат повышения производительности способов генерации и проверки ЭЦП достигается с сохранением высокого уровня стойкости ЭЦП.

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

Изобретение относится к области электросвязи, а именно к области криптографических устройств и способов проверки электронной цифровой подписи (ЭЦП). Технический результат - повышение производительности алгоритмов ЭЦП без снижения ее уровня стойкости. Способ генерации и проверки ЭЦП включает следующую последовательность действий: генерируют эллиптическую кривую (ЭК) над конечным полем в виде совокупности точек, каждая из которых определяется парой элементов конечного поля, формируют секретный ключ в виде многоразрядного двоичного числа k, по секретному ключу формируют открытый ключ в виде точки Р ЭК, принимают электронный документ (ЭД), в зависимости от принятого ЭД и от значения k формируют ЭЦП Q, формируют первую А и вторую В проверочные битовые строки, сравнивают их и при совпадении порядка следования единичных и нулевых битов в проверочных битовых строках А и В делают вывод о подлинности электронной цифровой подписи. Генерируют ЭК над векторным конечным полем. 4 з.п. ф-лы, 7 табл.

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

2. Способ по п.1, отличающийся тем, что генерируют эллиптическую кривую над векторным конечным полем, заданным над простым конечным полем GF(p), где р - характеристика поля, причем р>3.

3. Способ по п.1, отличающийся тем, что генерируют эллиптическую кривую над векторным конечным полем, заданным над конечным полем многочленов GF(р^s), где s - степень расширения поля и р - характеристика поля, причем р=3.

4. Способ по п.1, отличающийся тем, что генерируют эллиптическую кривую над векторным конечным полем, заданным над конечным полем многочленов GF(p^s), где s - степень расширения поля и р - характеристика поля, причем р=2.

5. Способ по п.1, отличающийся тем, что генерируют эллиптическую кривую над векторным конечным полем, заданным над конечным полем многочленов GF(p^s), где s - степень расширения поля и р - характеристика поля, причем р>3.