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

1)
1)
Изобретение относится к области электросвязи и вычислительной техники, а конкретнее к области криптографических способов аутентификации электронных сообщений, передаваемых по телекоммуникационным сетям и сетям ЭВМ, и может быть использовано в системах передачи электронных сообщений (документов), заверенных электронной цифровой подписью (ЭЦП), представленной в виде многоразрядного двоичного числа (МДЧ). Здесь и далее под МДЧ понимается электромагнитный сигнал в двоичной цифровой форме, параметрами которого являются: число битов и порядок следования их единичных и нулевых значений( толкование используемых в описании терминов приведено в Приложении 1).
Известен способ формирования и проверки ЭЦП, предложенный в патенте США №4405829 от 20.09.1983 и детально описанный в книгах [1. М.А.Иванов. Криптография. М., КУДИЦ-ОБРАЗ, 2001; 2. А.Г.Ростовцев, Е.Б.Маховенко. Введение в криптографию с открытым ключом. С-Петербург, Мир и семья, 2001. - с.43]. Известный способ заключается в следующей последовательности действий:
формируют секретный ключ в виде трех простых МДЧ р, q и d, формируют открытый ключ (n, е) в виде пары МДЧ n и е, где n - число, представляющее собой произведение двух простых МДЧ р и q, и е - МДЧ, удовлетворяющее условию ed=1 mod (p-1)(q-1), принимают электронный документ, представленный МДЧ Н,
d
в зависимости от значения Н и значения секретного ключа формируют ЭЦП в виде МДЧ Q=S=Н mod n.
формируют первое проверочное МДЧ А=Н;
e
формируют второе проверочное МДЧ В, для чего МДЧ S возводят в целочисленную степень е по модулю n: В=S mod n,
сравнивают сформированные проверочные МДЧ А и В;
при совпадении параметров сравниваемых МДЧ А и В делают вывод о подлинности ЭЦП.
Недостатком известного способа является относительно большой размер подписи и необходимость увеличения размера подписи при разработке новых более эффективных методов разложения числа n на множители или при росте производительности современных вычислительных устройств. Это объясняется тем, что значение элемента подписи S вычисляются путем выполнения арифметических операций по модулю n, а стойкость ЭЦП определяется сложностью разложения модуля n на множители р и q.
Известен также способ формирования и проверки подлинности ЭЦП Эль-Гамаля, описанный в книге [Молдовян А.А., Молдовян Н.А., Советов Б.Я. Криптография. - СПб., Лань, 2000. - с.156-159], который включает следующие действия:
х
формируют простое МДЧ р и двоичное число G, являющееся первообразным корнем по модулю р, генерируют секретный ключ в виде МДЧ х, в зависимости от секретного ключа формируют открытый ключ в виде МДЧ Y=G mod р, принимают электронный документ (ЭД), представленный в виде МДЧ Н, в зависимости от Н и секретного ключа формируют ЭЦП Q в виде двух МДЧ S и R, то есть Q=(S,R);
осуществляют процедуру проверки подлинности ЭЦП, включающую вычисление двух контрольных параметров с использованием исходных МДЧ р, G, Y, H и S путем возведения МДЧ G, Y, R в дискретную степень по модулю р и сравнение вычисленных контрольных параметров;
при совпадении значений контрольных параметров делают вывод о подлинности ЭЦП.
Недостатком данного способа также является относительно большой размер ЭЦП. Это объясняется тем, что значения элементов подписи S и R вычисляют путем выполнения арифметических операций по модулю р-1 и по модулю p соответственно.
Наиболее близким по своей технической сущности к заявленному является известный способ формирования и проверки подлинности ЭЦП, предлагаемый российским стандартом ГОСТ Р 34.10-94 и описанный, например, в книге [Молдовян H.А. Практикум по криптосистемам с открытым ключом. - «БХВ-Петербург», Санкт-Петербург, 2007. - 298 с.; см. с.51-52]. Ближайший аналог (прототип) заключается в выполнении следующей последовательности действий:
формируют простое МДЧ p, такое что р=Nq+1, где q - простое МДЧ;
q
формируют простое МДЧ а, такое что а≠1 и a mod p=1;
методом генерации случайной равновероятной последовательности формируют секретный ключ в виде МДЧ х;
х
формируют открытый ключ в виде МДЧ y по формуле y=a mod p;
принимают электронный документ, представленный МДЧ H;
k
электронную цифровую подпись в виде пары многоразрядных двоичных чисел (R, S), для чего генерируют случайное МДЧ k, формируют МДЧ R по формуле R=(a mod р) mod q и формируют МДЧ S по формуле S=(kH+xR) mod q;
-1
-1
v
w
формируют первое проверочное МДЧ А, для чего генерируют МДЧ ν по формуле v=SH mod q и МДЧ w по формуле w=(q-RH) mod q, после чего МДЧ А определяют по формуле А=(аy mod p)mod q;
формируют второе проверочное МДЧ В путем копирования МДЧ R: B=R;
сравнивают сформированные проверочные МДЧ А и В;
при совпадении параметров сравниваемых МДЧ А и В делают вывод о подлинности ЭЦП.
Недостатком ближайшего аналога также является относительно большой размер МДЧ р, используемого в качестве модуля, по которому выполняют ряд операций возведения в степень. Для обеспечения требуемого уровня стойкости ЭЦП размер МДЧ p составляет 1024 бит и более.
Целью изобретения является разработка способа формирования и проверки подлинности ЭЦП, заверяющей ЭД, обеспечивающего уменьшение размера модуля без снижения уровня стойкости ЭЦП, благодаря чему уменьшается время, необходимое для формирования и проверки ЭЦП.
Поставленная цель достигается тем, что в известном способе формирования и проверки подлинности ЭЦП, заверяющей ЭД, заключающемся в том, что формируют МДЧ р, формируют секретный ключ, представляющий собой МДЧ х, по секретному ключу формируют открытый ключ в виде МДЧ y, принимают электронный документ, представленный МДЧ Н, в зависимости от значения Н и значения секретного ключа формируют электронную цифровую подпись в виде пары МДЧ (R, S), формируют первое А и второе В проверочные МДЧ, сравнивают их и при совпадении их параметров делают вывод о подлинности электронной цифровой подписи, открытый ключ формируют в виде МДЧ y путем возведения МДЧ х в степень z-разрядного двоичного числа k по модулю р, причем число z>16.
s
Новым является также то, что z-разрядное двоичное число k и модуль р являются простыми числами, такими, что для них выполняется соотношение p=Nk+1, где N и s - натуральные числа, причем N является четным, a s≥2.
s
Новым является также то, что z-разрядное двоичное число k является простым числом, а модуль р равен произведению двух МДЧ чисел q и r, причем q=Nk+1, где N и s - натуральные числа, причем N является четным, a s≥2.
k
R
k
p-R-1
Новым также является то, что для формирования электронной цифровой подписи генерируют случайное многоразрядное двоичное число t и промежуточное многоразрядное двоичное число Е=t mod p, а многоразрядное двоичное число R формируют по формуле R=EH mod δ, где δ - дополнительное простое многоразрядное двоичное число, а многоразрядное двоичное число S формируют по формуле S=xt mod p, причем первое проверочное многоразрядное двоичное число А формируют по формуле A=(Symod p)H mod δ, а второе проверочное многоразрядное двоичное число В формируют по формуле В=Е.
Благодаря новой совокупности существенных признаков путем изменения метода формирования открытого ключа и проверочных МДЧ достигается уменьшение размера модуля р, чем и обеспечивается уменьшение времени формирования и проверки ЭЦП при поддержании стойкости ЭЦП на заданном уровне, т.е. реализуется сформулированный технический результат.
2
80
Возможность реализации заявленного способа объясняется тем, что стойкость ЭЦП, формируемой по предложенному способу, основана на сложности задачи извлечения корней большой степени k по модулю р достаточно большого размера. В случае, когда число k делит значение r-1, где r является большим делителем числа р, сложность указанной задачи растет экспоненциально с ростом длины числа k. Благодаря этому достаточная стойкость ЭЦП, формируемой по предложенному способу, достигается при использовании модуля значительно меньшего размера по сравнению с известными способами. Сложность решения указанной задачи оценивается в Приложении 2, где показано, что она составляет  операций возведения в степень по модулю и зависит экспоненциально от длины . При  бит равна ≈2 операций, что соответствует минимально приемлемому уровню стойкости для систем ЭЦП, который достигается в предложенном способе при длине модуля р, равной  бит, что значительно меньше размера модуля в прототипе (1024), криптосистеме RSA (1024) и других способах-аналогах при таком же уровне криптостойкости.
Рассмотрим примеры реализации заявленного технического решения с искусственно уменьшенной разрядностью используемых чисел.
Пример 1. Реализации заявляемого способа с иллюстрацией конкретных численных значений.
Приводимые в примере МДЧ записаны для краткости в виде десятичных чисел, которые в вычислительных устройствах представляются и преобразуются в двоичном виде, т.е. в виде последовательности сигналов высокого и низкого потенциала. При формировании и проверке подлинности ЭЦП (подписью является пара чисел R и S) выполняют следующую последовательность действий.
2
1. Формируют простое число, такое что р-1 содержит квадрат большого простого числа k, т.е. р=Nk+1, где N - четное число:
р=4153476369892465269012870897623282390047400100719, где
k=132104433635297779312031;
N=238.
2. Формируют секретный ключ в виде случайного МДЧ
х=3526378981324543353612.
k
3. Формируют открытый ключ в виде МДЧ y по формуле y=x mod p:
y=3864858100219352940369774847788552018367055197706.
4. Принимают ЭД, представленный, например, следующим МДЧ Н (в качестве которого может быть взята, в частности, хэш-функция от ЭД):
Н=73568790119017231823457.
5. Формируют ЭЦП в виде пары чисел (R, S), для чего выполняют следующие действия:
5.1. Задают случайное число t=87193323415243553115136314;.
k
5.2. Формируют элемент подписи R путем выполнения операций, задаваемых формулой R=t mod p:
R=1965194394329054883669233593435354225553528543048.
5.3. Генерируют вспомогательное МДЧ Е по формуле Е=RH mod δ, где дополнительное простое МДЧ δ=35488784369499179:
E=30895498554403274.
E
5.4. Формируют элемент подписи S путем выполнения операций, задаваемых формулой S=xt mod p:
E
x mod p=4142896032174293277370541286118603008687412846512;
E
S=xt mod p=3459399960786475246293210038787580593601377527459.
k
6. Формируют первое проверочное МДЧ А по формуле А=S mod p:
А=1223628632990799695380329960945050775755031656237.
E
7. Формируют второе проверочное МДЧ В по формуле В=yR mod p:
E
y mod p=3723255340242797754117228676090833888172733014830;
E
В=yR mod p=1223628632990799695380329960945050775755031656237.
8. Сравнивают (например, поразрядно) параметры первого и второго проверочных МДЧ А и В. Сравнение показывает, что параметры МДЧ А и В совпадают, что указывает на подлинность ЭЦП, т.е. принятая ЭЦП относится к принятому ЭД, представленному МДЧ Н, и сформирована подписывающим, которому соответствует открытый ключ y, использованный в процедуре проверки подписи.
Это доказывается теоретически следующим образом. Для ЭЦП, сформированной с использованием правильного значения секретного ключа мы имеем:
т.е. для подписи, сформированной по секретному ключу, соответствующему открытому ключу, уравнение проверки подписи выполняется.
Пример 2. Генерация подписи сокращенного размера.
В данном примере генерируют ЭЦП, в которой один из элементов подписи (R,S) имеет уменьшенную длину, что позволяет сократить общий размер подписи.
2
1. Формируют простое число, такое что р-1 содержит квадрат большого простого числа k, т.е. р=Nk+1, где N - четное число:
р=4153476369892465269012870897623282390047400100719, где
k=132104433635297779312031;
N=238.
2. Формируют секретный ключ в виде случайного МДЧ
х=3526378981324543353612.
k
3. Формируют открытый ключ в виде МДЧ y по формуле y=х mod p:
y=3864858100219352940369774847788552018367055197706.
4. Принимают ЭД, представленный, например, следующим МДЧ Н (в качестве которого может быть взята, в частности, хэш-функция от ЭД):
H=73568790119017231823457.
5. Формируют ЭЦП в виде пары чисел (R,S) для чего выполняют следующие действия:
5.1. Задают случайное число t=87193323415243553115136314;.
k
5.2. Формируют вспомогательное число Е путем выполнения операций, задаваемых формулой E=t mod р:
Е=1965194394329054883669233593435354225553528543048.
5.4. Генерируют первый элемент ЭЦП в виде МДЧ R по формуле R=EH mod δ, где дополнительное простое число δ=35488784369499179:
R=EH mod δ=30895498554403274.
R
5.5. Формируют элемент подписи S путем выполнения операций, задаваемых формулой S=хt mod p:
R
x mod p=4142896032174293277370541286118603008687412846512;
R
S=х mod p=3459399960786475246293210038787580593601377527459.
k
p-R-1
6. Формируют первое проверочное МДЧ А по формуле А=(Sy mod p)H mod δ:
k
S mod р=1223628632990799695380329960945050775755031656237;
p-R-1 mod p-1=4153476369892465269012870897623251494548845697444;
p-R-1
y mod p=3940798203474215574106281018935399640248176139523;
k
p-R-1
E'=Symod p mod p= 1965194394329054883669233593435354225553528543048;
R'=E'H mod δ=30895498554403274.
7. Формируют второе проверочное МДЧ В по формуле B=R: В=R=30895498554403274.
8. Сравнивают (например, поразрядно) параметры первого и второго проверочных МДЧ А и В. Сравнение показывает, что параметры МДЧ А и В совпадают, что указывает на подлинность ЭЦП, т.е. принятая ЭЦП относится к принятому ЭД, представленному МДЧ Н, и сформирована подписывающим, которому соответствует принятый открытый ключ y.
Пример 3. Реализация заявляемого способа при использовании составного модуля.
Данный пример соответствует случаю составного модуля р=qr. Подписью является пара чисел R и S.
2
1. Формируют МДЧ р=15013595620933879012057057, такое что р содержит два больших простых делителя в виде МДЧ q=29921300821 и МДЧ r=501769482241117, где МДЧ r таково, что r-1 содержит квадрат большого простого числа k=1063067, т.е. r=Nk+1, где N=444 - четное число.
2. Формируют секретный ключ в виде случайного МДЧ х=6378981324543353612.
k
3. Формируют открытый ключ в виде МДЧ y по формуле y=х mod p:
k
y=х mod n=10983244071107369182920432.
4. Принимают ЭД, представленный, например, следующим МДЧ Н (в качестве которого может быть взята, в частности, хэш-функция от ЭД):
H=79019121235271.
5. Формируют ЭЦП в виде пары чисел (R,S) для чего выполняют следующие действия:
5.1. Задают случайное число t=8111342447574758314.
k
5.2. Формируют элемент подписи R путем выполнения операций, задаваемых формулой R=t mod p: R=154116794935359048626511.
5.4. Генерируют вспомогательное МДЧ Е по формуле Е=RH mod δ, где дополнительное простое МДЧ δ равно δ=35488784369499179:
E=27953322255219686.
E
5.5. Формируют элемент подписи S путем выполнения операций, задаваемых формулой S=xt mod p:
E
x mod p=1764312689474103465183543;
E
S=xt mod p=4903410267140570698301425.
k
6. Формируют первое проверочное МДЧ А по формуле А=S mod p:
A=5029317151545311958198952.
E
7. Формируют второе проверочное МДЧ В по формуле В=yR mod p:
E
y mod p=1306126429688415107035604;
E
B=yR mod p=5029317151545311958198952.
8. Сравнивают (например, поразрядно) параметры первого и второго проверочных МДЧ А и В. Сравнение показывает, что параметры МДЧ А и В совпадают, что указывает на подлинность ЭЦП, т.е. принятая ЭЦП относится к принятому ЭД, представленному МДЧ Н, и сформирована подписывающим, которому соответствует принятый открытый ключ y.
Пример 4. Реализации заявляемого способа в случае значения s=3.
При формировании и проверке подлинности ЭЦП, представленной парой чисел R и S, выполняют следующую последовательность действий.
3
1. Формируют простое число, такое что р-1 содержит третью степень большого простого числа k, т.е. р=Nk+1, где N - четное число:
p=46158524389138903787140956692911043, где
k=284713006241;
N=2.
2. Формируют секретный ключ в виде случайного МДЧ
х=1354353612.
k
3. Формируют открытый ключ в виде МДЧ y по формуле y=х mod p:
y=15250253342985101891087107362337409.
4. Принимают ЭД, представленный, например, следующим МДЧ Н (в качестве которого может быть взята, в частности, хэш-функция от ЭД):
Н=367910135.
5. Формируют ЭЦП в виде пары чисел (R,S), для чего выполняют следующие действия:
5.1. Задают случайное число t=31235133;.
k
5.2. Формируют элемент подписи R путем выполнения операций, задаваемых формулой R=t mod p:
R=23157705938909511105394314605753824.
5.3. Генерируют вспомогательное МДЧ Е по формуле Е=RH mod δ, где дополнительное простое число δ=354839919:
Е=RH mod δ=291762596.
E
5.4. Формируют элемент подписи S путем выполнения операций, задаваемых формулой S=xt mod p:
E
x mod p=25993534131735435651913144295817098;
E
S=xt mod p=38076817738901233006171796144597858.
k
6. Формируют первое проверочное МДЧ А по формуле А=S mod p:
A=40480831299574768063189406647049319.
E
7. Формируют второе проверочное МДЧ В по формуле В=yR mod p:
E
y mod p=25993534131735435651913144295817098;
E
В=yR mod p=40480831299574768063189406647049319.
8. Сравнивают (например, поразрядно) параметры первого и второго проверочных МДЧ А и В.
Сравнение показывает, что параметры МДЧ А и В совпадают. Совпадение значений А и В означает, что ЭЦП является подлинной, т.е. относится к принятому ЭД, представленному МДЧ Н, и сформирована подписывающим, которому соответствует принятый открытый ключ. Это доказывается теоретически.
Таким образом, показано, что заявляемый способ может быть положен в основу стойких систем ЭЦП, обеспечивающих уменьшение размера модуля, по которому выполняются операции над МДЧ, благодаря чему сокращается время формирования и проверки ЭЦП.
Приведенные пример и математическое обоснование показывают, что предлагаемый способ формирования и проверки подлинности электронной цифровой подписи работает корректно, технически реализуем и позволяет решить поставленную задачу.
Приложение 1
Толкование терминов, используемых в описании заявки
1. Двоичный цифровой электромагнитный сигнал - последовательность битов в виде нулей и единиц.
2. Параметры двоичного цифрового электромагнитного сигнала: разрядность и порядок следования единичных и нулевых битов.
3. Разрядность двоичного цифрового электромагнитного сигнала - общее число его единичных и нулевых битов, например число 10011 является 5-разрядным.
4. Электронная цифровая подпись (ЭЦП) - двоичный цифровой электромагнитный сигнал, параметры которого зависят от подписанного электронного документа и от секретного ключа. Проверка подлинности ЭЦП осуществляют с помощью открытого ключа, который зависит от секретного ключа.
5. Электронный документ (ЭД) - двоичный цифровой электромагнитный сигнал, параметры которого зависят от исходного документа и способа его преобразования к электронному виду.
6. Секретный ключ - двоичный цифровой электромагнитный сигнал, используемый для формирования подписи к заданному электронному документу. Секретный ключ представляется, например, в двоичном виде как последовательность цифр «0» и «1».
7. Открытый ключ - двоичный цифровой электромагнитный сигнал, параметры которого зависят от секретного ключа и который предназначен для проверки подлинности цифровой электронной подписи.
8. Хэш-функция от электронного документа - двоичный цифровой электромагнитный сигнал, параметры которого зависят от электронного документа и выбранного метода ее вычисления.
9. Многоразрядное двоичное число - двоичный цифровой электромагнитный сигнал, интерпретируемый как двоичное число и представляемый в виде последовательности цифр «0» и «1».
Z
10. Операция возведения числа S в дискретную степень А по модулю n - это операция, выполняемая над конечным множеством натуральных чисел {0, 1, 2, …, n-1}, включающим n чисел, являющихся остатками от деления всевозможных целых чисел на число n; результат выполнения операций сложения, вычитания и умножения по модулю n представляет собой число из этого же множества [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.]; операция возведения числа S в дискретную степень Z по модулю n определяется как Z-кратное последовательное умножение по модулю n числа S на себя, т.е. в результате этой операции также получается число W, которое меньше или равно числу n-1; даже для очень больших чисел S, Z и n существуют эффективные алгоритмы выполнения операции возведения в дискретную степень по модулю [см. Молдовян А.А., Молдовян Н.А., Гуц Н.Д., Изотов Б.В. Криптография: скоростные шифры. - СПб., БХВ-Петербург, 2002. - с.58-61 или Б.Шнайер. Прикладная криптография. - М., изд-во «Триумф», 2002. - с.278-280] и электронные устройства, осуществляющие эту операцию с большой скоростью [У.Диффи. Первые десять лет криптографии с открытым ключом // ТИИЭР. 1988. т.76. №5. с.67-68]; выполнение операции возведения числа S в дискретную степень Z по модулю n обозначается как W=Smod n, где W - число, являющееся результатом выполнения данной операции.
11. Функция Эйлера от натурального числа n - это число чисел, являющихся взаимно простыми с n и не превосходящими n [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.; Бухштаб А.А. Теория чисел. - М.: Просвещение, 1966. - 384 с].
γ
1
2
12. Показатель q по модулю n числа а, являющегося взаимно простым с n - это минимальное из чисел γ, для которых выполняется условие amod n=1, т.е. q=min{γ, γ, …} [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.].
13. Порядок числа q по модулю n числа а - это показатель q по модулю n числа а.
14. Первообразный корень - это число, относящееся к показателю, который равен функции Эйлера от модуля.
-1
-1
15. Обратный элемент по модулю n к числу а, являющемуся взаимно простым с n, есть натуральное число, обозначаемое как а, для которого выполняется условие аа=1; для любого числа, являющегося взаимно простым с модулем, существует элемент, обратный этому числу. Известны эффективные алгоритмы вычисления обратных элементов [Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. - М., Радио и связь. - с.308-310].
-1
16. Операция деления целого числа А на целое число В по модулю n выполняется как операция умножения по модулю n числа А на целое число B, которое является обратным к В по модулю n.
Приложение 2
2
Оценка сложности, вычисление корней степени k по простому модулю p=Nk+1
В предложенном ниже методе решения этой задачи и оценке его вычислительной сложности использованы некоторые результаты, следующие из трех известных фактов.
j
1. Существуют  различных вычетов а степени k (j=1, 2, …, ).
2. Для любого вычета а степени k имеем: .
i
3. Для некоторого невычета b имеем:
где  и i=1, 2, …, k-1.
i
ij
ij
ij'
j
ij'
Из этих фактов следует, что каждому корню е соответствует ровно  различных значений b, где j=1, 2, …, , таких что . Действительно, пусть для b и b выполняется . Тогда имеем: , т.~е. отношение  есть вычет степени k по модулю p. Поскольку существует ровно  различных вычетов a, то существует ровно столько же различных значений b. Поэтому для случайного значения t имеют место следующие вероятности:
1
1
k-1
р
1
i
для всех i=1, 2, …, k-1. Пусть выбран случайный вычет а. Очевидно, что значение  принадлежит множеству {е, е, …, e, 1}. Число степенных вычетов а, для которых имеем  равно значению , где # обозначает мощность множества {*} и ω(а) обозначает порядок числа а по модулю р. Число вычетов, для которых имеем , равно . Известно [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.], что  и , где φ(N) - значение функции Эйлера от числа N, следовательно Z=N и . Получаем, что вероятность  пренебрежимо мала и с вероятностью  мы имеем , где e - некоторый корень из единицы, не равный 1.
Учитывая, что для каждого i существует некоторый i', такой что , можно записать , поэтому для некоторого невычета b имеем:
Если сравнение (1) выполняется, то можно легко вычислить . Действительно, сравнение (1) можно представить в виде
-1
где с достаточно высокой вероятностью имеем наибольший общий делитель НОД (k-N, p-1)=1 (в противном случае задача несколько усложнится, так как потребуется дополнительно вычислить корень сравнительно малой степени, однако в целом ее решение не будет сложным). В рассматриваемом случае можно вычислить значение N'=(k-N) mod p-1 и затем
N'
NN'
i
j
Сравнение (3) показывает, что величина ab mod p есть один из корней . Вопрос состоит в нахождении невычета b, удовлетворяющего сравнению (1). Заметим, что значение b может быть представлено в виде , где b и b - некоторые невычеты. Действительно, любой корень из единицы можно представить в виде произведения двух других корней из единицы, поэтому имеем:
i
j
Следующий алгоритм позволяет с достаточно высокой вероятностью найти значения b и b, удовлетворяющие сравнению (4).
i
i
1. Выбрать случайное значение b. Вычислить и сохранить в гипотетической таблице 1 значения b и  для i=1, 2, …, , где  и [*] обозначает целую часть значения* (сложность этого шага составляет примерно  операций модульного экспоненциирования).
j
j
2. Выбрать случайное значение b. Вычислить и сохранить в гипотетической таблице 2 значения b и  для j=1, 2, …,  (сложность этого шага составляет примерно  операций модульного экспоненциирования).
3. Упорядочить таблицу 1 Сложность этого шага составляет примерно
операций сравнения,  обозначает битовую длину числа k).
i0
j
4. Для j=1, 2, …,  проверить, если в таблице 1 содержится значение А=В (сложность этого шага составляет примерно  операций сравнения).
i
j
i
j
i
j
i0
i0
i0
j0
-1
Для случайно выбранных b и b имеем Рr(A=B)=k, поэтому в таблицах 1 и 2, содержащих по количеству значений b и b соответственно, с вероятностью ≈0.5 имеется пара равных значений А и В (парадокс дней рождения) [см. A.J.Menezes, P.C.Van Oorschot, and S.A.Vanstone. Handbook of Applied Cryptography. CRC Press, Boca Raton, FL, 1997; или Pieprzyk J., Hardjono Th., and Seberry J. Fundamentals of Computer Security. Springer-Verlag. Berlin, 2003. - 677 p.]. Таким образом, с вероятностью ≈0.5 алгоритм находит невычеты bи b, удовлетворяющие сравнению (4).
i0
j0
80
Далее вычисляем невычет b=bb mod p, удовлетворяющий сравнению (1) и затем вычисляем . Выполняя описанный алгоритм m раз, где m - небольшое число, мы с вероятностью, близкой к 1, вычислим значение z. Сложность алгоритма составляет  операций экспоненциирования по модулю. Таким образом, сложность процедуры вычисления z зависит экспоненциально от длины  и при  бит равна ≈2 операций, что соответствует минимальному приемлемому уровню стойкости для систем ЭЦП.