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

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

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

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

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

принимают электронный документ (ЭД), представленный БС H, в зависимости от значения H, под которым понимается значение МДЧ, представленное БС H, и значения секретного ключа формируют ЭЦП в виде МДЧ

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

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

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

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

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

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

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

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

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

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

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

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

формируют простое МДЧ а, такое, что и

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

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

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

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

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

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

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

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

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

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

и

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

(n раз)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поставленная цель достигается тем, что в известном способе формирования и проверки подлинности ЭЦП, заверяющей ЭД, заключающемся в том, формируют секретный ключ, по секретному ключу формируют открытый ключ в виде, по крайней мере, одной БС, принимают ЭД, представленный, по крайней мере, одной БС Н, в зависимости от принятого ЭД и значения секретного ключа формируют ЭЦП в виде, по крайней мере, двух БС, формируют первую А и вторую В проверочные БС, сравнивают их и при совпадении их параметров делают вывод о подлинности ЭЦП, новым в заявленном изобретении является то, что формируют секретный ключ в виде, по крайней мере, двух элементов, каждый из которых представляет собой, по крайней мере, одну БС, и при формировании открытого ключа осуществляют операции возведения первого и второго элементов секретного ключа в степени -разрядного двоичного числа w₁ z₁-разрядного двоичного числа w₂ соответственно, где и

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

Новым является также и то, что формируют секретный ключ в виде двух МДЧ K₁ и K₂, по секретному ключу формируют открытый ключ в виде МДЧ Y путем возведения МДЧ K₁ в степень w₁ по модулю простого МДЧ p, возведения МДЧ K₂ в степень w₂ по модулю p и перемножения значений и по формуле причем где N- четное натуральное число, w, w¹ и - простые МДЧ, а и

Новым является также и то, что ЭЦП формируют в виде трех МДЧ e, S₁ и S₂ путем генерации двух случайных МДЧ Т₁ и T₂, генерации МДЧ R по формуле генерации первого МДЧ е ЭЦП по формуле где - выражение, задающее правило вычисления МДЧ е, генерации второго и третьего МДЧ S₁ и S₂ ЭЦП по формулам и а первую А и вторую B проверочные БС формируют в виде МДЧ по формулам где и

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

Новым является также и то, что формируют секретный ключ в виде двух многочленов и где x - формальная переменная, по секретному ключу формируют открытый ключ в виде многочлена Y(x) путем возведения многочлена в степень w₁ по модулю неприводимого многочлена p(x), возведения многочлена в степень w₂ по модулю неприводимого многочлена p(x) и перемножения значений и по формуле где w₁ и w₂ - простые МДЧ.

Новым является также и то, что ЭЦП формируют в виде МДЧ е и двух многочленов и путем генерации двух случайных многочленов и генерации многочлена R(x) по формуле генерации МДЧ е ЭЦП по формуле где - выражение, задающее правило вычисления МДЧ е, генерации первого и второго многочленов и ЭЦП по формулам и а первую А и вторую В проверочные БС формируют в виде МДЧ по формулам где и

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

Новым является также и то, что формируют секретный ключ в виде двух векторов БС K₁ и K₂, по секретному ключу формируют открытый ключ в виде вектора БС Y путем возведения вектора БС K₁ в степень w₁, возведения вектора БС K₂ в степень w₂ и перемножения значений и по формуле где знак обозначает операцию умножения векторов БС, и принимают ЭД, представленный двумя битовыми строками и .

Новым является также и то, что ЭЦП формируют в виде МДЧ е и двух векторов БС S₁ и S₂ путем генерации двух случайных векторов БС T₁ и T₂ а, генерации вектора БС R по формуле генерации МДЧ е ЭЦП по формуле где - выражение, задающее правило вычисления МДЧ е, генерации первого и второго векторов БС S₁ и S₂ ЭЦП по формулам и а первую А и вторую В проверочные БС формируют в виде МДЧ по формулам где и

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

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

