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

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

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

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

ed=1 mod (p-1)(q-1), принимают электронный документ (ЭД), представленный МДЧ H;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

формируют первое проверочное МДЧ A, для чего генерируют МДЧ R' по формуле

R'=a^sγ^e и формируют МДЧ A=e'=f(M||R');

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

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

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

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

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

x_c=k²-x_A-x_B mod p и y_c=k(x_A-x_c)-y_A mod p,

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

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

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

В прототипе, т.е. в способе формирования и проверки подлинности ЭЦП по стандарту ГОСТ Р 34.10-2001, генерируют ЭК, описываемую уравнением

y²=x³+ax+b mod p, поэтому генерация ЭК состоит в генерации чисел a, b и p, являющихся параметрами ЭК и однозначно задающих множество точек ЭК, абсцисса и ордината каждой из которых удовлетворяет указанному уравнению. Ближайший аналог (прототип) заключается в выполнении следующей последовательности действий:

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

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

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

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

генерируют случайное МДЧ 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;

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

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

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

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

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

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

Поставленная цель достигается тем, что в известном способе формирования и проверки подлинности ЭЦП, заверяющей ЭД, заключающемся в том, что генерируют секретный ключ в виде МДЧ x, по секретному ключу формируют открытый ключ Y в виде более чем одного МДЧ, принимают электронный документ, представленный МДЧ H, в зависимости от принятого электронного документа и от секретного ключа формируют электронную цифровую подпись Q в виде двух МДЧ, в зависимости от ЭД, ЭЦП и открытого ключа формируют первое A и второе B проверочные МДЧ, сравнивают их и при совпадении их параметров делают вывод о подлинности электронной цифровой подписи, согласно изобретению открытый ключ Y формируют в виде матрицы МДЧ размерности w×w, где 2≤w≤32.

Новым является то, что открытый ключ Y формируют в виде матрицы МДЧ размерности w×w, где 2≤w≤32, значение определителя которой равно единице по модулю p.

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

Новым является также и то, что открытый ключ Y генерируют в виде матрицы МДЧ размерности 2×2, для чего генерируют матрицу МДЧ G размерности 2×2, имеющую порядок q, и открытый ключ Y формируют по формуле Y=G^x (mod p), а электронную цифровую подпись Q формируют в виде пары МДЧ e и s, для чего генерируют случайное МДЧ k, генерируют матрицу МДЧ R по формуле R=G^k (mod p), где p - МДЧ, являющееся модулем, по которому выполняются операции над МДЧ, входящими в состав матрицы МДЧ G при выполнении над G операции возведения в степень, затем формируют первое МДЧ e электронной цифровой подписи по формуле e=rH mod δ, где r=(r₁₁||r₁₂) - МДЧ, равное конкатенации МДЧ первой строки матрицы МДЧ R, и δ - вспомогательное простое МДЧ, затем генерируют второе МДЧ s электронной цифровой подписи по формуле s=(k-ex)mod q, после чего формируют первое и второе проверочные МДЧ A и B по формулам A=r'H mod δ и B=e, где r=(r'₁₁||r'₁₂) МДЧ, равное конкатенации МДЧ первой строки матрицы МДЧ R', вычисленной по формуле R'=Y^eG^s(mod p).

Новым является также и то, что генерируют матрицу МДЧ G размерности 2×2, значение определителя которой равно единице по модулю p.

Новым является также и то, что открытый ключ Y генерируют в виде матрицы МДЧ размерности 3×3, для чего генерируют матрицу МДЧ G размерности 3×3, имеющую порядок q, и открытый ключ Y формируют по формуле Y=G^x (mod p), где p - МДЧ, являющееся модулем по которому выполняются операции над МДЧ, входящими в состав матрицы МДЧ G при выполнении над G операции возведения в степень, а электронную цифровую подпись Q формируют в виде пары МДЧ e и s, для чего генерируют случайное МДЧ k, генерируют матрицу МДЧ R по формуле R=G^k (mod p), затем формируют первое МДЧ е электронной цифровой подписи по формуле e=rH mod δ, где r=(r₁₁||r₁₂||r₁₃) - МДЧ, равное конкатенации МДЧ первой строки матрицы МДЧ R, и δ - вспомогательное простое МДЧ, затем генерируют второе МДЧ s электронной цифровой подписи по формуле s=(k+ex)mod q, после чего формируют первое и второе проверочные МДЧ A и B по формулам A=r'H mod δ и B=e, где r=(r'₁₁||r'₁₂||r'₁₃) - МДЧ, равное конкатенации МДЧ первой строки матрицы МДЧ R', вычисленной по формуле R'=Y^q-eG^s(mod p).

