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

Изобретение относится к области электросвязи и вычислительной техники, а конкретнее к области криптографических способов аутентификации электронных сообщений, передаваемых по телекоммуникационным сетям и сетям ЭВМ, и может быть использовано в системах передачи электронных сообщений (документов), заверенных электронной цифровой подписью (ЭЦП), представленной в виде многоразрядного двоичного числа (МДЧ). Здесь и далее под МДЧ понимается электромагнитный сигнал в двоичной цифровой форме, параметрами которого являются: число битов и порядок следования их единичных и нулевых значений (толкование терминов, используемых в описании изобретения см. в Приложении 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 - простое МДЧ;

формируют простое МДЧ а, такое что а≠1 и a^q 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);

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

формируют открытые ключи в виде точек ЭК P₁, 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 по формуле , где 1≤i≤n;

формируют первое проверочное МДЧ А, для чего генерируют МДЧ v по формуле и МДЧ w по формуле , затем генерируют точку R' по формуле , после чего МДЧ А получают по формуле , где x_R' - абсцисса точки R';

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

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

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

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

Наиболее близким по своей технической сущности к заявленному является известный способ формирования и проверки подлинности ЭЦП, описанный в патенте РФ №2356172 по заявке №2007130982 от 13.08.2007 [Молдовян А.А., Молдовян Н.А. Способ формирования и проверки подлинности электронной цифровой подписи, заверяющей электронный документ // Бюл. №14 от 20.05.2009].

Ближайший аналог (прототип) заключается в выполнении следующей последовательности действий

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

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

3) формируют открытые ключи в виде точек ЭК P₁, P_2, …, P_n, для чего генерируют точку G, имеющую значение порядка, равное q, и генерируют открытые ключи путем умножения точки G на МДЧ k₁, k₂, …, k_n, т.е. формируют открытые ключи по формулам P₁=k₁G, P₂=k₂G, …, P_n=k_nG;

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

5) формируют коллективный открытый ключ в виде точки Р ЭК, вычисляемой по формуле где α₁, α₂, …, α_m - натуральные числа; 2≤m≤n; α_j≤n и j=1, 2, …, m;

6) формируют коллективную ЭЦП Q, принадлежащую пользователям, владеющим секретными ключами , , …, в виде пары МДЧ (е, s), для чего

6.1) генерируют m случайных МДЧ , , …, таких, что выполняются условия , , …, ;

6.2) формируют m точек ЭК , , …, по формуле , где j=1, 2, …, m;

6.3) формируют точку R ЭК по формуле

6.4) генерируют МДЧ е по формуле , где x_R - абсцисса точки R;

6.5) генерируют m МДЧ , , …, по формуле , где j=1, 2, …, m;

6.6) генерируют МДЧ s по формуле ;

7) формируют первое проверочное МДЧ А, для чего

7.1) генерируют МДЧ v по формуле ;

7.2) генерируют МДЧ w по формуле ;

7.3) генерируют точку R' ЭК по формуле

7.4) проверочное МДЧ A получают по формуле , где x_R' - абсцисса точки R';

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

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

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

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

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

Технический результат достигается тем, что в известном способе формирования и проверки подлинности коллективной ЭЦП, заверяющей ЭД, заключающемся в том, что генерируют ЭК в виде совокупности точек, каждая из которых определяется парой МДЧ, являющихся соответственно абсциссой и ординатой данной точки ЭК в декартовой системе координат, генерируют точку G ЭК, имеющую порядок q, формируют совокупность из n≥2 секретных ключей в виде МДЧ k₁, k₂, …, k_n, по секретным ключам формируют n открытых ключей в виде точек P₁, P₂, …, P_n ЭК, получаемых по формуле P_i=k_iG, где i=1, 2, …, n, принимают ЭД, представленный МДЧ H, формируют коллективный открытый ключ в виде точки Р ЭК, генерируемой в зависимости от точек ЭК , , …, , где α₁, α₂, …, α_m - натуральные числа; 2≤m≤n; α_j≤n и j=1, 2, …, m, по формуле в зависимости от принятого ЭД и от значения секретных ключей , , …, , формируют ЭЦП Q в виде двух МДЧ, формируют первое А и второе В проверочные МДЧ, сравнивают их и при совпадении их параметров делают вывод о подлинности ЭЦП, причем, по крайней мере, одно из проверочных МДЧ формируют в зависимости от коллективного открытого ключа Р, новым является то, что ЭЦП формируют в зависимости от коллективного открытого ключа, а в качестве ЭК используют ЭК, заданную над простым полем GF(p), где p - простое число вида , где k≥99; 0<g<k; 0<h<g; ; .

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

