Патент на изобретение №2280896

(54) СПОСОБ ПРОВЕРКИ ПОДЛИННОСТИ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ, ЗАВЕРЯЮЩЕЙ ЭЛЕКТРОННЫЙ ДОКУМЕНТ

(57) Реферат:

Изобретение относится к области электросвязи, а именно к области криптографических устройств и способов проверки электронной цифровой подписи (ЭЦП). Техническим результатом, достигаемым в заявленном способе, является снижение вероятности несанкционированного формирования ЭЦП (“ложного” подтверждения подлинности ЭЦП) в системах электронной цифровой подписи. Способ проверки ЭЦП включает следующую последовательность действий: прием электронного документа (ЭД) в виде многоразрядного двоичного числа Н, открытого ключа в виде первого g-разрядного и второго f-разрядного двоичных чисел n и и электронную цифровую подпись в виде многоразрядного двоичного числа S; формирование проверочного многоразрядного двоичного числа В путем возведения ЭЦП в степень Н по модулю n; сравнение двоичных чисел В и . При их совпадении делают вывод о подлинности ЭЦП.

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

Известен способ проверки ЭЦП, описанный в книге [Иванов М.А. Криптография. М., КУДИЦ-ОБРАЗ, 2001. – C.189-191]. Известный способ заключается в следующей последовательности действий:

принимают электронный документ (ЭД), представленный в виде многоразрядного двоичного числа Н, открытый ключ в виде многоразрядного двоичного числа Y, ЭЦП в виде двух многоразрядных двоичных чисел s и r, простые многоразрядные двоичные числа р и q и двоичное число , относящееся к показателю q по модулю р (здесь и далее по тексту описания под многоразрядным двоичным числом следует понимать электромагнитный сигнал в двоичной цифровой форме, в котором общее число битов и порядок их следования отражает некоторое значение двоичного числа);

вычисляют два контрольных параметра с использованием исходных многоразрядных двоичных чисел р, , Y, Н и S путем возведения многоразрядных двоичных чисел , Y, r в дискретную степень по модулю р;

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

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

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

принимают электронный документ (ЭД), представленный в виде многоразрядного двоичного числа Н, открытый ключ в виде многоразрядного двоичного числа Y, ЭЦП в виде двух многоразрядных двоичных чисел s и r, простое многоразрядное двоичное число р и двоичное число , являющееся первообразным корнем по модулю p;

вычисляют два контрольных параметра с использованием исходных многоразрядных двоичных чисел р, , Y, Н и S путем возведения многоразрядных двоичных чисел , Y, r в дискретную степень по модулю р;

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

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

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

принимают электронный документ, представленный многоразрядным двоичным числом Н, принимают открытый ключ в виде первого g-разрядного двоичного числа n и второго f-разрядного двоичного числа и ЭЦП в виде многоразрядного двоичного числа S;

формируют проверочное многоразрядное двоичное число В, для чего многоразрядное двоичное число S возводят в степень по модулю n;

сравнивают сформированное проверочное многоразрядное двоичное число В с эталонным многоразрядным двоичным числом, в качестве которого используют многоразрядное двоичное число Н;

при совпадении параметров сравниваемых многоразрядных двоичных чисел В и Н делают вывод о подлинности ЭЦП.

Недостатком ближайшего аналога является относительно высокая вероятность несанкционированного формирования ЭЦП к электронному документу, представленному многоразрядным двоичным числом Н, имеющему меньшую разрядность, чем у первого g-разрядного двоичного числа n. Это обусловлено тем, что для произвольного значения S легко вычисляется значение Н, т.е. Н=Smod n, которое проходит процедуру проверки подлинности ЭЦП, т.е. будет иметь место «ложное» подтверждение подлинности ЭЦП, заверяющей ЭД.

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

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

Благодаря новой совокупности существенных признаков за счет изменения процедуры формирования проверочного числа достигается снижение вероятности несанкционированного формирования ЭЦП, т.е. «ложного» подтверждения подлинности ЭЦП.

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

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

