СПОСОБ ФОРМИРОВАНИЯ И ПРОВЕРКИ ПОДЛИННОСТИ КОЛЛЕКТИВНОЙ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ, ЗАВЕРЯЮЩЕЙ ЭЛЕКТРОННЫЙ ДОКУМЕНТ
METHOD OF CREATING AND AUTHENTICATING COLLECTIVE ELECTRONIC DIGITAL SIGNATURE CERTIFYING ELECTRONIC DOCUMENT

Изобретение относится к области электросвязи и вычислительной техники, а конкретнее к области криптографических способов аутентификации электронных сообщений, передаваемых по телекоммуникационным сетям и сетям ЭВМ, и может быть использовано в системах передачи электронных сообщений (документов), заверенных электронной цифровой подписью (ЭЦП), представленной в виде многоразрядного двоичного числа (МДЧ). Здесь и далее под МДЧ понимается электромагнитный сигнал в двоичной цифровой форме, параметрами которого являются: число битов и порядок следования их единичных и нулевых значений (толкование терминов, используемых в описании изобретения см. в Приложении 1).
Известен способ формирования и проверки подлинности ЭЦП Эль-Гамаля, описанный в книге [Молдовян А.А., Молдовян Н.А., Советов Б.Я. Криптография. - СПб, Лань, 2000. - с.156-159], который включает следующие действия:
формируют простое МДЧ p и двоичное число G, являющееся первообразным корнем по модулю p, генерируют секретный ключ в виде МДЧ x, в зависимости от секретного ключа формируют открытый ключ в виде МДЧ , принимают электронный (ЭД), представленный в виде МДЧ Н, в зависимости от Н и секретного ключа формируют ЭЦП Q в виде двух МДЧ S и R, то есть Q=(S, R);
осуществляют процедуру проверки подлинности ЭЦП, включающую вычисление двух контрольных параметров с использованием исходных МДЧ p, G, Y, Н и S путем возведения МДЧ G, Y, R в дискретную степень по модулю p и сравнение вычисленных контрольных параметров;
при совпадении значений контрольных параметров делают вывод о подлинности ЭЦП.
Недостатком данного способа также является относительно большой размер ЭЦП. Это объясняется тем, что значения элементов подписи S и R вычисляют путем выполнения арифметических операций по модулю p-1 и по модулю p, соответственно.
Известен также способ формирования и проверки ЭЦП, предложенный в патенте США №4995089 от 19.02.1991.
Известный способ заключается в следующей последовательности действий:
формируют простое МДЧ p, такое что p=Nq+1, где q - простое МДЧ;
q
формируют простое МДЧ а, такое что а≠1 и a mod p=1;
методом генерации случайной равновероятной последовательности формируют секретный ключ в виде МДЧ x;
формируют открытый ключ в виде МДЧ y по формуле ;
принимают ЭД, представленный МДЧ М;
формируют ЭЦП в виде пары МДЧ (е, s) для чего генерируют случайное МДЧ t, формируют МДЧ R по формуле , формируют МДЧ , где знак || обозначает операцию присоединения двух МДЧ и f - некоторая специфицированная хэш-функция, значение которой имеет фиксированную длину (обычно 160 или 256 бит), независим от размера аргумента, т.е. от размера МДЧ , а затем формируют МДЧ s по формуле ;
формируют первое проверочное МДЧ А, для чего генерируют МДЧ R' по формуле  и формируют МДЧ ;
формируют второе проверочное МДЧ В путем копирования МДЧ е: В=е;
сравнивают сформированные проверочные МДЧ А и В;
при совпадении параметров сравниваемых МДЧ А и В делают вывод о подлинности ЭЦП.
Недостатком способа по патенту США является относительно высокая вычислительная сложность процедуры формирования и проверки ЭЦП, что связано с тем, что для обеспечения минимально требуемого уровня стойкости требуется использовать простой модуль p разрядностью не менее 1024 бит.
Недостатком известного способа является относительно большой размер подписи и необходимость увеличения размера подписи при разработке новых более эффективных методов разложения числа n на множители или при росте производительности современных вычислительных устройств. Это объясняется тем, что значение элемента подписи s вычисляются путем выполнения арифметических операций по модулю n, а стойкость ЭЦП определяется сложностью разложения модуля n на множители p и q.
Известен также способ формирования и проверки подлинности ЭЦП, предлагаемый российским стандартом ГОСТ Р 34.10-2001 и описанный, например, в книге [Б.Я.Рябко, А.Н.Фионов. Криптографические методы защиты информации. М., Горячая линия - Телеком, 2005. - 229 с. (см. с.110-111)], согласно которому ЭЦП формируется в виде пары МДЧ r и s, для чего генерируют эллиптическую кривую (ЭК) в виде совокупности точек, причем каждая точка представляется двумя координатами в декартовой системе координат в виде двух МДЧ, называемых абсциссой (x) и ординатой (y), затем осуществляют операции генерации точек ЭК, сложения точек ЭК и умножения точки ЭК на число, а также арифметические операции над МДЧ, после чего в результате выполненных операций формируются МДЧ r и s. Указанные операции над точками выполняются как операции над МДЧ, являющимися координатами точек, по известным формулам [Б.Я.Рябко, А.Н.Фионов. Криптографические методы защиты информации. М., Горячая линия - Телеком, 2005. - 229 с. (см. с.110-111)]. В прототипе генерируют ЭК, описываемую уравнением , поэтому генерация ЭК состоит в генерации чисел a, b и p, являющихся параметрами ЭК и однозначно задающих множество точек ЭК как множество точек, абсцисса и ордината которых удовлетворяет указанному уравнению. В рассматриваемом аналоге выполняется следующая последовательности действий:
генерируют ЭК, которая представляет собой совокупность пар МДЧ, называемых точками ЭК и обладающих определенными свойствами (см. Приложение 1, пп.15-19);
1
2
n
методом генерации случайной равновероятной последовательности формируют секретные ключи в виде МДЧ k, k, …, k;
1
2
n
1
2
n
1
1
2
2
n
n
формируют открытые ключи в виде точек ЭК P, P, …, P, для чего генерируют точку G, имеющую значение порядка, равное q (порядком точки ЭК называется наименьшее положительное целое число q, такое что результатом умножения данной точки на число q является так называемая бесконечно удаленная точка О; результатом умножения любой точки ЭК на нуль по определению является точка О [Б.Я.Рябко, А.Н.Фионов. Криптографические методы защиты информации. М., Горячая линия - Телеком, 2005. - 229 с. (см. с.97-130)]; см. также Приложение 1, пп.15-19) и генерируют открытые ключи путем умножения точки G на МДЧ k, k, …, k, т.е. формируют открытые ключи по формулам P=kG, P=kG, …, P=kG;
принимают ЭД, представленный МДЧ Н;
генерируют случайное МДЧ 0<t<q, по которому формируют точку R по формуле R=tG;
R
R
формируют ЭЦП Q в виде пары МДЧ (r, s), для чего генерируют МДЧ r по формуле r=x mod q, где x - абсцисса точки R, а затем генерируют МДЧ s по формуле , где 1≤i≤n;
R'
формируют первое проверочное МДЧ А, для чего генерируют МДЧ v по формуле  и МДЧ w по формуле , затем генерируют точку R' по формуле , после чего МДЧ А получают по формуле , где x - абсцисса точки R';
формируют второе проверочное МДЧ В путем копирования МДЧ r: В=r;
сравнивают сформированные проверочные МДЧ А и В;
при совпадении параметров сравниваемых МДЧ А и В делают вывод о подлинности ЭЦП.
Недостатком этого аналога является возрастание размера коллективной ЭЦП, т.е. ЭЦП, устанавливающей факт подписания некоторого заданного ЭД двумя и более пользователями, пропорционально числу пользователей, подписывающих заданный ЭД, что обусловлено тем, что каждый пользователь формирует ЭЦП, которая не зависит от ЭЦП других пользователей.
Наиболее близким по своей технической сущности к заявленному является известный способ формирования и проверки подлинности ЭЦП, описанный в патенте РФ №2356172 по заявке №2007130982 от 13.08.2007 [Молдовян А.А., Молдовян Н.А. Способ формирования и проверки подлинности электронной цифровой подписи, заверяющей электронный документ // Бюл. №14 от 20.05.2009].
Ближайший аналог (прототип) заключается в выполнении следующей последовательности действий
1) генерируют ЭК, которая представляет собой совокупность пар МДЧ, называемых точками ЭК и обладающих определенными свойствами (см. Приложение 1, пп.15-19);
1
2
n
2) методом генерации случайной равновероятной последовательности формируют секретные ключи в виде МДЧ k, k, …, k;
1
2,
n
1
2
n
1
1
2
2
n
n
3) формируют открытые ключи в виде точек ЭК P, P …, P, для чего генерируют точку G, имеющую значение порядка, равное q, и генерируют открытые ключи путем умножения точки G на МДЧ k, k, …, k, т.е. формируют открытые ключи по формулам P=kG, P=kG, …, P=kG;
4) принимают ЭД, представленный МДЧ Н;
1
2
m
j
5) формируют коллективный открытый ключ в виде точки Р ЭК, вычисляемой по формуле  где α, α, …, α - натуральные числа; 2≤m≤n; α≤n и j=1, 2, …, m;
6) формируют коллективную ЭЦП Q, принадлежащую пользователям, владеющим секретными ключами , , …,  в виде пары МДЧ (е, s), для чего
6.1) генерируют m случайных МДЧ , , …,  таких, что выполняются условия , , …, ;
6.2) формируют m точек ЭК , , …,  по формуле , где j=1, 2, …, m;
6.3) формируют точку R ЭК по формуле
R
6.4) генерируют МДЧ е по формуле , где x - абсцисса точки R;
6.5) генерируют m МДЧ , , …,  по формуле , где j=1, 2, …, m;
6.6) генерируют МДЧ s по формуле ;
7) формируют первое проверочное МДЧ А, для чего
7.1) генерируют МДЧ v по формуле ;
7.2) генерируют МДЧ w по формуле ;
7.3) генерируют точку R' ЭК по формуле
R'
7.4) проверочное МДЧ A получают по формуле , где x - абсцисса точки R';
8) формируют второе проверочное МДЧ В путем копирования МДЧ е: В=e;
9) сравнивают сформированные проверочные МДЧ А и В;
10) при совпадении параметров сравниваемых МДЧ А и В делают вывод о подлинности ЭЦП.
Недостатком ближайшего аналога является сравнительно высокая временная сложность процедур формирования и проверки подлинности коллективной ЭЦП, что связано с тем, что сложение точек выполняется по формулам, включающим операцию умножения по модулю простого числа p, для выполнении которой требуется выполнить операцию арифметического умножения и операцию арифметического деления на число p, причем операция деления имеет временную сложность в десять и более раз более высокую, чем операция арифметического умножения.
Техническим результатом заявленного изобретения является обеспечение снижения временной сложности процедур формирования и проверки подлинности коллективной ЭЦП благодаря использованию простых чисел специального вида, для которых операция умножения по модулю МДЧ p может быть выполнена без осуществления операции арифметического деления.
1
2
n
1
2
n
i
i
1
2
m
j
Технический результат достигается тем, что в известном способе формирования и проверки подлинности коллективной ЭЦП, заверяющей ЭД, заключающемся в том, что генерируют ЭК в виде совокупности точек, каждая из которых определяется парой МДЧ, являющихся соответственно абсциссой и ординатой данной точки ЭК в декартовой системе координат, генерируют точку G ЭК, имеющую порядок q, формируют совокупность из n≥2 секретных ключей в виде МДЧ k, k, …, k, по секретным ключам формируют n открытых ключей в виде точек P, P, …, P ЭК, получаемых по формуле P=kG, где i=1, 2, …, n, принимают ЭД, представленный МДЧ H, формируют коллективный открытый ключ в виде точки Р ЭК, генерируемой в зависимости от точек ЭК , , …, , где α, α, …, α - натуральные числа; 2≤m≤n; α≤n и j=1, 2, …, m, по формуле  в зависимости от принятого ЭД и от значения секретных ключей , , …, , формируют ЭЦП Q в виде двух МДЧ, формируют первое А и второе В проверочные МДЧ, сравнивают их и при совпадении их параметров делают вывод о подлинности ЭЦП, причем, по крайней мере, одно из проверочных МДЧ формируют в зависимости от коллективного открытого ключа Р, новым является то, что ЭЦП формируют в зависимости от коллективного открытого ключа, а в качестве ЭК используют ЭК, заданную над простым полем GF(p), где p - простое число вида , где k≥99; 0<g<k; 0<h<g; ; .
Формирование ЭЦП в зависимости от коллективного открытого ключа обеспечивает целостность коллективной подписи, которая заключается в практической невозможности генерации по известной коллективной ЭЦП каких-либо других ЭЦП. Выбор простых чисел такого вида обеспечивает выполнение операции модульного умножения путем выполнения операции арифметического умножения и не более десяти операций арифметического сложения и четырех операций арифметического сдвига, причем совокупная временная сложность всех операций арифметического сложения и арифметического сдвига существенно ниже временной сложности операции арифметического умножения. Благодаря устранению необходимости выполнения операции арифметического деления при выполнении модульного умножения обеспечивается существенное снижение временной сложности операции сложения точек ЭК, а следовательно, и существенное снижение временной сложности процедур формирования и проверки подлинности коллективной ЭЦП.
R
р
Новым является также то, что генерируют точку G ЭК, имеющую порядок q, равный простому λ-разрядному двоичному числу, где λ≥100, а ЭЦП формируют в виде пары МДЧ е и s, для чего генерируют m случайных МДЧ , , …,  генерируют m точек , , …,  ЭК по формуле , где j=1, 2, …, m, генерируют точку R ЭК по формуле , после чего формируют первое МДЧ е электронной цифровой подписи по формуле , где x - абсцисса точки R, х - абсцисса точки Р и δ - вспомогательное простое МДЧ, затем генерируют m МДЧ , , …, , по формуле  после чего генерируют второе МДЧ s электронной цифровой подписи по формуле ,
R'
причем первое проверочное МДЧ А формируют по формуле , где x - абсцисса точки R' ЭК, вычисленной по формуле , а второе проверочное МДЧ В формируют по формуле В=е.
Формирование первого проверочного МДЧ по точке R', вычисляемой по формуле , обеспечивает возможность применения заявленного способа формирования и проверки подлинности коллективной ЭЦП для построения на его основе протоколов слепой коллективной подписи, представляющих интерес для применения в системах тайного электронного голосования и системах электронных денег.
R
R'
Новым является также то, что генерируют точку G ЭК, имеющую порядок q, равный простому λ-разрядному двоичному числу, где λ≥100, а ЭЦП формируют в виде пары МДЧ r и s, для чего генерируют m случайных МДЧ , , …,  генерируют m точек , , …,  ЭК по формуле , где j=1, 2, …, m, генерируют точку R ЭК по формуле , после чего формируют первое МДЧ е ЭЦП по формуле , где x - абсцисса точки R, затем генерируют m МДЧ , , …,  по формуле , где j=1, 2, …, m, после чего генерируют второе МДЧ s ЭЦП по формуле , причем первое проверочное МДЧ А формируют по формуле , где x - абсцисса точки R' ЭК, вычисленной по формуле  где  и , а второе проверочное МДЧ В формируют по формуле В=e.
Вычисление значения МДЧ s в зависимости от абсциссы точки Р задает зависимость коллективной ЭЦП от коллективного открытого ключа, благодаря чему предотвращается возможность осуществления атак на коллективную ЭЦП, состоящих в формировании по коллективной ЭЦП, сгенерированной m пользователями к некоторому заданному ЭД, некоторой другой коллективной ЭЦП к этому же ЭД, принадлежащей коллективу пользователей, численность которого меньше, чем число m.
1
2
m
j
1
2
n
i
Предлагаемый способ может быть использован для числа пользователей, равного n≥2. Пользователи условно обозначаются номерами i=1, 2, …, n. Этот номер используется как индекс, указывающий на то, какому пользователю принадлежит секретный и открытый ключи, или на то, какой из пользователей генерирует отмеченные индексом МДЧ или точки ЭК. Из совокупности n пользователей некоторое их подмножество, состоящее из m произвольно выбранных пользователей, может быть задано номерами пользователей, входящих в данное подмножество, например номерами α, α, …, α, каждый из которых выбирается из множества чисел 1, 2, …, n. Таким образом, числа α, где j=1, 2, …, m, представляют собой выборку произвольных m номеров из множества {1, 2, …, n}, при этом m≤n. Соответственно этому совокупность открытых ключей , , …,  представляет собой выборку из множества всех открытых ключей P, P, …, P, а совокупность секретных ключей , где j=1, 2, …, m, представляет собой выборку из множества всех секретных ключей k, где i=1, 2, …, n.
1
2
m
Корректность заявленного способа доказывается теоретически. Рассмотрим, например, вариант реализации способа по п.2 формулы изобретения. Коллективный открытый ключ, соответствующий подмножеству пользователей с условными номерами α, α, …, α, представляет собой точку
Значения , которые представляют собой «доли» пользователей в коллективной подписи, генерируются по формуле , поэтому
Значение точки R', используемой для формирования первого проверочного МДЧ А, генерируется по формуле , т.е. оно равно
Следовательно, , т.е. правильно сформированная коллективная подпись удовлетворяет процедуре проверки подписи, т.е. корректность процедур генерации и проверки ЭЦП доказана.
1
2
m
Корректность заявленного способа по п.2 формулы изобретения доказывается следующим образом. Коллективный открытый ключ, соответствующий подмножеству пользователей с условными номерами α, α, …, α, представляет собой точку
Значения , которые представляют собой «доли» пользователей в коллективной подписи, генерируются по формуле , поэтому
.
Значение точки R', используемой для формирования первого проверочного МДЧ А, генерируется по формуле  где  и , т.е. оно равно
Таким образом, в процессе выполнения процедуры проверки подлинности ЭЦП получено равенство первого А и второго В проверочных МДЧ. Это означает, что коллективная подпись (е, s), сформированная в соответствии с п.3 формулы изобретения, удовлетворяет процедуре проверки подписи, т.е. корректность процедур генерации и проверки ЭЦП доказана.
Рассмотрим примеры реализации заявленного технического решения с использованием ЭК, описываемой уравнением (см. Приложение 1, пп.15-19)
,
где конкретные значения использованных параметров описаны в приводимых ниже численных примерах. Использованные в примерах ЭК были сгенерированы с помощью программы, разработанной специально для генерации ЭК, генерации точек ЭК, включая точки с заданным порядком, и выполнения операций над точками ЭК. Приводимые в примере МДЧ записаны для краткости в виде десятичных чисел, которые в вычислительных устройствах представляются и преобразуются в двоичном виде, т.е. в виде последовательности сигналов высокого и низкого потенциала. При этом выбор простого числа вида , где k≥99; 0<g<k; 0<h<g; ; , обеспечивает существенное уменьшение временной сложности умножения по модулю p, за счет чего увеличивается производительность процедур формирования и проверки коллективной ЭЦП, поскольку временная сложность операции сложения точек ЭК определяется временной сложностью операции умножения по модулю p.
1
2
3
4
2
3
4
1
Уменьшение временной сложности операции умножения по модулю p определяется следующими математическими выкладками. Пусть требуется умножить по модулю p два k-разрядных двоичных числа a и b. Выполним операцию арифметического умножения, получим МДЧ c=ab, которое представим в виде конкатенации четырех чисел u, u, u, u: , где u - (k-g)-разрядное МДЧ, u - (g-h)-разрядное МДЧ и u- h-разрядное МДЧ, а разрядность МДЧ u не превышает значение k+1. Тогда МДЧ с можно представить в виде следующей суммы
k
g
h
Из последнего выражения видно, что первое слагаемое сравнимо с нулем по модулю p=2±2±2±1, поэтому после выполнения пяти операций сложения и двух операций арифметического сдвига (на g и h двоичных разрядов) получим (g+k+1)-разрядное МДЧ , где  - (k-g)-разрядное МДЧ,  - (g-h)-разрядное МДЧ и  - h-разрядное МДЧ, а разрядность МДЧ  не превышает значение g+1. Представим МДЧ с' в виде следующей суммы
Из последнего выражения видно, что первое слагаемое сравнимо с нулем по модулю, , поэтому после выполнения пяти операций сложения и двух операций арифметического сдвига получим (2g+1)-разрядное МДЧ с*. При выборе значения g<k/2 разрядность МДЧ с* будет меньше значения k, т.е. . Таким образом, для выбранной структуры простого модуля операция модульного умножения выполняется за одно арифметическое умножение, четыре операции арифметического сдвига и десять арифметических сложений (вычитаний), т.е. без операции арифметического деления, трудоемкость которой в десять раз и более превышает трудоемкость операции арифметического умножения, а операции сложения (вычитания) и сдвига имеют трудоемкость в несколько десятков раз более низкую по сравнению с арифметическим умножением.
Пример 1. Простые числа вида .
Для генерации требуемых простых чисел была составлена компьютерная программа, с помощью которой были сгенерированы числа, представленные в таблице 1.
Пример 2. Реализация заявляемого способа по п.2 формулы изобретения.
В данном примере иллюстрируется конкретный вариант реализации заявленного способа, соответствующий п.2 формулы изобретения. В примере используется ЭК с параметрами, обеспечивающими достаточную стойкость для применения при решении реальных практических задач аутентификации информации. Этот пример иллюстрирует реальные размеры чисел, которые используются на практике при генерации и проверке подлинности ЭЦП. В примере 2 используется ЭК, определяемая следующими параметрами:
a=6277101735386680763835789423207666416083908700390324961276,
b=2455155546008943817740293915197451784769108058161191238065 и
p=6277101735386680763835789423207666416083908700390324961279.
Данная ЭК содержит количество точек, равное простому числу N=6277101735386680763835789423176059013767194773182842284081, т.е. любая ее точка имеет порядок q, равный значению N, т.е. q=N.
Рассмотрим коллектив из трех пользователей. При формировании и проверке подлинности ЭЦП (Подписью является пара МДЧ е и s) выполняют следующую последовательность действий.
1. Генерируют ЭК с параметрами, указанными выше.
2. Генерируют точку G:
G=(602046282375688656758213480587526111916698976636884684818,
174050332293622031404857552280219410364023488927386650641);
3. Формируют секретные ключи в виде случайных МДЧ
1
k=835789421138978964367813234978502635 - ключ первого пользователя;
2
k=432354875234868757699569735797423656 - ключ второго пользователя;
3
k=378236995234654633738959325641256478 - ключ третьего пользователя.
1
2
3
i
i
4. Формируют открытые ключи в виде точек ЭК P, P, P, генерируемых по формуле P=kG, где i=1, 2, 3:
1
P=(4998632987863305969589383775609285508391259684468221878571,
3936977070282976311058449358088801812667263289808569552507);
2
P=(3183995529308712653472894666414467994550809036839813286314,
3
533937252572420277336489931376120639477895768796475116755) P=(2460519770441949557377308960570234322707453364723768002258,
5697221429895096007852763432675082634800695858846874811546).
1
2
3
5. Формируют коллективный открытый ключ в виде точки Р по формуле P=P+P+P:
P=(5466709808663132160427804997530557588261999466785071607919, 3094755529860412503138802761495528631147969722560482750435).
6. Принимают ЭД, представленный, например, следующим МДЧ H (в качестве которого может быть взята, в частности, хэш-функция от ЭД):
Н=5632446783468748928950678390567120545845654255467.
7. Формируют ЭЦП Q в виде пары МДЧ е и s, для чего выполняют следующие действия.
1
2
3
1
7.1. Первый, второй и третий пользователи генерируют случайные МДЧ t, t и t, соответственно: t=238354578947621138997896343627813157;
2
t=3541159873322442346938797249222345146;
3
t=8783245153424329578927645512328452434.
1
2
3
i
i
7.2. Затем первый, второй и третий пользователи генерируют точки R, R и R, соответственно, по формуле R=tG:
1
R=(4034616864600876893968566340661364277862209951204087168214,
5354986298671793306148455265656005753266924704427361177928);
2
R=(763896398707307135746174586878825942002718762871849951765,
2190268348789982887368714134763583158952166104619959537922);
3
R=(4768439987199848340297410624554365763395501196612120808598,
1780080108542334678025936801360601044910398435222142281213).
1
2
3
7.3. Генерируют точку R по формуле R=R+R+R:
R1+R2=
(2115040644166268150259602186557982833629862018386492108246,
265231360319972006851956078734463687762899759456597797037);
R=(R1+R2)+R3=
=(2049342445469025355657309690147389401514754800026139293465,
2871959932873106080935776340098885530554301780485553661815).
P
R
7.4. В зависимости от x - абсциссы точки P (т.е. в зависимости открытого ключа) формируют первое МДЧ е электронной цифровой подписи по формуле , где x - абсцисса точки R и δ - вспомогательное простое МДЧ (δ=14321351422445826418603787835813271331335525254774025943):
е=14196952406774050805937925246208322744830763834670345067.
1
2
3
7.5. Первый, второй и третий пользователи генерируют МДЧ s, s и s, соответственно, по формуле , где q'=N и i=1, 2, 3:
1
s=5002732898284895478932205399925805958825563341982860766303;
2
s=3361998345454092481387593665247655640757729226072380144442;
3
s=635075841301660368515987217173134583188534557636864442199.
7.6. Генерируют второе МДЧ s электронной цифровой подписи по формуле :
s=2722705349653967564999996859170537169004632352509263068863.
8. Формируют первое проверочное МДЧ А, для чего выполняют следующую последовательность действий.
8.2. Генерируют точку R'=eP+sG:
eP=(1947187246176769247975833102262503011822374858475141545524, 3342861823410818659508496467470052690250788887830963414660);
sG=(5252519820860957470921503243612778322011766078195833864083,
4524870657215189484632767964134992401274413726033628771254);
R'=(2049342445469025355657309690147389401514754800026139293465,
2871959932873106080935776340098885530554301780485553661815);
8.3. Генерируют МДЧ А по формуле , где дополнительное МДЧ δ=14321351422445826418603787835813271331335525254774025943:
P
x=2049342445469025355657309690147389401514754800026139293465;
R'
x=2049342445469025355657309690147389401514754800026139293465;
H=5632446783468748928950678390567120545845654255467;
9. Формируют второе проверочное МДЧ В путем копирования МДЧ е: В=е=14196952406774050805937925246208322744830763834670345067.
10. Сравнивают первое А и второе В проверочные МДЧ.
Сравнение показывает, что параметры МДЧ А и В совпадают. Совпадение значений А и В означает, что коллективная ЭЦП является подлинной, т.е. относится к принятому ЭД, представленному МДЧ H, и сформирована тремя пользователями, по открытым ключам которых был сформирован коллективный открытый ключ, использованный для проверки подлинности подписи.
Пример 3. Реализация заявляемого способа по п.3 формулы изобретения.
1
2
3
В данном примере иллюстрируется конкретный вариант реализации заявленного способа, соответствующий п.3 формулы изобретения. В примере 3 используются секретные ключи, ЭК, количество пользователей и значения МДЧ t, t и t такие же как и в примере 2. Отличие состоит в том, что в примере 3 ЭЦП представляет собой пару МДЧ е и s, которые вычисляются с использованием других соотношений, а также первое проверочное МДЧ формируется по другой формуле. В примере 3 последовательно выполняют действия в полном соответствии с шагами 1, 2, 3, 4, 5, 6, 7.1, 7.2, и 7.3, описанными в примере 2, после чего выполняют следующую последовательность действий:
R
7.4. Формируют первое МДЧ e электронной цифровой подписи по формуле , где x - абсцисса точки R:
P
1
2
3
7.5. В зависимости от x - абсциссы точки P (т.е. в зависимости открытого ключа) первый, второй и третий пользователи генерируют МДЧ s, s и s, соответственно, по формуле , где i=1, 2, 3:
7.6. Генерируют второе МДЧ s электронной цифровой подписи по формуле :
s=3864949771235837049180758676735173133335987619584093868897.
8. Формируют первое проверочное МДЧ А, для чего выполняют следующую последовательность действий.
8.1. Вычисляют значения  и :
8.2. Генерируют точку  где  и :
wP=(3477338820102177084638700470951767405444887688243451296171,
2939308849110413774272148215167192630021513848994571097620)
vG=(5483431945087935931853246965615030770693093589259968673840,
4659673904494541361622703010838292502513523923212176703055)
R'=(2049342445469025355657309690147389401514754800026139293465,
2871959932873106080935776340098885530554301780485553661815);
8.3. Генерируют МДЧ A по формуле :
А=2049342445469025355657309690147389401514754800026139293465.
9. Формируют второе проверочное МДЧ В путем копирования МДЧ е:
В=е=2049342445469025355657309690147389401514754800026139293465.
10. Сравнивают первое А и второе В проверочные МДЧ.
Сравнение показывает, что параметры МДЧ А и В совпадают. Совпадение значений А и В означает, что коллективная ЭЦП является подлинной.
Пример 1 показывает, что простые числа с требуемой структурой двоичного представления могут быть легко сгенерированы, а примеры 2 и 3 экспериментально подтверждают корректность реализации заявленного способа, что дополняет математическое доказательство корректности, приведенное выше.
Таким образом, показано, что заявляемый способ может быть положен в основу стойких систем ЭЦП, обеспечивающих уменьшение времени формирования коллективной ЭЦП.
Приведенные примеры и математическое обоснование показывают, что предлагаемый способ формирования и проверки подлинности ЭЦП работает корректно, технически реализуем и позволяет получить сформулированный технический результат.
Приложение 1
Толкование терминов, используемых в описании заявки
1. Двоичный цифровой электромагнитный сигнал - последовательность битов в виде нулей и единиц.
2. Параметры двоичного цифрового электромагнитного сигнала: разрядность и порядок следования единичных и нулевых битов.
3. Разрядность двоичного цифрового электромагнитного сигнала - общее число его единичных и нулевых битов, например, число 10011 является 5-разрядным.
4. Электронный документ (ЭД) - двоичный цифровой электромагнитный сигнал, параметры которого зависят от исходного документа и способа его преобразования к электронному виду.
5. Электронная цифровая подпись (ЭЦП) - двоичный цифровой электромагнитный сигнал, параметры которого зависят от подписанного ЭД и от секретного ключа.
6. Секретный ключ - двоичный цифровой электромагнитный сигнал, используемый для формирования подписи к заданному электронному документу. Секретный ключ представляется, например, в двоичном виде как последовательность цифр «0» и «1».
7. Открытый ключ - двоичный цифровой электромагнитный сигнал, параметры которого зависят от секретного ключа и который предназначен для проверки подлинности ЭЦП,
8. Хэш-функция от ЭД - двоичный цифровой электромагнитный сигнал, параметры которого зависят от ЭД и выбранного метода ее вычисления.
9. Многоразрядное двоичное число (МДЧ) - двоичный цифровой электромагнитный сигнал, интерпретируемый как двоичное число и представляемый в виде последовательности цифр «0» и «1».
10. Операция возведения числа S в дискретную степень A по модулю n - это операция, выполняемая над конечным множеством натуральных чисел {0, 1, …, n-1}, включающем n чисел, являющихся остатками от деления всевозможных целых чисел на число n; результат выполнения операций сложения, вычитания и умножения по модулю n представляет собой число из этого же множества [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.]; операция возведения числа S в дискретную степень Z по модулю n определяется как Z-кратное последовательное умножение по модулю n числа S на себя, т.е. в результате этой операции также получается число W, которое меньше или равно числу n-1; даже для очень больших чисел S, Z и n существуют эффективные алгоритмы выполнения операции возведения в дискретную степень по модулю [см. Молдовян A.A., Молдовян Н.A., Гуц Н.Д., Изотов Б.В. Криптография: скоростные шифры. - СПб. БХВ-Петербург, 2002. - С.58-61]; выполнение операции возведения числа S в дискретную степень Z по модулю n обозначается как , где МДЧ W есть результат выполнения данной операции.
11. Функция Эйлера от натурального числа n - это число чисел, являющихся взаимно простыми с n и не превосходящими n [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.].
1
2
12. Показатель q по модулю n числа а, являющегося взаимно простым с n - это минимальное из чисел γ, для которых выполняется условие , т.е. q=min{γ, γ, …} [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.].
-1
13. Операция деления целого числа A на целое число В по модулю n выполняется как операция умножения по модулю n числа A на целое число В, которое является обратным к В по модулю n.
а
а
14. Порядок числа q по модулю n числа  - это показатель q по модулю n числа .
а
15. Эллиптическая кривая (ЭК) - это совокупность пар МДЧ, которые удовлетворяют соотношению вида , где коэффициенты  и b и модуль p определяют конкретный вариант ЭК. Над ЭК определены операция сложения пар МДЧ и операция умножения пары МДЧ на произвольное целое число. Указанные пары МДЧ записываются в виде (x, y), где x называется абсциссой точки, а y - ординатой. Операции, определенные над точками ЭК, выполняются как операции над координатами точек ЭК. В результате вычисляется пара МДЧ, которая является координатами точки, являющейся результатом операции. Точки ЭК называются равными, если равны их обе координаты x и y. Детальное описание ЭК можно найти в широко доступных книгах: [Б.Я.Рябко, A.Н.Фионов. Криптографические методы защиты информации. М., Горячая линия - Телеком, 2005. - 229 с. (см. с.97-130)]
A
A
B
B
16. Операция сложения двух точек A и В с координатами (x,y) и (x,y), соответственно, выполняется по формулам:  и , где , если точки A и В не равны, и , если точки A и В равны.
17. Операция умножения точки A на натуральное число n определяется как многократное сложение токи A: nА=A+A+…+A (n раз). Результатом умножения любой точки ЭК на нуль определяется точка, называемая бесконечно удаленной точкой и обозначаемой буквой О. Две точки A=(x, y) и -A=(x, -y) называются противоположными. Умножение на целое отрицательное число -n определяется следующим образом: (-n)A=n(-A). По определению принимают, что сумма двух противоположных точек равна бесконечно удаленной точке О [Б.Я.Рябко, A.Н.Фионов. Криптографические методы защиты информации. М., Горячая линия - Телеком, 2005. - 229 с. (см. с.97-130)].
18. Выполнение операций на точками ЭК осуществляется в вычислительных устройствах как действия над двоичными цифровыми электромагнитными сигналами, осуществляемыми по определенными правилам, определяемым через операции над МДЧ.
19. Порядком точки A ЭК называется наименьшее натуральное число q, такое что qA=О, т.е. такое, что результатом умножения точки A на число q является бесконечно удаленная точка.