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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

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

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

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

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

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

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

осуществляют процедуру проверки подлинности ЭЦП, включающую вычисление двух контрольных параметров с использованием исходных МДЧ р, G, Y, Н и S путем возведения МДЧ G, Y, R в дискретную степень по модулю p и сравнение вычисленных контрольных параметров;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

nА=А+А+…+А (n раз).

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

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

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

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

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

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

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

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

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

Поставленная цель достигается тем, что в известном способе формирования и проверки подлинности ЭЦП, заверяющей ЭД, заключающемся в том, что генерируют секретный ключ в виде, по крайней мере, одной битовой строки, по секретному ключу формируют открытый ключ Y в виде более чем одной БС, принимают ЭД, представленный БС Н₁, Н₂, …, Н_z, где z≥1, в зависимости от принятого ЭД и от значения секретного ключа формируют ЭЦП Q в виде совокупности МДЧ е, s₁, s₂, …, s_u, где 1≤u≤8, в зависимости от открытого ключа, принятого ЭД и ЭЦП, формируют первую А и вторую В проверочные БС, сравнивают их и при совпадении их параметров делают вывод о подлинности ЭЦП, новым в заявленном изобретении является то, открытый ключ Y формируют в виде w-мерного, где 2≤m≤64, вектора путем генерации w-мерных векторов G₁, G₂, …, G_u, координатами каждого из которых являются БС разрядностью r, где 16≤r≤512, генерации секретного ключа в виде МДЧ k₁, k₂, …, k_u и генерации открытого ключа Y по формуле

,

где знак ° обозначает операцию умножения векторов.

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

Новым является также и то, что открытый ключ Y формируют в виде m-мерного, где 2≤m≤64, вектора МДЧ путем генерации m-мерных векторов МДЧ G₁, G₂, …, G_u, координатами каждого из которых являются МДЧ разрядностью r, где 16≤r≤512, генерации секретного ключа в виде МДЧ k₁, k₂, …, k_u и генерации открытого ключа Y по формуле

,

где знак ° обозначает операцию умножения векторов МДЧ.

Использование в качестве векторов БС векторов МДЧ позволяет эффективно реализовать заявленный способ в программах для ЭВМ.

Новым является также и то, что открытый ключ Y формируют в виде m-мерного, где 2≤m≤64, вектора многочленов путем генерации m-мерных векторов многочленов G₁, G₂, …, G_u, координатами каждого из которых являются многочлены разрядностью r, где 16≤r≤512, генерации секретного ключа в виде МДЧ k₁, k₂, …, k_u и генерации открытого ключа Y по формуле

,

где знак ° обозначает операцию умножения векторов многочленов.

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

Новым является также то, что открытый ключ Y формируют в виде m-мерного, где m=2, вектора путем генерации m-мерных векторов G₁ и G₂, имеющих порядок, равный простому МДЧ q, генерации секретного ключа в виде МДЧ k₁ и k₂ и генерации открытого ключа Y по формуле

,

принимают ЭД, представленный БС Н₁, а ЭЦП формируют в виде трех МДЧ е, s₁ и s₂, для чего генерируют случайные МДЧ t₁ и t₂, генерируют вектор R по формуле

,

затем в зависимости от R и Н₁ формируют первое МДЧ е ЭЦП по формуле e=f(R,Н₁), где f(R,Н₁) - выражение, задающее правило вычисления МДЧ е, затем в зависимости от секретного ключа генерируют пару МДЧ s₁ и s₂ ЭЦП по формулам

s₁=(t₁-k₁e)mod q и s₂=(t₂-k₂e)mod q,

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

