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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

формируют первое проверочное МДЧ А, для чего генерируют МДЧ R' по формуле R'=a ^sy^-emod р и формируют МДЧ

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

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

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

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

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

х_C=k²-х_А-х_Bmodр и y_C=k(х_А-х_C)-y_Аmodр,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поставленная цель достигается тем, что в известном способе формирования и проверки подлинности ЭЦП, заверяющей ЭД, заключающемся в том, что генерируют секретный ключ в виде, по крайней мере, одной БС, по секретному ключу формируют открытый ключ Y в виде более чем одной БС, принимают ЭД, представленный БС H₁, Н₂,…, Н_z, где z≥1, в зависимости от принятого ЭД и от значения секретного ключа формируют ЭЦП Q в виде, по крайней мере, двух БС, в зависимости от открытого ключа, принятого ЭД и ЭЦП формируют первую А и вторую В проверочные БС, сравнивают их и при совпадении их параметров делают вывод о подлинности ЭЦП, новым в заявленном изобретении является то, что открытый ключ Y формируют в виде, по крайней мере, одного, m-мерного, где 2≤m≤64, вектора БС, формируют ЭЦП Q в виде, по крайней мере, одной БС и, по крайней мере, одного m-мерного вектора БС, а при осуществлении процедуры формирования, по крайней мере, одной проверочной БС выполняется операция возведения m-мерного вектора БС ЭЦП в целочисленную степень w>1.

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

Новым является также и то, что открытый ключ Y формируют в виде m-мерного, где 2≤m≤64, вектора МДЧ.

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

Новым является также и то, что открытый ключ Y формируют в виде m-мерного, где 2≤m≤64, вектора многочленов.

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

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

