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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где если точки А и В не равны, и если точки А и В равны. Операция умножения точки А на натуральное число n определяется как многократное сложение токи А:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поставленная цель достигается тем, что в известном способе формирования и проверки подлинности ЭЦП, заверяющей ЭД, заключающемся в том, что генерируют совокупность из n≥2 секретных ключей в виде многоразрядных двоичных чисел k₁, k₂, …, k_n, no секретным ключам формируют n открытых ключей P₁, P₂, …, P_n, соответственно, принимают, по крайней мере, один электронный документ, представленный многоразрядным двоичным числом Н, в зависимости от принятого электронного документа и от значения, по крайней мере, одного секретного ключа формируют электронную цифровую подпись Q в виде двух или более многоразрядных двоичных чисел, формируют первое А и второе В проверочные многоразрядные двоичные числа, сравнивают их и при совпадении их параметров делают вывод о подлинности электронной цифровой подписи, новым является то, что дополнительно генерируют коллективный открытый ключ в зависимости от m открытых ключей … где α₁, α₂, …, α_m - натуральные числа, 2≤m≤n, α_j≤n и j=1, 2, …, m, причем, по крайней мере, одно из проверочных многоразрядных двоичных чисел формируют в зависимости от коллективного открытого ключа.

Новым является также и то, что открытые ключи P₁, P₂, …, P_n генерируют в виде точек эллиптической кривой, для чего генерируют эллиптическую кривую в виде совокупности точек, каждая из которых определяется парой многоразрядных двоичных чисел, являющихся соответственно абсциссой и ординатой данной точки эллиптической кривой в декартовой системе координат, причем точки P_i, Р₂, …, P_n эллиптической кривой генерируют по формуле Р_i=k_iG, где i=1, 2, …, n, G - дополнительно сгенерированная точка эллиптической кривой, имеющая порядок q, принимают m электронных документов, представленных многоразрядными двоичными числами Н₁, Н₂, …, H_m, а электронную цифровую подпись формируют в виде пары многоразрядных двоичных чисел е и s, для чего генерируют m случайных многоразрядных двоичных чисел генерируют m точек … эллиптической кривой по формуле генерируют точку R эллиптической кривой по формуле после чего формируют первое многоразрядное двоичное число е электронной цифровой подписи по формуле е=x_R mod δ, где x_R - абсцисса точки R и δ - вспомогательное простое многоразрядное двоичное число, затем генерируют m многоразрядных двоичных чисел … по формуле после чего генерируют второе многоразрядное двоичное число s электронной цифровой подписи по формуле причем коллективный открытый ключ генерируют в виде точки Р эллиптической кривой, вычисляемой по формуле и первое проверочное многоразрядное двоичное число А формируют по формуле A=x_R' mod δ, где X_R' - абсцисса точки R' эллиптической кривой, вычисленной по формуле R'=eP+sG, а второе проверочное многоразрядное двоичное число В формируют по формуле В=е.

Новым является также то, что открытые ключи P₁, Р₂, …, P_n генерируют в виде точек эллиптической кривой, для чего генерируют эллиптическую кривую в виде совокупности точек, каждая из которых определяется парой многоразрядных двоичных чисел, являющихся соответственно абсциссой и ординатой данной точки эллиптической кривой в декартовой системе координат, причем точки P₁, Р₂, …, P_n эллиптической кривой генерируют по формуле P_i=k_iG, где i=1, 2, …, n, G - дополнительно сгенерированная точка эллиптической кривой, имеющая порядок q, а электронную цифровую подпись формируют в виде пары многоразрядных двоичных чисел е и s, для чего генерируют m случайных многоразрядных двоичных чисел …, генерируют m точек …, эллиптической кривой по формуле генерируют точку R эллиптической кривой по формуле после чего формируют первое многоразрядное двоичное число е электронной цифровой подписи по формуле е=X_RH mod δ, где x_R - абсцисса точки R и δ - вспомогательное простое многоразрядное двоичное число, затем генерируют m многоразрядных двоичных чисел …, по формуле после чего генерируют второе многоразрядное двоичное число s электронной цифровой подписи по формуле причем коллективный открытый ключ генерируют в виде точки Р эллиптической кривой, вычисляемой по формуле и первое проверочное многоразрядное двоичное число А формируют по формуле А=x_R'H mod δ, где x_R' - абсцисса точки R' эллиптической кривой, вычисленной по формуле R'=еР+sG, а второе проверочное многоразрядное двоичное число В формируют по формуле В=е.