A=f(R',H₁) и B=e,

где вектор R' вычисляют по формуле

.

Генерация двух различных секретных ключей позволяет повысить стойкость алгоритма ЭЦП при использовании нециклических групп векторов за счет использования векторов БС G₁ и G₂ размерности m=2, генерирующих циклические подгруппы нециклической группы векторов, такие, что они не попадают в какую либо одну циклическую подгруппу нециклической группы векторов.

Новым является также и то, что открытый ключ Y формируют в виде m-мерного, где m=3, вектора путем генерации w-мерных векторов G₁, G₂ и G₃, имеющих порядок, равный простому МДЧ q, генерации секретного ключа в виде МДЧ k₁, k₂ и k₃ и генерации открытого ключа Y по формуле

,

принимают ЭД, представленный БС H₁, а ЭЦП формируют в виде четырех битовых строк е, s₁, s₂, и s₃, для чего генерируют случайные МДЧ t₁, t₂, и t₃, генерируют вектор R по формуле

,

затем в зависимости от R и Н₁ формируют первое МДЧ е ЭЦП по формуле е=f(R,Н₁), где f(R,H₁) - выражение, задающее правило вычисления МДЧ е, затем в зависимости от секретного ключа генерируют тройку МДЧ s₁, s₂, и s₃ ЭЦП по формулам

s₁=(t₁-k₁e)mod q, s₂=(t₂-k₂e)mod q

и s₃=(t₃-k₃e)mod q,

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

A=f(R',H₁) и B=e,

где вектор R' вычисляют по формуле

.

В качестве выражения e=f(R,H₁) может быть, например, использована формула е=rH₁mod δ, где r=(r₁||r₂||r₃) - МДЧ, заданное конкатенацией БС, являющихся координатами вектора БС R, и δ - вспомогательное простое МДЧ. Генерация трех различных секретных ключей позволяет повысить стойкость алгоритма ЭЦП при использовании нециклических групп векторов БС за счет использования векторов БС G₁, G₂ и G₃, размерности m=3, генерирующих циклические подгруппы нециклической группы векторов БС, такие, что они попарно не попадают в какую либо одну циклическую подгруппу нециклической группы векторов БС. Конкатенацией двух БС а и b, представленных в виде и , называется БС . Знак || обозначает операцию конкатенации.

Новым является также и то, что открытый ключ Y формируют в виде m-мерного, где m=5, вектора путем генерации m-мерных векторов G₁ и G₂, имеющих порядки, равные МДЧ q₁ и q₂, соответственно, генерации секретного ключа в виде МДЧ k₁ и k₂ и генерации открытого ключа Y по формуле

,

принимают ЭД, представленный БС Н₁, а ЭЦП формируют в виде трех МДЧ е, s₁ и s₂, для чего генерируют случайные МДЧ числа t₁ и t₂, генерируют вектор R по формуле

,

затем в зависимости от R и Н₁ формируют первое МДЧ е ЭЦП по формуле е=f(R',H₁), где f(R,H₁) - выражение, задающее правило вычисления числа е, затем в зависимости от секретного ключа генерируют пару МДЧ s₁ и s₂ ЭЦП по формулам

s₁=(t₁-k₁e)mod q₁ и s₂=(t₂-k₂e)mod q₂,

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

A=f(R',H₁) и B=e,

где вектор R вычисляют по формуле

.

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

Новым является также и то, что открытый ключ Y формируют в виде m-мерного, где m=3, вектора путем генерации m-мерного вектора G₁, имеющего порядок, равный МДЧ q, генерации секретного ключа в виде МДЧ k₁ и генерации открытого ключа Y по формуле , принимают ЭД, представленный БС H₁, а ЭЦП формируют в виде двух МДЧ е и s₁, для чего генерируют случайное МДЧ t, генерируют вектор R по формуле R=G^t, затем в зависимости от R и Н₁ формируют первое МДЧ е ЭЦП по формуле e=f(R,H₁), где f(R,H₁) - выражение, задающее правило вычисления числа е, затем в зависимости от секретного ключа генерируют второе МДЧ s₁ ЭЦП по формуле

s₁=(t+k₁e)mod q,

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

А=f(R',Н₁) и В=е,

где вектор R' вычисляют по формуле

.

Новым является также и то, что открытый ключ Y формируют в виде m-мерного, где 2≤m≤8, вектора путем генерации m-мерных векторов G₁, G₂, …, G_m, имеющих порядок, равный простому МДЧ q, генерации секретного ключа в виде МДЧ k₁, k₂, …, k_m и генерации открытого ключа Y по формуле

,

принимают ЭД, представленный БС Н₁, Н₂, …, Н_m, а ЭЦП формируют в виде совокупности МДЧ е, s₁, s₂, …, s_m, для чего генерируют случайные МДЧ t₁, t₂, …, t_m, генерируют вектор R по формуле

,

затем в зависимости от R формируют первое МДЧ число е ЭЦП по формуле е=f(R,H), где f(R,H) - выражение, задающее правило вычисления числа е, и Н=H₁||H₂||H₃||…||H_m, где знак || обозначает операцию конкатенации, затем в зависимости от секретного ключа генерируют m МДЧ s₁, s₂, …, s_m ЭЦП по формулам

s₁=(t₁-k₁e)H₁ ^-1mod q, s₂=(t₂-k₂e)H₂ ^-1mod q, …,

…, s_m=(t_m-k_me)H_m ^-1mod q,

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

A=f(R',H) и В=е,

где вектор R вычисляют по формуле

.

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

Вектор БС - это набор из двух или более БС, называемых координатами вектора БС. Вектор БС записывается различными способами, требование к которым состоит в том, чтобы они идентифицировали позиции координат вектора БС. Например, вектор БС можно записать в виде (a₁, a₂, …, a_m), где m≥2 - это размерность вектора БС, равная числу координат в векторе БС. В качестве разделителя может быть использован знак операции сложения векторов БС, определенной как сложение одноименных координат двух векторов БС, являющихся слагаемыми. При использовании такого разделителя координаты вектора идентифицируются указанием формального базисного вектора (устанавливаемого перед или после соответствующей координаты) в виде буквы латинского алфавита. Формальными базисные вектора называются потому, что им не приписывается никакого физического смысла. Они служат только для того, чтобы идентифицировать координаты вектора БС, независимо от последовательности их записи. Так, например, вектора БС Z₁=523425e+3676785i+53453453j и Z₂=3676785i+523425e+53453453j, в которых координатами являются МДЧ, рассматриваются как равные, т.е. Z₁=Z₂. Отдельные слагаемые в такой записи векторов БС называются компонентами вектора БС, поскольку они представляют собой вектора БС с одной ненулевой координатой. Размерность вектора БС - это количество БС, входящих в вектор БС в качестве его координат. В данной заявке рассматриваются конечные группы векторов БС, т.е. алгебраические группы, элементами которых являются вектора БС вида Z=ае+bi+…+cj, а групповая операция определена через операции над векторами БС как операция перемножения компонентов векторов БС, являющихся операндами, с учетом того, что возникающие при этом произведения формальных базисных векторов, заменяются по некоторой специфицированной таблице одним базисным вектором или однокомпонентным вектором, т.е. вектором, содержащим только одну ненулевую координату. Такая таблица умножения базисных векторов для случая векторов БС размерности m=3 имеет, например, следующий вид:

Эта таблица определяет следующее правило подстановки базисных векторов:

e·i→i, e·j→j, j·i→e, i·i→j, j·j→i и т.д.

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

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

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

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

В случае векторов МДЧ в качестве координат вектора МДЧ могут быть заданы целые числа из конечного кольца целых чисел, являющихся остатками от деления всех целых чисел на составное натуральное число. Возможный вариант таких случаев подробно описан в примере 6, приведенном ниже.

В зависимости от размерности векторов БС, над которыми определяются операции умножения, и конкретного варианта задания операции умножения векторов БС могут быть использованы различные таблицы умножения базисных векторов, например, для векторов БС размерности m=2 приемлемая таблица имеет вид таблицы 2, где 0<ε<р, а для векторов БС размерности m=3 - вид таблицы 3, где 0<ε<р. Значение параметра ε, называемого коэффициентом растяжения, может выбираться произвольно из указанного интервала. Различные значения параметра ε придают различные свойства конечной группе векторов БС при фиксированном значении размерности m и модуля р. Таблицы умножения базисных векторов для случая векторов МДЧ и векторов многочленов, представляющих частные варианты задания векторов БС, имеют одинаковый вид, за исключением того, что в случае векторов МДЧ коэффициент ε представляет собой некоторое МДЧ, а в случае векторов многочленов коэффициент ε представляет собой некоторый многочлен.

Аналогичным способом могут быть определены групповые операции над конечными группами векторов БС размерностей m=4, m=5 и т.д. Например, правила умножения базисных векторов для случая m=7 приведены в следующей таблице 4, где в качестве коэффициентов растяжения p, τ, λ, ε, µ и τ могут быть использованы произвольные шесть значений, являющихся многочленами в случае, когда вектора БС представляют собой вектора многочленов, или являющихся МДЧ в случае, когда вектора БС представляют собой вектора МДЧ.

При соответствующем выборе таблицы умножения базисных векторов и простого значения р множество векторов МДЧ является конечным и это конечное множество содержит подмножество векторов МДЧ, которое образуют группу с групповой операцией причем порядок этой подгруппы является достаточно большим. Группа - это алгебраическая структура (т.е. множество математических элементов некоторой природы), над элементами которой задана некоторая операция таким образом, что алгебраическая структура обладает следующим набором свойств: операция ассоциативна, результатом выполнения операции над двумя элементами является элемент этой же структуры, существует нейтральный элемент такой, что при выполнении операции над ним и другим некоторым элементом а группы результатом является элемент а. Детальное описание групп дано в широко доступной математической литературе, например в книгах [А.Г.Курош. Теория групп.- М., изд-во «Наука», 1967. - 648 с.] и [М.И.Каргаполов, Ю.И.Мерзляков. Основы теории групп.- М., изд-во «Наука. Физматлит», 1996. - 287 с.]. Операция, определенная над элементами группы, называется групповой операцией. Группа называется циклической, если каждый ее элемент может быть представлен в виде g=аⁿ для некоторого натурального числа n, где а - элемент данной подгруппы, называющийся генератором или образующим элементом циклической подгруппы, и степень n означает, что над элементом а выполняются n последовательных операций, т.е. (n раз). Известно, что, если порядок группы есть простое число, то она циклическая [А.И. Кострикин. Введение в алгебру. Основы алгебры. М.: Физматлит. 1994. - 320 с.]. Важной характеристикой группы является ее порядок, который равен числу элементов в группе. Для элементов группы также применяется понятие порядка. Порядком элемента группы является минимальное значение степени, в которую нужно возвести этот элемент, чтобы результатом операции было получение нейтрального элемента группы.

Обычно при разработке способов формирования и проверки ЭЦП используются циклические группы большого простого порядка или группы, порядок которых делится нацело на большое простое число [Венбо Мао. Современная криптография. Теория и практика. - М., СПб, Киев. Издательский дом «Вильямс», 2005. - 763 с.]. При соответствующем задании группы векторов БС это условие легко обеспечивается. При этом стойкость способов формирования и проверки ЭЦП определяется сложностью задачи дискретного логарифмирования, которая состоит в определении значения степени n, в которую надо возвести заданный элемент группы, чтобы результатом этой операции был некоторый другой заданный элемент группы [Молдовян НА. Практикум по криптосистемам с открытым ключом. - СПб. БХВ-Петербург, 2007. - 298 с.].

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

Порядком вектора БС V называется наименьшее натуральное число q, такое что V^q=1, т.е. такое, что результатом умножения вектора МДЧ Q на самого себя q раз является единичный вектор МДЧ Е=1e+0i+…+0j=(1, 0, 0,…, 0).

В частных случаях задания конечного множества векторов БС оно будет представлять расширенное поле, в котором все ненулевые вектора БС составляют циклическую мультипликативную группу [Молдовян Н.А. Алгоритмы аутентификации информации в АСУ на основе структур в конечных векторных пространствах // Автоматика и телемеханика (М., РАН), 2008]. В других частных случаях формируемые группы являются нециклическими, в которых содержится q+1 циклических подгрупп простого порядка q, где q является делителем порядка поля, над которым заданы вектора БС. При этом значение q является достаточно большим, благодаря чему нециклические группы векторов БС могут быть основой для реализации стойких алгоритмов ЭЦП даже в случае, когда размер максимального простого порядка подгрупп составляет 60-100 бит и менее. Это обеспечивается за счет того, что открытый ключ формируется на основе нескольких заданных векторов БС, входящих в разные подгруппы простого порядка, которые имеют единственный общий элемент - единичный вектор БС. Данный механизм задания открытого ключа в способах формирования и проверки ЭЦП является новым и ранее неизвестным.

Корректность заявленного способа доказывается теоретически. Рассмотрим, например, вариант реализации способа по п.9 формулы изобретения. Открытый ключ, соответствующий секретному ключу k, представляет собой вектор БС Y=G^k. Вектор БС R генерируется по формуле R=G^k, а первое МДЧ в ЭЦП (e, s) вычисляется по формуле е=f(R,H). Значение s генерируется по формуле s=(k+ex) mod q, поэтому вектор МДЧ R', генерируемый по формуле и используемый для формирования первого проверочного МДЧ А, равен

Поскольку вектора МДЧ R' и R одинаковы, то равны между собой и значения е'=f(R',H) и e=f(R,H), т.е. А=е'=е=В. Таким образом, правильно сформированная ЭЦП подпись удовлетворяет процедуре проверки подписи, т.е. корректность процедур генерации и проверки ЭЦП доказана. Аналогичным образом дается доказательство корректности и для пп.5-8 формулы изобретения.

Особенностью пп.5-7 и п.11 формулы изобретения является использование нескольких различных векторов БС G₁,…, G_u (G₁ и G₂ в пп.5 и 7; G₁, G₂ и G₃, в п.6; G₁, G₂,…, G_m в п.11), по которым вычисляется открытый ключ и которые входят в соответствующие формулы проверки подлинности ЭЦП. Этот признак является новым в области способов формирования и проверки ЭЦП и имеет принципиальное значение для случая использования конечных групп векторов БС, которые являются нециклическими. В нециклических группах векторов БС отсутствуют отдельные значения векторов БС, степени которого могут выразить любой вектор БС. Используемые различные значения G₁, G₂ и G₃ относятся к различным циклическим подгруппам нециклической группы векторов БС, поэтому для определения секретного ключа по