1) конечные группы МДЧ, включающие набор МДЧ {1, 2, 3,…,р-1}, где р - простое МДЧ, причем групповой операцией является умножение МДЧ по модулю р; данный тип групп широко применяется при реализации известных способов формирования и проверки ЭЦП [Смарт Н. Мир программирования. Криптография.- М., ТЕХНОСФЕРА, 2005. - 525 с.];

2) конечные группы многочленов, в которых групповой операцией является умножение многочленов по модулю неприводимого многочлена; конечные группы многочленов также широко представлены в хорошо известных литературных источниках и применяются в криптографических алгоритмах [Венбо Мао. Современная криптография. Теория и практика. - М., СПб., Киев. Издательский дом «Вильямс», 2005. - 763 с.].

3) конечные группы векторов БС, в которых групповой операцией является умножение векторов БС; данный тип групп является менее известным и при построении способов формирования и проверки подлинности ЭЦП ранее не применялся; достаточно детальное рассмотрение криптографических применений групп векторов БС дано в работе [Молдовян Н.А. Группы векторов для алгоритмов электронной цифровой подписи // Вестник СПбГУ. Сер. 10. 2008];

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

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

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

Стойкость ЭЦП, генерируемой по заявленному способу формирования и проверки ЭЦП, заверяющей ЭД, основана на том факте, что операция извлечения корней степени, равной простому МДЧ w, из элементов конечной группы порядка Ω в случае, когда МДЧ w делит МДЧ Ω, может быть выполнена только для числа элементов групп, равного При достаточно большом значении w вероятность того, что случайно сгенерированный элемент группы а может быть представлен в виде является пренебрежимо малой. Кроме того, для обеспечения стойкости следует выбрать соответствующими значения МДЧ w₁ и w₂. Последнее можно сделать различными способами. Например, можно задать МДЧ w₁ в виде a МДЧ w₂ в виде где w, и - простые 80-разрядные числа. Рассмотрим на примере частного варианта реализации заявленного способа формирования и проверки ЭЦП, соответствующего п.3 формулы изобретения, возможные атаки на ЭЦП. Без знания секретного ключа подделка ЭЦП может быть осуществлена выбором значений T₁ и T₂, генерации МДЧ вычисления МДЧ где H - МДЧ, представляющее ЭД, с последующим вычислением пары МДЧ S₁ и S₂. Однако шаг вычисления МДЧ S₁ и S₂ требует решения уравнения вида

где неизвестными являются S₁ и S₂. При этом правая часть уравнения имеет случайное значение, если в качестве функции выбрать некоторую хэш-функцию или функцию вида где

Если задать значение одной из неизвестных, например S₂, то уравнение преобразуется в уравнение с одной неизвестной S₁ вида а затем к уравнению вида В последнем уравнении правая часть с пренебрежимо малой вероятностью будет иметь значение, при котором последнее уравнение разрешимо. Для проверки условия разрешимости выполняется одна операция возведения в степень по модулю р. Для получения случая, когда условие разрешимости удовлетворяется, требуется выполнить описанную попытку в среднем раз. При размере равном 80 бит и более, вычислительная сложность подделки ЭЦП настолько велика, что практически невыполнима. Аналогичным путем подделку подписи можно свести к решению уравнения относительно неизвестной S₂, когда требуется выполнить описанных попыток. При размере равном 80 бит и более, такой объем попыток вычислительно нереализуем. Попытка подделать подпись путем генерации МДЧ и вычисления МДЧ связана с вычислением МДЧ и таких, что выполняется соотношение Последнее соотношение выполняется, если выполняется соотношение которое сводится к диофантовому уравнению относительно неизвестных и вида Поскольку и где w, и - простые МДЧ, то указанное диофантовое уравнение имеет решение в целых числах только в случае, когда правая часть уравнения делится на МДЧ w, которое равно наибольшему общему делителю коэффициентов при неизвестных и (условия разрешимости диофантовых уравнений хорошо известны, см., например, книгу [Бухштаб А.А. Теория чисел. - М.: Просвещение, 1966. -384 с.]). Значение МДЧ е формируется по формуле и вероятность того, что диофантовое уравнение будет иметь решения, равна . При размере w, равном 80 бит, для получения одного случая разрешимости диофантового уравнения в среднем требуется выполнить 2⁸⁰ попыток подделки подписи, что превышает значение сложности, равное 2⁸⁰ операций возведения в степень по модулю p, т.е. второй тип атаки на ЭЦП, формируемую по заявленному способу, также практически невыполним. Рассмотрим примеры реализации заявленного способа формирования и проверки ЭЦП при использовании трех типов конечных групп, указанных выше.

Пример 1.

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

1. Генерируют простое число p, такое, что p-1 содержит большие простые множители w, w' и w'' т.е. где N - четное число. В качестве МДЧ w₁ и w₂ используют числа и соответственно.

2. Генерируют секретный ключ в виде двух случайных МДЧ К₁ и К₂.

3. Формируют открытый ключ Y в виде МДЧ

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

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

4.1. Генерируют пару случайных МДЧ T₁ и T₂.

4.2. Вычисляют МДЧ

4.3. Вычисляют первое МДЧ е ЭЦП по формуле например,

4.4. Вычисляют второе МДЧ S₁ ЭЦП по формуле

4.5. Вычисляют третье МДЧ S₂ ЭЦП по формуле

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

5.1. Генерируют МДЧ

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

т.е.

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

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

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

т.е. получаемое в процессе проверки подлинной ЭЦП значение МДЧ равно МДЧ R, поэтому

Приведем пример частной реализации указанной выше последовательности действий для случая использования двухмерных векторов БС.

1. Генерируют простое число p, такое, что p-1 содержит большие простые множители w, w' и w'', т.е. где N - четное число:

р=207058210173317975283840168452786556059;

N=122; w=43391; w'=1037327; w''=37706592177541972343870177. w₁=ww'=45010655857;

w₂=ww''=1636126741175723721972870850207.

2. Генерируют секретный ключ в виде двух случайных МДЧ K₁ и К₂: К₁=716898509375431306272081;

К₂=84625032531337128506088.

3. Формируют открытый ключ Y в виде МДЧ, вычисляемого по формуле

=184786771613225274241947728803805332534;

=166715777768672168097282226515237158347;

Y=117996294309150575198921568244513363511.

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

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

4.1. Генерируют пару случайных МДЧ Т₁ и T₂:

Т₁=36186064562670643172585697;

T₂=90758345139287902502537148;

4.2. Вычисляют МДЧ mod р:

=189875188145657029662935356717403411470;

=196150962023012787693205423497619024711;

R=152085758341426732402146934384987086068.

4.3. Вычисляют первое МДЧ е ЭЦП по формуле :е=17916429455.

4.4. Вычисляют второе МДЧ S₁ ЭЦП по формуле :

=81705713996940932088325229911270482200;

S₁=77096791017192058620671986273319937381.

4.5. Вычисляют третье МДЧ S₂ ЭЦП по формуле :

=178027052274072413960850519819518927832;

S₂=124719856404421356993673024300549206635.

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

5.1. Генерируют МДЧ :

=51112026969055849193858105601335008373;

=110039988699446955325815724938200899118;

=187553964633263335850348739028438656069;

=152085758341426732402146934384987086068.

5.2. Формируют БС А в виде МДЧ, вычисляемого по формуле :

A=17916429455.

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

В=е=17916429455.

7. Сравнивают первую и вторую проверочные БС А и В: А=В. Поскольку параметры проверочных БС совпадают, делают вывод о подлинности ЭЦП, заверяющей ЭД.

Пример 2.

Данный пример иллюстрирует конкретный вариант реализации заявленного способа формирования и проверки ЭЦП по п.5 формулы изобретения. Пункт 5 раскрывает конкретный вариант реализации п.4, а последний пункт относится к частной реализации п.1, поэтому пример 2 иллюстрирует реализацию пп.1, 2 и 3 формулы изобретения. В данном примере вначале представлена обобщенная реализация способа по п.3 с использованием произвольных параметров многочленов, удовлетворяющих условиям, сформулированным в п.1, приводимой ниже последовательности действий. Доказательство корректности заявленного способа формирования и проверки подлинности ЭЦП при его реализации по п.5 дается в общем случае. Рассматриваемый в примере 2 частный вариант реализации заявленного способа связан с выполнением операций в конечной группе многочленов. В качестве такой группы может быть использована мультипликативная группа конечного поля многочленов, которая представляет собой множество всех ненулевых многочленов конечного поля многочленов с операцией умножения многочленов, играющей роль групповой операции. Многочлены записываются в виде , где - коэффициенты многочлена, x - формальная переменная, которой не приписывается какое-либо значение, z - степень многочлена. Многочлены могут быть записаны в виде упорядоченной последовательности коэффициентов (с₀, с₁, …, с₂), что используется при выполнении операций над ними с помощью электронных устройств. Формальная переменная служит для идентификации каждого коэффициента многочлена как значения при формальной переменной в некоторой заданной степени и удобства описания правил выполнения операций сложения, умножения и деления многочленов. Наибольшее значение степени формальной переменной, при которой коэффициент отличен от нуля, называется степенью многочлена. Коэффициентами многочлена являются элементы некоторого поля, в частности поля чисел, являющихся остатками от деления всех целых чисел на некоторое простое число q. Такие поля называются простыми и обозначаются следующим образом GF{q).

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

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

1. Генерируют неприводимый многочлен заданный над простым конечным полем GF(q), где q - простое МДЧ, такой, что его степень равна целому числу z. Известно, что множество ненулевых остатков от деления многочленов над простым конечным полем GF(q) на неприводимый многочлен содержит ненулевых многочленов степени z-1. Значения МДЧ q и степени z выбирают таким образом, что разложение содержит большие простые множители

w₁ и w₂, т.е. где N - четное число.

2. Генерируют секретный ключ в виде двух случайных многочленов и степени z-1 над простым конечным полем GF{q).

3. Формируют открытый ключ Y(x) в виде многочлена, вычисляемого по формуле Выполнение этого шага включает операции возведения многочленов и в степени w₁ и w₂, соответственно, по модулю неприводимого многочлена , что является отличительным признаком заявленного способа формирования и проверки подлинности ЭЦП.

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

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

4.1. Генерируют два случайных многоч1лена и степени z-1 над простым конечным полем GF(q).

4.2. Вычисляют многочлен .

4.3. Вычисляют первое МДЧ е ЭЦП по формуле , например, , где - функция, отображающая множество всех многочленов степени не выше z-1 на множество целых чисел, например где r_i - коэффициент при формальной переменной хⁱ в многочлене R(x).

4.4. Вычисляют первый многочлен ЭЦП по формуле

.

4.5. Вычисляют второй многочлен , ЭЦП по формуле

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

5.1. Генерируют многочлен

5.2. Формируют БС А в виде МДЧ, вычисляемого по формуле , т.е. (в соответствии с конкретным вариантом реализации функции , выбранным на шаге 4.3).

6. Формируют вторую проверочную БС В путем копирования МДЧ е: В=e.

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

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

значения и получаем

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

Пример 3.

Данный пример иллюстрирует конкретный вариант реализации заявленного способа формирования и проверки ЭЦП по п.7 формулы изобретения. В данном варианте выполняются операции над элементами конечной группы векторов БС, групповой операцией в которой является умножение векторов БС. Понятия векторов БС и операции умножения над ними раскрываются ниже. Пункт 7 раскрывает конкретный вариант реализации п.6, а последний пункт относится к частной реализации п.6, поэтому пример 3 иллюстрирует реализацию пп.1, 6 и 7 формулы изобретения. В данном примере вначале представлена обобщенная реализация способа по п.7 с использованием конечных групп векторов БС произвольной размерности, а затем для случая размерности m=2 приводится пример выполнения действий по п.7 с указанием конкретных численных значений, которые принимают параметры, используемые для данного конкретного примера. Доказательство корректности заявленного способа формирования и проверки подлинности ЭЦП при его реализации по п.7 дается в общем случае для произвольных значений размерности векторов БС и размеров используемых параметров. В обобщенном виде выполняемые операции представляются следующей последовательностью действий.

1. Генерируют конечную группу векторов БС, порядок которой равен , где w₁ и w₂ - простые числа; N - некоторое натуральное число (примеры генерации групп векторов описаны ниже).

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

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

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

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

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

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

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

5.4. Генерируют векторы БС S₁ и S₂ по формулам и для чего

5.4.1. Вычисляют значение

5.4.2. Генерируют вектор БС

5.4.3. Генерируют вектор БС

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

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

6.2. Формируют первую проверочную БС А по формуле т.е. где и - БС, являющиеся координатами вектора БС (в соответствии с конкретным вариантом реализации функции выбранным на шаге 6.2).

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

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

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

значения и получаем

т.е. получаемое в процессе проверки подлинной ЭЦП значение вектора БС равно вектора БС R, поэтому

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

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

и т.д.

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

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

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

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

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

При соответствующем выборе таблицы умножения базисных векторов и простого значения p множество векторов МДЧ является конечным и это конечное множество содержит подмножество векторов МДЧ, которое образуют группу с групповой операцией «», причем порядок этой подгруппы является достаточно большим. Порядком вектора БС V называется наименьшее натуральное число q, такое, что V^q=1, т.е. такое, что результатом умножения вектора МДЧ Q на самого себя q раз является единичный вектор МДЧ В частных случаях задания конечного множества векторов БС оно будет представлять расширенное поле, в котором все ненулевые векторы БС составляют циклическую мультипликативную группу [Молдовян Н.А. Группы векторов для алгоритмов электронной цифровой подписи // Вестник СПбГУ. Сер. 10. 2008].

Приведем пример частной реализации заявленного способа по пп.6 и 7 формулы изобретения, в которой используется конечная группа двухмерных векторов БС и в котором выполняют следующую последовательность действий. 1. Генерируют простое число p, такое, что p-1 содержит большие простые множители w₁ и w₂, т.е. где N - четное число:

р=74578501539448125066803; w₁=582433; w₂=660033455637401; N=194. 1.

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

К₁=(16509353102781, 6271051783011);

К₂=(7630452849756,18462544596047).

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

где w₁ и w₂ - вспомогательные МДЧ, являющиеся делителями числа р-1, и умножение векторов БС задано по таблице XX при коэффициенте растяжения ε=4032064 (квадрат числа 2008):

=(26043600042089751755891, 2938220419758255108424);

=(24122228766679853892218, 24744929396882456576877);

=(49454363410163500735959, 9465343958333544118202).

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

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

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

T₁=(603090172801, 237075837107); Т₂=(163545224976, 2042645322047).

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

=(3025445843278052087674, 1992327547314508252640);

=(23488268671301337304814, 17053243593410703701562);

=(59184587233421257829761, 19835895736331299617687).

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

е=23629549520720869599146.

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

4.4.1. Вычисляют значение

4.4.2. Генерируют вектор БС

4.4.3. Генерируют вектор БС

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

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

Y^e=(53292929230121547155100, 64029764165166408825324);

=(61310631059846977589955, 10926911066423229091262);

=(43913846618324434082604, 26119821889659793087507);

=(72364163556432207150430, 53022947699548612603699);

=(59184587233421257829761, 19835895736331299617687).

5.2. Формируют первую проверочную БС А по формуле где , и - БС, являющиеся координатами вектора БС : А=23629549520720869599146.

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

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

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

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

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

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

Приравнивая нулю главный определитель этой системы, получаем характеристическое уравнение e²-εb²≡0 mod p.

Значение (a, b)=(0, 0) является решением характеристического уравнения для любых значений модуля, поэтому для этой пары не существует обратного значения. Пусть в определении операции умножения используется параметр ε, который является квадратичным вычетом по модулю р. При этих условиях характеристическое уравнение имеет кроме (a, b)=(0, 0) еще 2(p-1) следующих решений вида: и где Для пар такого вида не существует решений системы сравнений, которые определяют значение обратных элементов. Следовательно, количество элементов, для которых существуют единственные обратные значения, равно Эти элементы составляют мультипликативную группу, поскольку результат умножения любых двух элементов из этого множества является элементом этого же множества. Эти элементы составляют конечную группу двухмерных векторов, порядок которой равен Ω=(p-1)².

Аналогичным образом заявленный способ формирования и проверки ЭЦП по п.7 может быть реализован, используя вычисление над векторами размера m=3, 4, 5 и m>5. Для задания операции умножения над векторами заданной размерности m требуется составить таблицу умножения базисных векторов и задать значение коэффициентов, присутствующих в определенных клетках этой таблицы. Для случаев m=3 и m=7 могут быть использованы таблицы 3 и 4, соответственно. Выбирая соответствующим образом значения коэффициентов растяжения, можно добиться, чтобы порядок конечной группы m-мерных векторов был (p-1)^m, где р - простое число, такое, что p-1=Nww'w'' (N - четное число, w, w' и w'' - простые МДЧ).

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

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

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

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

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

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

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

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

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

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

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

4. Битовая строка (БС) - двоичный цифровой электромагнитный сигнал, представляемый в виде конечной последовательности цифр «0» и «1».

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

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

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

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

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

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

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

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

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

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

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

16. Алгебраическая структура - это множество математических элементов, некоторой природы. В качестве математических элементов могут выступать, например, многочлены, МДЧ, пары МДЧ, пары многочленов, тройки МДЧ, тройки многочленов, матрицы МДЧ, матрицы многочленов и т.д., над которыми заданы математические действия (операции). Математически алгебраическая структура определяется путем задания конкретного множества математических элементов и одной или нескольких операций, выполняемых над элементами.

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

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

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

20. Поле - это алгебраическая структура (т.е. множество математических элементов различной природы), над элементами которой определены две операции, одна из которых называется сложением, а вторая - умножением. При этом при заданных операциях в эта алгебраическая структура обладает заданным набором свойств: операции сложения и умножения ассоциативны и коммутативны, операция умножения является дистрибутивной относительно операции сложения, а результатом выполнения каждой из этих операций над двумя элементами является также элемент этой же структуры. Причем для каждой из указанных двух операций существует нейтральный элемент такой, что при выполнении операции над ним и другим некоторым элементом а группы результатом является элемент а. Нейтральный элемент относительно сложения называется нулевым элементом (или просто нулем), а нейтральный элемент относительно умножения называется единичным элементом (или просто единицей). Кроме того, каждому ненулевому элементу а может быть сопоставлен в соответствие единственный элемент а^-1, называемый обратным элементом по отношению к данному элементу, такой, что произведение a ^-1 a (а значит и aa ^-1) равно единице. Детальное описание полей дано в книгах [А.И. Кострикин. Введение в алгебру. Основы алгебры. М.: Физматлит. 1994. - 320 с.] и [Курош А.Г. Курс высшей алгебры. - М.: Наука, 1971. - 431 с.].

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

22. Циклическая подгруппа группы - это подгруппа, каждый элемент g которой может быть представлен в виде g=a ⁿ для некоторого натурального значения n, где a - элемент данной подгруппы, называющийся генератором или образующим элементом циклической подгруппы.

23. Вектор - это набор из двух или более элементов заданной алгебраической структуры, называемых компонентами вектора. Число элементов алгебраической структуры, над которым задан вектор, называется размерностью вектора.

24. Вектор битовых строк (вектор БС) - это набор из двух или более БС, каждая из которых представляет заданную алгебраическую структуру. Битовые строки называются координатами (или компонентами) вектора. Вектор БС записывается различными способами, требование к которым состоит в том, чтобы они идентифицировали позиции координат. Например, вектор БС можно записать в виде (a ₁, a ₂,…,a _m), где m≥2 - это размерность вектора БС, означающая число координат (компонентов) в векторе БС. В качестве разделителя может быть использован знак операции, определенной над координатами (компонентами) вектора, и тогда координаты (компоненты) вектора идентифицируются указанием формальной переменной (в начале или в конце соответствующего компонента) в виде буквы латинского алфавита. Формальной называется переменная потому, что ей не приписывается никакого численного значения и она служит только для того, чтобы идентифицировать конкретную позицию Координаты (компоненты) вектора БС, независимо от последовательности его записи. Так, векторы БС Z₁=ae+bi+cj и Z₂=bi+ae+cj рассматриваются как равные, т.е. Z₁=Z₂. При использовании некоторых частных таблиц замены переменных формальные переменные в литературе иногда называются базисными векторами, а векторы Z₁ и Z₂ - векторами m-мерного пространства [Л.Б.Шнеперман. Курс алгебры и теории чисел в задачах и упражнениях. - Минск, «Вышэйшая школа», 1986. - 272 с.].

25. Вектор многоразрядных двоичных чисел (вектора МДЧ) - это вектор БС, координатами которого являются МДЧ.

26. Размерность вектора БС - это количество БС, входящих в вектор БС в качестве координат.

27. Эллиптическая кривая (ЭК) - это совокупность пар МДЧ, которые удовлетворяют соотношению вида

y²=x³+ax+b mod p,

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

28. Операция сложения двух точек А и В с координатами (x_A, y_A) и (x_B, y_B), соответственно, выполняется по формулам:

и

где если точки А и В не равны, и если точки А и В равны.

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

(n раз).

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

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

31. Порядком точки А ЭК называется наименьшее натуральное число q, такое, что qA=O, т.е. такое, что результатом умножения точки А на число q является бесконечно удаленная точка.

Изобретение относится к области криптографии. Достигаемым техническим результатом является повышение производительности алгоритмов ЭЦП без снижения ее уровня стойкости. Сущность изобретения заключается в том, что формируют секретный ключ в виде, по крайней мере, двух элементов, каждый из которых представляет собой, по крайней мере, одну битовую строку (БС), по секретному ключу формируют открытый ключ в виде, по крайней мере, одной БС, причем при формировании открытого ключа осуществляют операции возведения первого и второго элементов секретного ключа в степени z₁-разрядного двоичного числа ω₁ и z₂-разрядного двоичного числа ω₂ соответственно, где ω₁≠ω₂, z₁>16 и z₂>16, принимают электронный документ (ЭД), представленный, по крайней мере, одной БС Н, в зависимости от принятого ЭД и значения секретного ключа формируют ЭЦП в виде, по крайней мере, двух БС, формируют первую А и вторую В проверочные БС, сравнивают их и при совпадении их параметров делают вывод о подлинности ЭЦП. 6 з.п. ф-лы, 5 табл.

1. Способ формирования и проверки подлинности электронной цифровой подписи, заверяющей электронный документ, заключающийся в том, что формируют секретный ключ, по секретному ключу формируют открытый ключ в виде, по крайней мере, одной битовой строки, принимают электронный документ, представленный, по крайней мере, одной битовой строкой, в зависимости от принятого электронного документа и значения секретного ключа формируют электронную цифровую подпись в виде, по крайней мере, двух битовых строк, формируют первую А и вторую В проверочные битовые строки, сравнивают их и при совпадении их параметров делают вывод о подлинности электронной цифровой подписи, отличающийся тем, что формируют секретный ключ в виде, по крайней мере, двух элементов, каждый из которых представляет собой, по крайней мере, одну битовую строку, и при формировании открытого ключа осуществляют операции возведения первого и второго элементов секретного ключа в степени z₁-разрядного двоичного числа ω₁ и z₁-разрядного двоичного числа ω₂ соответственно, где ω₁≠ω₂, z₁>16 и z₂>16.

2. Способ по п.1, отличающийся тем, что формируют секретный ключ в виде двух многоразрядных двоичных чисел K₁ и K₂, по секретному ключу формируют открытый ключ в виде многоразрядного двоичного числа Y путем возведения многоразрядного двоичного числа K₂ в степень ω₁ по модулю простого многоразрядного двоичного числа ρ, возведения многоразрядного двоичного числа K₂ в степень ω₂ по модулю ρ и перемножения значений по формуле причем р=Nωω'ω'' +1, где N - четное натуральное число, ω, ω', ω'' - простые многоразрядные двоичные числа, а ω₁=ωω' и ω₂=ωω''.

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

4. Способ по п.1, отличающийся тем, что формируют секретный ключ в виде двух многочленов K₁(x) и К₂(х), где х формальная переменная, по секретному ключу формируют открытый ключ в виде многочлена Y(x) путем возведения многочлена K₁(x) в степень ω₁ по модулю неприводимого многочлена, ρ(χ) возведения многочлена K₂(χ) в степень ω₂ по модулю неприводимого многочлена ρ(χ) и перемножения значений по формуле ,
где ω₁ и ω₂ - простые многоразрядные двоичного числа.

5. Способ по п.4, отличающийся тем, что электронную цифровую подпись формируют в виде многоразрядного двоичного числа е и двух многочленов s₁(χ) и s₂(χ) путем генерации двух случайных многочленов T₁(χ) и T₂(χ) генерации многочлена R(χ) по формуле , генерации многоразрядного двоичного числа е электронной цифровой подписи по формуле е=f₂(R(χ), H), где f₂(R(χ), H) - выражение, задающее правило вычисления многоразрядного двоичного числа е, генерации первого и второго многочленов s₁(χ) и s₂(χ) электронной цифровой подписи по формулам и , а первую A и вторую B проверочные битовые строки формируют в виде многоразрядных двоичных чисел по формулам А=f₂(R'(χ), H), где , и В=е.

6. Способ по п.1, отличающийся тем, что формируют секретный ключ в виде двух векторов битовых строк K₁ и K₂, по секретному ключу формируют открытый ключ в виде вектора битовых строк Y путем возведения вектора битовых
строк K₁ в степень ω₁, возведения вектора битовых строк K₂ в степень ω₂ и перемножения значений по формуле где знак обозначает операцию умножения векторов битовых строк, и принимают электронный документ, представленный двумя битовыми строками H₁ и H₂.

7. Способ по п.6, отличающийся тем, что электронную цифровую подпись формируют в виде многоразрядного двоичного числа е и двух векторов битовых строк S₁ и S₂ путем генерации двух случайных векторов битовых строк T₁ и Т₂, генерации вектора битовых строк R по формуле , генерации многоразрядного двоичного числа е электронной цифровой подписи по формуле е=f₃(R, H₁, Н₂), где f₃(R, H₁, Н₂) - выражение, задающее правило вычисления многоразрядного двоичного числа е, генерации первого и второго векторов битовых строк S₁ и S₂ электронной цифровой подписи по формулам а первую А и вторую В проверочные битовые строки формируют в виде многоразрядных двоичных чисел по формулам А=f₃(R', H₁, H₂), где , и B=e.