способ электронного подписывания сообщений (его варианты)

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

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

В = A^smod m,

где m - произведение секретных простых чисел p и q;

s - секретный показатель, образующие секретный ключ,

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

((s + x) e + y) mod ((p - 1) (q - 1)) = z

и указанную проверку осуществляют путем формирования двух проверочных величин C и D:



где e - открытый показатель;

x, y, z - заданные числа;

A_t и B_t - соответственно принятые по линии передачи сообщение и подпись, причем числа e и m образуют открытый ключ,

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

2. Способ электронного подписывания сообщений, включающий формирование цифрового сигнала подписи B из цифрового сигнала исходного сообщения A, пересылку цифровых сигналов исходного сообщения и подписи по линии передачи и последующую проверку подлинности подписи, отличающийся тем, что в нем величину секретного показателя s выбирают из соотношения

((s + x) e + y) mod ((p - 1) (q - 1)) = z,

где секретный показатель s и простые числа p q образуют секретный ключ;

e - открытый показатель;

x, y, z - заданные числа,

формирование цифрового сигнала подписи производят путем формирования величины B₁ по формуле



где величина s₁ равна smod(p - 1),

формирования величины B₂ по формуле



где величина s₂ равна s(q - 1),

и последующего формирования подписи B по формуле

B = (((B₂ - B₁) r) modq) p + B₁,

где r - инверсия, выбранная из соотношения (r p)mod q = 1,

а указанную проверку осуществляют путем формирования двух проверочных величин C и D



где A_t и B_t - соответственно принятые по линии передачи сообщение и подпись;

m - произведение чисел p и q, причем числа m и e образуют открытый ключ,

и сравнения указанных проверочных величин между собой.

3. Способ по п.2, отличающийся тем, что числа p, z и y выбраны из условий, что отношения (p - 1)/e и (z - y)/e - целые числа.

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

Изобретение относится к технике связи и предназначено для обеспечения подлинности сообщений, пересылаемых по линиям передачи.

Известно несколько способов [1,2] электронного подписывания сообщений, когда отправитель сообщения шифрует его секретным ключом и пересылает получателю исходное и зашифрованное сообщение. Зашифрованное сообщение и является подписью. Получатель с помощью открытого ключа проверяет соответствие полученных им исходного и зашифрованного сообщений, в результате чего убеждается в том, что исходное сообщение не было никем случайно или преднамеренно испорчено, либо обнаруживает искажение (или подделку). Более того, так как получатель не в состоянии сам подделать подпись отправителя, то он может доказать, что полученное им сообщение и подпись были посланы конкретным отправителем.

Надежность электронной подписи обеспечивается тем, что никто, не владеющий секретным ключом, не сможет за приемлемое время ни подделать ключ, ни подделать подпись под конкретным сообщением.

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

В качестве составной части секретного ключа задают число m - модуль и s - секретный показатель. Для формирования цифрового сигнала подписи реализуют операцию возведения исходного цифрового сообщения A в степень s по модулю m:

B = A^s mod m, (1)

где B - подпись.

Эта операция для больших многоразрядных чисел выполняется очень медленно. Иногда m представляют как произведение двух больших простых чисел p и q. В этом случае вместо прямого формирования по формуле (1) подпись формируют по частям, используя китайскую теорему об остатках [3]. Для этого предварительно определяют инверсию r согласно соотношению:

(rp) mod q = 1.

Вычисление инверсии производят обобщенным алгоритмом Евклида для наибольшего общего делителя [4]. Тогда подпись B формируют следующим образом:

s₁ = s mod (p - 1), (3)

s₂ = s mod (q - 1), (4)





B = (((B₂ -B₁)r) mod q) p+B₁, (7)

где s₁, s₂, B₁, B₂ - вспомогательные величины. Самым трудоемким здесь являются возведения в степень по модулю (5) - (6), остальные действия выполняются в сотни раз быстрее. При прямом возведении в степень по модулю в соответствии с формулой (1) длина всех чисел: A, s и B составляет n знаков (для двоичного представления информации n бит). Время вычислений при больших n пропорционально n³. При вычислении по формулам (2) - (7) длина чисел p, q, r, s₁, s₂, B₁, B₂ составляет n/2 знаков, поэтому два возведения в степень по модулю (5) - (6) выполняются почти в 4 раза быстрее, чем одно в (1).

Наиболее совершенный способ электронного подписывания в настоящее время предоставляет метод RSA [2], который реализует две функции: шифрование сообщений открытым ключом и электронное подписывание. Функция подписывания реализована следующим образом. Открытый ключ содержит пару целых чисел: модуль m и открытый показатель степени e. Модуль m выбирают равным произведению двух секретных простых чисел p и q. Открытый показатель степени e выбирают удовлетворяющим соотношению:

НОД (e, (p -1)(q - 1)) = 1, (8)

где НОД - наибольший общий делитель.

Секретный ключ содержит секретный показатель степени s и секретные простые числа p, q. Секретный показатель выбирают согласно соотношению:

(se) mod ((p - 1)(q - 1)) = 1. (9)

При формировании подписи B возводят исходное сообщение A в степень s по модулю m по формуле (1):

B = A^s mod m

Затем исходное сообщение A и подпись B пересылают по линии передачи сообщений получателю. Получатель проверяет подпись путем возведения принятой подписи - числа B_t в степень e по модулю m:

G = B^e_t mod m (10)

и проверки на совпадение величины G с принятым исходным сообщением A_t. Если искажений при передаче исходного сообщения и подписи не было (B_t = B, A_t = A), то благодаря тождеству

A^(p-1)(q-1) mod (pq) = 1

G будет совпадать с A_t:

G = (A^s mod m)^e mod m = A^{s e} mod m = A^{K(p-1)(q-1)+1} mod m = A.

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

Для высокой надежности длина чисел n должна быть порядка 500 - 1000 бит (или 150-300 десятичных цифр), тогда разложение модуля m на простые множители p и q невозможно произвести за приемлемое время на любых сверхмощных компьютерах и, следовательно, невозможно вычислить секретный показатель степени s по формуле (9).

Вычисление G по формуле (10) при проверке подписи осуществляется быстро, обычно за доли секунды, так как длина открытого показателя степени e выбирается небольшой: ее порядок 3 - 5 бит (1-2 десятичные цифры). Однако формирование подписи по формулам (1) или (2)-(7) составляет десятки секунд для микропроцессора средней мощности. Основным недостатком способа RSA является большое время формирования подписи.

Задачей изобретения является создание способа электронного подписывания сообщений с повышенной экспрессностью при заданной высокой степени защищенности способа от подделки подписи.

В соответствии с поставленной задачей изобретение - способ электронного подписывания сообщений, как и прототип, включает формирование цифрового сигнала подписи B из цифрового сигнала исходного сообщения A по формуле (1):

B = A^s mod m,

где s - секретный показатель, m - произведение двух секретных простых чисел p и q, пересылку подписи и исходного сообщения по линии передачи и последующую проверку подлинности принятой подписи и принятого исходного сообщения.

В отличие от прототипа в изобретении величину секретного показателя s выбирают из соотношения:

((s + x)e + y) mod ((p - 1) (q - 1)) = z, (12)

где секретный показатель s и простые числа p, q образуют секретный ключ, e - открытый показатель, x, y, z - заданные числа, а при последующей проверке принятой подписи формируют и сравнивают между собой две проверочные величины:

C = ((B_tA^X_t)^yA^v_t)mod m, (13)

D = A^z mod m (14)

причем числа e и m образуют открытый ключ, и в случае равенства проверочных величин C и D принимают решение, что подпись подлинная.

При совпадении посланного и принятого сообщений и подписи (A_i = A, B_i=B) проверочные величины C и D будут равным между собой благодаря тождеству (11) и соотношению (12):

C = ((A^s A^x)^e) mod m = A^(s+x)e+y mod m = A^z mod m = D.

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

В отличие от прототипа в этом варианте заявляемого изобретения величину секретного показателя s выбирают из соотношения (12):

((s + x)e + y) mod ((p - 1)(q - 1)) = z,

где секретный показатель s и простые числа p, q образуют секретный ключ, e - открытый показатель, x, y, z - заданные числа, формирование цифрового сигнала подписи производят путем формирования величины B₁ по формуле (5):



где величина s₁ равна s mod (p - 1), формирования величины B₂ по формуле (6):



где величина s₂ равна s mod (q - 1), и последующего формирования подписи B по формуле (7):

B = (((B₂ - B₁ )r) mod q) p + B₁,

где r - инверсия, выбранная из соотношения (rp) mod q = 1, а указанную проверку осуществляют путем формирования двух проверочных величин C и D по формулам (13) и (14):



где A_t и B_t - соответственно принятые по линии передачи сообщение и подпись, m - произведение чисел p и q, причем числа m и e образуют открытый ключ, и сравнения указанных проверочных величин между собой.

При этом целесообразно числа p, e, z и y выбрать таким образом, чтобы отношения (z - y)/e и (p - 1)/e были целыми числами. В этом случае величина s₂ оказывается равной:

s₂ = (z - y)/e - x,

так как секретный показатель s ввиду (12) равен:



где K - некоторое целое. Числа x, y, z следует выбирать небольшими, тогда величина s₂ будет также небольшой и основное время при формировании подписи будет тратиться на одно n/2 - битовое возведение в степень по формуле (5). Поэтому в настоящем способе по сравнению со способом RSA формирование подписи ускоряется практически в два раза при той же длине ключа, обеспечивающей высокую надежность.

Далее изобретение поясняется описанием работы системы электронного подписывания сообщений, представленной в виде блок-схемы на чертеже на примере осуществления способа в предпочтительном воплощении. Блок-схема содержит последовательно соединенные блок 1 формирования подписи, линию передачи 2 и блок 3 проверки подписи. В свою очередь блок 1 формирования подписи содержит параллельно соединенные подблок 4 формирования величины B₁ по формуле (5) и подблок 5 формирования величины B₂ по формуле (6), выходы которых соединены с входами подблока 6 формирования подписи по формуле (7). Блок 3 проверки подписи содержит параллельно соединенные подблоки 7 и 8 формирования проверочных величин соответственно по формулам (13) и (14), выходы которых соединены с входами блока сравнения 9.

В подблоках 4, 5, 7 и 8 выполняется операция возведения в степень по модулю, алгоритм ее эффективной реализации приведен в [5]. Другие операции, применяемые в этих подблоках (сложение, вычитание, умножение и вычисление остатка от деления) для многоразрядных чисел, приведены в [6]. Все эти подблоки могут быть реализованы в виде программно-управляемых микропроцессоров, в памяти которых (например, ПЗУ) записаны соответствующие алгоритмы.

Входами системы электронного подписывания сообщений являются входы блока 1 формирования подписи для сигнала исходного сообщения A и сигнала секретного ключа (p, q, r, s₁, s₂), а также входы блока 3 проверки подписи для сигналов открытого ключа (m, e). Выходами системы являются выходы "да" и "нет" блока 3 - результат проверки подписи.

Сигнал исходного сообщения A поступает на подблоки 4 и 5 блока 1 формирования подписи и через 1-й выход блока 1 - на линию 2 передачи сообщений. Сигнал секретного ключа, содержащий два секретных простых числа p и q, инверсию r, величины s₁, s₂, поступает на подблоки блока 1 в следующем порядке: сигнал простого числа p - на блоки 4 и 6, сигнал простого числа q - на подблоки 5 и 6, сигнал величины s₁ - на подблок 4, сигнал величины s₂ - на подблок 5, сигнал инверсии r - на подблок 6. Сформированные в подблоках 4 и 5 сигналы величин B₁ по формуле (5) и B₂ по формуле (6) соответственно поступают на входы подблока 6, в котором формируется сигнал подписи B по формуле (7). Из выхода подблока 6, являющимся 2-м выходом блока 1, сигнал сформированной подписи B поступает на линию 2 передачи сообщений. Из линии передачи сообщений принятый сигнал исходного сообщения A_t поступает на подблоки 7 и 8 блока 3, а сигнал подписи B_t на подблок 7 блока 3. Сигнал открытого ключа, содержащий произведение двух секретных простых чисел и открытый показатель степени (m, e), поступает на подблоки блока 3 в следующем порядке: сигнал произведения m двух секретных простых чисел - на подблок 7 и 8, сигнал открытого показателя e - на подблок 7. В подблоке 7 формируется сигнал проверочной величины С по формуле (13), а в подблоке 8 - сигнал проверочной величины D по формуле (14). С выходов подблоков 7 и 8 сигналы проверочных величин C и D поступают на входы блока сравнения 9. При совпадении значений сигналов проверочных величин результат сравнения поступает на выход "да", а при несовпадении - на выход "нет".

Предложенный способ ускоряет формирование подписи в два раза по сравнению со способом RSA, например, при длине ключа 1000 бит в микропроцессоре 80286/20 МГц на вычисления будет затрачено около 10 с, что вполне приемлемо. Если же допускается тратить на формирование подписи 20 с (как при использовании метода RSA), то при этом нужно увеличить длину ключа до 1250 бит, что увеличит надежность в 10⁶ раз (подсчеты сделаны на основании формулы сложности разложения большого числа на два простых множителя, приведенной в [1]).

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

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

Источники информации

1. ElGamal T.A public key criptosystem and a signature scheme based on discrete logaritms.IEEE Trans. Inform. Theory, v. 31, N 4, p, 469-472, July, 1985.

2. Патент США N 4405829, кл. H 04 Л 1.00, 1984.

3. Кнут Д. Искусство программирования для ЭВМ, т.2. Получисленные алгоритмы.-М.: Мир, 1977-726 с., разд. 4. 3. 2, с. 303-310.

4. Там же, разд. 4.5.2, с. 356-373.

5. Там же, разд. 4.6.3, с. 482-485.

6. Там же, разд., 4.3.1, с. 282-295.