Новым также является и то, что открытые ключи P₁, P₂, …, P_n генерируют в виде многоразрядных двоичных чисел, для чего генерируют простое многоразрядное двоичное число р, такое что р=Nz²+1, где N - четное натуральное многоразрядное двоичное число и z - простое w-разрядное двоичное число, w>64, причем многоразрядные двоичные числа P₁, Р₂, …, P_n генерируют по формуле где i=1, 2, …, n, а электронную цифровую подпись формируют в виде пары многоразрядных двоичных чисел R и S, для чего генерируют m случайных многоразрядных двоичных чисел …, генерируют m вспомогательных многоразрядных двоичных чисел …, по формуле генерируют первое многоразрядное двоичное число R электронной цифровой подписи по формуле после чего формируют вспомогательное многоразрядное двоичное число Е по формуле E=RH mod δ, где δ - дополнительное простое многоразрядное двоичное число, затем генерируют m многоразрядных двоичных чисел …, по формуле после чего генерируют второе многоразрядное двоичное число S электронной цифровой подписи по формуле причем коллективный открытый ключ генерируют в виде многоразрядного двоичного числа P, вычисляемого по формуле и первое проверочное многоразрядное двоичное число А формируют по формуле А=S^z mod p, а второе проверочное многоразрядное двоичное число В формируют по формуле В=P^ER mod p.

Новым также является и то, что открытые ключи P₁, Р₂, …, P_n генерируют в виде многоразрядных двоичных чисел, для чего генерируют простое многоразрядное двоичное число p, такое что р=Nz²+1, где N - четное натуральное многоразрядное двоичное число и z - простое w-разрядное двоичное число, w>64, причем многоразрядные двоичные числа P₁, P₂, …, P_n генерируют по формуле где i=1, 2, …, n, а электронную цифровую подпись формируют в виде пары многоразрядных двоичных чисел Е и S, для чего генерируют m случайных многоразрядных двоичных чисел …, генерируют m вспомогательных многоразрядных двоичных чисел …, по формуле генерируют вспомогательное многоразрядное двоичное число R по формуле после чего формируют первое многоразрядное двоичное число Е электронной цифровой подписи по формуле E=RH mod δ, где δ - дополнительное простое многоразрядное двоичное число, затем генерируют m многоразрядных двоичных чисел …, по формуле после чего генерируют второе многоразрядное двоичное число S электронной цифровой подписи по формуле причем коллективный открытый ключ генерируют в виде многоразрядного двоичного числа Р, вычисляемого по формуле а первое А и второе В проверочные многоразрядные двоичные числа формируют соотвественно по формулам A=(S^z P^-E mod p)H mod δ и В=E.

Новым также является и то, что открытые ключи P₁, P₂, …, P_n генерируют в виде многоразрядных двоичных чисел, для чего генерируют простое многоразрядное двоичное число р, причем многоразрядные двоичные числа P₁, P₂, …, P_n генерируют по формуле где i=1, 2, …, n, g - дополнительно сгенерированное многоразрядное двоичное число, имеющее порядок q, a электронную цифровую подпись формируют в виде пары многоразрядных двоичных чисел Е и S, для чего генерируют m случайных многоразрядных двоичных чисел …, генерируют m вспомогательных многоразрядных двоичных чисел …, по формуле генерируют многоразрядное двоичное число R по формуле после чего формируют первое многоразрядное двоичное число Е электронной цифровой подписи по формуле E=R mod δ, где δ - дополнительное простое многоразрядное двоичное число, затем генерируют m многоразрядных двоичных чисел …, по формуле после чего генерируют второе многоразрядное двоичное число S электронной цифровой подписи по формуле причем коллективный открытый ключ генерируют в виде многоразрядного двоичного числа Р, вычисляемого по формуле и первое проверочное многоразрядное двоичное число А формируют по формуле A=R'H mod δ, где R' - многоразрядное двоичное число, вычисленное по формуле R'=P^-Eg^s mod p, а второе проверочное многоразрядное двоичное число В формируют по формуле В=Е.