Новым является также и то, что генерируют матрицу МДЧ G размерности 3×3, значение определителя которой равно единице по модулю p.

Конкатенацией двух чисел α и b, представленных в некоторой позиционной системе исчисления в виде a=a₁a₂a₃…a_g и b=b₁b₂b₃…b_k, называется число c=a||b==a₁a₂a₃…a_gb₁b₂b₃…b_k. Знак || обозначает операцию конкатенации.

Матрица МДЧ - это набор МДЧ, расположенный в следующем виде.

Матрицу МДЧ обычно обозначают заглавной латинской буквой, например Q. Ее также записывают в сокращенном виде {q_ij}, i=1, 2, …, m; j=1, 2, …, h, где МДЧ q_ij называются элементами матрицы. Если m=h, то матрица является квадратной. Размерность матрицы - это два натуральных числа, означающие количество строк (w) и количество столбцов (h) в матрице. Размерность матрицы записывается в виде w × h. Квадратной матрицей называется матрица, содержащая одинаковое число строк и столбцов. Над квадратными матрицами МДЧ определена операция умножения, которая осуществляется путем выполнения операций над МДЧ, являющимися элементами перемножаемых матриц МДЧ. В результате вычисляется новая матрица МДЧ, являющаяся результатом операции умножения двух матриц. Матрицы МДЧ Q и U называются равными, если выполняется равенство q_ij=u_ij для всех значений индексов. Детальное описание свойств матриц и действий над ними можно найти в широко доступных книгах: [А.И.Кострикин. Введение в алгебру. Основы алгебры. - М.: Физматлит. 1994. - 320 с.], [А.Г.Курош. Курс высшей алгебры. - М.: «Наука», 1971. - 431 с.] и [Л.Б.Шнеперман. Курс алгебры и теории чисел в задачах и упражнениях.- Минск: «Вышэйшая школам, 1986. - 272 с.]. Определителем матрицы Q, задаваемой набором чисел {q_ij}, называется алгебраическая сумма всевозможных произведений коэффициентов q_ij, взятых по одному из каждой строки и из каждого столбца, причем слагаемые, отвечающие четным перестановкам, входят со знаком «плюс», а слагаемые, отвечающие нечетным перестановкам, - со знаком «минус» (детальное описание правил вычисления определителя можно найти в книге [А.И.Кострикин. Введение в алгебру. Основы алгебры. - М.: Физматлит. 1994. - 320 с.]). При использовании над матрицами МДЧ, принадлежащими некоторому конечному множеству матриц МДЧ, операции умножения, определенной через операции сложения МДЧ по модулю p и умножения МДЧ по модулю p, определитель также вычисляется по модулю p. Операция умножения квадратной матрицы Q на квадратную матрицу U (матрицы О и U представлены наборами чисел {q_ij} и {u_ij}, i=1, 2, …, w; j=1, 2, …w, соответственно) выполняется по формуле:

либо по формуле

где p - простое МДЧ, c_ij - элемент матрицы С, являющейся результатом операции умножения матриц МДЧ Q и U. При вычислении по второй формуле и фиксированном размере МДЧ p матрицы МДЧ состоят из элементов конечного множества следующих МДЧ: 0, 1, 2, 3, …, p-1, т.е. совокупность всех существующих матриц заданной фиксированной размерности является конечным множеством. Однако число таких матриц чрезвычайно велико при достаточно больших значениях p, благодаря чему матрицы МДЧ с операциями над их элементами, выполняемыми по модулю простого МДЧ р, могут быть эффективно использованы для построения алгоритмов электронной цифровой подписи. Операция возведения матрицы М в натуральную степень n определяется как n-кратное умножение матрицы М на саму себя: MⁿМ·М·М·…М (n раз). Если операции сложения и умножения над элементами матрицы выполняются по модулю простого МДЧ p, то в конце правой части формул будем указывать в скобках mod p, например: С=Q+U (mod p); С=QU (mod p) и С=Qⁿ (mod p). Единичной матрицей называется такая матрица Е, элементы которой равны δ_ij:

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

