способ формирования и проверки подлинности электронной цифровой подписи, заверяющей электронный документ

Формула изобретения

1. Способ генерации и проверки подлинности электронной цифровой подписи, заверяющей электронный документ, заключающийся в том, что формируют многоразрядное двоичное число р, формируют секретный ключ, представляющий собой многоразрядное двоичное число х, по секретному ключу формируют открытый ключ в виде многоразрядного двоичного числа у, принимают электронный документ, представленный многоразрядным двоичным числом Н, в зависимости от значения Н и значения секретного ключа формируют электронную цифровую подпись в виде пары многоразрядных двоичных чисел (R, S), формируют первое А и второе В проверочные многоразрядные двоичные числа, сравнивают их и при совпадении их параметров делают вывод о подлинности электронной цифровой подписи, отличающийся тем, что открытый ключ формируют в виде многоразрядного двоичного числа у путем возведения многоразрядного двоичного числа х в степень z-разрядного двоичного числа k по модулю р, причем число z>16, для формирования электронной цифровой подписи генерируют случайное многоразрядное двоичное число t и промежуточное многоразрядное двоичное число Е=t^k mod р, а многоразрядное двоичное число R формируют по формуле R=EH mod , где - дополнительное простое многоразрядное двоичное число, после чего формируют многоразрядное двоичное число S=x^R t mod р, при этом первое проверочное многоразрядное двоичное число А формируют по формуле A=(S^ky^p-R-1 mod p)H mod , а второе проверочное многоразрядное двоичное число В формируют по формуле B=R.

2. Способ по п.1, отличающийся тем, что z-разрядное двоичное число k и модуль р являются простыми числами, такими, что для них выполняется соотношение p=Nk ^s+1, где N и s - натуральные числа, причем N является четным, a s 2.

3. Способ по п.1, отличающийся тем, что z-разрядное двоичное число k является простым числом, а модуль р равен произведению двух простых многоразрядных двоичных чисел q и r, причем q=Nk ^s+1, где N и s - натуральные числа, причем N является четным, a s 2.

Описание изобретения к патенту

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

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

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

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

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

формируют второе проверочное МДЧ В, для чего МДЧ S возводят в целочисленную степень е по модулю n: В=S ^e 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 - простое МДЧ;

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

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

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

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

электронную цифровую подпись в виде пары многоразрядных двоичных чисел (R, S), для чего генерируют случайное МДЧ k, формируют МДЧ R по формуле R=(a^k mod р) mod q и формируют МДЧ S по формуле S=(kH+xR) mod q;

формируют первое проверочное МДЧ А, для чего генерируют МДЧ по формуле v=SH^-1 mod q и МДЧ w по формуле w=(q-RH^-1) mod q, после чего МДЧ А определяют по формуле А=(а^vy^w mod p)mod q;

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

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

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

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

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

Поставленная цель достигается тем, что в известном способе формирования и проверки подлинности ЭЦП, заверяющей ЭД, заключающемся в том, что формируют МДЧ р, формируют секретный ключ, представляющий собой МДЧ х, по секретному ключу формируют открытый ключ в виде МДЧ y, принимают электронный документ, представленный МДЧ Н, в зависимости от значения Н и значения секретного ключа формируют электронную цифровую подпись в виде пары МДЧ (R, S), формируют первое А и второе В проверочные МДЧ, сравнивают их и при совпадении их параметров делают вывод о подлинности электронной цифровой подписи, открытый ключ формируют в виде МДЧ y путем возведения МДЧ х в степень z-разрядного двоичного числа k по модулю р, причем число z>16.

Новым является также то, что z-разрядное двоичное число k и модуль р являются простыми числами, такими, что для них выполняется соотношение p=Nk^s+1, где N и s - натуральные числа, причем N является четным, a s 2.

Новым является также то, что z-разрядное двоичное число k является простым числом, а модуль р равен произведению двух МДЧ чисел q и r, причем q=Nk^s+1, где N и s - натуральные числа, причем N является четным, a s 2.

Новым также является то, что для формирования электронной цифровой подписи генерируют случайное многоразрядное двоичное число t и промежуточное многоразрядное двоичное число Е=t^k mod p, а многоразрядное двоичное число R формируют по формуле R=EH mod , где - дополнительное простое многоразрядное двоичное число, а многоразрядное двоичное число S формируют по формуле S=x ^Rt mod p, причем первое проверочное многоразрядное двоичное число А формируют по формуле A=(S^ky^p-R-1 mod p)H mod , а второе проверочное многоразрядное двоичное число В формируют по формуле В=Е.

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