Новым также является и то, что открытые ключи P₁, Р₂, …, P_n генерируют в виде многоразрядных двоичных чисел, для чего генерируют простое многоразрядное двоичное число p, причем многоразрядные двоичные числа P₁, Р₂, …, P_n генерируют по формуле где i=1, 2, …, n, g - дополнительно сгенерированное многоразрядное двоичное число, имеющее порядок q, принимают m электронных документов, представленных многоразрядными двоичными числами Н₁, Н₂, …, H_m, а электронную цифровую подпись формируют в виде пары многоразрядных двоичных чисел Е и S, для чего генерируют m случайных многоразрядных двоичных чисел …, генерируют m вспомогательных многоразрядных двоичных чисел …, по формуле генерируют многоразрядное двоичное число R по формуле после чего формируют первое многоразрядное двоичное число Е электронной цифровой подписи по формуле E=R Hmod δ, где δ - дополнительное простое многоразрядное двоичное число, затем генерируют m многоразрядных двоичных чисел …, по формуле после чего генерируют второе многоразрядное двоичное число s электронной цифровой подписи по формуле причем коллективный открытый ключ генерируют в виде многоразрядного двоичного числа Р, вычисляемого по формуле и первое проверочное многоразрядное двоичное число А формируют по формуле А=R' mod δ, где R' - многоразрядное двоичное число, вычисленное по формуле R'=Р^-Eg^S mod p, а второе проверочное многоразрядное двоичное число В формируют по формуле В=Е.

Предлагаемый способ может быть использован для числа n пользователей, удовлетворяющего условию n≥2. Пользователи условно обозначаются номерами i=1, 2, …, n. Этот номер используется как индекс, указывающий на то, какому пользователю принадлежит секретный и открытый ключи, или на то, какой из пользователей генерирует отмеченные индексом МДЧ или точки ЭК. Из совокупности n пользователей некоторое их подмножество, состоящее из m произвольно выбранных пользователей, может быть задано номерами пользователей, входящих в данное подмножество, например номерами α₁, α₂, …, α_m, каждый из которых выбирается из множества чисел 1, 2, …., n. Таким образом, числа α_j, где j=1, 2, …, m, представляют собой выборку произвольных m номеров из множества {1, 2, …, n}, при этом m≤n. Соответственно этому совокупность открытых ключей, например, точек …, ЭК представляет собой выборку из множества всех открытых ключей Р₁, Р₂, …, P_n, а совокупность секретных ключей …, представляет собой выборку из множества всех секретных ключей k₁, k₂, …, k_n, где i=1, 2, …, n.

Корректность заявленного способа доказывается теоретически. Рассмотрим, например, вариант реализации способа по п.3 формулы изобретения. Коллективный открытый ключ, соответствующий подмножеству пользователей с условными номерами α₁, α₂, …, α_m, представляет собой точку

Значения которые представляют собой «доли» пользователей в коллективной подписи, генерируются по формуле поэтому

Значение точки R', используемой для формирования первого проверочного МДЧ А генерируется по формуле R'=еР+sG, т.е. оно равно

Следовательно, А=x_R'H mod δ=x_RH mod δ=е=В, т.е. правильно сформированная коллективная подпись удовлетворяет процедуре проверки подписи, т.е. корректность процедур генерации и проверки ЭЦП доказана.

Рассмотрим примеры реализации заявленного технического решения с использованием ЭК, описываемой уравнением (см. Приложение 1, пп.15-19)

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

Пример 1. Реализация заявляемого способа по п.2 формулы изобретения.

В данном примере иллюстрируется п.2 формулы изобретения. В нем используется ЭК с параметрами, обеспечивающими достаточную стойкость для применения при решении реальных практических задач аутентификации информации. Этот пример иллюстрирует реальные размеры чисел, которые используются на практике при генерации и проверке подлинности ЭЦП. Особенностью данного примера является то, что принимают три различных ЭД, представленных МДЧ Н₁, H₂ и Н₃. При этом первый пользователь подписывает первый ЭД, второй пользователь - второй ЭД и третий пользователь - третий ЭД. Возможность реализации коллективной ЭЦП с такими свойствами обеспечивается за счет того, что при проверке ЭЦП используется коллективный открытый ключ, формируемый в зависимости от открытых ключей пользователей по формуле Р=H₁P₁+H₂P₂+H₃P₃.

В примере 1 используется ЭК, определяемая следующими параметрами: а=5521767865737634555390416300599776622347333359784, b=9717196 и р=5521767865737634555390416300599776622347333359787.

Данная ЭК содержит количество точек, равное простому числу V=5521767865737634555390416228783886913339823841723, т.е. любая ее точка имеет порядок q, равный значению F, т.е. q=V.