Определителем матрицы А размерности w×w, задаваемой набором чисел {a_ij}, называется алгебраическая сумма всевозможных произведений, включающих w сомножителей a_ij, взятых по одному из каждой строки и из каждого столбца таким образом, что в каждое произведение взят элемент из каждой строки и каждого столбца (ни в одно из произведений не входят два сомножителя, принадлежащие одной и той же строке или одному и тому же столбцу). При этом слагаемые, отвечающие четным перестановкам входят со знаком «плюс», а слагаемые, отвечающие нечетным перестановкам, - со знаком «минус» (детальное описание правил вычисления определителя можно найти в книге [А.И.Кострикин. Введение в алгебру. Основы алгебры. - М.: Физматлит. 1994. - 320 с.]). В заявленном способе используются матрицы, элементами которых являются МДЧ, принимающие значения от нуля до p-1 и над которыми выполняются операции сложения и умножения по модулю p. Для таких матриц значение определителя вычисляется по модулю p и находится в интервале от нуля до p-1, т.е. определитель равен некоторому значению d по модулю p, где 0≤d≤p-1.

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

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

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

Порядком матрицы М называется наименьшее натуральное число q, такое что M^q=Е, т.е. такое, что результатом умножения матрицы М на саму себя q раз является единичная матрица Е.

Корректность заявленного способа доказывается теоретически. Рассмотрим, например, варианты реализации заявленного способа по пп.3 и 4 формулы изобретения. Открытый ключ, соответствующий секретному ключу x, представляет собой матрицу МДЧ

Y=G^x(mod p).

Матрица МДЧ R генерируется по формуле R=G^k (mod p), а первое МДЧ в ЭЦП (e, s) вычисляется по формуле e=rH mod δ, где r=(r₁₁||r₁₂) - МДЧ, равное конкатенации МДЧ первой строки матрицы e=rH mod δ, где r=(r₁₁||r₁₂) - МДЧ, равное конкатенации МДЧ первой строки матрицы МДЧ R. Значение s генерируется по формуле

s=(k-ex) mod q, поэтому матрица МДЧ R', генерируемая по формуле R'=Y^eG^s (modp) и используемая для формирования первого проверочного МДЧ A, равна

R'=Y^eG^s(mod p)=G^exG^s(mod p)=G^ex+(k-ex)(mod p)=G^k(mod p)=R.

Поскольку матрицы МДЧ R' и R одинаковы, то конкатенация МДЧ первой строки матрицы МДЧ R' равна конкатенации МДЧ первой строки матрицы МДЧ R, т.е. r'=(r'₁₁||r'₁₂ ||r'₁₃)=r=(r₁₁||r₁₂||r₁₃), следовательно, A=r'H mod δ=rH mod δ=e=B. Это означает, что правильно сформированная коллективная ЭЦП удовлетворяет процедуре проверки подписи, т.е. корректность процедур генерации и проверки ЭЦП доказана. Аналогичным образом дается доказательство корректности и для частных вариантов реализации способа по пп.5 и 6 формулы изобретения.

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

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

1. Формируют простое число р, такое что p-1 содержит большой простой множитель q, т.е. p=Nq+1, где N - четное число: p=10005473, где q=2767 и N=3616.

2. Генерируют секретный ключ x в виде случайного МДЧ:

x=33827005351925439685.

3. Формируют открытый ключ Y в виде матрицы размерности 5×5, для чего выполняют следующую последовательность действий:

3.1 Генерируют матрицу G размерности 5×5, значение определителя которой равно 1 по модулю p=10005473:

G=(5521418; 9882273; 9796931; 4431857; 2841720; 4578372; 9738756; 4426894; 3055035; 8474489; 4006629; 4515646; 4234851; 5725156; 2191602; 9982583; 9078580; 4277820; 3587111; 8135893; 7201177; 4103066; 6317790; 1548718; 7990799).

Полученная вспомогательная матрица МДЧ G имеет порядок q, т.е. для нее выполняется условие G^q mod p=Е, где Е - единичная матрица.

3.2 Генерируют матрицу Y по формуле Y=G^x (mod p):

Y=(4296743; 8563867; 8471863; 8368695; 7928365; 4134935; 3148248; 6191206; 6229991; 772279; 1327899; 2606056; 639497; 1480633; 6698567; 9124160; 9801301; 7270257; 4120460; 2299830; 6583146; 7368696; 9905973; 1882611; 7275024).