Новым является также то, что генерируют точку G ЭК, имеющую порядок q, равный простому λ-разрядному двоичному числу, где λ≥100, а ЭЦП формируют в виде пары МДЧ е и s, для чего генерируют m случайных МДЧ , , …, генерируют m точек , , …, ЭК по формуле , где j=1, 2, …, m, генерируют точку R ЭК по формуле , после чего формируют первое МДЧ е электронной цифровой подписи по формуле , где x_R - абсцисса точки R, х_р - абсцисса точки Р и δ - вспомогательное простое МДЧ, затем генерируют m МДЧ , , …, , по формуле после чего генерируют второе МДЧ s электронной цифровой подписи по формуле ,

причем первое проверочное МДЧ А формируют по формуле , где x_R' - абсцисса точки R' ЭК, вычисленной по формуле , а второе проверочное МДЧ В формируют по формуле В=е.

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

Новым является также то, что генерируют точку G ЭК, имеющую порядок q, равный простому λ-разрядному двоичному числу, где λ≥100, а ЭЦП формируют в виде пары МДЧ r и s, для чего генерируют m случайных МДЧ , , …, генерируют m точек , , …, ЭК по формуле , где j=1, 2, …, m, генерируют точку R ЭК по формуле , после чего формируют первое МДЧ е ЭЦП по формуле , где x_R - абсцисса точки R, затем генерируют m МДЧ , , …, по формуле , где j=1, 2, …, m, после чего генерируют второе МДЧ s ЭЦП по формуле , причем первое проверочное МДЧ А формируют по формуле , где x_R' - абсцисса точки R' ЭК, вычисленной по формуле где и , а второе проверочное МДЧ В формируют по формуле В=e.

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

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

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

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

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

Следовательно, , т.е. правильно сформированная коллективная подпись удовлетворяет процедуре проверки подписи, т.е. корректность процедур генерации и проверки ЭЦП доказана.

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

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

.

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

Таким образом, в процессе выполнения процедуры проверки подлинности ЭЦП получено равенство первого А и второго В проверочных МДЧ. Это означает, что коллективная подпись (е, s), сформированная в соответствии с п.3 формулы изобретения, удовлетворяет процедуре проверки подписи, т.е. корректность процедур генерации и проверки ЭЦП доказана.

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

,

где конкретные значения использованных параметров описаны в приводимых ниже численных примерах. Использованные в примерах ЭК были сгенерированы с помощью программы, разработанной специально для генерации ЭК, генерации точек ЭК, включая точки с заданным порядком, и выполнения операций над точками ЭК. Приводимые в примере МДЧ записаны для краткости в виде десятичных чисел, которые в вычислительных устройствах представляются и преобразуются в двоичном виде, т.е. в виде последовательности сигналов высокого и низкого потенциала. При этом выбор простого числа вида , где k≥99; 0<g<k; 0<h<g; ; , обеспечивает существенное уменьшение временной сложности умножения по модулю p, за счет чего увеличивается производительность процедур формирования и проверки коллективной ЭЦП, поскольку временная сложность операции сложения точек ЭК определяется временной сложностью операции умножения по модулю p.

Уменьшение временной сложности операции умножения по модулю p определяется следующими математическими выкладками. Пусть требуется умножить по модулю p два k-разрядных двоичных числа a и b. Выполним операцию арифметического умножения, получим МДЧ c=ab, которое представим в виде конкатенации четырех чисел u₁, u₂, u₃, u₄: , где u₂ - (k-g)-разрядное МДЧ, u₃ - (g-h)-разрядное МДЧ и u₄ - h-разрядное МДЧ, а разрядность МДЧ u₁ не превышает значение k+1. Тогда МДЧ с можно представить в виде следующей суммы

Из последнего выражения видно, что первое слагаемое сравнимо с нулем по модулю p=2^k±2^g±2^h±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. Формируют секретные ключи в виде случайных МДЧ

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

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

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

4. Формируют открытые ключи в виде точек ЭК P₁, P₂, P₃, генерируемых по формуле P_i=k_iG, где i=1, 2, 3:

P₁=(4998632987863305969589383775609285508391259684468221878571,

3936977070282976311058449358088801812667263289808569552507);

P₂=(3183995529308712653472894666414467994550809036839813286314,

533937252572420277336489931376120639477895768796475116755) P₃=(2460519770441949557377308960570234322707453364723768002258,

5697221429895096007852763432675082634800695858846874811546).

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

P=(5466709808663132160427804997530557588261999466785071607919, 3094755529860412503138802761495528631147969722560482750435).

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

Н=5632446783468748928950678390567120545845654255467.

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

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