Возможность реализации заявленного способа объясняется следующим образом. Известно, что возможность несанкционированного формирования ЭЦП предотвращается тем, что для формирования правильного значения ЭЦП требуется знание секретного ключа, которым обладает только лицо, подписывающее ЭД. Открытый ключ формируют в зависимости от выбранного секретного ключа, благодаря чему обеспечивается возможность проверки подлинности ЭЦП при использовании только открытого ключа. Однако некоторые способы проверки подлинности ЭЦП (в том числе в ближайшем аналоге) сохраняют относительно высокую вероятность несанкционированного формирования ЭЦП по известному открытому ключу и без использования секретного ключа. Например, в случае прототипа эта возможность возникает из-за того, что для произвольного многоразрядного двоичного числа S можно вычислить такое значение Н, для которого выполняется условие S mod n=Н, т.е. оказывается возможным сформировать пары значений S и Н, при которых обеспечивается «ложное» подтверждение подлинности ЭЦП.

В заявленном техническом решении в значительной мере такая вероятность снижается.

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

Пример реализации заявляемого способа.

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

1. Принимают открытый ключ подписывающего (n, ), рассылаемый, например, удостоверяющим центром по телекоммуникационным сетям. В качестве примера ниже приняты двоичные числа и n, имеющие разрядности g=332 f=331 соответственно, и следующие последовательности нулевых и единичных битов:

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

3. Принимают ЭЦП в виде 331-разрядного двоичного числа S:

4. Формируют проверочное многоразрядное двоичное число число В путем возведения ЭЦП в степень Н по модулю n:

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

Практическую реализуемость заявленного способа с достижением указанного технического результата можно продемонстрировать на следующем примере.

Процедуре проверки подлинности ЭЦП, заверяющей ЭД, всегда предшествуют действия по формированию секретного и открытого ключей, формированию ЭЦП и заверению ЭД. Совокупность процедур формирования секретного и открытого ключей, формирования ЭЦП и проверки ЭЦП составляют общую систему ЭЦП (см., например, книгу [Молдовян Н.А., Молдовян А.А., Еремеев М.А. Криптография: от примитивов к синтезу алгоритмов. – СПб, БХВ-Петербург, 2004. – С.95-121]). Приведенному выше примеру реализации заявленного способа проверки подлинности ЭЦП, заверяющей ЭД, должны предшествовать действия по формированию секретного и открытого ключей, преобразованию исходного документа в электронный вид и формированию ЭЦП.

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

1. Формируют секретный ключ, для чего:

1.1. Генерируют (например, с помощью генератора случайных чисел) первое случайное простое число р, например, 133-разрядное:

1.2. Формируют второе случайное простое число q, для чего:

1.2.1. Генерируют первое и второе дополнительные простые случайные числа q’ и W, например, с разрядностью соответственно 109 и 91:

1.2.2. Вычисляют второе случайное многоразрядное (в нашем примере 199-разрядное) двоичное число q как увеличенное на единицу произведение первого и второго дополнительных случайных чисел q=q’W+1:

Сформированная тройка случайных многоразрядных двоичных чисел р, q и q’ составляет секретный ключ.

2. Формируют открытый ключ в виде первого g-разрядного и второго f-разрядного чисел n и , для чего:

2.1. Вычисляют первое g-разрядное (в нашем примере 332-разрядное) двоичное число n как произведение чисел р и q, входящих в секретный ключ:

2.1. Формируют второе f-разрядное (в нашем примере 331-разрядное) двоичное число , для чего:

2.2.1. Генерируют случайное двоичное, например 270-разрядное, число р:

2.2.2. Вычисляют функцию Эйлера (n)=(p-1)(q-1) от первого g-разрядного двоичного числа n:

2.2.3. Вычисляют дополнительный параметр t путем деления функции Эйлера (n) на первое дополнительное простое случайное число q’, т.е.

2.2.4. Вычисляют второе f-разрядное (в нашем примере 331-разрядное) двоичное число путем возведения двоичного числа в степень t по модулю n, т.е. =^tmod n:

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