Полученная матрица такова, что значение ее определителя по модулю p равно единице. Это имеет место в силу следующего известного математического факта: определитель произведения матриц равен произведению определителей матриц, являющихся сомножителями [А.Г.Курош. Курс высшей алгебры. - М.: «Наука», 1971. - 431 с.].

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

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

5.1. Генерируют случайное число k: k=14793055334187273340.

5.2. Формируют матрицу R по формуле R=G^k (mod p):

R=(8460438; 5362248; 2710988; 2628738; 3561800; 435362; 5699998; 9421229; 1097018; 2072055; 9502353; 7784036; 3072771; 712851; 2950747; 4615012; 4704650; 5571737; 5627045; 864825; 6956383; 7481137; 3731806; 6080056; 1515799).

5.3. Генерируют первый элемент e электронной подписи в виде МДЧ, вычисляемого по формуле e=rH mod δ, где r=(r₁₁||r₁₂||r₁₃||r₁₄||r₁₅) - МДЧ, равное конкатенации МДЧ первой строки матрицы МДЧ R и δ - дополнительное простое МДЧ (δ=590162611): e=36603270.

5.4. Формируют значение s путем выполнения операции, задаваемого формулой

s=(k+ex)mod q: s=385.

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

6.2. Генерируют матрицу R'=Y^eG^s (mod p):

Y^e=(517561; 8536686; 6521010; 4917725; 8562973; 1364690; 3655546; 3336162; 6584305; 6377174; 5175358; 4529740; 9376409; 4684982; 5575429; 7366320; 9877290; 852679; 2007774; 8990862; 7166747; 6359216; 3306906; 4104536; 185598) G^s=(6000694; 4327060; 2285488; 3818885; 7999488; 363129; 4668557; 9725034; 2664600; 8325335; 4873523; 4533324; 7194179; 5582214; 5934647; 866186; 6026734; 5845480; 7846208; 1090778; 4219697; 6286490; 7327398; 9134835; 4959056) R'=(8460438; 5362248; 2710988; 2628738; 3561800; 435362; 5699998; 9421229; 1097018; 2072055; 9502353; 7784036; 3072771; 712851; 2950747; 4615012; 4704650; 5571737; 5627045; 864825; 6956383; 7481137; 3731806; 6080056; 1515799).

6.3. Генерируют МДЧ A по формуле A=r'H mod δ и B=e, где r'=(r'₁₁||r'₁₂||r'₁₃||r'₁₄||r'₁₅) - МДЧ, равное конкатенации МДЧ первой строки матрицы МДЧ R', где дополнительное МДЧ δ=590162611: A=36603270.

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

B=e=36603270.

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

Сравнение показывает, что параметры МДЧ A и B совпадают. Совпадение значений A и B означает, что ЭЦП является подлинной, т.е. относится к принятому ЭД, представленному МДЧ Н.

Пример 2. Реализация заявленного способа по п.4 формулы изобретения (этот пример иллюстрирует частный вариант реализации п.3 формулы изобретения, отличающийся тем, что генерируется матрица G со значением определителя равным единице по модулю p). Предположим, что пользователю необходимо подписать сообщение, представленное МДЧ H. Для этого выполняется следующая последовательность действий.

1. Формируют простое число p, такое что p-1 содержит большой простой множитель q, т.е. p=Nq+1, где N - четное число:

p=1213101055353860365198942393055406360449930466509, где q=910683421037711696704229;

N=1332077676314286889695452.

2. Генерируют секретный ключ в виде случайного МДЧ x:

x=26412233452258564873.

3. Формируют открытый ключ в виде матрицы Y размерности 2×2, значение определителя которой равно единице по модулю p, для чего выполняют следующую последовательность действий:

3.1 Генерируют матрицу G размерности 2×2, значение определителя которой по модулю p равно 1, причем такую, что ее порядок равен значению q:

G=(1202355537700013630255474902061928748859377385024;

296060370551540592849932964420977114748927579258\\

661780860731578736974963326904080423309318448732;

726266908513412605605689590295630046107457372564). Ввиду достаточно большой длины МДЧ, являющихся элементами матрицы G, каждый элемент матрицы указан отдельно, при этом строки матрицы разделены двойной наклонной чертой. В такой записи элементы матрицы g₁₁, g₁₂ g₂₁ и g₂₂ записаны последовательно сверху вниз в отдельных строках.

3.2 Генерируют матрицу Y по формуле Y=G^x (mod p):

Y=(765668645922971131462637659176175002121265271912;

632062461662953235981713575015866586830213534137\\

686546034364915360874564606107543524491696599648;

173718371623103935352742823316230007430864301765).

4. Принимают ЭД, представленный, например, следующим МДЧ H:

H=435346457676523423.

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

5.1. Пользователь генерирует случайное число k:

k=27049461528626923206.

5.2. Затем формируют матрицу R путем выполнения операции, задаваемой формулой R=G^k (mod p):

R=(455363329583359023625266899777316926640501013681;

648976367168776500763467574763935700112689500783\\

193145359861504811918206048283567465987970607659;

385854600850718001481881779520448776959506610386).

5.3. Генерируют первый элемент e электронной цифровой подписи в виде МДЧ, вычисляемого по формуле e=rH mod δ, где r=(r₁₁||r₁₂) - МДЧ, равное конкатенации МДЧ первой строки матрицы МДЧ R, δ - дополнительное простое МДЧ

δ=590162611):