Возможность реализации заявленного способа объясняется тем, что стойкость ЭЦП, формируемой по предложенному способу, основана на сложности задачи извлечения корней большой степени k по модулю р достаточно большого размера. В случае, когда число k² делит значение r-1, где r является большим делителем числа р, сложность указанной задачи растет экспоненциально с ростом длины числа k. Благодаря этому достаточная стойкость ЭЦП, формируемой по предложенному способу, достигается при использовании модуля значительно меньшего размера по сравнению с известными способами. Сложность решения указанной задачи оценивается в Приложении 2, где показано, что она составляет операций возведения в степень по модулю и зависит экспоненциально от длины . При бит равна 2⁸⁰ операций, что соответствует минимально приемлемому уровню стойкости для систем ЭЦП, который достигается в предложенном способе при длине модуля р, равной бит, что значительно меньше размера модуля в прототипе (1024), криптосистеме RSA (1024) и других способах-аналогах при таком же уровне криптостойкости.

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

Пример 1. Реализации заявляемого способа с иллюстрацией конкретных численных значений.

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

1. Формируют простое число, такое что р-1 содержит квадрат большого простого числа k, т.е. р=Nk²+1, где N - четное число:

р=4153476369892465269012870897623282390047400100719, где

k=132104433635297779312031;

N=238.

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

х=3526378981324543353612.

3. Формируют открытый ключ в виде МДЧ y по формуле y=x^k mod p:

y=3864858100219352940369774847788552018367055197706.

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

Н=73568790119017231823457.

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

5.1. Задают случайное число t=87193323415243553115136314;.

5.2. Формируют элемент подписи R путем выполнения операций, задаваемых формулой R=t^k mod p:

R=1965194394329054883669233593435354225553528543048.

5.3. Генерируют вспомогательное МДЧ Е по формуле Е=RH mod , где дополнительное простое МДЧ =35488784369499179:

E=30895498554403274.

5.4. Формируют элемент подписи S путем выполнения операций, задаваемых формулой S=x^Et mod p:

x^E mod p=4142896032174293277370541286118603008687412846512;

S=x^Et mod p=3459399960786475246293210038787580593601377527459.

6. Формируют первое проверочное МДЧ А по формуле А=S^k mod p:

А=1223628632990799695380329960945050775755031656237.

7. Формируют второе проверочное МДЧ В по формуле В=y^ER mod p:

y^E mod p=3723255340242797754117228676090833888172733014830;

В=y^ER mod p=1223628632990799695380329960945050775755031656237.

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

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

т.е. для подписи, сформированной по секретному ключу, соответствующему открытому ключу, уравнение проверки подписи выполняется.

Пример 2. Генерация подписи сокращенного размера.

В данном примере генерируют ЭЦП, в которой один из элементов подписи (R,S) имеет уменьшенную длину, что позволяет сократить общий размер подписи.

1. Формируют простое число, такое что р-1 содержит квадрат большого простого числа k, т.е. р=Nk²+1, где N - четное число:

р=4153476369892465269012870897623282390047400100719, где

k=132104433635297779312031;

N=238.

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

х=3526378981324543353612.

3. Формируют открытый ключ в виде МДЧ y по формуле y=х^k mod p:

y=3864858100219352940369774847788552018367055197706.

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

H=73568790119017231823457.

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

5.1. Задают случайное число t=87193323415243553115136314;.

5.2. Формируют вспомогательное число Е путем выполнения операций, задаваемых формулой E=t^k mod р:

Е=1965194394329054883669233593435354225553528543048.

5.4. Генерируют первый элемент ЭЦП в виде МДЧ R по формуле R=EH mod , где дополнительное простое число =35488784369499179:

R=EH mod =30895498554403274.

5.5. Формируют элемент подписи S путем выполнения операций, задаваемых формулой S=х ^Rt mod p:

x^R mod p=4142896032174293277370541286118603008687412846512;

S=х^R mod p=3459399960786475246293210038787580593601377527459.

6. Формируют первое проверочное МДЧ А по формуле А=(S^ky^p-R-1 mod p)H mod :

S^k mod р=1223628632990799695380329960945050775755031656237;

p-R-1 mod p-1=4153476369892465269012870897623251494548845697444;