Рассмотрим коллектив из трех пользователей. При формировании и проверке подлинности ЭЦП (подписью является пара чисел е и s) выполняют следующую последовательность действий.

1. Генерируют ЭК с параметрами, указанными выше.

2. Формируют секретные ключи в виде случайных МДЧ k₁, k₂ и k₃:

k₁=8182108890892890101467333434019 - ключ первого пользователя;

k₂=3952504539403758278808581024791 - ключ второго пользователя;

k₃=9763160941600092631935520658071 - ключ третьего пользователя.

3. Формируют открытые ключи в виде точек ЭК P₁, P₂, Р₃, для чего

3.1. Генерируют точку G, имеющую порядок q:

G=(4058138998817699569976678358233335958495037969465, 768568926336036825718495218916308682494116144160);

3.2. Генерируют точки P₁, Р₂, Р₃ по формуле P_i=k_iG, где i=1, 2, 3:

P₁=(2406767665928158899446906165821747218883574602371, 562377648521692290689031507205008060205345636991);

P₂=(348708108378027085357389414044825237922683510732, 1402026191996080196399482770468472598076052599809)

Р₃=(4307166077833519301063322533024162005091025020313, 5280296312549156028148905914215570655514986217509).

4. Принимают три ЭД, представленных МДЧ Н₁, Н₂ и H₃:

H₁=135708092215597910168314154751917220633712178686;

Н₂=3812498990028819155316571350634376652814331770527;

H₃=8925999026871145131520337612117778680659192576033.

5. Формируют ЭЦП Q в виде двух МДЧ е и s, для чего выполняют следующие действия.

5.1. Первый, второй и третий пользователи генерируют случайные МДЧ t₁, t₂ и t₃ соответственно:

t₁=2090880922625982683584460167862382379;

t₂=5360383526856663700583896205266418341;

t₃=7677118810723142352012317453400887449.

5.2. Затем первый, второй и третий пользователи генерируют точки R₁, R₂ и R₃ соответственно по формуле R_i=t_iG:

R₁=(4533360075292446608850664400364711592205136618460, 1175061337062232179584348686477324762101164050095);

R₂=(1958279223827902047379336465285895435330140185477, 8836508908256232955144234242970494318564852573);

R₃=(5038616028852959877509554081789667436853794753557, 209613157933044677924551688484534713038841468913).

5.3. Генерируют точку R по формуле R=R₁+R₂+R₃:

R=(2597097970263610863546069436833994580002105418569, 3304915040104400813802374282473985550015521973383).

5.4. Формируют МДЧ е по формуле е=x_R mod δ, где x_R - абсцисса точки R и δ - вспомогательное простое МДЧ (δ=7118198218659321028989011): е=5079008233076932087473789.

5.5. Первый, второй и третий пользователи генерируют МДЧ s₁, s₂ и s₃ соответственно по формуле s_i=(t_i-eH_ik_i) mod q, где q=N и i=1, 2, 3:

s₁=133444963875333388923743187271473122915443205289;

s₂=1887661653203847944710282450835612551620081427016;

s₃=4850696161955991125559318084555021335580302189827.

5.6. Генерируют МДЧ s=s₁+s₂+s₃ mod q:

s=1350034913297537903802927493878220096776002980409.

6. Формируют первое проверочное МДЧ А, для чего выполняют следующую последовательность действий.

6.1. Формируют коллективный открытый ключ в виде точки Р по формуле Р=H₁P₁+H₂P₂+H₃P₃:

H₁P₁=(1386084349002545424511668926945575066838407867380, 4543633731958840101124845818771841004374561021017)

H₂P₂=(299211431532419026428141393395396288778694972469, 5300327094421154876022064946876206296853312043729)

H₃P₃=(4523528487954522900878694877895556963796345154180, 4100826103480972798980996909196526199327733122181)

Р=(228426539485900338090938878090464611548638254406, 1202278174553095231135389060209649902535727110543).

6.2. Генерируют точку R'=eP+sG:

еР=(4556848179595887141400726723891321438602307875189, 2883779289574756983177387955618073719731329543379);

sG=(1360352815531577166684912233134001496389816081366, 3543269787247235781900897404104279341644752005600);

R'=(2597097970263610863546069436833994580002105418569, 3304915040104400813802374282473985550015521973383).

6.3. Генерируют МДЧ А по формуле А=x_R' mod δ, где дополнительное МДЧ δ=7118198218659321028989011:

А=5079008233076932087473789.

7. Формируют второе проверочное МДЧ В путем копирования МДЧ е:

В=е=5079008233076932087473789.

8. Сравнивают первое А и второе В проверочные МДЧ.

Сравнение показывает, что параметры МДЧ А и В совпадают. Совпадение значений А и В означает, что коллективная ЭЦП является подлинной, т.е. относится к принятым ЭД, представленных МДЧ Н₁, Н₂ и Н₃, причем первый пользователь подписал ЭД, представленный МДЧ H₁, второй пользователь - ЭД, представленный МДЧ Н₂, а третий пользователь - ЭД, представленный МДЧ Н₃.

Пример 2. Реализация заявляемого способа по п.3 формулы изобретения.

В данном примере используется ЭК, секретные и открытые ключи пользователей такие же, как и в примере 1. В примере используется ЭК, определяемая следующими параметрами:

а=5521767865737634555390416300599776622347333359784, b=9717196 и р=5521767865737634555390416300599776622347333359787.

Данная ЭК содержит количество точек, равное простому числу V=5521767865737634555390416228783886913339823841723, т.е. любая ее точка имеет порядок q, равный значению V, т.е. q=V.

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

1. Генерируют ЭК с параметрами, указанными выше.

2. Формируют секретные ключи в виде случайных МДЧ

k₁=8182108890892890101467333434019 - ключ первого пользователя;

k₂=3952504539403758278808581024791 - ключ второго пользователя;

k₃=9763160941600092631935520658071 - ключ третьего пользователя.

3. Формируют открытые ключи в виде точек ЭК P₁, P₂, Р₃, для чего

3.1. Генерируют точку G:

G=(4058138998817699569976678358233335958495037969465, 768568926336036825718495218916308682494116144160).

3.2. Генерируют точки P₁, P₂, Р₃ по формуле P_i=k_iG, где i=1, 2, 3:

Р₁=(2406767665928158899446906165821747218883574602371, 562377648521692290689031507205008060205345636991);

P₂=(348708108378027085357389414044825237922683510732, 1402026191996080196399482770468472598076052599809);

Р₃=(4307166077833519301063322533024162005091025020313, 5280296312549156028148905914215570655514986217509).

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

Н=8925999026871145131520337612117778680659192576033.

5. Формируют ЭЦП Q в виде пары МДЧ е и s, для чего выполняют следующие действия.

5.1. Первый, второй и третий пользователи генерируют случайные МДЧ t₁, t₂ и t₃ соответственно:

t₁=2090880922625982683584460167862382379;

t₂=5360383526856663700583896205266418341;

t₃=7677118810723142352012317453400887449.

5.2. Затем первый, второй и третий пользователи генерируют точки R₁, R₂ и R₃ соответственно по формуле R_i=t_iG:

R₁=(4533360075292446608850664400364711592205136618460, 1175061337062232179584348686477324762101164050095);

R₂=(1958279223827902047379336465285895435330140185477, 8836508908256232955144234242970494318564852573);

R₃=(5038616028852959877509554081789667436853794753557, 209613157933044677924551688484534713038841468913).

5.3. Генерируют точку R по формуле R=R₁+R₂+R₃:

R=(2597097970263610863546069436833994580002105418569, 3304915040104400813802374282473985550015521973383).

5.4. Формируют первое МДЧ е электронной цифровой подписи по формуле е=x_RH mod δ, где x_R - абсцисса точки R и δ - вспомогательное простое МДЧ (δ=7118198218659321028989011):

е=4927124871592959793329711.

5.5. Первый, второй и третий пользователи генерируют МДЧ s₁, s₂ и s₃ соответственно по формуле s_i=(t_i-ek_i) mod q, где q'=N и i=1, 2, 3:

s₁=359849983424274307716254877984953159149283598626;

s₂=2228471503399271451844174588034195792013686207551;

s₃=3321295738385055881020248326363803564813773402448.

5.6. Генерируют второе МДЧ s электронной цифровой подписи по формуле s=s₁+s₂+s₃ mod q:

s=387849359470967085190261563599065602636919366902.

6. Формируют первое проверочное МДЧ А, для чего выполняют следующую последовательность действий.

6.1. Формируют коллективный открытый ключ в виде точки Р по формуле Р=Р₁+Р₂+P₃:

8. Сравнивают первое А и второе В проверочные МДЧ.

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