e=247157248.

5.4. Формируют второй элемент подписи s путем выполнения операции, задаваемой формулой s=(k-ex)mod q: s=714538875050403859391403.

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

6.1. Генерируют матрицу R'=Y^eG^s (mod p):

Y^e=(1054289836977813241220692865884055278112848775391;

143920443514015090545932680147055853856811193745\\

412720594141934652505374888529868609136342061615;

497953129779437524509848233343978685201212761147)

G^s=(557140970524604453256865016479207346842314027711;

853953720518151165717250776060151697410440223270\\

654964802199660308072055093173837833684333897401;

246994405741321957387664288252066868517103968796)

R'=(455363329583359023625266899777316926640501013681;

648976367168776500763467574763935700112689500783\\

193145359861504811918206048283567465987970607659;

385854600850718001481881779520448776959506610386).

6.3. Генерируют МДЧ A по формуле A=r'H mod δ, где r'=(r'₁₁||r'₁₂) - МДЧ, равное конкатенации МДЧ первой строки матрицы МДЧ R', где дополнительное МДЧ δ=590162611:

A=247157248.

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

B=e=247157248.

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

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

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

1. Формируют простое число p, такое что p-1 содержит большой простой множитель q, т.е. p=Nq+1, где N - четное число:

p=882693152152073761004890298352885499372774448173, где q=985479877918161283757537;

N=895698808195631774845356.

2. Генерирует секретный ключ x в виде случайного МДЧ:

x=3451073958338264285.

3. Формируют открытый ключ Y в виде матрицы размерности 3×3, значение определителя которой по модулю p равно 1, для чего выполняют следующую последовательность действий:

3.1 Генерируют матрицу G размерности 3×3, значение определителя которой по модулю p равно 1, причем такую, что ее порядок равен значению q:

G=(363721035304855322270717595705381196622143562753;

342045577522215337424809683133061190595364260060;

568428018033030838358100753510855868372542160348\\

388524193794655360623939908830582907417739970436;

435124243767703655645468663573798796968229028088;

463861800676775168887578605344607683965346873378\\

728967772850853898600948656958266412109957471628;

430092459273736209053619942186148755067683099452;

436091184234493207523503292485824458657311822562).

Полученная дополнительная матрица G имеет порядок q, т.е. для нее выполняется условие G^q mod p=1.

3.2 Генерируют матрицу Y пo формуле Y=G^x (modp):

Y=(793649427315761259406026831506906225041194804340;

645841333769727307401444994977369021466398790655;

638569888366953175867918938367514561265665271725\\

805215282344370055909657251366622501259863265035;

554880153034978377878010779839396184509620640898;

403887562274208021593244476181441917851844232905\\

353096382126238920667662144589525065608865066344;

138815970154523201194960482573446216625756028413;

653804408722869157056518320036150833843832588519).

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

H=6756345234523465.

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

5.1. Пользователь генерирует случайное число k:

k=12860134276868188623.

5.2. Формируют матрицу R путем выполнения операции, задаваемых формулой

R=G^k(mod p):

R=(456138598778574934094067405707408823929620188965;

134838090968284020883275585101955145958537373351;

712597734764234344232810530794307868494671952084\\

725194419963133604462301246966629245403495216092;

196023528841210323468350988094893160456639667948;

479537360665405040641147720611639243385991097375\\

747287101147541789531616146212253869003469601318;

188409773319432556126047166877690183782372779200;

32009504965824735724901667917940853117887655802).