y^p-R-1 mod p=3940798203474215574106281018935399640248176139523;

E'=S^ky^p-R-1 mod p mod p= 1965194394329054883669233593435354225553528543048;

R'=E'H mod =30895498554403274.

7. Формируют второе проверочное МДЧ В по формуле B=R: В=R=30895498554403274.

8. Сравнивают (например, поразрядно) параметры первого и второго проверочных МДЧ А и В. Сравнение показывает, что параметры МДЧ А и В совпадают, что указывает на подлинность ЭЦП, т.е. принятая ЭЦП относится к принятому ЭД, представленному МДЧ Н, и сформирована подписывающим, которому соответствует принятый открытый ключ y.

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

Данный пример соответствует случаю составного модуля р=qr. Подписью является пара чисел R и S.

1. Формируют МДЧ р=15013595620933879012057057, такое что р содержит два больших простых делителя в виде МДЧ q=29921300821 и МДЧ r=501769482241117, где МДЧ r таково, что r-1 содержит квадрат большого простого числа k=1063067, т.е. r=Nk²+1, где N=444 - четное число.

2. Формируют секретный ключ в виде случайного МДЧ х=6378981324543353612.

3. Формируют открытый ключ в виде МДЧ y по формуле y=х^k mod p:

y=х^k mod n=10983244071107369182920432.

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

H=79019121235271.

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

5.1. Задают случайное число t=8111342447574758314.

5.2. Формируют элемент подписи R путем выполнения операций, задаваемых формулой R=t^k mod p: R=154116794935359048626511.

5.4. Генерируют вспомогательное МДЧ Е по формуле Е=RH mod , где дополнительное простое МДЧ равно =35488784369499179:

E=27953322255219686.

5.5. Формируют элемент подписи S путем выполнения операций, задаваемых формулой S=x^Et mod p:

x^E mod p=1764312689474103465183543;

S=x^Et mod p=4903410267140570698301425.

6. Формируют первое проверочное МДЧ А по формуле А=S^k mod p:

A=5029317151545311958198952.

7. Формируют второе проверочное МДЧ В по формуле В=y^E R mod p:

y^E mod p=1306126429688415107035604;

B=y^ER mod p=5029317151545311958198952.

8. Сравнивают (например, поразрядно) параметры первого и второго проверочных МДЧ А и В. Сравнение показывает, что параметры МДЧ А и В совпадают, что указывает на подлинность ЭЦП, т.е. принятая ЭЦП относится к принятому ЭД, представленному МДЧ Н, и сформирована подписывающим, которому соответствует принятый открытый ключ y.

Пример 4. Реализации заявляемого способа в случае значения s=3.

При формировании и проверке подлинности ЭЦП, представленной парой чисел R и S, выполняют следующую последовательность действий.

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

p=46158524389138903787140956692911043, где

k=284713006241;

N=2.

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

х=1354353612.

3. Формируют открытый ключ в виде МДЧ y по формуле y=х^k mod p:

y=15250253342985101891087107362337409.

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

Н=367910135.

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

5.1. Задают случайное число t=31235133;.

5.2. Формируют элемент подписи R путем выполнения операций, задаваемых формулой R=t^k mod p:

R=23157705938909511105394314605753824.

5.3. Генерируют вспомогательное МДЧ Е по формуле Е=RH mod , где дополнительное простое число =354839919:

Е=RH mod =291762596.

5.4. Формируют элемент подписи S путем выполнения операций, задаваемых формулой S=x^E t mod p:

x^E mod p=25993534131735435651913144295817098;

S=x^Et mod p=38076817738901233006171796144597858.

6. Формируют первое проверочное МДЧ А по формуле А=S^k mod p:

A=40480831299574768063189406647049319.

7. Формируют второе проверочное МДЧ В по формуле В=y^ER mod p:

y^E mod p=25993534131735435651913144295817098;

В=y^ER mod p=40480831299574768063189406647049319.

8. Сравнивают (например, поразрядно) параметры первого и второго проверочных МДЧ А и В.

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

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

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

Приложение 1

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

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

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

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

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

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

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

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

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

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

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=S^Z mod n, где W - число, являющееся результатом выполнения данной операции.

11. Функция Эйлера от натурального числа n - это число чисел, являющихся взаимно простыми с n и не превосходящими n [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.; Бухштаб А.А. Теория чисел. - М.: Просвещение, 1966. - 384 с].

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

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

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