t₂=3541159873322442346938797249222345146;

t₃=8783245153424329578927645512328452434.

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

R₁=(4034616864600876893968566340661364277862209951204087168214,

5354986298671793306148455265656005753266924704427361177928);

R₂=(763896398707307135746174586878825942002718762871849951765,

2190268348789982887368714134763583158952166104619959537922);

R₃=(4768439987199848340297410624554365763395501196612120808598,

1780080108542334678025936801360601044910398435222142281213).

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

R1+R2=

(2115040644166268150259602186557982833629862018386492108246,

265231360319972006851956078734463687762899759456597797037);

R=(R1+R2)+R3=

=(2049342445469025355657309690147389401514754800026139293465,

2871959932873106080935776340098885530554301780485553661815).

7.4. В зависимости от x_P - абсциссы точки P (т.е. в зависимости открытого ключа) формируют первое МДЧ е электронной цифровой подписи по формуле , где x_R - абсцисса точки R и δ - вспомогательное простое МДЧ (δ=14321351422445826418603787835813271331335525254774025943):

е=14196952406774050805937925246208322744830763834670345067.

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

s₁=5002732898284895478932205399925805958825563341982860766303;

s₂=3361998345454092481387593665247655640757729226072380144442;

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:

x_P=2049342445469025355657309690147389401514754800026139293465;

x_R'=2049342445469025355657309690147389401514754800026139293465;

H=5632446783468748928950678390567120545845654255467;

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

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

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

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

В данном примере иллюстрируется конкретный вариант реализации заявленного способа, соответствующий п.3 формулы изобретения. В примере 3 используются секретные ключи, ЭК, количество пользователей и значения МДЧ t₁, t₂ и t₃ такие же как и в примере 2. Отличие состоит в том, что в примере 3 ЭЦП представляет собой пару МДЧ е и s, которые вычисляются с использованием других соотношений, а также первое проверочное МДЧ формируется по другой формуле. В примере 3 последовательно выполняют действия в полном соответствии с шагами 1, 2, 3, 4, 5, 6, 7.1, 7.2, и 7.3, описанными в примере 2, после чего выполняют следующую последовательность действий:

7.4. Формируют первое МДЧ e электронной цифровой подписи по формуле , где x_R - абсцисса точки R:

7.5. В зависимости от x_P - абсциссы точки 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 с.].

12. Показатель q по модулю n числа а, являющегося взаимно простым с n - это минимальное из чисел γ, для которых выполняется условие , т.е. q=min{γ₁, γ₂, …} [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.].

13. Операция деления целого числа A на целое число В по модулю n выполняется как операция умножения по модулю n числа A на целое число В^-1, которое является обратным к В по модулю n.

14. Порядок числа q по модулю n числа а - это показатель q по модулю n числа а.

15. Эллиптическая кривая (ЭК) - это совокупность пар МДЧ, которые удовлетворяют соотношению вида , где коэффициенты а и b и модуль p определяют конкретный вариант ЭК. Над ЭК определены операция сложения пар МДЧ и операция умножения пары МДЧ на произвольное целое число. Указанные пары МДЧ записываются в виде (x, y), где x называется абсциссой точки, а y - ординатой. Операции, определенные над точками ЭК, выполняются как операции над координатами точек ЭК. В результате вычисляется пара МДЧ, которая является координатами точки, являющейся результатом операции. Точки ЭК называются равными, если равны их обе координаты x и y. Детальное описание ЭК можно найти в широко доступных книгах: [Б.Я.Рябко, A.Н.Фионов. Криптографические методы защиты информации. М., Горячая линия - Телеком, 2005. - 229 с. (см. с.97-130)]

16. Операция сложения двух точек A и В с координатами (x_A,y_A) и (x_B,y_B), соответственно, выполняется по формулам: и , где , если точки 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 является бесконечно удаленная точка.

Изобретение относится к области электросвязи, а именно к области криптографических устройств и способов проверки электронной цифровой подписи (ЭЦП). Техническим результатом является уменьшение времени формирования и проверки подлинности коллективной ЭЦП без снижения ее уровня стойкости. Способ генерации и проверки ЭЦП заключается в том, что генерируют эллиптическую кривую (ЭК), заданную над простым полем GF(p), где p - простое число вида , где k≥99; 0<g<k; 0<h<g; ; , в виде совокупности точек, каждая из которых задается двумя многоразрядными двоичными числами (МДЧ) - ее абсциссой и ординатой, формируют n≥2 секретных ключей в виде МДЧ k₁, k₂, …, k_n, по секретным ключам формируют n открытых ключей в виде точек P₁, P₂, …, P_n, принимают электронный документ (ЭД), представленный МДЧ H, формируют коллективный открытый ключ в виде точки Р ЭК, генерируемой в зависимости от точек , , …, , где ось α₁, α₂,…, α_m - натуральные числа, 2≤m≤n, α_j≤n и j=1, 2, …, m, в зависимости от принятого ЭД, от значений , , …, и от точки Р формируют ЭЦП Q в виде двух МДЧ е и s, формируют первое А и второе В проверочные МДЧ, причем, по крайней мере, одно из проверочных МДЧ формируют в зависимости от коллективного открытого ключа P, сравнивают МДЧ А и В. При совпадении их параметров делают вывод о подлинности ЭЦП. 2 з.п. ф-лы, 1 табл.