5.3. Генерируют первый элемент e электронной подписи в виде МДЧ, вычисляемого по формуле e=rH mod δ, где r=(r₁₁||r₁₂||r₁₃) - МДЧ, равное конкатенации МДЧ первой строки матрицы МДЧ R, δ - дополнительное простое МДЧ

(δ=1011932689):

e=644117540.

5.5. Формируют значение s путем выполнения операции, задаваемого формулой

s=(k+ex)mod q:

s=640156557585861119001588.

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

6.2. Генерируют матрицу R'=Y^q-eG^s(mod p)=Y^q-eG^s(mod p):

q-e=985479877918160639639997;

Y^q-e=(480039256397844235392097964436954752722231271379;

43525703614678367797622053909289662734508446485;

621482813419723875717789152794218157594939695803\\

594427188164364341885587693597522368397543407967;

795365846233004098177105822781927741349303132756;

642387569971198053344061537576576204643826715679\\

543716309036298412258991999827654617223985145669;

180471582091367944622121423646832322388139112345;

140159879304206682557015533315183354508497921826)

G^s=(630064404804120002899043649410178012882848244991;

275025358523863904761511873188319990669954654707;

197905564701079164883948973819987567672616933610\\

192845503297590775248455116562714514304860114920;

404238445746336652176571611625346772176575052622;

162276339095416444649406055174213223482444891319\\

496371813589504230909314363323196807492773807177;

836287570593455187972972244740643582757106958732;

881783771774713241919479482510519794701877329632)

R'=(456138598778574934094067405707408823929620188965;

134838090968284020883275585101955145958537373351;

712597734764234344232810530794307868494671952084\\

725194419963133604462301246966629245403495216092;

196023528841210323468350988094893160456639667948;

479537360665405040641147720611639243385991097375\\

747287101147541789531616146212253869003469601318;

188409773319432556126047166877690183782372779200;

32009504965824735724901667917940853117887655802).