15. Обратный элемент по модулю n к числу а, являющемуся взаимно простым с n, есть натуральное число, обозначаемое как а^-1, для которого выполняется условие а^-1а=1; для любого числа, являющегося взаимно простым с модулем, существует элемент, обратный этому числу. Известны эффективные алгоритмы вычисления обратных элементов [Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. - М., Радио и связь. - с.308-310].

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

Приложение 2

Оценка сложности, вычисление корней степени k по простому модулю p=Nk²+1

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

1. Существуют различных вычетов а_j степени k (j=1, 2, , ).

2. Для любого вычета а степени k имеем: .

3. Для некоторого невычета b_i имеем:

где и i=1, 2, , k-1.

Из этих фактов следует, что каждому корню е_i соответствует ровно различных значений b_ij, где j=1, 2, , , таких что . Действительно, пусть для b_ij и b_ij' выполняется . Тогда имеем: , т.~е. отношение есть вычет степени k по модулю p. Поскольку существует ровно различных вычетов a_j, то существует ровно столько же различных значений b_ij'. Поэтому для случайного значения t имеют место следующие вероятности:

для всех i=1, 2, , k-1. Пусть выбран случайный вычет а. Очевидно, что значение принадлежит множеству {е₁, е₁, , e_k-1, 1}. Число степенных вычетов а, для которых имеем равно значению , где # обозначает мощность множества {*} и _р(а) обозначает порядок числа а по модулю р. Число вычетов, для которых имеем , равно . Известно [Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 167 с.], что и , где (N) - значение функции Эйлера от числа N, следовательно Z₁=N и . Получаем, что вероятность пренебрежимо мала и с вероятностью мы имеем , где e_i - некоторый корень из единицы, не равный 1.

Учитывая, что для каждого i существует некоторый i', такой что , можно записать , поэтому для некоторого невычета b имеем:

Если сравнение (1) выполняется, то можно легко вычислить . Действительно, сравнение (1) можно представить в виде

где с достаточно высокой вероятностью имеем наибольший общий делитель НОД (k-N, p-1)=1 (в противном случае задача несколько усложнится, так как потребуется дополнительно вычислить корень сравнительно малой степени, однако в целом ее решение не будет сложным). В рассматриваемом случае можно вычислить значение N'=(k-N)^-1 mod p-1 и затем

Сравнение (3) показывает, что величина a^N'b^NN' mod p есть один из корней . Вопрос состоит в нахождении невычета b, удовлетворяющего сравнению (1). Заметим, что значение b может быть представлено в виде , где b_i и b_j - некоторые невычеты. Действительно, любой корень из единицы можно представить в виде произведения двух других корней из единицы, поэтому имеем:

Следующий алгоритм позволяет с достаточно высокой вероятностью найти значения b_i и b_j , удовлетворяющие сравнению (4).

1. Выбрать случайное значение b_i. Вычислить и сохранить в гипотетической таблице 1 значения b_i и для i=1, 2, , , где и [*] обозначает целую часть значения* (сложность этого шага составляет примерно операций модульного экспоненциирования).

2. Выбрать случайное значение b_j. Вычислить и сохранить в гипотетической таблице 2 значения b_j и для j=1, 2, , (сложность этого шага составляет примерно операций модульного экспоненциирования).

3. Упорядочить таблицу 1 Сложность этого шага составляет примерно

операций сравнения, обозначает битовую длину числа k).

4. Для j=1, 2, , проверить, если в таблице 1 содержится значение А _i0=В_j (сложность этого шага составляет примерно операций сравнения).

Для случайно выбранных b_i и b_j имеем Рr(A_i=B_j )=k^-1, поэтому в таблицах 1 и 2, содержащих по количеству значений b_i и b_j соответственно, с вероятностью 0.5 имеется пара равных значений А_i0 и В _i0 (парадокс дней рождения) [см. 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_i0 и b_j0 , удовлетворяющие сравнению (4).

Далее вычисляем невычет b=b_i0b_j0 mod p, удовлетворяющий сравнению (1) и затем вычисляем . Выполняя описанный алгоритм m раз, где m - небольшое число, мы с вероятностью, близкой к 1, вычислим значение z. Сложность алгоритма составляет операций экспоненциирования по модулю. Таким образом, сложность процедуры вычисления z зависит экспоненциально от длины и при бит равна 2⁸⁰ операций, что соответствует минимальному приемлемому уровню стойкости для систем ЭЦП.