4. Формируют ЭЦП, для чего:

4.1. Предварительно вычисляют 107-разрядное двоичное число К, являющееся обратным к Н по модулю q’, т.е. КН mod q’=1:

4.2. Вычисляют ЭЦП (в нашем примере 331-разрядное двоичное число) по формуле S=^K mod n:

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

– секретный ключ в виде трех двоичных чисел: 133-разрядного р, 199-разрядного q и 109-разрядного q’;

– открытый ключ в виде двух двоичных чисел: 332-разрядного n и 331-разрядного ;

– ЭЦП в виде 331-разрядного двоичного числа S,

– ЭД, хэш-функция от которого представляет 107-разрядное двоичное число Н.

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

S^H mod n=.

Для рассмотренных в примере реализации заявленного способа многоразрядных двоичных чисел это условие выполняется, так как

Из приведенного выше выражения следует, что значение двоичного числа К, соответствующего правильной ЭЦП, можно вычислить только при знании двоичного числа q’. В то же время такая задача с использованием только открытого ключа (n, ) вычислительно неосуществима, поскольку для этого необходимо разложить число n на два больших простых множителя, что является практически неразрешимой задачей.

Для несанкционированного формирования ЭЦП необходимо нахождение пары многоразрядных двоичных чисел S и Н, при которых справедливо выражение S^H mod n=. Однако при большой разрядности числа q’ без знания секретного ключа, а именно одного из его составляющих – двоичного числа q’, это практически невозможно. Этим определяется стойкость системы ЭЦП, основанной на заявляемом способе. Детальное математическое обоснование реализуемости и стойкости систем ЭЦП, основанных на заявляемом способе, приведено в Приложении 2.

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

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

Приложение 1

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

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

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

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

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

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

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

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

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

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

^Z mod n, где W – число, являющееся результатом выполнения данной операции.

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

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

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

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

Приложение 2

Математическое обоснование технической реализуемости заявленного способа

В заявляемом способе проверки ЭЦП в качестве модуля используют многоразрядное двоичное число n, представляющее собой произведение двух больших простых многоразрядных двоичных чисел р и q (n=pq). В свою очередь, числа р и q формируют в зависимости от некоторых случайно выбранных параметров, например в соответствии с процедурой, предписываемой стандартом ГОСТ Р 34.10-94 [Молдовян Н.А., Молдовян А.А., Еремеев М.А. Криптография: от примитивов к синтезу алгоритмов. – СПб, БХВ-Петербург, 2004. – С.418-419]. При таком способе генерации чисел р и q в разложении функции Эйлера от модуля n, т.е. в разложении числа (n)=(р-1)(q-1), присутствует простой множитель q’, разрядность которого примерно в два раза меньше разрядности одного из чисел р и q или примерно равна его разрядности, благодаря чему субъект, который генерирует свой секретный ключ, имеет возможность сформировать такое значение n, для которого q’ имеет желаемую разрядность. Для обеспечения достаточно высокой стойкости системы ЭЦП длину многоразрядного двоичного числа q’ целесообразно выбирать равной 160 бит и более. Многоразрядные двоичные числа р, q и q’ являются секретными, т.е. составляют секретный ключ, который не используется в процедуре проверки подлинности ЭЦП. После того как сформирован модуль n, в дальнейшем для формирования ЭЦП достаточно использовать только секретное многоразрядное двоичное число q’. Для проверки же подлинности ЭЦП секретные параметры не используются. Подлинность ЭЦП проверяется по открытому ключу.

Открытым ключом является пара многоразрядных двоичных чисел (n, ), где является числом, относящимся к показателю q’ по модулю n. Двоичное число формируют следующим образом [Молдовян Н.А., Молдовян А.А., Еремеев М.А. Криптография: от примитивов к синтезу алгоритмов. – СПб, БХВ-Петербург, 2004. – С.409-410]. Генерируют случайное число и вычисляют дополнительный параметр t=((n)/q’), после чего вычисляют многоразрядное двоичное число =^t mod n. Если вычисленное 1, то оно берется в качестве второго f-разрядного числа открытого ключа. Действительно, в силу теоремы Эйлера [Бухштаб А.А. Теория чисел. – М.: Просвещение, 1966. – 384 с.] имеем: ^q’ mod n=b⁽ⁿ⁾ mod n=1, причем q’ является минимальным числом, для которого выполняется условие ^q’ mod n=1, т.е. является числом, относящимся по модулю n к показателю q’.