6.3. Генерируют МДЧ A по формуле A=r'Hmod δ и B=е, где r'=(r'₁₁||r'₁₂||r'₁₃) - МДЧ, равное конкатенации МДЧ первой строки матрицы МДЧ R', где дополнительное

МДЧ

δ=1011932689:

A=644117540.

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

B=е=644117540.

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

Сравнение показывает, что параметры МДЧ A и B совпадают. Совпадение значений A и B означает, что ЭЦП является подлинной, т.е. относится к принятому ЭД, представленному МДЧ H.

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

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

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

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

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

Приложение 1

Толкование терминов, используемых в описании заявки

1. Двоичный цифровой электромагнитный сигнал - последовательность битов в виде нулей и единиц.

2. Параметры двоичного цифрового электромагнитного сигнала: разрядность и порядок следования единичных и нулевых битов.

3. Разрядность двоичного цифрового электромагнитного сигнала - общее число его единичных и нулевых битов, например число 10011 является 5-разрядным.

4. Электронная цифровая подпись (ЭЦП) - двоичный цифровой электромагнитный сигнал, параметры которого зависят от подписанного электронного документа и от секретного ключа. Проверка подлинности ЭЦП осуществляют с помощью открытого ключа, который зависит от секретного ключа.

5. Электронный документ (ЭД) - двоичный цифровой электромагнитный сигнал, параметры которого зависят от исходного документа и способа его преобразования к электронному виду.

6. Секретный ключ - двоичный цифровой электромагнитный сигнал, используемый для формирования подписи к заданному электронному документу. Секретный ключ представляется, например, в двоичном виде как последовательность цифр «0» и «1».

7. Открытый ключ - двоичный цифровой электромагнитный сигнал, параметры которого зависят от секретного ключа и который предназначен для проверки подлинности цифровой электронной подписи.

8. Хэш-функция от электронного документа - двоичный цифровой электромагнитный сигнал, параметры которого зависят от электронного документа и выбранного метода ее вычисления.

9. Многоразрядное двоичное число (МДЧ) - двоичный цифровой электромагнитный сигнал, интерпретируемый как двоичное число и представляемый в виде последовательности цифр «0» и «1».

10. Операция возведения числа S в дискретную степень A по модулю n - это операция, выполняемая над конечным множеством натуральных чисел {0, 1, 2, …, n-1}, включающем n чисел, являющихся остатками от деления всевозможных целых чисел на число n; результат выполнения операций сложения, вычитания и умножения по модулю n представляет собой число из этого же множества [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.]; операция возведения числа S в дискретную степень Z по модулю n определяется как Z-кратное последовательное умножение по модулю n числа S на себя, т.е. в результате этой операции также получается число W, которое меньше или равно числу n-1.

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

12. Циклическая группа - это группа, каждый элемент которой может быть представлен в виде g=aⁿ для некоторого натурального значения n, где a - элемент данной группы, называемый генератором или образующим элементом циклической группы. Степень n означает, что над элементом a выполняются n последовательных операций, т.е. выполняются вычисления по формуле aⁿ=a∘a∘a∘…∘a (n раз), где «∘» обозначает операцию определенную над элементами группы. Каждая группа содержит хотя бы одну циклическую подгруппу простого порядка.

13. Матрица многоразрядных двоичных чисел - это набор МДЧ, расположенный в следующем виде m строк и h столбцов. Матрицу также записывают в сокращенном виде {a_ij}, где i=1, 2, …, w; j=1, 2, …, h и МДЧ a_ij называются элементами матрицы. Если w=h, то матрица является квадратной.

14. Размерность матрицы - это два натуральных числа, означающие количество строк (w) и количество столбцов (h) в матрице. Размерность матрицы записывается в виде w×h.

15. Квадратной матрицей называется матрица, содержащая одинаковое число строк и столбцов и имеющая размерность w×w.

16. Над квадратными матрицами МДЧ определены операции сложения и умножения матриц МДЧ. Операции, определенные над матрицами, выполняются путем выполнения операций над элементами матриц, которыми являются некоторые МДЧ. В результате вычисляется набор новых МДЧ, которые являются элементами новой матрицы, являющейся результатом операции. Матрицы A и B называются равными, если выполняется равенство a_ij=b_ij для всех значений индексов. Детальное описание свойств матриц и действий над ними можно найти в широко доступных книгах: [А.И.Кострикин. Введение в алгебру. Основы алгебры. - М.: Физматлит. 1994. - 320 с.].

17. Определителем матрицы А, задаваемой набором чисел {a_ij}, называется алгебраическая сумма всевозможных произведений коэффициентов a_ij, взятых по одному из каждой строки и из каждого столбца, причем слагаемые, отвечающие четным перестановкам, входят со знаком «плюс», а слагаемые, отвечающие нечетным перестановкам, - со знаком «минус» (детальное описание правил вычисления определителя можно найти в книге [А.И.Кострикин. Введение в алгебру. Основы алгебры. - М.: Физматлит. 1994. - 320 с.]).

18. Операция умножения квадратной матрицы А на квадратную матрицу В, представленых наборами чисел {a_ij} и {b_ij}, i=1, 2, …, w; j=1, 2, …, w, соответственно выполняется по формуле либо по формуле где p - простое МДЧ, с_ij - элемент матрицы С, являющейся результатом операции. При вычислении по второй формуле и фиксированном размере МДЧ p матрицы МДЧ состоят из элементов конечного множества следующих МДЧ: 0, 1, 2, 3, …, p-1, т.е. совокупность всех существующих матриц заданной фиксированной размерности является конечным множеством. Однако число таких матриц чрезвычайно велико при достаточно больших значениях p, благодаря чему матрицы МДЧ с операциями над их элементами, выполняемыми по модулю простого МДЧ p, могут быть эффективно использованы для построения алгоритмов электронной цифровой подписи.

19. Операция возведения матрицы А в натуральную степень и определяется как n-кратное умножение матрицы А на саму себя: Aⁿ=A·A·A· … (n раз). Если операции сложения и умножения над элементами матрицы выполняются по модулю простого МДЧ p, то в конце правой части формул указывают в скобках mod p, например: С=А+В (mod p); C=AB (mod p) и C=Aⁿ (mod p).

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

21. Порядком матрицы A циклической подгруппы называется наименьшее натуральное число q, такое что A^q=Е, т.е. такое, что результатом умножения матрицы А на саму себя q раз является единичная матрица Е.

22. Единичной матрицей Е - называется такая матрица {δ_ij}, для которой верно:

т.е. все диагональные элементы равны единице, а все остальные равны нулю.

Изобретение относится к области криптографических устройств. Техническим результатом настоящего изобретения является повышение производительности алгоритмов электронной цифровой подписи (ЭЦП) без снижения ее уровня стойкости. Сущность изобретения заключается в том, что способ генерации и проверки ЭЦП включает следующую последовательность действий: генерируют секретный ключ в виде многоразрядного двоичного числа (МДЧ) х, по секретному ключу формируют открытый ключ Y в виде матрицы МДЧ размерности w×w, где 2≤w≤32, принимают электронный документ, представленный МДЧ Н, в зависимости от принятого электронного документа и от значения секретного ключа формируют электронную цифровую подпись Q в виде двух МДЧ, в зависимости от Q, Y и Н формируют первое А и второе В проверочные МДЧ, сравнивают МДЧ А и В. При совпадении их параметров делают вывод о подлинности электронной цифровой подписи. 5 з.п. ф-лы.

1. Способ генерации и проверки подлинности электронной цифровой подписи, заверяющей электронный документ, заключающийся в том, что генерируют секретный ключ в виде многоразрядного двоичного числа х, по секретному ключу формируют открытый ключ Y в виде более чем одного многоразрядного двоичного числа, принимают электронный документ, представленный многоразрядным двоичным числом Н, в зависимости от принятого электронного документа и от значения секретного ключа формируют электронную цифровую подпись Q в виде двух многоразрядных двоичных чисел, в зависимости от электронного документа, электронной цифровой подписи и открытого ключа формируют первое А и второе В проверочные многоразрядные двоичные числа, сравнивают их и при совпадении их параметров делают вывод о подлинности электронной цифровой подписи, отличающийся тем, что открытый ключ Y формируют в виде матрицы многоразрядных двоичных чисел размерности w×w, где 2≤w≤32.

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

3. Способ по п.1, отличающийся тем, что открытый ключ Y генерируют в виде матрицы многоразрядных двоичных чисел размерности 2×2, для чего генерируют матрицу многоразрядных двоичных чисел G размерности 2×2, имеющую порядок q, и открытый ключ Y формируют по формуле Y=G^x (mod р), где р - простое МДЧ, а электронную цифровую подпись Q формируют в виде пары многоразрядных двоичных чисел е и s, для чего генерируют случайное многоразрядное двоичное число k, генерируют матрицу многоразрядных двоичных чисел R по формуле
R=G^k (mod р), затем формируют первое многоразрядное двоичное число е электронной цифровой подписи по формуле e=rH mod δ, где r=(r₁₁||r₁₂) - многоразрядное двоичное число, равное конкатенации многоразрядных двоичных чисел первой строки матрицы многоразрядных двоичных чисел R, и δ - вспомогательное простое многоразрядное двоичное число, затем генерируют второе многоразрядное двоичное число s электронной цифровой подписи по формуле s=(k-ex)mod q, после чего формируют первое и второе проверочные многоразрядные двоичные числа А и В по формулам A=r' H mod δ и В=е, где r'=(r'₁₁||r'₁₂) - многоразрядное двоичное число, равное конкатенации многоразрядных двоичных чисел первой строки матрицы многоразрядных двоичных чисел R', вычисленной по формуле R'Y^eG^smod р).

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