Новым является также то, что генерируют секретный ключ в виде m-мерного, где m=2, вектора БС К и открытый ключ Y формируют в виде двухмерного вектора БС по формуле Y=K^w, где w - вспомогательное МДЧ, принимают ЭД, представленный БС Н₁, а ЭЦП формируют в виде БС е и двухмерного вектора БС S, для чего генерируют случайный двухмерный вектор БС Т, генерируют вектор БС R по формуле R=T^w, затем формируют первую БС е ЭЦП в виде МДЧ, вычисляемого в зависимости от R и Н₁ по формуле e=f(R,H₁), где f(R,H₁) - выражение, задающее правило вычисления МДЧ е, затем генерируют двухмерный вектор БС S ЭЦП по формуле где знак обозначает операцию умножения векторов БС, после чего формируют первую и вторую проверочные БС А и В по формулам А=f(R',H₁) и B=e, где вектор БС R' вычисляют по формуле В качестве выражения e=f(R,H₁) может быть, например, использована формула е=rH₁mod δ, где - МДЧ, равное конкатенации МДЧ, входящих в состав вектора МДЧ R, и δ - вспомогательное простое МДЧ. Таким образом, при формировании проверочной БС А над вектором БС S ЭЦП выполняется операция возведения в целочисленную степень w>1. Конкатенацией двух БС а и b, представленных в виде а=a ₁ a ₂ a ₃…a _g и bm=b₁b₂b₃…b_k называется БС Знак обозначает операцию конкатенации.

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

Новым является также и то, что генерируют секретный ключ в виде двух m-мерных, где m=3, векторов БС K₁ и К₂, открытый ключ Y формируют в виде трехмерного вектора БС по формуле где w₁ и w₂ - вспомогательные МДЧ, и принимают ЭД, представленный БС H₁ и Н₂, а ЭЦП формируют в виде битовой строки е и двух трехмерных векторов БС S₁ и S₂, для чего генерируют два случайных трехмерных вектора БС T₁ и Т₂, генерируют вектор БС R по формуле затем формируют первую БС е ЭЦП в виде МДЧ, вычисляемого в зависимости от R, Н₁ и Н₂ по формуле е=f(R,H₁,H₂), где f(R,H₁,H₂) - выражение, задающее правило вычисления МДЧ е, затем генерируют трехмерные вектора БС S₁ и S₂ ЭЦП по формулам и после чего формируют первую и вторую проверочные БС А и В по формулам А=f(R',H₁,H₂) и В=е, где вектор БС R' вычисляют по формуле

Генерация открытого ключа по двум различным секретным векторам БС K₁ и К₂ позволяет повысить стойкость алгоритма ЭЦП за счет неопределенности вычисления пары секретных ключей по одному открытому ключу. В этом частном варианте реализации заявленного способа при формировании проверочной БС А над векторами БС S₁ и S₂ ЭЦП выполняются операции возведения в целочисленную степень w₁>1 и w₂>1 соответственно.

Новым является также и то, что генерируют секретный ключ в виде МДЧ k и m-мерного, где m=2, вектора БС К и открытый ключ Y формируют в виде двухмерного вектора БС, для чего генерируют вектор БС G размерности m=2, имеющий порядок, равный МДЧ q, после чего открытый ключ Y генерируют по формуле где w - вспомогательное МДЧ, принимают ЭД представленный БС H₁ а ЭЦП формируют в виде двухмерного вектора БС S и двух БС е и s, для чего генерируют случайное МДЧ t и случайный двухмерный вектор БС Т, генерируют вектор БС R по формуле затем формируют первую БС е электронной цифровой подписи в виде МДЧ, вычисляемого в зависимости от R и H₁ по формуле e=f(R,H₁), где f(R,H₁) - выражение, задающее правило вычисления МДЧ е, затем генерируют двухмерный вектор БС S ЭЦП, вычисляемый по формуле где S=(s₁,s₂), и вторую БС s ЭЦП в виде МДЧ, вычисляемого по формуле после чего формируют первую и вторую проверочные БС А и В по формулам А=f(R',Н₁) и В=е, где вектор БС R' вычисляют по формуле где F(S)=s₁.

Генерация открытого ключа по двум различным секретным элементам k и К позволяет повысить стойкость алгоритма ЭЦП за счет неопределенности вычисления пары секретных элементов по одному открытому ключу.

Новым является также и то, что генерируют секретный ключ в виде МДЧ k и m-мерного, где m=2, вектора БС К и открытый ключ Y формируют в виде двух двухмерных векторов БС Y₁ и Y₂, для чего генерируют вектор БС G размерности m=2, имеющий порядок, равный МДЧ q, после чего вектора БС Y₁ и Y₂ открытого ключа Y генерируют по формулам Y₁=G^k и Y₂=K^w, где w - вспомогательное МДЧ, принимают ЭД, представленный БС Н₁ и Н₂, а ЭЦП формируют в виде двухмерного вектора БС S и двух БС e и s, для чего генерируют случайное МДЧ t и случайный двухмерный вектор БС Т, генерируют вектор БС R по формуле R=G^t⊕T^w, где ⊕ обозначает операцию сложения векторов БС, затем формируют первую БС е ЭЦП в виде МДЧ, вычисляемого в зависимости от R, Н₁ и Н₂ по формуле е=f(R,H₁,H₂), где f(R,H₁,Н₂) - выражение, задающее правило вычисления МДЧ е, затем генерируют двухмерный вектор БС S ЭЦП, вычисляемый по формуле и вторую БС s ЭЦП в виде МДЧ, вычисляемого по формуле после чего формируют первую и вторую проверочные БС А и В по формулам А=f(R',H₁,H₂) и В=е, где вектор БС R' вычисляют по формуле

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

Новым является также и то, что генерируют секретный ключ в виде двух m-мерных, где m=5, векторов БС С и К, открытый ключ Y формируют в виде пятимерного вектора БС, генерируемого по формуле где w - вспомогательное МДЧ, принимают ЭД, представленный БС Н₁, а ЭЦП формируют в виде пятимерного вектора БС S и двух БС е и s, для чего генерируют случайное МДЧ t и случайный пятимерный вектор БС Т, генерируют вектор БС R по формуле R=С^t·Т^w, затем формируют первую БС е ЭЦП в виде МДЧ, вычисляемого в зависимости от R и H₁ по формуле e=f(R,H₁), где f(R,H₁) - выражение, задающее правило вычисления МДЧ е, формируют вторую БС s ЭЦП в виде МДЧ, вычисляемого по формуле s=е^-1t mod q, затем генерируют пятимерный вектор БС S ЭЦП, вычисляемый по формуле после чего формируют первую и вторую проверочные БС А и В по формулам A=f(R',H₁) и В=е, где вектор БС R' вычисляют по формуле

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

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

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

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

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

где знак обозначает операцию суммирования векторов, а знак + обозначает операцию суммирования БС, представляющих собой координаты векторов БС.

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

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

Сложение векторов БС Z₁=(a ₁e⊕b₁i⊕…⊕c₁j) и Z₂=а ₂е⊕b₂i⊕…⊕c₂j выполняется как сложение одноименных координат, т.е. в соответствии со следующей формулой:

Z₁⊕Z₂=(a ₁e⊕b₁i⊕…⊕c₁j)⊕(a ₂e⊕b₂i⊕…⊕c₂j)=

=(a ₁+b₁modp)e⊕(b₁+b₂modp)i⊕(c₁+c₂modp)j,

где знак ⊕ обозначает операцию суммирования векторов, а знак + обозначает операцию суммирования МДЧ или многочленов в случаях, когда БС представляют собой МДЧ или многочлены соответственно.

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

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

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

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

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

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

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

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

В частных случаях задания конечного множества векторов БС оно будет представлять расширенное поле, в котором все ненулевые вектора БС составляют циклическую мультипликативную группу [Молдовян Н.А. Алгоритмы аутентификации информации в АСУ на основе структур в конечных векторных пространствах. // Автоматика и телемеханика (М.: РАН), 2008].

В других частных случаях формируемые группы являются нециклическими, в которых содержится q+1 циклических подгрупп простого порядка q, где q является делителем порядка поля, над которым заданы вектора БС. При этом значение q является достаточно большим, благодаря чему нециклические группы векторов БС могут быть основой для реализации стойких алгоритмов ЭЦП даже в случае, когда размер максимального простого порядка подгрупп составляет 60-100 бит и менее. В нециклических группах задача извлечения корней большой простой степени w в случае, когда значение w² делит значение порядка нециклической группы, имеет повышенную трудность. Поэтому формирование открытого ключа путем возведения в степень w секретного ключа, представляющего собой вектор БС, может быть положено в основу стойких способов формирования и проверки подлинности ЭЦП, обеспечивающих более высокую производительность по сравнению с известными способами-аналогами.

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

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

При использовании на практике заявляемого способа следует выбрать таблицу умножения базисных векторов и размер параметров р, w и q таким образом, чтобы разрядность значения степени w и разрядность значения порядка q были равны или превышали 32, 40, 64, 80 и 160 бит, в зависимости от конкретного варианта реализации заявленного способа. В приводимых ниже примерах, содержащих численные значения результатов промежуточных операций, используются параметры с искусственно уменьшенной разрядностью, чтобы уменьшить размер примеров и сделать их более наглядными. Примеры иллюстрируют частные варианты реализации заявленного способа и демонстрируют их корректность как способа формирования и проверки ЭЦП.

Пример 1

Данный пример иллюстрирует вариант реализации заявленного способа, соответствующий п.4 формулы изобретения, в котором действия выполняются над двухмерными векторами БС. Для получения конечной группы двухмерных векторов БС вида (а,b)=ае⊕bi БС а и b интерпретируются как МДЧ, над которыми определены операции умножения и сложения координат, выполняемые по модулю целого положительного числа М. В данном примере групповая операция выполняется с использованием таблицы 2. В соответствии с этой таблицей умножения базисных векторов для случая размерности m = 2 имеем i·i=ε, где ε∈{1,…,М-1}. Операция умножения двухмерных БС (а, b) и (с, d) выполняется по правилу:

(a,b)(c,d)=((ас+εbd)modМ,(ad+bc)modM)=g'e⊕h'i,

где g'=(ac+εbd)modM и h'=(ad+bc)modM. Легко проверить, что определенные таким образом операции сложения и умножения обладают свойствами ассоциативности и коммутативности. Среди алгебраических структур такого типа имеются конечные поля и мультипликативные группы, существенным свойством которых является наличие единицы Е=(1,0) - нейтрального элемента по умножению, который определяет существование для каждой ненулевой пары А единственного обратного значения А^-1, такого, что АА^-1=Е.

Группа - это алгебраическая структура с ассоциативной операцией, для которой существует обратная операция [Курош А.Г. Курс высшей алгебры. - М.: «Наука», 1971. - 431 с.], т.е. уравнения

АХ=В и YA=В

имеют единственное решение для любых элементов А и В. Поскольку определенная выше операция умножения является коммутативной, то указанные уравнения являются эквивалентными и можно рассматривать только одно из них. Легко показать, что однозначность решения указанных уравнений выполняется, если для каждого элемента А существует единственное обратное значение А^-1, поэтому представляет интерес рассмотреть решение уравнений вида АХ=Е, которое можно представить следующим образом:

(ае+bi)(хе+yi)=((ах+εby)modМ)е⊕((ay+bx)modМ)i=1е⊕0i.

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

Рассмотрим существование решений этой системы для случая использования в качестве модуля простого МДЧ р, т.е. М=р. Приравнивая нулю главный определитель этой системы, получаем характеристическое уравнение

e²-εb²=0modр.

Значение (а, b)=(0, 0) является решением характеристического уравнения для любых значений модуля, поэтому для этой пары не существует обратного значения. Значения р и а можно выбрать таким образом, что характеристическое уравнение не имеет других решений, а значит рассматриваемая система сравнений имеет единственное решение для любой пары (а, b)≠(0, 0). Рассмотрим несколько важных частных случаев.

Случай 1. Значительный интерес представляет выбор в качестве параметра а значения, которое является квадратичным невычетом по модулю р. В этом случае получаем структуру, являющуюся конечным полем GF(p²), мультипликативная группа которого имеет порядок

Ω=р²-1=(р-1)(р+1).

Задавая различные значения модуля р и параметра а, получаем различные варианты конечного поля типа GF(p²). Для заданного значения р имеем (р-1)/2 различных вариантов поля GF(p²), включающих одно и то же множество элементов, но отличающихся видом операции умножения, соответственно числу различных квадратичных невычетов по модулю р.

Случай 2 (данный случай формирования групп двухмерных векторов БС используется ниже в примере 3 для иллюстрации частного варианта реализации заявленного способа по п.6 формулы изобретения). Пусть в определении операции умножения используется параметр ε, который является квадратичным вычетом по модулю р. При этих условиях характеристическое уравнение имеет, кроме (а, b)=(0, 0), еще 2(р-1) следующих решений вида

(ε^1/2bmodр,b) и (-ε^1/2bmodр,b),

где b∈{0,1,…,p-1}. Для пар такого вида не существует решений системы сравнений, которые определяют значение обратных элементов. Следовательно, количество элементов, для которых существуют единственные обратные значения равно

Ω=р²-2(р-1)-1=(p-1)².

Эти элементы составляют мультипликативную группу, поскольку результат умножения любых двух элементов из этого множества является элементом этого же множества.

Случай 3 (этот случай используется в рассматриваемом примере для иллюстрации частного варианта реализации заявляемого способа по п.4 формулы изобретения). Особенностью этого случая является задание операций сложения и умножения над координатами вектора БС, выполняемых по модулю, который не является простым. В этом случае общий анализ условий существования групп и определение их порядка является более сложным. Однако интересующий нас следующий частный случай составного модуля М=w², где w - простое число, позволяет получить формулы для расчета порядка группы при произвольных значениях простого МДЧ w.

Пусть используется значение M=w², где w - простое число, в качестве модуля, а параметр а делится на w. При этих условиях для элементов (а, b), таких, что а не делится на w, характеристическое уравнение не имеет решений, поскольку w|ε, а определитель системы сравнений является взаимно простым с модулем М=w², т.е. для каждого из указанных элементов имеются обратные значения. При этом операция умножения двух элементов дает третий элемент, в котором первая координата также не делится на w, т.е. операция умножения является замкнутой на указанном множестве пар (а, b). Следовательно, это множество является группой, порядок которой можно определить из того факта, что число возможных значений первой координаты равно функции Эйлера от модуля φ(М)=φ(w²)=w(w-1), число возможных значений второй координаты равно М=w². Получаем следующую формулу для значения порядка построенной мультипликативной группы

Ω=w(w-1)·w²=w³(w-1).

Опыт показал, что в построенной группе содержится циклическая группа порядка

Ω'=w²(w-1),

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

Для реализации частного варианта заявленного по п.4 формулы изобретения воспользуемся нециклической группой БС Г, содержащей циклические подгруппы, порядок которых делится на w². Формирование такой нециклической группы описан выше как случай 3. В данном конкретном примере, относящемся к использованию группы, порядок группы выражается формулой Ω=w³(w-1), где w - простое число. В группе Г существуют элементы порядка ω=w²(w-1). Возьмем значение

w=92618137318729677928546646365838873180498085133. Тогда имеем значение модуля

M=w²=8578119360391067054292626600438708965746964997146182659298964331315788956009108954679715627689.

В качестве коэффициента растяжения ε возьмем значение 101 w>, т.е. ε=9354431869191697470783211282949726191230306598433.

Выбор группы данного конкретного вида вносит определенную специфику в синтезируемый алгоритм ЭЦП. При генерации случайного секретного ключа К=(k₁, k₂)∈Г следует делать проверку: НОД(w,k₁)=1 и K^w(w-1)≠(1,0). Первое условие обеспечивает выбор в качестве секретного ключа элемента, принадлежащего группе Г. Второе условие обеспечивает выбор в качестве секретного ключа элемента, порядок которого делится на квадрат степени корня, что является требованием повышения стойкости ЭЦП. Аналогичную проверку следует выполнить и при генерации случайного вектора БС Т=(t₁, t₂)∈Г. Если указанное условие не выполняется (вероятность этого события мала) для случайно выбранных координат k₁ и k₂ (или для координат t₁ и t₂), то следует выбрать новые случайные значения координат k₁≤M=w² и k₂≤M=w² (или координат t₁≤M=w² и t₂≤M=w²).

В рассматриваемом частном варианте реализации п.4 формулы изобретения используются указанные выше значения параметров М, w, ε и выполняется следующая последовательность действий.

1. Генерируют секретный ключ К в виде двухмерного вектора БС, представленного двумя МДЧ:

К=(162748957475865968, 9787164395071945749328495).

2. Формируют открытый ключ Y в виде двухмерного вектора БС путем выполнения операции возведения секретного ключа в степень w в соответствии с формулой Y=K^w=(y₁,y₂). В результате генерируют следующие значения координат

y₁=21228784879778840523736855349044078599261832125691229247376837230 26454694663820975943984437961;

y₂=906468935903755351742894544834008526404457603521609627108387168092764835.

3. Принимают ЭД, представленный БС Н₁.

4. Формируют ЭЦП в виде трех БС е и двухмерного вектора БС S=(s₁, s₂), для чего выполняют следующую последовательность действий:

4.1. Генерируют случайный двухмерный вектор БС, в котором пара БС интерпретируется как пара МДЧ:

Т=(96846596736586738292216171, 37586931174658693746285927).

4.2. Генерируют вектор БС R путем выполнения операции возведения вектора БС Т в степень w в соответствии с формулой R=T^w=(r₁, r₂). В результате генерируют следующие значения координат вектора БС R:

r₁=6676527716822018383957988126039278418617223915758582479614295011535668063135439573548109332464;

r₂=3481231552924180293255968160466563282460623255695990065475962954205823291.

4.3. Формируют первую БС е ЭЦП в виде МДЧ, вычисляемого по формуле e=f(R,H₁), где f(R,H₁) - выражение, специфицирующее процедуру вычисления числа е. Пусть получено значение, равное

е=75867496586968496537352193793673918466970375638.

4.4. Вычисляют двухмерный вектор БС S=(s₁, s₂) ЭЦП, по формуле

s₁=8256594105547617216423939012826302237218370734284428450969373421295221722475025012259161992826;

s₂=422260754784925502959681748215173239940083978470857855504330212012892903897205453209052939744.

5. Проверяют подлинность ЭЦП, для чего выполняют следующую последовательность действий:

5.1. Формируют первую проверочную БС А, для чего:

5.1.1. Формируют вектор БС R' по формуле R'=Y^eS^w=(r'₁,r'₂):

r'₁=6676527716822018383957988126039278418617223915758582479614295011535668063135439573548109332464;

r'₂=3481231552924180293255968160466563282460623255695990065475962954205823291.

5.1.2. Генерируют первую проверочную ВС А по формуле А=f(R',H₁). Сравнение показывает, что R'=R, поэтому А=f(R',H)=f(R',H)=е, т.е. получают: А=75867496586968496537352193793673918466970375638.

5.2. Формируют вторую проверочную БС В путем копирования БС е, т.е. по формуле В=е: В=75867496586968496537352193793673918466970375638.

5.4. Сравнивают проверочные БС A и В.

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

Отметим, что при формировании проверочной БС А на шаге 5.1.1 выполняется операция возведения вектора БС S ЭЦП в целочисленную степень w>1, что является одним из отличительных признаков заявленного способа формирования и проверки ЭЦП.

Пример 2 (иллюстрация п.5 формулы изобретения)

Данный пример относится к варианту реализации заявленного способа по п.5 формулы изобретения. В нем используется группа, элементами которой являются вектора БС размерности m=3, над которыми определена операция умножения таким образом, что порядок группы равен (р-1)³, где р - простое число, такое, что р-1=3Nw₁w₂ (N - четное число). Операция умножения трехмерных БС выполняется при использовании таблицы 3 умножения базисных векторов, в которой в качестве коэффициента используется куб некоторого натурального числа, т.е. ε=z³ для некоторого натурального z. При указанных выше условиях максимальный порядок элементов группы равен р-1, где р - характеристика конечного простого поля, над которым заданы векторы БС, причем БС интерпретируются как МДЧ, а операции над БС выполняются как oпeрации над МДЧ. В данном примере не приводятся конкретные значения получаемых значений БС, а описываются результаты процедур формирования и генерации БС и векторов БС в обобщенном виде для произвольного случая. Подставляя вместо буквенных обозначений конкретные численные значения, могут быть построены различные варианты численной иллюстрации п.5 формулы изобретения. В данном примере акцент делается на корректность процедуры проверки подлинности ЭЦП, которая доказывается для общего случая. Выполняют следующую последовательность действий.

1. Генерируют секретный ключ в виде двух трехмерных векторов БС K₁ и К₂.

2. Формируют открытый ключ Y в виде трехмерного вектора БС по формуле где w₁ и w₂ - вспомогательные МДЧ, являющиеся делителями числа р-1.

3. Принимают ЭД, представленный двумя БС H₁ и H₂.

4. Формируют ЭЦП в виде МДЧ е и двух векторов БС S₁ и S₂, для чего выполняют следующие действия.

4.1. Генерируют два случайных трехмерных вектора БС T₁ и Т₂.

4.2. Генерируют трехмерный вектор БС R по формуле

4.3. Формируют первую БС е ЭЦП в виде МДЧ, вычисляемого в зависимости от R, H₁ и H₂ по формуле где знак - обозначает операцию конкатенации; r₁, r₂ и r₃ - БС, являющиеся координатами трехмерного вектора БС R.

4.4. Генерируют векторы БС S₁ и S₂ по формулам и

5. Формируют первую проверочную БС А, для чего выполняют следующие действия.

5.1. Формируют вектор БС R', выполняя вычисления по формуле (шаг 5.1, входящий в процедуру формирования проверочной БС А, включает выполнение операции возведения векторов БС S₁ и S₂ в целочисленную степень w₁>1 и w₂>1, что является одним из отличительных признаков заявленного способа формирования и проверки ЭЦП).

5.2. Формируют первую проверочную БС А по формуле где r'₁, r₂' и r₃' - БС, являющиеся координатами трехмерного вектора БС R'.

6. Формируют вторую проверочную БС В путем копирования БС е, т.е. по формуле В=е.

7. Сравнивают проверочные БС А и В.

Сравнение показывает, что параметры проверочных БС А и В совпадают, на основании чего делают вывод о подлинности ЭЦП. Тот факт, что при проверке ЭЦП, сформированной по процедуре формирования ЭЦП с использованием правильного секретного ключа, на шаге 7 будет получено совпадение параметров проверочных БС, доказывается следующим образом. Подставим в формулу, по которой формируется вектор БС R', значение БС е и значения векторов БС S₁ и S₂ ЭЦП, вычисленные по формулам S₁=T₁·К и S₂=Т₂·К (см. шаг 4.4), получим

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

Пример 3 (иллюстрация п.6 формулы изобретения)

Данный пример относится к варианту реализации заявленного способа по п.6 формулы изобретения. В данном примере используется нециклическая группа Г, содержащая циклические подгруппы, порядок которых делится на w². Формирование такой нециклической группы описано в примере 1 как случай 2. В данном конкретном примере, относящемся к использованию группы, порядок которой выражается формулой Ω=(р-1)², в группе Г существуют элементы порядка ω=(р-1)=Nw², где N - четное число и w - простое число достаточно большого размера.

В примере 1 в качестве модуля, по которому ведут вычисления, используется простое МДЧр=2qw²+1, где

р=757095462971039987; q=1433729993 - простое МДЧ;

w=16249 - простое МДЧ.

Выполняют следующую последовательность действий, используя значение параметра ε=152399025, являющегося квадратом числа 12345.

1. Генерируют секретный ключ в виде двухмерного вектора БС К=(k₁, k₂), представленного двумя МДЧ k₁ и k₂, и одной БС, представленной МДЧ k.

К=(k₁ k₂)=(162748957475865968,978716439507194574);

k =3678436295562.

2. Генерируют вектор БС G, порядок которого равен q:

G=(89833863138176218, 481445738651243524).

3. Формируют открытый ключ Y в виде двухмерного вектора БС, вычисляемого по формуле

G^k=(328752664651659001, 188933597249340036); K^w=(561576529082416854, 311520115027605902); Y=(y₁,y₂)=(355961954073853677, 52073643974617679).

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

5. Формируют ЭЦП в виде двух БС е и s и вектора S=(s₁, s₂), для чего выполняют следующую последовательность действий:

5.1. Генерируют случайную БС t и случайный двухмерный вектор БС, в которых БС интерпретируется как МДЧ:

t=2134356456473; Т=(64697680789267, 70914503766891).

5.2. Генерируют вектор БС R, выполняя вычисления по формуле

G^t=(633200307649534083, 225907802600880012); T^w=(334316797118875406, 694605535104513177).

В результате перемножения векторов БС G^t и T^w генерируют следующие значения координат вектора БС R:

R=(r₁, r₂)=(278285084410523629, 476437561152596152).

5.3. Формируют первую БС е ЭЦП в виде МДЧ, вычисляемого по формуле

e=f(R,H₁), где f(R,H₁) - выражение, специфицирующее процедуру вычисления числа е. Пусть получено значение, равное е=874095303603.

5.4. Вычисляют двухмерный вектор БС S ЭЦП по формуле

K^-е=K^р-1-e=(586016270354358239, 327468169526176273);

S=(s₁,s₂)=(120860422228891963, 483553947421564222).

5.5. Генерируют вторую БС s ЭЦП в виде МДЧ, вычисляемого по формуле s=s(t-ke)modq, предварительно вычисляя s=124122450:

s=222387665.

6. Проверяют подлинность ЭЦП, для чего выполняют следующую последовательность действий.

6.1. Формируют первую проверочную БС А, для чего выполняют следующие действия.

6.2. Формируют вектор БС R' по формуле где

s·F(S)=26877867090397379188836395;

G^s·F(S)=(117660193869193445, 78350012648906257);

Y^e=(45991950818968478, 376342549870250020);

S^w=(441809832936651938, 4975252013635854).

R'=(r'₁,r'₂)=(278285084410523629, 476437561152596152).

6.3. Формируют первую проверочную БС А по формуле А=f(R',H₁).

Сравнение показывает, что R'=R, поэтому A=f(R',Н₁)=f(R,Н₁)=е, т.е. имеем A=874095303603.

6.3. Формируют вторую проверочную БС В по формуле В=е:

B=874095303603.

6.4. Сравнивают проверочные БС А и В.

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

Отметим, что при формировании проверочной БС А на шаге 6.2. выполняется операция возведения вектора БС S ЭЦП в целочисленную степень w>1, что является одним из отличительных признаков заявленного способа формирования и проверки ЭЦП.

Пример 4 (иллюстрация п.7 формулы изобретения)

Данный пример относится к варианту реализации заявленного способа по п.7 формулы изобретения. В нем используется группа, элементами которой являются векторы БС размерности m=2, над которыми определена операция умножения таким образом, что порядок группы равен (р-1)², где р - простое число, такое, что р-1=Nw² (N - четное число). Операция умножения двухмерных БС выполняется при использовании таблицы 2 умножения базисных векторов, в которой в качестве коэффициента используется квадрат некоторого натурального числа, т.е. ε=z² для некоторого натурального z. При указанных выше условиях максимальный порядок элементов группы равен р-1, где р - характеристика конечного простого поля над которым заданы векторы БС, причем БС интерпретируются как МДЧ, а операции над БС выполняются как операции над МДЧ. Условия построения групп данного типа описаны в примере 1 (см. случай 2). В данном примере не приводятся конкретные значения получаемых значений БС, а описываются результаты процедур формирования и генерации БС и векторов БС в обобщенном виде для произвольного случая. Подставляя вместо буквенных обозначений конкретные численные значения, могут быть построены различные варианты численной иллюстрации п.7 формулы изобретения. В данном примере акцент делается на корректность процедуры проверки подлинности ЭЦП, которая доказывается в обобщенном виде. Выполняют следующую последовательность действий.

1. Генерируют секретный ключ в виде МДЧ k и двухмерного вектора БС К.

2. Формируют открытый ключ Y в виде в виде двух двухмерных векторов БС Y₁ и Y₂, для чего выполняют следующие действия:

2.1. Генерируют вектор БС G размерности m=2, имеющий порядок, равный МДЧ q.

2.2. Генерируют вектора БС Y₁ и Y₂ по формулам Y₁=G^k и Y₂=K^w, где w - вспомогательное МДЧ, являющееся делителем числа р-1.

3. Принимают ЭД, представленный БС Н₁ и H₂.

4. Формируют ЭЦП в виде двух МДЧ е и s вектора БС S, для чего выполняют следующие действия:

4.1. Генерируют случайное МДЧ t.

4.2. Генерируют случайный двухмерный вектор БС Т.

4.3. Генерируют двухмерный вектор БС R по формуле R=G^t⊕T^w, где знак ⊕ обозначает операцию сложения векторов БС.

4.3. Формируют БС е ЭЦП в виде МДЧ, вычисляемого в зависимости от R и Н по формуле где - обозначение операции конкатенации МДЧ; r₁ и r₂ - координаты двухмерного вектора БС R.

4.4. Генерируют вектор БС S по формуле

4.5. Формируют БС s ЭЦП в виде МДЧ, вычисляемого по формуле s=Н(t-kе)modq.

5. Формируют первую проверочную БС А, для чего выполняют следующие действия:

5.1. Формируют вектор БС R', выполняя вычисления по формуле

5.2. Генерируют проверочную БС А по формуле

где r'₁ и r'₂ - координаты вектора БС R'.

6. Формируют вторую проверочную БС В путем копирования БС е, т.е. по формуле В=е.

7. Сравнивают проверочные БС А и В.

При совпадении параметров проверочных БС А и B делают вывод о подлинности ЭЦП. Тот факт, что при проверке ЭЦП, сформированной по процедуре формирования ЭЦП с использованием правильного секретного ключа, на шаге 7 будет получено совпадение параметров проверочных БС, доказывается следующим образом. Подставим в формулу, по которой формируется вектор БС R', значение БС е, интерпретируемой как МДЧ, а также значение МДЧ s и значения вектора БС S, вычисленные по формулам s=H(t-kе)modq и получим

Поскольку R'=R, т.e. ()=(), a также A=()()modq и B=e=()()modq, то при подлинной ЭЦП имеет место А=В. Таким образом, корректность процедуры проверки подлинности ЭЦП доказана для рассмотренного частного варианта реализации заявленного способа.

Пример 5 (иллюстрация п.8 формулы изобретения)

Данный пример относится к варианту реализации заявленного способа по п.8 формулы изобретения. В нем используется группа, элементами которой являются векторы БС размерности m=5, над которыми определена операция умножения таким образом, что порядок группы равен (р-1)⁵, где р - простое число, такое, что р-1=5Nw₁w₂ (N - четное число). Операция умножения пятимерных БС выполняется при использовании таблицы 5 умножения базисных векторов, в которой в качестве коэффициента используется пятая степень некоторого натурального числа, т.е. ε=z⁵ для некоторого натурального z.

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

1. Генерируют секретный ключ в виде двух пятимерных векторов БС С и К.

2. Формируют открытый ключ Y в виде пятимерного вектора БС по формуле где w - вспомогательное МДЧ, являющееся делителем числа p-1.

3. Принимают ЭД, представленный БС Н₁.

4. Формируют ЭЦП в виде БС е и пятимерного вектора БС S, для чего выполняют следующие действия:

4.1. Генерируют случайное МДЧ t и случайный пятимерный вектор БС Т.

4.2. Генерируют пятимерный вектор БС R по формуле

4.3. Формируют БС е ЭЦП в виде МДЧ, вычисляемого в зависимости от R и Н₁ по формуле

где r₁ r₂, r₃, r₄ и r₅ - координаты пятимерного вектора БС R.

4.4. Формируют БС s ЭЦП в виде МДЧ, вычисляемого по формуле

s=e^-1tmodq.

4.5. Генерируют пятимерный вектор БС S по формуле

5. Формируют первую проверочную БС А, для чего выполняют следующие действия:

5.1. Формируют пятимерный вектор БС R', выполняя вычисления по формуле

5.2. Формируют первую проверочную БС А по формуле

где r'₁, r'₂, r'₃, r'_4, r'₅ - БС, являющиеся координатами пятимерного вектора БС R'.

6. Формируют вторую проверочную БС В путем копирования БС е, т.е. по формуле В=е.

7. Сравнивают проверочные БС А и В.

При совпадении параметров проверочных БС А и В делают вывод о подлинности ЭЦП. Тот факт, что при проверке ЭЦП, сформированной по процедуре формирования ЭЦП с использованием правильного секретного ключа, на шаге 7 будет получено совпадение параметров проверочных БС, доказывается следующим образом. Подставим в формулу, по которой формируется вектор БС R', значения БС е и s и значение вектора БС S, вычисленные по формулам s=e^-1t mod q и (см. шаги 4.4 и 4.5), получим

Поскольку R'=R, т.е. а также и то при корректно сформированной ЭЦП имеет место A=В. Таким образом, корректность процедуры проверки подлинности ЭЦП-доказана для рассмотренного частного варианта реализации заявленного способа.

Последовательность действий по формированию и проверке подлинности ЭЦП, заверяющей ЭД, описанная во всех приведенных выше примерах, за исключением примера 4, может быть выполнена также и для случая, когда БС представляют собой многочлены. Исключительность частного варианта реализации, соответствующего п.4 формулы изобретения, состоит в том, что в нем для повышения стойкости ЭЦП задано требование выполнения условия делимости порядка группы векторов БС на квадрат МДЧ w, выполнение которого в случае использования векторов многочленов в качестве векторов БС является проблематичным. При использовании векторов многочленов в качестве векторов БС таблицы умножения базисных векторов при заданном значении размерности m являются такими же, как приведенные выше, за исключением того, что коэффициент ε в случае реализации заявленного способа при использовании многочленов будет представлять собой некоторый заданный многочлен, определяющий конкретный вид операции умножения векторов многочленов. Доказательство корректности процедуры проверки ЭЦП в случае, когда векторы БС представляют собой векторы многочленов, является таким же, как и приведенное выше доказательство для случая использования векторов БС, являющихся векторами МДЧ. Частные примеры реализации заявленного способа, аналогичные описанным выше примерам 1-6, могут быть реализованы для случая использования вычислений над векторами БС, являющихся векторами многочленов. Выполнение операций сложения, умножения и деления многочленов, а также операций умножения и сложения по модулю неприводимого многочлена широко описано в научно-технической литературе. Также широко представлена реализация конечных полей многочленов и основные их свойства (см., например, книги [Курош А.Г. Курс высшей алгебры. - М.: «Наука», 1971. - 431 с.], [Кострикин А.И. Введение в алгебру. Основы алгебры. М.: Физматлит.1994. - 320 с.], [А.Акритас. Основы компьютерной алгебры с приложениями. М.: Мир, 1994. - 544 с.] и [Л.Б.Шнеперман. Курс алгебры и теории чисел в задачах и упражнениях. - Минск, «Вышэйшая школа», 1986. - 272 с.]). Варианты построения конечных групп векторов многочленов рассмотрены в работе [Молдовян Н.А. Группы векторов для алгоритмов электронной цифровой подписи. // Вестник СПбГУ. Сер. 10.2008].

Для практики представляют интерес различные варианты значений размерности m векторов БС. Выбор соответствующей размерности m зависит от требований конкретных применений заявленного способа формирования и проверки ЭЦП. Например, при использовании 32-разрядных процессоров для выполнения вычислений интерес представляют простые значения размерности m=5, m=7, m=11 и m=13. При аппаратной реализации в виде специализированных вычислительных устройств высокая производительность процедур формирования проверки ЭЦП может быть достигнута при значениях размерности векторов БС m=8, m=9, m=16 и m=32. Наиболее высокая производительность при аппаратной реализации может быть достигнута при использовании заявленного способа для случая использования векторов двоичных многочленов в качестве векторов БС. Это объясняется тем, что операции сложения и умножения двоичных многочленов в конечных полях двоичных многочленов являются наиболее эффективными с точки зрения получения высокого быстродействия и уменьшения сложности аппаратной реализации.

Приведенные выше примеры показывают принципиальную реализуемость и корректность заявленного способа формирования и проверки подлинности ЭЦП, заверяющей ЭД. Аналогичным образом реализуется заявляемый способ при использовании векторов МДЧ размерности m=4, m=6, m=7 и т.д. Например, могут быть использованы следующие таблицы умножения базисных векторов, в которых значение параметра ε может быть выбрано в интервале 0≤ε≤р, где МДЧ р выбирается таким образом, чтобы обеспечивалось значение порядка q векторов МДЧ, равное достаточно большому простому МДЧ, например, имеющее разрядность, равную 32, 40, 64, 80, 160 или 256 бит. Таблица умножения базисных векторов для задания групповой операции над четырехмерными векторами МДЧ (случай m=А) имеет вид таблицы 6. Таблица для задания групповой операции над шестимерными векторами МДЧ (случай m=6) имеет вид таблицы 7. Была разработана программа для ЭВМ, реализующая операции умножения и возведения в большую целочисленную степень векторов МДЧ, имеющих значения размерности от m=2 до m=55 для каждого промежуточного целочисленного значения размерности. С помощью этих программ были сгенерированы приведенные выше примеры и установлено, что аналогичные примеры реализации заявленного способа с использованием векторов МДЧ размерности m=7, m=8, m=11, m=13, m-16, m=17 и др. также обеспечивают корректность процедуры проверки подлинности ЭЦП.

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

Один из этих вариантов состоит в выделении квадрата, состоящего из всех клеток, не входящих в первый ряд или в первую строку, и внесении коэффициента растяжения ε в клетки этого квадрата, расположенные на диагонали, идущей из правого верхнего угла в левый нижний угол (каждая из этих клеток содержит базисный вектор е), а также во все клетки, расположенные выше этой диагонали. Второй из этих вариантов является симметричным первому относительно указанной диагонали (эта диагональ отмечена в таблице 8 серым фоном). Второй вариант распределения показан как распределение коэффициента µ, который вносится в каждую клетку диагонали, содержащей базисный вектор е и все клетки, расположенные ниже этой диагонали. Коэффициентам µ и ε может быть присвоено любое значение в интервале от 0 до р-1. При этом операция умножения векторов МДЧ будет обладать свойствами ассоциативности и коммутативности. Выбор конкретных значений коэффициентов растяжения определяет параметры групп векторов БС и должен осуществляться с привязкой к конкретным используемым значениям размерности m и числа р.

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

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

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

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

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

Изобретение относится к области электросвязи, а именно к области криптографических устройств и способов проверки электронной цифровой подписи (ЭЦП). Техническим результатом является повышение производительности алгоритмов ЭЦП без снижения ее уровня стойкости. В способе генерации и проверки ЭЦП генерируют секретный ключ в виде, по крайней мере одного вектора битовых строк К, по секретному ключу формируют открытый ключ Y в виде вектора битовых строк размерности m, где 2≤m<64, принимают электронный документ, в зависимости от которого и от значения секретного ключа формируют ЭЦП в виде, по крайней мере, одного вектора битовых строк, в зависимости от ЭЦП, документа и открытого ключа формируют первое А и второе В проверочных битовых строк, сравнивают их. При совпадении их параметров делают вывод о подлинности электронной цифровой подписи. При осуществлении процедуры формирования, по крайней мере, одной проверочной битовой строки выполняют операцию возведения m-мерного вектора битовых строк ЭЦП в целочисленную степень w>1. 7 з.п. ф-лы, 8 табл.

1. Способ формирования и проверки подлинности электронной цифровой подписи, заверяющей электронный документ, заключающийся в том, что генерируют секретный ключ в виде, по крайней мере, одной битовой строки, по секретному ключу формируют открытый ключ Y в виде более чем одной битовой строки, принимают электронный документ, представленный битовыми строками H₁, H₂,…,H_z, где z≥1, в зависимости от принятого электронного документа и от значения секретного ключа формируют электронную цифровую подпись Q в виде, по крайней мере, двух битовых строк, в зависимости от открытого ключа, принятого электронного документа и электронной цифровой подписи формируют первую А и вторую В проверочные битовые строки, сравнивают их и при совпадении их параметров делают вывод о подлинности электронной цифровой подписи, отличающийся тем, что открытый ключ Y формируют в виде, по крайней мере одного m-мерного, где 2≤m≤64, вектора битовых строк, формируют электронную цифровую подпись Q в виде, по крайней мере, одной битовой строки и, по крайней мере, одного m-мерного вектора битовых строк, а при осуществлении процедуры формирования, по крайней мере, одной проверочной битовой строки выполняют операцию возведения m-мерного вектора битовых строк электронной цифровой подписи в целочисленную степень w>1.

2. Способ по п.1, отличающийся тем, что открытый ключ Y формируют в виде m-мерного, где 2≤m≤64, вектора многоразрядных двоичных чисел.

3. Способ по п.1, отличающийся тем, что открытый ключ Y формируют в виде m-мерного, где 2≤m≤64, вектора многочленов.

4. Способ по п.1, отличающийся тем, что генерируют секретный ключ в виде m-мерного, где m=2, вектора битовых строк К и открытый ключ Y формируют в виде двухмерного вектора битовых строк по формуле Y=K^w, где w - вспомогательное многоразрядное двоичное число, принимают электронный документ, представленный битовой строкой H₁, a электронную цифровую подпись формируют в виде битовой строки е и двухмерного вектора битовых строк S, для чего генерируют случайный двухмерный вектор битовых строк Т, генерируют вектор битовых строк R по формуле R=Т^w, затем формируют первую битовую строку е электронной цифровой подписи в виде многоразрядного двоичного числа, вычисляемого в зависимости от R и H₁ по формуле e=f(R,H₁), где f(R,H₁) - выражение, задающее правило вычисления многоразрядного двоичного числа е, затем генерируют двухмерный вектор битовых строк S электронной цифровой подписи по формуле где знак обозначает операцию умножения векторов битовых строк, после чего формируют первую и вторую проверочные битовые строки А и В по формулам A=f(R',H₁) и В=е, где вектор битовых строк R' вычисляют по формуле

5. Способ по п.1, отличающийся тем, что генерируют секретный ключ в виде двух m-мерных, где m=3, векторов битовых строк K₁ и К₂, открытый ключ Y формируют в виде трехмерного вектора битовых строк по формуле где знак обозначает операцию умножения векторов битовых строк, w₁ и w₂ - вспомогательные многразрядные двоичные числа, и принимают электронный документ, представленный битовыми строками H₁ и Н₂, а электронную цифровую подпись формируют в виде битовой строки е и двух трехмерных векторов битовых строк S₁ и S₂, для чего генерируют два случайных трехмерных вектора битовых строк T₁ и Т₂, генерируют вектор битовых строк R по формуле затем формируют первую битовую строку е электронной цифровой подписи в виде многоразрядного двоичного числа, вычисляемого в зависимости от R, H₁ и Н₂ по формуле e=f(R,H₁,H₂), где f(R,H₁,H₂) - выражение, задающее правило вычисления многоразрядного двоичного числа е, затем генерируют трехмерные вектора битовых строк S₁ и S₂ электронной цифровой подписи по формулам и после чего формируют первую и вторую проверочные битовые строки А и В по формулам A=f(R',H₁,H₂) и В=е, где вектор битовых строк R' вычисляют по формуле

6. Способ по п.1, отличающийся тем, что генерируют секретный ключ в виде многоразрядного двоичного числа k и m-мерного, где m=2, вектора битовых строк К и открытый ключ Y формируют в виде двухмерного вектора битовых строк, для чего генерируют вектор битовых строк G размерности m=2, имеющий порядок, равный многоразрядному двоичному числу q, после чего открытый ключ Y генерируют по формуле где знак обозначает операцию умножения векторов битовых строк и w - вспомогательное многразрядное двоичное число, принимают электронный документ, представленный битовой строкой H₁, а электронную цифровую подпись формируют в виде двухмерного вектора битовых строк S и двух битовых строк е и s, для чего генерируют случайное многоразрядное двоичное число t и случайный двухмерный вектор битовых строк Т, генерируют вектор битовых строк R по формуле затем формируют первую битовую строку е электронной цифровой подписи в виде многоразрядного двоичного числа, вычисляемого в зависимости от R и Н₁ по формуле e=f(R,H₁), где f(R,H₁) - выражение, задающее правило вычисления многоразрядного двоичного числа е, затем генерируют двухмерный вектор битовых строк S электронной цифровой подписи, вычисляемый по формуле где S=(s₁,s₂), и вторую битовую строку s электронной цифровой подписи в виде многоразрядного двоичного числа, вычисляемого по формуле
после чего формируют первую и вторую проверочные битовые строки А и В по формулам A=f(R',H₁) и В=е, где вектор битовых строк R' вычисляют по формуле где F(S)=s₁.

7. Способ по п.1, отличающийся тем, что генерируют секретный ключ в виде многоразрядного двоичного числа k и m-мерного, где m=2, вектора битовых строк К и открытый ключ Y формируют в виде двух двухмерных векторов битовых строк Y₁ и Y₂, для чего генерируют вектор битовых строк G размерности m=2, имеющий порядок, равный многоразрядному двоичному числу q, после чего вектора битовых строк Y₁ и
Y₂ открытого ключа Y генерируют по формулам Y₁=G^k и Y₂=К^w, где w - вспомогательное многоразрядное двоичное число, принимают электронный документ, представленный битовыми строками H₁ и H₂, а электронную цифровую подпись формируют в виде двухмерного вектора битовых строк S и двух битовых строк е и s, для чего генерируют случайное многоразрядное двоичное число t и случайный двухмерный вектор битовых строк Т,
генерируют вектор битовых строк R по формуле R=Gt⊕T^w, где знак ⊕ обозначает операцию сложения векторов битовых строк, затем формируют первую битовую строку е электронной цифровой подписи в виде многоразрядного двоичного числа, вычисляемого в зависимости от R, H₁ и Н₂ по формуле e=f(R,H₁,H₂) где f(R,H₁,H₂) - выражение, задающее правило вычисления многоразрядного двоичного числа е, затем генерируют двухмерный вектор битовых строк S электронной цифровой подписи, вычисляемый по формуле где знак обозначает операцию умножения векторов битовых строк, и вторую битовую строку s электронной цифровой подписи в виде многоразрядного двоичного числа, вычисляемого по формуле после чего формируют первую и вторую проверочные битовые строки А и В по формулам A=f(R',H₁,H₂) и В=е, где вектор битовых строк R' вычисляют по формуле

8. Способ по п.1, отличающийся тем, что генерируют секретный ключ в виде двух m-мерных, где m=5, векторов битовых строк С и К, открытый ключ Y формируют в виде пятимерного вектора битовых строк, генерируемого по формуле где знак обозначает операцию умножения векторов битовых строк и w - вспомогательное многоразрядное двоичное число, принимают электронный документ, представленный битовой строкой H₁, а электронную цифровую подпись формируют в виде пятимерного вектора битовых строк S и двух битовых строк e и s, для чего генерируют случайное многоразрядное двоичное число t и случайный пятимерный вектор битовых строк Т, генерируют вектор битовых строк R по формуле затем формируют первую битовую строку е электронной цифровой подписи в виде многоразрядного двоичного числа, вычисляемого в зависимости от R и H₁ по формуле e=f(R,H₁), где f(R,H₁) - выражение, задающее правило вычисления многоразрядного двоичного числа е, формируют вторую битовую строку s электронной цифровой подписи в виде многоразрядного двоичного числа, вычисляемого по формуле s=e^-1tmodq, затем генерируют пятимерный вектор битовых строк S электронной цифровой подписи, вычисляемый по формуле после чего формируют первую и вторую проверочные битовые строки А и В по формулам A=f(R',H₁) и В=е, где вектор битовых строк R' вычисляют по формуле