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

1)
1)
Изобретение относится к области электросвязи и вычислительной техники, а конкретнее к области криптографических способов аутентификации электронных сообщений, передаваемых по телекоммуникационным сетям и сетям ЭВМ и может быть использовано в системах передачи электронных сообщений (документов), заверенных электронной цифровой подписью (ЭЦП), представленной в виде битовой строки (БС) или нескольких БС. Здесь и далее под БС понимается электромагнитный сигнал в двоичной цифровой форме, параметрами которого являются число битов и порядок следования их единичных и нулевых значений( толкование используемых в описании терминов приведено в Приложении 1).
Известен способ формирования и проверки ЭЦП, предложенный в патенте США №4405829 от 20.09.1983 и детально описанный также и в книгах [1. М.А.Иванов. Криптография. М., КУДИЦ-ОБРАЗ, 2001; 2. А.Г.Ростовцев, Е.Б.Маховенко. Введение в криптографию с открытым ключом. С-Петербург, Мир и семья, 2001. - с.43]. Известный способ заключается в следующей последовательности действий:
формируют секретный ключ в виде трех простых многоразрядных двоичных чисел (МДЧ) p, q и d, представленных тремя БС;
формируют открытый ключ (n, e) в виде пары МДЧ n и e, где n - число, представляющее собой произведение двух простых МДЧ p и q, и е - МДЧ, удовлетворяющее условию ed=1 mod (р-1)(q-1),
принимают электронный документ (ЭД), представленный БС Н,
d
в зависимости от значения Н, под которым понимается значение МДЧ, представленное БС Н, и значения секретного ключа формируют ЭЦП в виде MДЧ Q=S=Hmod n;
формируют первое проверочное МДЧ А=Н;
е
формируют второе проверочное МДЧ В, для чего МДЧ S возводят в целочисленную степень е по модулю n: В=S mod n;
сравнивают сформированные проверочные МДЧ А и В;
при совпадении параметров сравниваемых МДЧ А и В делают вывод о подлинности ЭЦП.
Недостатком известного способа является относительно большой размер подписи и необходимость увеличения размера подписи при разработке новых более эффективных методов разложения числа n на множители или при росте производительности современных вычислительных устройств. Это объясняется тем, что значение элемента подписи S вычисляются путем выполнения арифметических операций по модулю n, а стойкость ЭЦП определяется сложностью разложения модуля n на множители p и q.
Известен также способ формирования и проверки подлинности ЭЦП Эль-Гамаля, описанный в книге [Молдовян А.А., Молдовян НА., Советов Б.Я. Криптография. - СПб, Лань, 2000. - с.156-159], который включает следующие действия:
x
формируют простое МДЧ p и двоичное число G, являющееся первообразным корнем по модулю p, генерируют секретный ключ в виде МДЧ x, в зависимости от секретного ключа формируют открытый ключ в виде МДЧ Y=G mod p, принимают ЭД, представленный в виде МДЧ Н, в зависимости от H и секретного ключа формируют ЭЦП Q в виде двух МДЧ S и R, то есть Q=(S, R);
осуществляют процедуру проверки подлинности ЭЦП, включающую вычисление двух контрольных параметров с использованием исходных МДЧ p, G, Y, Н и S путем возведения МДЧ G, Y, R в дискретную степень по модулю р и сравнение вычисленных контрольных параметров;
при совпадении значений контрольных параметров делают вывод о подлинности ЭЦП.
Недостатком данного способа также является относительно большой размер ЭЦП. Это объясняется тем, что значения элементов подписи S и R вычисляют путем выполнения арифметических операций по модулю р-1 и по модулю p, соответственно.
Известен также способ формирования и проверки ЭЦП, предложенный в патенте США №4995089 от 19.02.1991. Известный способ заключается в следующей последовательности действий:
формируют простое МДЧ p, такое что р=Nq+1, где q - простое МДЧ;
q
формируют простое МДЧ а, такое что а≠1 и a mod p=1;
методом генерации случайной равновероятной последовательности формируют секретный ключ в виде МДЧ k;
k
формируют открытый ключ в виде МДЧ y по формуле y=a mod p;
принимают ЭД, представленный МДЧ М;
t
формируют ЭЦП в виде пары МДЧ (е, s), для чего генерируют случайное МДЧ t, формируют МДЧ R по формуле R=amod p, формируют МДЧ е=f(М||R), где знак || обозначает операцию присоединения двух МДЧ и f - некоторая специфицированная хэш-функция, значение которой имеет фиксированную длину (обычно 160 или 256 бит), независимую от размера аргумента, т.е. от размера МДЧ M|R, а затем формируют МДЧ s по формуле s=(t+ek) mod q;
s
-е
формируют первое проверочное МДЧ А, для чего генерируют МДЧ R' по формуле R'=ау mod p и формируют МДЧ е'=f(М||R');
формируют второе проверочное МДЧ В путем копирования МДЧ е: B=е;
сравнивают сформированные проверочные МДЧ А и В;
при совпадении параметров сравниваемых МДЧ А и В делают вывод о подлинности ЭЦП.
Недостатком способа по патенту США является относительно высокая вычислительная сложность процедуры формирования и проверки ЭЦП, что связано с тем, что для обеспечения минимально требуемого уровня стойкости требуется использовать простой модуль p разрядностью не менее 1024 бит.
A
A
B
B
C
A
B
C
A
C
A
2
Наиболее близким по своей технической сущности к заявленному является известный способ формирования и проверки подлинности ЭЦП, предлагаемый российским стандартом ГОСТ Р 34.10-2001 и описанный, например, в книге [Б.Я.Рябко, А.Н.Фионов. Криптографические методы защиты информации. М., Горячая линия - Телеком, 2005. - 229 с. (см. с.110-111)], согласно которому ЭЦП формируется в виде пары МДЧ г и s, для чего генерируют эллиптическую кривую (ЭК) в виде совокупности точек, причем каждая точка представляется двумя координатами в декартовой системе координат в виде двух МДЧ, называемых абсциссой (x) и ординатой (у), затем осуществляют операции генерации точек ЭК, сложения точек ЭК и умножения точки ЭК на число, а также арифметические операции над МДЧ, после чего в результате выполненных операций формируются МДЧ r и s. Указанные операции над точками выполняются как операции над МДЧ, являющимися координатами точек, по известным формулам [Б.Я.Рябко, А.Н.Фионов. Криптографические методы защиты информации. М., Горячая линия - Телеком, 2005. - 229 с. (см. с.110-111)]. Операция сложения двух точек А и В с координатами (х, y) и (х, y), соответственно, выполняется по формулам: х=k-x-x mod p и y=k(x-х)-у mod p, где , если точки А и В не равны, и , если точки А и В равны. При вычислении значения k выполняется операция деления МДЧ по модулю простого МДЧ, что ограничивает производительность формирования и проверки подлинности ЭЦП по стандарту ГОСТ Р 34.10-2001. Операция умножения точки А на натуральное число n определяется как многократное сложение токи А: nА=А+А+…+А (n раз). Результатом умножения любой точки ЭК на нуль определяется точка, называемая бесконечно удаленной точкой и обозначаемой буквой О. Две точки А=(х, у) и -А=(х, -у) называются противоположными. Умножение на целое отрицательное число -n определяется следующим образом: (-n)А=n(-А). По определению принимают, что сумма двух противоположных точек равна бесконечно удаленной точке О.
В прототипе, т.е. в способе формирования и проверки подлинности ЭЦП по стандарту ГОСТ Р 34.10-2001, генерируют ЭК, описываемую уравнением y=x+ax+b mod p, поэтому генерация ЭК состоит в генерации чисел а, b и p, являющихся параметрами ЭК и однозначно задающих множество точек ЭК, абсцисса и ордината каждой из которых удовлетворяет указанному уравнению. Ближайший аналог (прототип) заключается в выполнении следующей последовательности действий:
генерируют эллиптическую кривую (ЭК), которая представляет собой совокупность пар МДЧ, называемых точками ЭК и обладающих определенными свойствами (см. Приложение 1, пп.27-31);
методом генерации случайной равновероятной последовательности формируют секретный ключ в виде МДЧ k;
формируют открытый ключ Р в виде двух МДЧ, являющихся координатами точки ЭК Р, для чего генерируют точку G, имеющую значение порядка равное q (порядком точки ЭК называется наименьшее положительное целое число q, такое что результатом умножения данной точки на число q является так называемая бесконечно удаленная точка О; результатом умножения любой точки ЭК на нуль по определению является точка О [Б.Я.Рябко, А.Н.Фионов. Криптографические методы защиты информации. М., Горячая линия - Телеком, 2005. - 229 с. (см. с.97-130)]; (см. также Приложение 1, пп.27-31) и генерируют открытый ключ путем умножения точки G на МДЧ k, т.е. формируют открытый ключ по формуле Р=kG;
принимают ЭД, представленный МДЧ Н;
генерируют случайное МДЧ 0<t<q, по которому формируют точку R по формуле R=tG;
R
R
формируют ЭЦП Q в виде пары МДЧ (r, s), для чего генерируют МДЧ r по формуле r=x mod q, где х - абсцисса точки R, а затем генерируют МДЧ s по формуле s=(tH+rk) mod q;
-1
-1
R'
R'
формируют первое проверочное МДЧ А, для чего генерируют МДЧ ν по формуле ν=sH mod q и МДЧ w по формуле w=(q-rH) mod q, затем генерируют точку R' по формуле R'=νG+wP, после чего МДЧ А получают по формуле А=x mod q, где x - абсцисса точки R';
формируют второе проверочное МДЧ В путем копирования МДЧ r: В=r;
сравнивают сформированные проверочные МДЧ А и В;
при совпадении параметров сравниваемых МДЧ А и В делают вывод о подлинности ЭЦП.
Недостатком ближайшего аналога является относительно невысокая производительность процедуры формирования и проверки ЭЦП, что связано с тем, что выполнение операций над точками ЭК включает операцию деления МДЧ по модулю простого МДЧ, которая требует времени выполнения, длительность которого более чем в 10 раз превышает время выполнения операции умножения.
Целью изобретения является разработка способа формирования и проверки подлинности ЭЦП, заверяющей ЭД, свободного от операции деления по модулю простого МДЧ, благодаря чему повышается производительность процедур формирования и проверки ЭЦП.
1
2
z
1
2
u
1
2
u
1
2
u
k1
k2
ku
Поставленная цель достигается тем, что в известном способе формирования и проверки подлинности ЭЦП, заверяющей ЭД, заключающемся в том, что генерируют секретный ключ в виде, по крайней мере, одной БС k, по секретному ключу формируют открытый ключ Y в виде более чем одной БС, принимают ЭД, представленный БС Н, Н, …, H, где z≥1, в зависимости от принятого ЭД и от значения секретного ключа формируют ЭЦП Q в виде двух или более БС, в зависимости от открытого ключа, принятого ЭД и ЭЦП формируют первое А и второе В проверочные БС, сравнивают их и при совпадении их параметров делают вывод о подлинности ЭЦП, новым в заявленном изобретении является то, что генерируют секретный ключ в виде МДЧ k, k, …, k, где u≥1, и открытый ключ Y формируют в виде m-мерного, где m≥2, вектора БС, для чего генерируют m-мерные вектора БС G, G, …, G, после чего открытый ключ Y генерируют по формуле Y=G °G °…°G , где знак ° обозначает операцию умножения векторов БС.
Осуществление операций умножения векторов БС не требует выполнения операции деления по модулю, благодаря чему повышается производительность формирования и проверки подлинности ЭЦП, заверяющей ЭД. Кроме того, поскольку координаты вектора БС, являющегося результатом выполнения операции умножения векторов БС, являющихся операндами, вычисляются по координатам векторов-операндов независимо друг от друга, то имеется возможность распараллелить операцию умножения векторов БС на m независимых процессов и выполнять их параллельно, благодаря чему применение вычислений над векторами позволяет существенно повысить скорость процедур формирования и проверки подлинности ЭЦП.
В заявленном способе формирования и проверки подлинности ЭЦП в качестве векторов БС могут быть применены вектора МДЧ и вектора многочленов. Использование в качестве векторов БС векторов МДЧ позволяет эффективно реализовать заявленный способ в специализированных вычислительных устройствах. Выполнение операции умножения векторов МДЧ включает выполнение над МДЧ, являющимися координатами векторов МДЧ, операций сложения и умножения по модулю простого МДЧ, а операции деления по модулю простого МДЧ не выполняются. Выполнение операции умножения векторов многочленов включает выполнение над многочленами, являющимися координатами векторов многочленов, операций сложения и умножения по модулю неприводимого многочлена, а операции деления по модулю неприводимого многочлена не выполняются. Таким образом, в обоих формах представления векторов БС при осуществлении операции умножения векторов БС не требуется выполнять операцию деления по модулю, благодаря чему обеспечивается повышение производительности процедур формирования и проверки подлинности ЭЦП как при программной, так и при аппаратной реализации заявленного способа.
1
2
u
1
2
u
k1
k2
ku
Новым является также и то, что открытый ключ Y формируют в виде m-мерного вектора МДЧ, для чего генерируют w-мерные вектора МДЧ G, G, …, G, после чего открытый ключ Y генерируют по формуле Y=G °G °…°G , где знак ° обозначает операцию умножения векторов МДЧ.
Применение в качестве векторов БС векторов МДЧ позволяет эффективно реализовать заявленный способ формирования и проверки ЭЦП в программах для ЭВМ.
1
2
u
1
2
u
k1
k2
ku
Новым является также и то, что открытый ключ Y формируют в виде m-мерного вектора многочленов, для чего генерируют m-мерные вектора многочленов G, G, …, G, после чего открытый ключ Y генерируют по формуле Y=G °G °…°G , где знак ° обозначает операцию умножения векторов многочленов.
Применение в качестве векторов БС векторов многочленов позволяет эффективно реализовать заявленный способ формирования и проверки ЭЦП в специализированных электронных устройствах. При этом наиболее высокая производительность при низкой сложности аппаратной реализации достигается применением в заявленном способе векторов двоичных многочленов.
1
2
u
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
m
1
2
m
1
2
m
k1
k2
km
t1
t2
tm
2
e
H1s1
H2s2
Hmsm
Новым является также то, что генерируют секретный ключ в виде МДЧ k, k, …, k, где u=m, и открытый ключ Y формируют в виде m-мерного вектора БС, для чего генерируют m-мерные вектора МДЧ G, G, …, G, имеющие порядок, равный простому МДЧ q, после чего открытый ключ Y генерируют по формуле Y=G °G °…°G , принимают электронный документ, представленный БС Н, Н, …, Н, а ЭЦП формируют в виде совокупности БС е, s, s, …, s, для чего генерируют случайные МДЧ t, t, …, t, генерируют вектор БС R по формуле R=G °G °…°G , затем формируют первую БС е ЭЦП в виде МДЧ, вычисляемого в зависимости от R по формуле e=f(R,H), где f(R,H) - выражение, задающее правило вычисления МДЧ е, и H=H||H||…|H, затем генерируют m БС s, s, …, s ЭЦП в виде МДЧ, вычисляемых по формулам , , …, , после чего формируют первую и вторую проверочные БС А и В по формулам А=f(R', Н) и B=е, где вектор БС R вычисляют по формуле R'=Y°G °G °…°G .
Использование секретного ключа в виде набора из нескольких МДЧ позволяет обеспечить высокую стойкость ЭЦП при использовании векторов БС, порядок которых равен простому числу сравнительно малого размера, что упрощает выбор параметров для реализации заявленного способа формирования и проверки ЭЦП, заверяющей ЭД.
k
t
q-e
s
1
1
1
1
1
Новым является также и то, что генерируют секретный ключ в виде МДЧ k и открытый ключ Y формируют в виде трехмерного вектора БС, для чего генерируют трехмерный вектор БС G, имеющий порядок, равный МДЧ q, после чего открытый ключ Y генерируют по формуле Y=G, принимают ЭД, представленный БС H, а ЭЦП формируют в виде двух БС е и s, для чего генерируют случайное МДЧ t, генерируют вектор БС R по формуле R=G, затем формируют первую БС е ЭЦП в виде МДЧ, вычисляемого в зависимости от R и Н по формуле e=f(R,H), где f(R,H) - выражение, задающее правило вычисления МДЧ е, затем генерируют вторую БС s ЭЦП в виде МДЧ, вычисляемого по формуле s=(t+ke)mod q, после чего формируют первую и вторую проверочные БС А и В по формулам А=f(R',H) и B=е, где вектор БС R' вычисляют по формуле R'=Y°G.
В данном частном варианте реализации п.1 формулы изобретения используется секретный ключ в виде одного МДЧ k и один вектор G, благодаря чему при реализации заявленного способа формирования и проверки ЭЦП и использовании циклических групп векторов БС обеспечивается сравнительно малый размер ЭЦП при заданном уровне стойкости ЭЦП.
1
2
1
2
1
2
1
2
1
2
1
2
1
1
1
1
2
1
1
1
2
2
2
1
1
2
k1
t2
t1
t2
e
s1
s2
Новым является также и то, что генерируют секретный ключ в виде двух МДЧ k и k, и открытый ключ Y формируют в виде двухмерного вектора БС, для чего генерируют два двухмерных вектора БС G и G, имеющие порядок, равный простому МДЧ q, после чего открытый ключ Y генерируют по формуле Y=G °G , принимают ЭД, представленный БС Н^, а ЭЦП формируют в виде трех БС е, s и s, для чего генерируют случайные МДЧ t и t, генерируют двухмерный вектор БС R по формуле R=G °G , затем формируют первую БС е ЭЦП в виде МДЧ, вычисляемого в зависимости от R и H по формуле e=f(R,H), где f(R,H) - выражение, задающее правило вычисления МДЧ е, затем генерируют пару БС s и s ЭЦП в виде МДЧ, вычисляемых по формулам s=(t-ke)mod q и s=(t-ke)mod q, после чего формируют первую и вторую проверочные БС А и В по формулам А=f(R',H) и B=е, где вектор битовых строк R' вычисляют по формуле R'=Y°G °G .
1
2
Генерация двух различных секретных ключей позволяет повысить стойкость алгоритма ЭЦП при использовании нециклических групп двухмерных векторов за счет использования двухмерных векторов БС G и G, генерирующих циклические подгруппы нециклической группы векторов БС, такие, что они не попадают в какую либо одну циклическую подгруппу нециклической группы векторов БС.
1
2
1
2
1
2
1
2
1
1
2
1
2
1
2
1
1
1
1
2
1
1
1
1
2
2
2
2
1
2
k1
k2
t1
t2
e
s1
s2
Новым является также и то, что генерируют секретный ключ в виде двух МДЧ k и k, и открытый ключ Y формируют в виде в виде пятимерного вектора БС, для чего генерируют два пятимерных вектора БС G и G, имеющие порядки, равные простым МДЧ q и q, соответственно, после чего открытый ключ Y генерируют по формуле Y=G °G , принимают ЭД, представленный БС H, а ЭЦП формируют в виде трех БС е, s и s, для чего генерируют случайные МДЧ t и t, генерируют вектор БС R по формуле R=G °G , затем формируют первую БС е ЭЦП в виде МДЧ, вычисляемого в зависимости от R и Н по формуле e=f(R,H), где f(R,H) - выражение, задающее правило вычисления МДЧ е, затем генерируют пару БС s и s ЭЦП в виде МДЧ, вычисляемых по формулам s=(t-ke)mod q и s=(t-ke)mod q, после чего формируют первую и вторую проверочные БС А и В по формулам A=f(R',H^) и В=е, где вектор БС R' вычисляют по формуле R'=Y°G °G .
Использование векторов БС размерности m=5 позволяет снизить сложность операции умножения векторов БС по сравнению со случаями использования векторов БС меньшей размерности, сохраняя возможность получения нециклических групп векторов БС, содержащих различные циклические подгруппы, не принадлежащие какой-либо одной циклической подгруппе, что позволяет повысить стойкость алгоритмов ЭЦП путем формирования открытого ключа по двум секретным ключам.
1
2
3
1
2
3
1
2
3
1
1
2
3
1
2
3
1
2
3
1
1
1
1
2
3
1
1
1
2
2
2
3
3
3
1
1
2
3
k1
k2
k3
t1
t2
t3
e
s1
s2
s3
Новым является также и то, что генерируют секретный ключ в виде трех МДЧ k, k и k, и открытый ключ Y формируют в виде трехмерного вектора БС, для чего генерируют три трехмерных вектора БС G, G и G, имеющие порядок, равный простому МДЧ q, после чего открытый ключ Y генерируют по формуле Y=G °G °G , принимают ЭД, представленный Н, а ЭЦП формируют в виде четырех БС е, s, s, и s, для чего генерируют случайные МДЧ t, t, и t, генерируют вектор БС R по формуле R=G °G °G , затем формируют первую БС е ЭЦП в виде МДЧ, вычисляемого в зависимости от R и Н по формуле e=f(R,H), где f(R,H) - выражение, задающее правило вычисления МДЧ е, затем генерируют тройку БС s, s, и s ЭЦП в виде МДЧ, вычисляемых по формулам s=(t-ke)mod q, s=(t-ke)mod q и s=(t-ke)mod q, после чего формируют первую и вторую проверочные БС А и В по формулам А=f(R',Н) и B=е, где вектор БС R вычисляют по формуле R'=Y°G °G °G .
1
1
1
2
3
1
2
3
1
2
3
g
1
2
3
k
1
2
3
g
1
2
3
k
В качестве выражения е=f(R,H) может быть, например, использована формула е=rH mod δ, где r=(r||r||r) - МДЧ, заданное конкатенацией БС, являющихся координатами вектора БС R, и δ - вспомогательное простое МДЧ. Генерация трех различных секретных ключей позволяет повысить стойкость алгоритма ЭЦП при использовании нециклических групп векторов БС за счет использования векторов БС G, G и G размерности m=3, генерирующих циклические подгруппы нециклической группы векторов БС, такие, что они попарно не попадают в какую либо одну циклическую подгруппу нециклической группы векторов БС. Конкатенацией двух БС а и b, представленных в виде а=ааа…a и b=bbb…b, называется БС с=а||b=ааа…аbbb…b. Знак || обозначает операцию конкатенации.
1
2
m
1
2
1
2
Вектор БС - это набор из двух или более БС, называемых координатами вектора БС. Вектор БС записывается различными способами, требование к которым состоит в том, чтобы они идентифицировали позиции координат вектора БС. Например, вектор БС можно записать в виде (a, a, …, а), где m>2 - это размерность вектора БС, равная числу координат в векторе БС. В качестве разделителя может быть использован знак операции сложения векторов БС, определенной как сложение одноименных координат двух векторов БС, являющихся слагаемыми. При использовании такого разделителя координаты вектора идентифицируются указанием формального базисного вектора (устанавливаемого перед или после соответствующей координаты) в виде буквы латинского алфавита. Формальными базисные вектора называются потому, что им не приписывается никакого физического смысла. Они служат только для того, чтобы идентифицировать координаты вектора БС, независимо от последовательности их записи. Так, например, вектора БС Z=523425e+3676785i+53453453j и Z=3676785i+523425e+53453453j, в которых координатами являются МДЧ, рассматриваются как равные, т.е. Z=Z. Отдельные слагаемые в такой записи векторов БС называются компонентами вектора БС, поскольку они представляют собой вектора БС с одной ненулевой координатой. Размерность вектора БС - это количество БС, входящих в вектор БС в качестве его координат. В данной заявке рассматриваются конечные группы векторов БС, т.е. алгебраические группы, элементами которых являются вектора БС вида Z=ае+bi+…+cj, а групповая операция определена через операции над векторами БС как операция перемножения компонентов векторов БС, являющихся операндами, с учетом того, что возникающие при этом произведения формальных базисных векторов заменяются по некоторой специфицированной таблице одним базисным вектором или однокомпонентным вектором, т.е. вектором, содержащим только одну ненулевую координату. Такая таблица умножения базисных векторов для случая векторов БС размерности m=3 имеет, например, следующий вид:
Таблица 1
Таблица умножения базисных векторов для случая m=3
е
i
i
е
е
i
j
j
i
j
е
j
j
е
i
Эта таблица определяет следующее правило подстановки базисных векторов:
e·i→i, e·j→j, j·i→e, i·i→j, j·j→i и т.д.
1
1
1
1
2
2
2
2
1
2
Такие таблицы будем называть таблицами умножения базисных векторов. Например, пусть Z=ае+bi+cj и Z=ае+bi+cj, тогда операция умножения векторов БС Z и Z (обозначим ее знаком «°») выполняется следующим образом:
1
2
1
1
i
2
2
2
Z°Z=(aе+bi+cj)°(ae+bi+сj)=
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
aaеe+abei+acej+baie+bbij+bcij+ccje+cbji+ccjj=
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
(aa+bc+cb)e+(аb+ba+сc)i+(ас+сa+bb)j.
d
d
Чтобы задать конечные группы векторов БС операции сложения и умножения над БС, являющимися координатами векторов БС, задаются специальным образом, а именно так, что координатами являются элементы конечного поля, в частности поля чисел, являющихся остатками от деления всех целых чисел на некоторое простое число р, называемое модулем. Такие поля называются простыми и обозначаются следующим образом GF(p). Число элементов простого конечного поля равно р и называется порядком поля. Другим практически важным случаем задания конечных множеств векторов БС является задание векторов БС над конечными полями многочленов. Такие поля называются расширенными конечными полями и обозначаются следующим образом: GF(p), где d - натуральное число, называемое степенью расширения простого поля характеристики р. Понятие поля хорошо известно в научно-технической литературе [см., например, А.И.Кострикин. Введение в алгебру. Основы алгебры. М.: Физматлит. 1994. - 320 с.]. Многочлен - это последовательность коэффициентов, например МДЧ, являющихся элементами поля GF(p). Над многочленами определены операции сложения многочленов и умножения многочленов, которые сводятся к выполнению действий с коэффициентами многочленов, являющихся операндами. Многочлены и правила действия над ними подробно рассмотрены в книгах [А.И.Кострикин. Введение в алгебру. Основы алгебры. М.: Физматлит. 1994. - 320 с.] и [Курош А.Г. Курс высшей алгебры. - М., «Наука», 1971. - 431 с.]. В вычислительных устройствах многочлены представляются в виде БС, в которых каждый бит или каждая подстрока битов фиксированной длины интерпретируется как один из коэффициентов многочлена, над которыми определены операции сложения и умножения коэффициентов. Элементами конечного поля многочленов являются все возможные многочлены, коэффициентами которых являются элементы простого поля GF(p) для некоторого заданного значения простого числа р. Операция умножения в поле многочленов состоит в умножении многочленов-сомножителей и взятии остатка от делении полученного произведения на некоторый заданный неприводимый многочлен. Число элементов конечного поля многочленов (порядок поля) равно p, где d - степень неприводимого многочлена, которая совпадает с максимальным числом ненулевых коэффициентов в многочленах, получаемых в качестве остатка от деления на неприводимый многочлен.
1
1
1
1
2
2
2
2
Вектора, в которых БС являются элементами конечного простого поля, т.е. многоразрядными двоичными числами, будем называть векторами МДЧ. Вектора, в которых БС являются элементами конечного расширенного поля, т.е. многочленами, будем называть векторами многочленов. Действия над конечными множествами векторов МДЧ и конечными множествами многочленов описываются одинаково, за исключением того, что действия над координатами векторов относятся к полям различного типа, а потому отличаются в этих двух случая. Действия над координатами векторов МДЧ можно описать как выполнение операций сложения и умножения по модулю простого числа р. Действия над координатами векторов многочленов можно описать как выполнение операций сложения и умножения по модулю неприводимого многочлена р. Размер модуля в обоих случаях выбирается таким, чтобы обеспечить достаточно большой порядок группы векторов МДЧ. В обоих случаях формула, описывающая действия, которые выполняются при умножении векторов БС Z=(ae+bi+cj) и Z=ae+bi+cj, имеет одинаковый вид:
1
2
1
1
1
2
2
2
Z°Z=(ae+bi+cj)°(ae+bi+сj)=
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
(аа+bc+cb modp)e+(аb+ba+сс modp)i+(аc+са+bb modp)j.
Таким образом, примеры реализации заявляемого способа формирования и проверки подлинности ЭЦП, приведенные для случая задания векторов БС над простыми полями, одновременно задают и примеры реализации заявляемого способа для случая задания векторов БС над конечными расширенными полями, т.е. полями многочленов.
В случае векторов МДЧ в качестве координат вектора МДЧ могут быть заданы целые числа из конечного кольца целых чисел, являющихся остатками от деления всех целых чисел на составное натуральное число. Возможный вариант таких случаев подробно описан в примере 6, приведенном ниже.
В зависимости от размерности векторов БС, над которыми определяются операции умножения, и конкретного варианта задания операции умножения векторов БС могут быть использованы различные таблицы умножения базисных векторов, например, для векторов БС размерности m=2 приемлемая таблица имеет вид таблицы 2, а для векторов БС размерности m=3 - вид таблицы 3, где ε - БС, представляющая элемент конечного поля, над которым задано множество векторов БС. В качестве параметра s может быть выбран произвольный элемент указанного поля. Например, различные значения параметра ε, выбираемые в интервале 0<ε<p, придают различные свойства конечной группе векторов МДЧ при фиксированном значении размерности m и модуля р. Таблицы умножения базисных векторов для случая векторов МДЧ и векторов многочленов, представляющих частные варианты задания векторов БС, имеют одинаковый вид, за исключением того, что в случае векторов МДЧ коэффициент е представляет собой некоторое МДЧ ε, такое, что 0<ε<p, а в случае векторов многочленов коэффициент ε представляет собой некоторый многочлен.
Таблица 2
Таблица умножения базисных векторов для случая m=2
е
i
е
е
i
i
i
εе
Таблица 3
Таблица умножения базисных векторов для случая m=3
е
i
j
е
е
i
j
i
i
εj
εе
j
j
εе
i
Таблица 4
Таблица умножения базисных векторов для случая m=7
е
i
j
k
u
v
w
е
е
i
l
k
u
v
w
i
i
λε·j
ρλε·k
τε·u
ρλε·v
λε·w
ρτλεµ·е
j
J
φλε·k
ρλε·u
ρτε·v
ρλε·w
ρτλεµ·е
ρτµ·k
k
k
τε·u
ρτε·v
τε·w
ρτλεµ·е
τµ·i
τµ·j
u
u
ρλε·v
ρλε·w
ρτλεµ·e
ρτλε·v
λµ·j
ρλµ·k
V
v
λε·w
ρτλεµ·e
τµ·i
λµ·j
λµ·k
τµ·u
w
w
ρτλεµτ·е
ρτµ·k
τµ·j
ρλµ·k
τµ·u
ρτµ·v
Аналогичным способом могут быть определены групповые операции над конечными группами векторов БС размерностей m=4, m=5 и т.д. Например, правила умножения базисных векторов для случая m=7 приведены в таблице 4, где в качестве коэффициентов растяжения ρ, τ, λ, ε, µ и τ могут быть использованы произвольные шесть значений, являющихся многочленами в случае, когда вектора БС представляют собой вектора многочленов, или являющихся МДЧ в случае, когда вектора БС представляют собой вектора МДЧ.
n
n
При соответствующем выборе таблицы умножения базисных векторов и простого значения р множество векторов МДЧ является конечным и это конечное множество содержит подмножество векторов МДЧ, которое образуют группу с групповой операцией «°», причем порядок этой подгруппы является достаточно большим. Группа - это алгебраическая структура (т.е. множество математических элементов некоторой природы), над элементами которой задана некоторая операция таким образом, что алгебраическая структура обладает следующим набором свойств: операция ассоциативна, результатом выполнения операции над двумя элементами является элемент этой же структуры, существует нейтральный элемент такой, что при выполнении операции над ним и другим некоторым элементом а группы результатом является элемент а. Детальное описание групп дано в широко доступной математической литературе, например в книгах [А.Г.Курош. Теория групп. - М., изд-во «Наука», 1967. - 648 с.] и [М.И.Каргаполов, Ю.И.Мерзляков. Основы теории групп. - М., изд-во «Наука. Физматлит», 1996. -287 с.]. Операция определенная над элементами группы называется групповой операцией. Группа называется циклической, если каждый ее элемент может быть представлен в виде g=a для некоторого натурального числа n, где а - элемент данной подгруппы, называющийся генератором или образующим элементом циклической подгруппы, и степень n означает, что над элементом а выполняются n последовательны операций, т.е. а=а°а°а°…°а (n раз). Известно, что, если порядок группы есть простое число, то она циклическая [А.И.Кострикин. Введение в алгебру. Основы алгебры. М.: Физматлит. 1994. - 320 с.]. Важной характеристикой группы является ее порядок, который равен числу элементов в группе. Для элементов группы также применяется понятие порядка. Порядком элемента группы является минимальное значение степени, в которую нужно возвести этот элемент, чтобы результатом операции было получение нейтрального элемента группы.
Обычно при разработке способов формирования и проверки ЭЦП используются циклические группы большого простого порядка или группы, порядок которых делится нацело на большое простое число [Венбо Мао. Современная криптография. Теория и практика. - М., СПб, Киев. Издательский дом «Вильямс», 2005. - 763 с.]. При соответствующем задании группы векторов БС это условие легко обеспечивается. При этом стойкость способов формирования и проверки ЭЦП определяется сложностью задачи дискретного логарифмирования, которая состоит в определении значения степени n, в которую надо возвести заданный элемент группы, чтобы результатом этой операции был некоторый другой заданный элемент группы [Молдовян Н.А. Практикум по криптосистемам с открытым ключом. - СПб. БХВ-Петербург, 2007. - 298 с.].
Поскольку групповая операция о над векторами МДЧ выполняется путем выполнения модульных умножений и сложений над МДЧ, являющихся координатами векторов МДЧ, достаточно высокая трудность задачи дискретного логарифмирования в группе векторов МДЧ достигается при сравнительно малом значении размера модуля p, благодаря чему обеспечивается сравнительно высокая производительность операции возведения векторов МДЧ в большую степень. Поскольку производительность процедур формирования и проверки ЭЦП определяется производительностью операции возведения в степень, то при использовании операций над векторами МДЧ обеспечивается сравнительно высокая производительность процедур формирования и проверки ЭЦП.
q
Порядком вектора БС V называется наименьшее натуральное число q, такое что V=1, т.е. такое, что результатом умножения вектора МДЧ Q на самого себя q раз является единичный вектор МДЧ Е=1e+0i+…+0j=(1, 0, 0, …, 0).
В частных случаях задания конечного множества векторов БС оно будет представлять расширенное поле, в котором все ненулевые вектора БС составляют циклическую мультипликативную группу [Молдовян НА. Алгоритмы аутентификации информации в АСУ на основе структур в конечных векторных пространствах // Автоматика и телемеханика (М., РАН), 2008]. В других частных случаях формируемые группы являются нециклическими, в которых содержится q+1 циклических подгрупп простого порядка q, где q является делителем порядка поля, над которым заданы вектора БС. При этом значение q является достаточно большим, благодаря чему нециклические группы векторов БС могут быть основой для реализации стойких алгоритмов ЭЦП даже в случае, когда размер максимального простого порядка подгрупп составляет 60-100 бит и менее. Это обеспечивается за счет того, что открытый ключ формируется на основе нескольких заданных векторов БС, входящих в разные подгруппы простого порядка, которые имеют единственный общий элемент - единичный вектор БС. Данный механизм задания открытого ключа в способах формирования и проверки ЭЦП является новым и ранее неизвестным.
k
t
e
s
Корректность заявленного способа доказывается теоретически. Рассмотрим, например, вариант реализации способа по п.5 формулы изобретения. Открытый ключ, соответствующий секретному ключу k, представляет собой вектор БС Y=G. Вектор БС R генерируется по формуле R=G, а первое МДЧ в ЭЦП (е, s) вычисляется по формуле е=f(R,H). Значение s генерируется по формуле s=(k+ek)mod q, поэтому вектор МДЧ R', генерируемый по формуле R'=YG и используемый для формирования первого проверочного МДЧ А, равен
e
s
ek
s
ek+(t-ek)
t
R'=YG=GG=G=G=R.
Поскольку вектора МДЧ R' и R одинаковы, то равны между собой и значения e'=f(R',H) и e=f(R,H), т.е. A=e'=e=В. Таким образом, правильно сформированная ЭЦП подпись удовлетворяет процедуре проверки ЭЦП, т.е. корректность процедур генерации и проверки ЭЦП доказана. Аналогичным образом дается доказательство корректности и для пп.6-8 формулы изобретения.
1
2
1
2
3
1
2
u
1
2
u
1
2
u
1
2
u
1
2
u
1
2
u
i
1
2
u
1
2
u
1
2
u
1
2
u
k1
k2
ku
e
s1
s2
su
Особенностью реализации заявленного способа формирования и проверки ЭЦП, заверяющей ЭД, по пп.6-8 и 4 формулы изобретения является использование двух G и G (пп.6 и 7), трех G, G и G (пп.8) или больше трех различных значений векторов БС (п.4), по которым вычисляется открытый ключ и которые входят в соответствующие формулы проверки подлинности ЭЦП. Этот признак является новым в области способов формирования и проверки ЭЦП и имеет принципиальное значение для случая использования конечных групп векторов БС, которые являются нециклическими. В нециклических группах векторов БС отсутствуют отдельные значения векторов БС, степени которых могут выразить любой вектор БС. Используемые различные значения G, G, …, Gотносятся к различным циклическим подгруппам нециклической группы векторов БС, поэтому для определения секретного ключа по открытому ключу требуется вычислять секретный ключ как единое целое, т.е. нет возможности вычислять секретный ключ по частям. Это позволяет построить стойкие алгоритмы ЭЦП даже в случаях, когда порядки векторов БС G, G, …, G, т.е. значения МДЧ q, q, …, q, соответственно, имеют размер значительно меньше 160 бит. Общее требование безопасности состоит в том, что суммарная длина значений q, q, …, q была не меньше, чем 160 бит. В частных реализациях высокая стойкость обеспечивается при использовании простых МДЧ q, q, …, q, равных между собой, т.е. при q=q=…=q=q. В зависимости от параметров конечного множества векторов БС и операции умножения, с помощью которой задаются конечные группы векторов БС для формирования открытого ключа, может быть использовано одно значение G (п.5 формулы изобретения), порядок которого имеет размер 160 бит и более, также могут быть использованы два (пп.6 и 7 формулы изобретения), три (п.8 формулы изобретения), четыре и более значений G, i=1, 2, …, u (п.4 формулы изобретения). В соответствии с этим также модифицируется уравнение проверки ЭЦП. Так в общем случае открытый ключ формируется по формуле Y=G °G °…°G , где k, k, …, k - элементы секретного ключа, а подлинность ЭЦП проверяется по  формуле R'=Y°G °G °…°G , где s, s, …, s - элементы ЭЦП, u≤m.
Рассмотрим примеры реализации заявленного технического решения, где конкретные значения использованных параметров описаны в приводимых ниже численных примерах. Использованные в примерах вектора МДЧ были сгенерированы с помощью программы, разработанной специально для генерации векторов МДЧ, включая вектора МДЧ с заданным порядком, и выполнения операций над векторами МДЧ. Приводимые в примере МДЧ взяты сравнительно малого размера и записаны для краткости в виде десятичных чисел. В вычислительных устройствах МДЧ представляются и преобразуются в двоичном виде, т.е. как БС в виде последовательности сигналов высокого и низкого потенциала. В реальных приложениях следует использовать вектора МДЧ, которые включают МДЧ длиной от 16 до 256 бит в зависимости от значения их размерности m. При размерности векторов МДЧ от m=12 до m=24 высокая стойкость может быть обеспечена при размере их координат, равном 16 бит. При меньшей размерности, например от m=5 до m=2, следует использовать МДЧ более высокой разрядности: от 64-128 до 160-256, соответственно.
При использовании на практике заявляемого способа следует выбрать таблицу умножения базисных векторов и размер параметров р и q таким образом, чтобы разрядность значения порядка q была равна или превышала 16, 32, 40, 64, 80 и 160 бит в зависимости от конкретного варианта реализации заявленного способа. В примерах, приводимых ниже, используются параметры с искусственно уменьшенной разрядностью, чтобы уменьшить размер примеров и сделать их более наглядными.
Пример 1.
m
Данный пример относится к варианту реализации заявленного способа по п.4 формулы изобретения. В нем используется группа, элементами которой являются вектора БС размерности m, над которыми определена операция умножения таким образом, что порядок группы равен (р-1), а максимальный порядок элементов группы равен р - 1, где p - характеристика конечного простого поля, над которым заданы вектора БС, причем БС интерпретируются как МДЧ, а операции над БС выполняются как операции над МДЧ. Условия построения групп данного типа описаны, например, для случая m=3, в работе [Молдовян НА. Группы векторов для алгоритмов электронной цифровой подписи // Вестник СПбГУ. Сер.10. 2008]. Аналогичным способом могут быть заданы группы БС для размерностей m=4, 5, 6, …. В данном примере не приводятся конкретные значения получаемых значений БС, а описываются результаты процедур формирования и генерации БС и векторов БС в обобщенном виде для произвольного случая. Подставляя вместо буквенных обозначений конкретные численные значения, могут быть построены различные варианты численной иллюстрации п.4 формулы изобретения. В данном примере акцент делается на корректность процедуры проверки подлинности ЭЦП, которая доказывается для общего случая. Выполняется следующая последовательность действий.
1
2
m
1. Генерируют секретный ключ в виде МДЧ k, k, …, k.
2. Формируют открытый ключ Y в виде m-мерного, где m≥2, вектора БС, для чего выполняют следующие действия.
1
2
m
2.1. Генерируют вектора БС G, G, …, G размерности m, имеющие порядок, равный простому МДЧ q.
1
2
m
k1
k2
km
2.2. Генерируют открытый ключ Y в виде БС, вычисляемой по формуле Y=G °G °…°G .
1
2
z
3. Принимают ЭД, представленный совокупностью БС Н, Н, …, Н, где z=m.
1
2
m
4. Формируют ЭЦП в виде совокупности БС е, s, s, …, s, для чего выполняют следующие действия.
1
2
m
4.1. Генерируют случайные МДЧ t, t, …, t.
1
2
m
t1
t2
tm
4.2. Генерируют вектор БС R по формуле R=G °G °…°G .
1
2
z
4.3. Формируют первую БС е ЭЦП в виде МДЧ, вычисляемого в зависимости от R и H по формуле е=f(R,H), где f(R,H) - выражение, задающее правило вычисления числа е и Н=H||Н||…Н, где z=m,.
1
2
m
4.4. Генерируют m БС s, s, …, s ЭЦП в виде МДЧ, вычисляемых по формулам , , …, .
5. Формируют первую проверочную БС А, для чего выполняют следующие действия.
e
H1s1
H2s2
Hmsm
1
2
m
5.1. Формируют вектор БС R', выполняя вычисления по формуле R'=Y°G °G °…°G .
1
2
z
5.2. Формируют БС А по формуле A=f(R',H), где H=H||H||…|H.
6. Формируют вторую проверочную БС В путем копирования БС е, т.е. по формуле B=е.
7. Сравнивают проверочные БС А и В.
1
2
m
Сравнение показывает, что параметры проверочных БС А и В совпадают, на основании чего делают вывод о подлинности ЭЦП. Тот факт, что при проверке ЭЦП, сформированной по процедуре формирования ЭЦП с использованием правильного секретного ключа, на шаге 7 будет получено совпадение параметров проверочных БС, доказывается следующим образом. Подставим в формулу, по которой формируется вектор БС R', значения БС s, s, …, s, полученные по формулам, приведенным в п.4.4. В результате получим
e
H1s1
H2s2
Hmsm
e
H
(t
-k
e)H
-1
H
(t
-k
e)
-1
H
(t
-k
e)H
-1
1
2
m
1
1
1
1
1
2
2
2
2
2
m
m
m
m
m
R'=Y°G °G …°G =Y°G         °G       H …°G         °G=
1
2
m
1
1
1
m
m
m
1
1
1
1
2
2
2
2
m
m
m
m
k1
k2
km
t
-k
e
t
-k
e
k
e+t
-k
e
k
e+t
-k
e
k
e+t
-k
e
=(G °G …°G )°G     …°G     =(G       °G       …°G       =
1
2
m
t1
t2
tm
G °G …°G =R⇒ A=f(R',H)=h(R,H)=B.
Таким образом, корректность процедуры проверки подлинности ЭЦП доказана.
Последовательность действий по формированию и проверке подлинности ЭЦП, заверяющей ЭД, описанная в примере 1, может быть выполнена также и для случая, когда БС представляют собой многочлены. При этом таблицы умножения базисных векторов при заданном значении размерности m являются такими же как приведенные выше, за исключением того, что коэффициент е в случае реализации заявленного способа при использовании многочленов будет представлять собой некоторый заданный многочлен, определяющий конкретный вид операции умножения векторов многочленов. Доказательство корректности процедуры проверки ЭЦП в случае, когда вектора БС представляют собой вектора многочленов, является таким же, как и приведенное выше доказательство для случая использования векторов БС, являющихся векторами МДЧ. Для практики представляют интерес различные варианты значений размерности т векторов БС. Выбор соответствующей размерности т зависит от требований конкретных применений заявленного способа формирования и проверки ЭЦП. Например, при использовании 32-разрядных процессоров для выполнения вычислений интерес представляют простые значения размерности m=5, m=7, m=11 и m=13. При аппаратной реализации в виде специализированных вычислительных устройств высокая производительность процедур формирования проверки ЭЦП может быть достигнута при значениях размерности векторов БС m=8, m=9, m=16 и m=32. Наиболее высокая производительность при аппаратной реализации может быть достигнута при использовании заявленного способа для случая использования векторов двоичных многочленов в качестве векторов БС. Это объясняется тем, что операции сложения и умножения и двоичных многочленов в конечных полях двоичных многочленов являются наиболее эффективными с точки зрения получения высокого быстродействия и уменьшения сложности аппаратной реализации.
При построении таблиц умножения базисных векторов для произвольных значений размерности m могут быть использованы таблицы умножения базисных векторов, в которых значение параметра 6 может быть выбрано в интервале 0≤ε<p, где число р выбирается таким образом, чтобы обеспечивалось значение порядка векторов БС, равное простому МДЧ q, имеющему достаточно большой размер, например, равный 32, 40, 64, 80, 160 или 256 бит. Таблица умножения базисных векторов для задания групповой операции над четырехмерными векторами МДЧ (случай m=4) имеет вид таблицы 5.
Таблица 5
Таблица умножения базисных векторов для случая m=4
е
i
j
k
е
е
i
j
k
i
i
εj
εk
εе
j
j
εk
εе
i
k
k
εе
i
j
Таблица 6
Таблица умножения базисных векторов для случая m=6
е
i
j
k
u
v
е
е
i
j
k
u
v
i
i
εj
εk
εu
εv
εе
j
j
εk
εu
εv
εе
i
k
k
εu
εv
εе
i
j
u
u
εv
εе
i
j
k
ν
v
εе
i
j
k
u
Таблица для задания групповой операции над шестимерными векторами МДЧ (случай m=6) имеет вид таблицы 6. Была разработана программа для ЭВМ, реализующая операции умножения и возведения в большую целочисленную степень векторов МДЧ, имеющих значения размерности от m=2 до m=55 для каждого промежуточного целочисленного значения размерности. С помощью этих программ были сгенерированы приведенные выше примеры и установлено, что аналогичные примеры реализации заявленного способа с использованием векторов МДЧ размерности m=7, m=8, m=11, m=13, m=16, m=17 и др. также обеспечивают корректность процедуры проверки подлинности ЭЦП.
Таблицы умножения базисных векторов, определяющие групповые операции над векторами произвольных размерностей m, строятся по следующему общему правилу. Первоначально строится исходная таблица, которая не включает коэффициентов растяжения, путем последовательной записи строк базисных векторов таким образом, что каждая следующая строка получается из предыдущей путем циклического сдвига на одну клетку. Получаемая при этом исходная таблица умножения базисных векторов имеет стандартный вид для произвольных значений размерности векторов, поэтому ее можно назвать типовой (см. распределение базисных векторов в таблице 7). Для типовой таблицы и произвольного значения т имеется два простых и общих варианта распределения коэффициента растяжения.
Один из этих вариантов состоит в выделении квадрата, состоящего из всех клеток, не входящих в первый ряд или в первую строку, и внесении коэффициента растяжения ε в клетки этого квадрата, расположенные на диагонали, идущей из правого верхнего угла в левый нижний угол (каждая из этих клеток содержит базисный вектор е), а также во все клетки, расположенные выше этой диагонали. Второй из этих вариантов является симметричным первому относительно указанной диагонали (эта диагональ отмечена в таблице 7 серым фоном). Второй вариант распределения показан как распределение коэффициента µ, который вносится в каждую клетку диагонали, содержащей базисный вектор е и все клетки, расположенные ниже этой диагонали. Коэффициентам растяжения µ и ε может быть присвоено любое значение в интервале от 0 до р-1, если задается операция умножения векторов БС, представляющих собой вектора МДЧ. В случае, когда вектора БС представляют собой вектора многочленов, коэффициентам растяжения µ и ε может быть присвоено значение произвольного многочлена, степень которого меньше степени неприводимого многочлена, используемого в качестве модуля при выполнении операций над многочленами, являющимися координатами векторов БС. При указанных вариантах произвольного выбора значений коэффициентов растяжения µ и ε операция умножения векторов БС будет обладать свойствами ассоциативности и коммутативности. Выбор конкретных значений коэффициентов растяжения определяет параметры групп векторов БС и должен осуществляться с привязкой к конкретным используемым значениям размерности m и параметра p.
Таблица 7
Таблица умножения базисных векторов для случая m=10
×
е
i
j
k
u
v
w
t
x
У
е
е
i
j
k
u
v
w
t
x
У
•
iε
εj
εk
εu
εv
εw
εt
εx
εy
µεe
j
j
εk
εu
εv
εw
εt
εx
εy
µεe
µi
k
k
εu
εv
εw
εt
εx
εy
µεe
µi
µj
u
u
εv
εw
εt
εx
εy
µεe
µi
µj
µk
v
v
εw
εt
εx
εy
µεe
µi
µj
µk
µu
w
w
εt
εx
εy
µεe
µi
µj
µk
µu
µv
t
t
εx
εу
µεe
µi
µj
µk
µu
µv
µw
x
х
εy
µεe
µi
µj
µk
µu
µv
µw
µt
У
У
µεe
µi
µj
µk
µu
µv
µw
µt
µx
При реализации заявленного способа с использованием операций над векторами многочленов различной размерности m таблицы умножения базисных векторов строятся по указанному выше общему правилу, за исключением того, что в случае векторов многочленов коэффициенты µ и ε представляют собой многочлены.
При использовании групп векторов БС, имеющих сравнительно большую размерность, высокая криптографическая стойкость ЭЦП обеспечивается при меньшей разрядности МДЧ, являющихся координатами векторов МДЧ. Например, при m=16 и m=32 разрядность указанных МДЧ может составлять 64 и 32 бита, соответственно, что позволяет повысить быстродействие процедур формирования и проверки ЭЦП при программной реализации для выполнения программ, реализующих заявляемый способ, на 64- и 32-разрядных микропроцессорах.
Пример 2 (иллюстрация п.5 формулы изобретения).
В данном примере групповая операция о выполняется с использованием следующей таблицы умножения базисных векторов.
Таблица 8
Таблица умножения базисных векторов для случая т=3 при 8=2
е
i
j
е
е
i
j
i
i
2j
2е
j
j
2е
i
Данный пример показывает, что при соответствующем выборе размерности m, простого числа p и коэффициента растяжения s значение порядка q может значительно превышать значение p. Выполняется следующая последовательность действий.
2
1. Генерируют простое число p, такое что число p+р+1 содержит простой множитель q, размер которого значительно превышает размер числа p:
р=97; q=3169.
2. Генерируют секретный ключ k в виде случайного МДЧ:
k=2079.
3. Формируют открытый ключ в виде вектора БС Y, для чего выполняют следующую последовательность действий.
3.1. Генерируют вектор БС G, имеющий порядок q=3169:
G=8е+3i+93j.
k
3.2. Генерируют вектор БС Y=G: Y=87е+96i+86j.
1
4. Принимают ЭД, представленный, например, следующим МДЧ Н(в качестве которого может быть взята, в частности, хэш-функция от ЭД):
1
H=5168.
5. Формируют ЭЦП Q в виде двух БС е и s, для чего выполняют следующие действия:
5.1. Формируют первую БС е ЭЦП, для чего
5.1.1. Генерируют случайное МДЧ t=5387.
t
5.1.2. Генерируют вектор МДЧ R по формуле R=G: R=96е+56i+81j.
1
1
2
3
5.1.3. Вычисляют БС е в виде МДЧ, вычисляемого по формуле e=rH mod δ, где r=(r||r||r) - МДЧ, равное конкатенации МДЧ, являющихся координатами вектора R, и δ=3169: е=3138.
5.2. Формируют вторую БС s ЭЦП в виде МДЧ, вычисляемого по формуле s=t+ke mod q: s=1149.
6. Формируют первую проверочную БС А, для чего выполняются следующие действия:
q-e
s
6.1. Вычисляют вектор МДЧ R' по формуле R'=Y°G (mod p):
q-e
Y (mod p)=75e+46i+84j,
s
G(mod p)=27e+81i+81j,
R'=96е+56i+81j.
1
1
2
3
6.2. Генерируют БС А в виде МДЧ, вычисляемого по формуле А A=r'H mod δ, где r'=r'||r'||r - МДЧ, равное конкатенации МДЧ, являющихся координатами вектора МДЧ R', и δ=3169 - вспомогательное простое число: А=3138.
7. Формируют вторую проверочную БС В путем копирования МДЧ е, т.е. по формуле В=е: В=е=3138.
8. Сравнивают первую и вторую проверочные БС: А=В. Совпадение проверочных БС подтверждает подлинность ЭЦП.
Пример 3.
Данный пример иллюстрирует вариант реализации заявленного способа, соответствующий п.6 формулы изобретения, в котором действия выполняются над двухмерными векторами БС. Для получения конечной группы двухмерных векторов БС вида (а, b)=ае+bi БС а и b интерпретируются как МДЧ, над которыми определены операции умножения и сложения координат, выполняемые по модулю целого положительного числа. В данном примере групповая операция о выполняется с использованием таблицы 2. В соответствии с этой таблицей умножения базисных векторов для случая размерности m=2 имеем i·i=ε, где ε∈{1,…,р-1}, где p - простое МДЧ. Операция умножения двухмерных БС (а, b) и (с, d) выполняется по правилу:
-1
-1
где g'=(ас+εbd) mod р и h'=(ad+be) mod p. Легко проверить, что определенные таким образом операции сложения и умножения обладают свойствами ассоциативности и коммутативности. Среди алгебраических структур такого типа имеются конечные поля и мультипликативные группы, существенным свойством которых является наличие единицы Е=(1,0) - нейтрального элемента по умножению, который определяет существование для каждой ненулевой пары А единственного обратного значения А, такого что АА=Е.
-1
Группа - это алгебраическая структура с ассоциативной операцией, для которой существует обратная операция [А.Г.Курош. Курс высшей алгебры. - М., «Наука», 1971. - 431 с.], т.е. уравнения АХ=В и YA=В имеют единственное решение для любых элементов А и В. Поскольку определенная выше операция умножения является коммутативной, то указанные уравнения являются эквивалентными им, можно рассматривать только одно из них. Легко показать, что однозначность решения указанных уравнений выполняется, если для каждого элемента А существует единственное обратное значение А, поэтому представляет интерес рассмотреть решение уравнений вида АХ=Е, которое можно представить следующим образом:
(ае+bi)(xe+yi)=((ax+εby)mod p)e+(ay+bx)mod p)i=1e+0i.
Из последней записи вытекает, что для определения обратных значений следует решать следующую систему из двух линейных сравнений с двумя неизвестными х и y
Рассмотрим существование решений этой системы. Приравнивая к нулю главный определитель этой системы, получаем характеристическое уравнение
2
2
a-εb≡0 mod p.
Значение (а, b)=(0, 0) является решением характеристического уравнения для любых значений модуля, поэтому для этой пары не существует обратного значения. Значения p и ε можно выбрать таким образом, что характеристическое уравнение не имеет других решений, а значит рассматриваемая система сравнений имеет единственное решение для любой пары (а, b)≠(0, 0).
В примере 1 используется группа двухмерных векторов БС, формируемая в случае задания операции умножения, определяемой по формуле (1) при использовании параметра ε, который является квадратичным вычетом по модулю р. При этих условиях характеристическое уравнение имеет, кроме (а, b)=(0, 0), еще 2(р-1) следующих решений вида
1/2
1/2
(εb mod р, b) и (-εb mod р, b),
где b∈{0, 1, …, р-1}. Для пар такого вида не существуют решений системы сравнений, которые определяют значение обратных элементов. Следовательно, количество элементов, для которых существуют единственные обратные значения, равно
2
2
Ω=p-2(p-1)-1=(p-1).
Эти элементы составляют мультипликативную группу, поскольку результат умножения любых двух элементов из этого множества является элементом этого же множества.
В рассматриваемом примере выполняется следующая последовательность действий.
1. Генерируют простое число p, такое что р-1 содержит большой простой множитель q, т.е. p=Nq+1, где N - четное число, и задают значение ε=225, являющееся квадратичным вычетом по модулю p:
р=3990163786012426536171919;
q=1997539432909;
1
2
2. Генерируют секретный ключ в виде пары случайных МДЧ k и k:
1
2
k=1853362791; k=8457313533;
3. Формируют открытый ключ в виде вектора МДЧ Y, для чего выполняют следующую последовательность действий.
1
2
3.1. Генерируют пару векторов МДЧ G и G, имеющих порядок q=1997539432909.
1
G=329450458956292027б812106е+2766233567473802431338876i;
2
G=1028484769067346813640211е+3852939155310569961109202i;
1
2
k1
k2
3.2. Генерируют вектор МДЧ Y=G °G :
1
1
k1
Y=G =1183619390973024467297431е+3703669051605973538784782i;
2
2
k2
Y=G =182788774563660856108049e+1936038364647789724421279i;
1
2
Y=Y°Y=1924471834140042300320534e+174837666126798422981001i;
1
4. Принимают ЭД, представленный, например, следующим МДЧ Н(в качестве которого может быть взята, в частности, хэш-функция от ЭД):
1
H=7579346783.
1
2
5. Формируют ЭЦП Q в виде трех БС е, s и s, для чего выполняют следующие действия:
5.1. Формируют первую БС е ЭЦП, для чего
1
2
5.1.1. Генерируют два случайных МДЧ t=18357236873 и t=38157216371.
1
2
t1
t2
5.1.2. Генерируют вектор МДЧ R по формуле R=G °G :
1
1
t1
R=G =755879295575251075473814е+440880985283782634380692i;
2
2
t2
R=G =14324905143б4096482144778е+9522884704673923116940461;
1
2
R=R°R=182878511143б413473493597е+3766810841718525336502327i.
1
1
1
5.1.3. Генерируют БС е в виде МДЧ, вычисляемого по формуле е=rH mod δ, где δ - вспомогательное простое число, например, δ=q=1997539432909; r - МДЧ, являющееся первой координатой вектора МДЧ R: е=1701612237557.
1
2
1
1
1
2
2
2
5.2. Формируют вторую и третью БС s и s, ЭЦП в виде двух МДЧ, вычисляемых по формулам s=t-ke mod q и s=t-ke mod q:
1
2
s=1767916348307; s=1894616394985.
6. Формируют первую проверочную БС А, для чего выполняют следующие действия:
е
s1
s2
1
2
6.1. Генерируют вектор МДЧ R' по формуле R'=Y°G °G :
e
Y=38490379439456736б0459504е+3583704901879536834939540i.
1
s1
G =3580532237073410771710519е+8968477484858204736035681;
2
s2
G =2902157646689814295993329e+1114779150752846285743470i. R'=182878511143б413473493597е+3766810841718525336502327i.
1
1
1
6.2. Генерируют БС А в виде МДЧ, вычисляемого по формуле А=r'H mod q, где r' - МДЧ, являющееся первой координатой вектора МДЧ R': А=1701612237557.
7. Формируют вторую проверочное БС В путем копирования МДЧ е, т.е. по формуле B=е: В=е=1701612237557.
8. Сравнивают первую и вторую проверочные БС: А=В.
Совпадение проверочных БС подтверждает подлинность ЭЦП.
Пример 4 (иллюстрация п.7 формулы изобретения).
В данном примере рассматривается случай использования пятимерных векторов БС (случай m=5), в котором групповая операция о выполняется с использованием таблицы 9 умножения базисных векторов.
Таблица 9
Таблица умножения базисных векторов для случая m=5
е
i
j
k
u
е
е
i
jJ
k
u
i
i
εj
εk
εu
εе
j
j
εk
εu
εе
i
k
k
εu
εе
i
j
u
u
εе
i
j
k
Выполняется следующая последовательность действий.
1. Генерируют простое число p, такое что р-1 содержит большой простой множитель q, т.е. р=Nq+1, где N - четное число, и задают значение е=17377: р=13900359797; q=820177;
1
2
2. Генерируют секретный ключ в виде пары случайных МДЧ k и k.
1
2
k=3178457367; k=4154733715.
3. Формируют открытый ключ в виде вектора БС Y, для чего выполняют следующую последовательность действий.
1
2
1
2
3.1. Генерируют два вектора БС G и G, имеющие порядок q=820177 и q=59403247.
1
G=4670230529e+6363758539i+1115493580j+11774211119k+4481291788u;
2
G=7346947995 с+9935549003i+571858634J+5252170971k+11375019823u.
1
2
k1
k2
3.2. Генерируют вектор МДЧ Y=G °G :
1
Y=5595374136e+6222510934i+5243302038J+12338881800k+1993502504u;
2
Y=8724284212 с+10520629249i+37795532J+9839512858k+9802549315u;
1
2
Y=Y°Y=13267009731e+3879646147i+6539448930J+107533229k++9727330067u.
1
1
4. Принимают ЭД, представленный, например, следующим МДЧ Н (в качестве которого может быть взята, в частности, хэш-функция от ЭД): H=89154314.
1
2
5. Формируют ЭЦП Q в виде трех БС е, s и s, для чего выполняют следующие действия:
5.1. Формируют первую БС е ЭЦП, для чего
1
2
5.1.1. Генерируют два случайных МДЧ k=613352348 и k=37591463.
1
2
t1
t2
5.1.2. Генерируют вектор МДЧ R по формуле R=G °G :
1
R=2267371210e+1531475463i+11370174246j+13211765802k+10527441855u;
2
R=13108093911e+3936822199i+9539524888j+5370585930k+6567932491u;
1
2
R=R°R=6897422139с+6311588041+593548634J+4117090044k++2590225180 ч.
1
2
3
1
1
2
3
5.1.3. Генерируют БС е в виде МДЧ, вычисляемого по формуле е=(r||r||r)H mod δ, где δ - вспомогательное простое число, в качестве которого в данном примере берется МДЧ δ=2376581; r||r||r - МДЧ, равное конкатенации первых трех координат вектора МДЧ R: е=119236.
1
2
1
1
1
1
2
2
2
2
1
2
5.2. Формируют вторую и третью БС s и s ЭЦП в виде МДЧ, вычисляемых по формулам s=t-ke mod q и s=t-kе mod q: s=626030; s=2528952.
6. Формируют первую проверочную БС А, для чего выполняются следующие действия:
е
s1
s2
1
2
6.1. Генерируют вектор БС R' по формуле R'=Y°G °G :
e
Y=977315114e+13874743606i+10113644214j+97683587k+971368210u;
1
sl
G =10769096929e+2654696484i+11130937343j+3507101146k+4306145379u;
1
s2
G =12814278574e+7057455723i+12699485338j+1124012626k+147947960u;
R'=6897422139е+631158804i+593548634j+4117090044k+2590225180u.
1
2
3
1
1
2
3
-
6.2. Генерируют БС A в виде МДЧ, вычисляемого по формуле А=(r'||r'||r')H mod δ, где r'||r'||r' МДЧ, равное конкатенации первых трех координат вектора МДЧ R': А=119236.
7. Формируют вторую проверочную БС путем копирования БС: В=е=119236.
8. Сравнивают первую и вторую проверочные БС: А=В. Совпадение проверочных БС подтверждает подлинность ЭЦП.
Пример 5 (иллюстрация п.8 формулы изобретения).
В данном примере рассматривается случай использования трехмерных векторов БС (m=3), в котором групповая операция о выполняется с использованием таблицы 3, задающей правило умножения базисных векторов в этом примере. Выполняется следующая последовательность действий.
1. Генерируют простое число р, такое что р-1 содержит большой простой множитель q, т.е. р=3Nq+1, где N - четное число, и задают значение ε=6859=19, являющееся кубичным вычетом по модулю з:
р=33888823497367; q=2376581;
1
2
3
2. Генерируют секретный ключ в виде тройки случайных МДЧ k, k и k:
1
2
3
k=1853362791; k=8457313533; k=3873059582.
3. Формируют открытый ключ в виде вектора МДЧ Y, для чего выполняют следующую последовательность действий.
1
2
3
3.1. Генерируют три вектора МДЧ G, G и G, имеющие одно и то же значение простого порядока q=2376581.
1
G=5955377462471e+28217758221981i+21380040635602j;
2
G=31195950338318е+1146212670059i+19798505045659j;
3
G=12169985178873e+22834221533336i+23611151771899j.
1
2
k1
k2
3k3
3.2. Генерируют вектор МДЧ Y=G °G °G:
1
1
k1
Y=G =2610б3б2944111е+9121853491576i+7998895962567j;
2
2
k2
Y=G =8841482011615e+31890466083034i+31068266275905j;
3
3
k3
Y=G =32249398803413e+18420663759564i+31373921099158j;
1
2
3
Y=Y°Y°Y=15717771070652е+3791961142030i+6994965346759j.
1
4. Принимают ЭД, представленный, например, следующим МДЧ Н (в качестве которого может быть взята, в частности, хэш-функция от ЭД):
1
H=1578147.
1
2
3
5. Формируют ЭЦП Q в виде четырех БС е, s, s и s, для чего выполняют следующие действия:
5.1. Формируют первую БС е ЭЦП, для чего
1
2
3
5.1.1. Генерируют три случайных МДЧ t=16355233827, t=9315216313 и t=286572167.
1
2
3
tl
t2
t3
5.1.2. Генерируют вектор БС R, выполняя вычисления по формуле R=G °G °G :
1
1
t1
R=G =26476756850873e+8962083625688i+670851250270j;
2
2
t2
R=G =30556526925766e+28584458265015i+8838154755582j;
3
3
3
R=Gt=11801846609303e+18076196032752i+32080216656488j;
1
2
3
R=R°R°R=1034404417б952е+11648038573307i+33051212302586j.
1
2
3
1
1
3
5.1.3. Генерируют БС е в виде МДЧ, вычисляемого по формуле е=(r||r||r)Н mod δ, где δ - вспомогательное простое число, в качестве которого в данном примере берется МДЧ q, т.е. δ=q=2376581; r||r||r - МДЧ, равное конкатенации МДЧ, являющихся координатами вектора МДЧ R: е=665438.
1
2
3
1
1
1
2
2
2
3
3
3
5.2. Формируют вторую s, третью s и четвертую s БС ЭЦП в виде МДЧ, вычисляемых по формулам s=t-ke mod q, s=t-ke mod q и s=t-ke mod q:
1
2
3
s=56419; s=1472355; s=1213067.
6. Формируют первую проверочную БС А, для чего выполняются следующие действия.
e
s1
s2
s3
1
2
3
6.1. Генерируют вектор БС R', выполняя вычисления по формуле R'=Y°G °G °G :
e
Y=6474526780075е+26594658074693i+27807198777585j;
1
s1
G =4656659662651e+31668525221129i+9741922667955j;
e
s1
1
Y°G =279838485154e+5003268053125i+2342331071067j;
2
s2
G =13878539449612e+10268579457949i+25993200515657j;
3
s3
G =8522604164956e+3729385407205i+6316798018014j;
2
2
s2
s2
G °G =8522604164956e+3729385407205i+6316798018014j;
R'=10344044176952e+11648038573307i+33051212302586j.
2
3
1
1
2
3
-
6.2. Генерируют БС А в виде МДЧ, вычисляемого по формуле А=(r'||r||r)H mod q, где r'||r'||r' МДЧ, равное конкатенации МДЧ, являющихся координатами вектора МДЧ R': А=665438.
7. Формируют вторую проверочную БС В путем копирования БС е: В=е=665438.
8. Сравнивают первую и вторую проверочные БС: А=В. Совпадение проверочных БС подтверждает подлинность ЭЦП.
Частные примеры реализации заявленного способа, аналогичные описанным выше примерам 1-5, могут быть реализованы для случая использования вычислений над векторами БС, являющимися векторами многочленов. Выполнение операций сложения, умножения и деления многочленов, а также операций умножения и сложения по модулю неприводимого многочлена широко, описано в научно-технической литературе. Также широко представлена реализация конечных полей многочленов и основные их свойства (см. например книги [Курош А.Г. Курс высшей алгебры. - М., «Наука», 1971. - 431 с.], [Кострикин А.И. Введение в алгебру. Основы алгебры. - М.: Физматлит. 1994. - 320 с.], [А.Акритас. Основы компьютерной алгебры с приложениями. М.: Мир, 1994. - 544 с.] и [Л.Б.Шнеперман. Курс алгебры и теории чисел в задачах и упражнениях. - Минск, «Вышэйшая школа», 1986. - 272 с.]). Варианты построения конечных множеств векторов многочленов рассмотрены в работе [Молдовян НА. Группы векторов для алгоритмов электронной цифровой подписи // Вестник СПбГУ. Сер.10. 2008].
Приведенные выше примеры показывают принципиальную реализуемость и корректность заявленного способа формирования и проверки подлинности ЭЦП, заверяющей ЭД.
Приведенные выше примеры экспериментально подтверждают корректность реализации заявляемого способа, что дополняет приведенные выше математические доказательства корректности описанных конкретных реализаций заявленного способа формирования и проверки ЭЦП, заверяющей ЭД.
Таким образом, показано, что заявляемый способ может быть положен в основу стойких систем ЭЦП, обеспечивающих повышение производительности устройств и программ формирования и проверки ЭЦП.
Приведенные примеры и математическое обоснование показывают, что предлагаемый способ формирования и проверки подлинности ЭЦП работает корректно, технически реализуем и позволяет достичь сформулированного технического результата.
Приложение 1
Толкование терминов, используемых в описании заявки
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; результат выполнения операций сложения, вычитания и умножения по модулю n представляет собой число из этого же множества [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.]; операция возведения числа S в дискретную степень Z по модулю n определяется как 7-кратное последовательное умножение по модулю n числа S на себя, т.е. в результате этой операции также получается число W, которое меньше или равно числу n-1; даже для очень больших чисел S, Z и n существуют эффективные алгоритмы выполнения операции возведения в дискретную степень по модулю.
γ
1
2
12. Показатель q по модулю n числа а, являющегося взаимно простым с n, - это минимальное из чисел γ, для которых выполняется условие a mod n=1, т.е. q=min{γ, γ, …} [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.].
-1
13. Операция деления целого числа А на целое число В по модулю n выполняется как операция умножения по модулю n числа А на целое число B, которое является обратным к В по модулю n.
14. Порядок числа q по модулю n числа а - это показатель q по модулю n числа а.
15. Многочлен - это последовательность коэффициентов, например многоразрядных двоичных чисел (МДЧ). Над многочленами определены операции сложения многочленов и умножения многочленов, которые сводятся к выполнению действий с коэффициентами многочленов, являющихся операндами. Многочлены и правила действия над ними подробно рассмотрены в книгах [Кострикин А.И. Введение в алгебру. Основы алгебры. М.: Физматлит. 1994. - 320 с.] и [Курош А.Г. Курс высшей алгебры. - М., «Наука», 1971. - 431 с.]. В вычислительных устройствах многочлены представляются в виде битовой строки, в которой каждый бит или каждая подстрока битов фиксированной длины интерпретируется как один из коэффициентов многочлена, над которыми определены операции сложения и умножения коэффициентов.
16. Алгебраическая структура - это множество математических элементов некоторой природы. В качестве математических элементов могут выступать, например многочлены, МДЧ, пары МДЧ, пары многочленов, тройки МДЧ, тройки многочленов, матрицы МДЧ, матрицы многочленов и т.д., над которыми заданы математические действия (операции). Математически алгебраическая структура определяется путем задания конкретного множества математических элементов и одной или нескольких операций, выполняемых над элементами.
17. Элемент алгебраической структуры - это одна битовая строка или набор из нескольких битовых строк, над которыми определена алгебраическая операция. При определении конкретного типа алгебраической структуры определяются операции над элементами алгебраической структуры, которые указывают однозначно правила интерпретации и преобразования битовых строк, представляющих эти элементы. Реализуемые в вычислительных устройствах преобразования битовых строк соответствуют операциям, выполняемым над элементами заданной алгебраической структуры.
18. Группа - это алгебраическая структура (т.е. множество элементов различной природы), над элементами которой определена одна операция, и которая при заданной операции обладает заданным набором свойств: операция ассоциативна, результатом выполнения операции над двумя элементами является также элемент этой же структуры, существует нейтральный элемент такой, что при выполнении операции над ним и другим некоторым элементом а группы результатом является элемент а. Детальное описание групп дано в книгах [А.Г.Курош. Теория групп. - М., изд-во «Наука», 1967. - 648 с.] и [М.И.Каргаполов, Ю.И.Мерзляков. Основы теории групп. - М., изд-во «Наука. Физматлит», 1996. - 287 с.]. Операция, определенная над элементами группы, называется групповой операцией.
19. Кольцо - это алгебраическая структура (т.е. множество математических элементов природы), над элементами которой определены две операции, одна из которых называется сложением, а вторая - умножением. При этом при заданных операциях в эта алгебраическая структура обладает заданным набором свойств: операции сложения и умножения ассоциативны и коммутативны, операция умножения является дистрибутивной относительно операции сложения, а результатом выполнения каждой из этих операций над двумя элементами является также элемент этой же структуры. Кроме того, для сложения существует нейтральный элемент такой, что при выполнении операции над ним и другим некоторым элементом а группы результатом является элемент а. Нейтральный элемент относительно сложения называется нулевым элементом (или просто нулем). Детальное описание колец дано в книгах [Кострикин А.И. Введение в алгебру. Основы алгебры. М.: Физматлит.1994. - 320 с.] и [Курош А.Г. Курс высшей алгебры. - М., «Наука», 1971. - 431 с.].
-1
-1
-1
20. Поле - это алгебраическая структура (т.е. множество математических элементов различной природы), над элементами которой определены две операции, одна из которых называется сложением, а вторая - умножением. При этом при заданных операциях в эта алгебраическая структура обладает заданным набором свойств: операции сложения и умножения ассоциативны и коммутативны, операция умножения является дистрибутивной относительно операции сложения, а результатом выполнения каждой из этих операций над двумя элементами является также элемент этой же структуры. Причем для каждой из указанных двух операций существует нейтральный элемент такой, что при выполнении операции над ним и другим некоторым элементом а группы результатом является элемент а. Нейтральный элемент относительно сложения называется нулевым элементом (или просто нулем), а нейтральный элемент относительно умножения называется единичным элементом (или просто единицей). Кроме того, каждому ненулевому элементу а может быть сопоставлен в соответствие единственный элемент а, называемый обратным элементом по отношению к данному элементу, такой, что произведение аа (а значит и аa) равно единице. Детальное описание полей дано в книгах [А.И.Кострикин. Введение в алгебру. Основы алгебры. М.: Физматлит.1994. - 320 с.] и [Курош А.Г. Курс высшей алгебры. - М., «Наука», 1971. - 431 с.].
n
n
21. Циклическая группа - это группа, каждый элемент которой может быть представлен в виде g=а для некоторого натурального значения n, где а - элемент данной группы, называемый генератором или образующим элементом циклической группы. Степень n означает, что над элементом а выполняются n последовательных операций, т.е. выполняются вычисления по формуле а=a°a°а°…а (n раз), где «°» обозначает операцию, определенную над элементами группы.
n
22. Циклическая подгруппа группы - это подгруппа, каждый элемент g которой может быть представлен в виде g=а для некоторого натурального значения n, где а - элемент данной подгруппы, называющийся генератором или образующим элементом циклической подгруппы.
23. Вектор - это набор из двух или более элементов заданной алгебраической структуры, называемых компонентами вектора. Число элементов алгебраической структуры, над которым задан вектор, называется размерностью вектора.
1
2
m
1
2
1
2
1
2
24. Вектор битовых строк (вектор БС) - это набор из двух или более БС, каждая из которых представляет заданную алгебраическую структуру. Битовые строки называются координатами (или компонентами) вектора. Вектор БС записывается различными способами, требование к которым состоит в том, чтобы они идентифицировали позиции координат. Например, вектор БС можно записать в виде (a, а, …, a), где m≥2 - это размерность вектора БС, означающая число координат (компонентов) в векторе БС. В качестве разделителя может быть использован знак операции, определенной над координатами (компонентами) вектора, и тогда координаты (компоненты) вектора идентифицируются указанием формальной переменной (в начале или в конце соответствующего компонента) в виде буквы латинского алфавита. Формальной называется переменная потому, что ей не приписывается никакого численного значения и она служит только для того, чтобы идентифицировать конкретную позицию координаты (компоненты) вектора БС, независимо от последовательности его записи. Так вектора БС Z=ае+bi+сj и Z=bi+ае+cj рассматриваются как равные, т.е. Z=Z. При использовании некоторых частных таблиц замены переменных формальные переменные в литературе иногда называются базисными векторами, а вектора Z и Z - векторами m-мерного пространства [Л.Б.Шнеперман. Курс алгебры и теории чисел в задачах и упражнениях. - Минск, «Вышэйшая школа», 1986. - 272 с.].
25. Вектор многоразрядных двоичных чисел (вектора МДЧ) - это вектор БС, координатами которого являются МДЧ.
26. Размерность вектора БС - это количество БС, входящих в вектор БС в качестве координат.
27. Эллиптическая кривая (ЭК) - это совокупность пар МДЧ, которые удовлетворяют соотношению вида
2
3
у=х+ax+b mod p,
где коэффициенты а и b и модуль р определяют конкретный вариант ЭК. Над ЭК определены операция сложения пар МДЧ и операция умножения пары МДЧ на произвольное целое число. Указанные пары МДЧ записываются в виде (х, у), где х называется абсциссой точки, а у - ординатой. Операции, определенные над точками ЭК, выполняются как операции над координатами точек ЭК. В результате вычисляется пара МДЧ, которая является координатами новой точки, являющейся результатом операции. Точки ЭК называются равными, если равны их обе координаты х и у. Детальное описание ЭК можно найти в широко доступных книгах: [Б.Я.Рябко, А.Н.Фионов. Криптографические методы защиты информации. М., Горячая линия - Телеком, 2005. - 229 с. (см. с.97-130)].
A
A
B
B
28. Операция сложения двух точек А и В с координатами (х,у) и (х,у), соответственно, выполняется по формулам:
c
A
B
C
A
C
А
2
x=k-x-x mod p и y=k(x-x)-y mod p,
где , если точки А и В не равны, и , если точки А и В равны.
29. Операция умножения точки А на натуральное число n определяется как многократное сложение токи А:
nА=А+А+…+А (n раз).
Результатом умножения любой точки ЭК на нуль определяется точка, называемая бесконечно удаленной точкой и обозначаемой буквой О. Две точки А=(х, у) и -А=(х, -у) называются противоположными. Умножение на целое отрицательное число -n определяется следующим образом: (-n)А=n(-А). По определению принимают, что сумма двух противоположных точек равна бесконечно удаленной точке О [Б.Я.Рябко, А.Н.Фионов. Криптографические методы защиты информации. М., Горячая линия - Телеком, 2005. - 229 с. (см. с.97-130)].
30. Выполнение операций на точками ЭК осуществляется в вычислительных устройствах как действия над двоичными цифровыми электромагнитными сигналами, осуществляемыми по определенными правилам, определяемым через операции над МДЧ.
31. Порядком точки А ЭК называется наименьшее натуральное число q, такое что qA=О, т.е. такое, что результатом умножения точки А на число q является бесконечно удаленная точка.