5. Способ по п.1, отличающийся тем, что открытый ключ Y генерируют в виде матрицы многоразрядных двоичных чисел размерности 3×3, для чего генерируют матрицу многоразрядных двоичных чисел G размерности 3×3, имеющую порядок q, и открытый ключ Y формируют по формуле Y=G^x (mod р), где р - простое МДЧ, а электронную цифровую подпись Q формируют в виде пары многоразрядных двоичных чисел е и s, для чего генерируют случайное многоразрядное двоичное число k, генерируют матрицу многоразрядных двоичных чисел R по формуле R=G^k (mod р), затем формируют первое многоразрядное двоичное число е электронной цифровой подписи по формуле e=rH mod δ, где r=(r₁₁||r₁₂||r₁₃) - многоразрядное двоичное число, равное конкатенации многоразрядных двоичных чисел первой строки матрицы многоразрядных двоичных чисел R, и δ - вспомогательное простое многоразрядное двоичное число, затем генерируют второе многоразрядное двоичное число s электронной цифровой подписи по формуле s=(k+ex)mod q, после чего формируют первое и второе проверочные многоразрядные двоичные числа А и В по формулам A=r'H mod δ и В=е, где r'=(r'₁₁||r'₁₂||r'₁₃) - многоразрядное двоичное число, равное конкатенации многоразрядных двоичных чисел первой строки матрицы многоразрядных двоичных чисел R', вычисленной по формуле R'=Y^q-eG^s (mod p).

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