1. Способ формирования и проверки подлинности коллективной электронной цифровой подписи, заверяющей электронный документ, заключающийся в том, что генерируют эллиптическую кривую в виде совокупности точек, каждая из которых определяется парой многоразрядных двоичных чисел, являющихся соответственно абсциссой и ординатой данной точки эллиптической кривой в декартовой системе координат, генерируют точку G эллиптической кривой, имеющую порядок q, формируют совокупность из n≥2 секретных ключей в виде многоразрядных двоичных чисел k₁, k₂, …, k_n, по секретным ключам формируют n открытых ключей в виде точек P₁, P₂, …, P_n эллиптической кривой, получаемых по формуле P_i=k_iG, где i=1, 2, …, n, принимают электронный документ, представленный многоразрядным двоичным числом Н, формируют коллективный открытый ключ в виде точки P эллиптической кривой, генерируемой в зависимости от точек эллиптической кривой , , …, , где α₁, α₂, …, α_m - натуральные числа; 2≤m≤n; α_j≤n и j=1, 2, …, m, по формуле в зависимости от принятого электронного документа и от значения секретных ключей , , …, формируют электронную цифровую подпись Q в виде двух многоразрядных двоичных чисел, формируют первое А и второе В проверочные многоразрядные двоичные числа, сравнивают их и при совпадении их параметров делают вывод о подлинности электронной цифровой подписи, причем, по крайней мере, одно из проверочных многоразрядных двоичных чисел формируют в зависимости от коллективного открытого ключа Р, отличающийся тем, что электронную цифровую подпись формируют в зависимости от коллективного открытого ключа, а в качестве эллиптической кривой используют эллиптическую кривую, заданную над простым полем GF(p), где p - простое число вида , где k≥99; 0<g<k; 0<h<g;

2. Способ по п.1, отличающийся тем, что генерируют точку G эллиптической кривой, имеющую порядок q, равный простому λ-разрядному двоичному числу, где λ≥100, а электронную цифровую подпись формируют в виде пары многоразрядных двоичных чисел е и s, для чего генерируют m случайных многоразрядных двоичных чисел , , …, , генерируют m точек , , …, эллиптической кривой по формуле , где j=1, 2, …, m, генерируют точку R эллиптической кривой по формуле , после чего формируют первое многоразрядное двоичное число е электронной цифровой подписи по формуле , где x_R - абсцисса точки R, x_P - абсцисса точки Р и δ - вспомогательное простое многоразрядное двоичное число, затем генерируют m многоразрядных двоичных чисел , , …, по формуле , после чего генерируют второе многоразрядное двоичное число s электронной цифровой подписи по формуле , причем первое проверочное многоразрядное двоичное число А формируют по формуле , где x_R' - абсцисса точки R' эллиптической кривой, вычисленной по формуле , а второе проверочное многоразрядное двоичное число В формируют по формуле В=e.

3. Способ по п.1, отличающийся тем, что генерируют точку G эллиптической кривой, имеющую порядок q, равный простому λ-разрядному двоичному числу, где λ≥100, а электронную цифровую подпись формируют в виде пары многоразрядных двоичных чисел е и s, для чего генерируют m случайных многоразрядных двоичных чисел , , …, , генерируют m точек , , …, эллиптической кривой по формуле , где j=1, 2, …, m, генерируют точку R эллиптической кривой по формуле после чего формируют первое многоразрядное двоичное число е электронной цифровой подписи по формуле , где x_R - абсцисса точки R, затем генерируют m многоразрядных двоичных чисел , , …, по формуле где j=1, 2, …, m, после чего генерируют второе многоразрядное двоичное число s электронной цифровой подписи по формуле , причем первое проверочное многоразрядное двоичное число А формируют по формуле , где x_R' - абсцисса точки R' эллиптической кривой, вычисленной по формуле где и , а второе проверочное многоразрядное двоичное число В формируют по формуле B=е.