Подпись к ЭД, представленному хэш-функцией Н, формируют следующим образом. Вычисляют двоичное число К, являющееся обратным к числу Н по модулю q’, т.е. K=H^-1 mod q’. Затем вычисляют ЭЦП S путем возведения числа в степень К по модулю n: S=^K mod n. Известен эффективный способ [Б.Шнайер. Прикладная криптография. – М., изд-во «Триумф», 2002. – С.278-280] осуществления операции возведения r-разрядных двоичных чисел в степень, равную z-разрядному двоичному числу, по модулю, равному g-разрядному числу, где 32r, z, g4096. Использование указанного способа позволяет выполнить процедуру формирования ЭЦП S на персональных ЭВМ за время от 100 мс до 10 с в зависимости от производительности ЭВМ и разрядности чисел К, и n. Согласно заявляемому способу проверки ЭЦП ее подлинность признается, если выполнено условие S^H mod n=. Это условие выполняется, так как имеем:

Определить значение двоичного числа К, соответствующее правильной ЭЦП можно только по известному двоичному числу q’. Нахождение двоичного числа q’ по открытому ключу (n, ) вычислительно неосуществимо, поскольку для этого требуется решить задачу разложения многоразрядного числа n на два больших простых множителя. Эта задача (задача факторизации модуля) при достаточно большой длине простых множителей практически неразрешима, что определяет стойкость системы ЭЦП, основанной на заявляемом способе проверки ЭЦП (сложность задачи факторизации модуля n лежит также и в основе системы RSA, описанной в книгах [Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. – М.: Радио и связь. – С.163-165; Молдовян А.А., Молдовян Н.А., Советов Б.Я. Криптография. – СПб, Лань, 2000. – С.151-155] и выбранной в качестве ближайшего аналога). Несанкционированное формирование ЭЦП связано с нахождением пары чисел S и Н, таких, что выполняется соотношение S^H mod n=. Поскольку без знания двоичного числа q’, являющегося элементом секретного ключа, практически невозможно подобрать пару значений S и Н, удовлетворяющих последнему соотношению, вероятность несанкционированного формирования ЭЦП пренебрежимо мала.

В случае ближайшего аналога проверка подлинности ЭЦП осуществляется в соответствии с формулой S mod n=Н, из-за чего имеется возможность несанкционированного формирования подписи в соответствии с так называемой мультипликативной атакой [Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. – М.: Радио и связь. – С.165].

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

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

Способ проверки подлинности электронной цифровой подписи, заверяющей электронный цифровой документ, заключающийся в том, что принимают электронный документ, представленный многоразрядным двоичным числом Н, открытый ключ в виде первого g-разрядного и второго f-разрядного двоичных чисел n и и электронную цифровую подпись в виде многоразрядного двоичного числа S, формируют проверочное многоразрядное двоичное число В, параметры которого сравнивают с параметрами эталонного многоразрядного двоичного числа, и при их совпадении делают вывод о подлинности электронной цифровой подписи, отличающийся тем, что для формирования проверочного многоразрядного двоичного числа В электронную цифровую подпись возводят в степень Н по модулю, равному первому g-разрядному двоичному числу n открытого ключа, причем в качестве эталонного многоразрядного двоичного числа используют второе f-разрядное число открытого ключа.

MM4A – Досрочное прекращение действия патента СССР или патента Российской Федерации на изобретение из-за неуплаты в установленный срок пошлины за поддержание патента в силе

Дата прекращения действия патента: 25.01.2007

Извещение опубликовано: 20.06.2008 БИ: 17/2008