Изобретение относится к технике связи и предназначено для обеспечения подлинности сообщений, пересылаемых по линиям передачи.
Известно несколько способов [1,2] электронного подписывания сообщений, когда отправитель сообщения шифрует его секретным ключом и пересылает получателю исходное и зашифрованное сообщение. Зашифрованное сообщение и является подписью. Получатель с помощью открытого ключа проверяет соответствие полученных им исходного и зашифрованного сообщений, в результате чего убеждается в том, что исходное сообщение не было никем случайно или преднамеренно испорчено, либо обнаруживает искажение (или подделку). Более того, так как получатель не в состоянии сам подделать подпись отправителя, то он может доказать, что полученное им сообщение и подпись были посланы конкретным отправителем.
Надежность электронной подписи обеспечивается тем, что никто, не владеющий секретным ключом, не сможет за приемлемое время ни подделать ключ, ни подделать подпись под конкретным сообщением.
В известных способах сообщение и подпись формируют в виде цифрового сигнала как большое целое число, и все операции над цифровыми сигналами выполняют в виде вычислений над целыми числами.
В качестве составной части секретного ключа задают число m - модуль и s - секретный показатель. Для формирования цифрового сигнала подписи реализуют операцию возведения исходного цифрового сообщения A в степень s по модулю m:
B = As mod m, (1)
где B - подпись.
Эта операция для больших многоразрядных чисел выполняется очень медленно. Иногда m представляют как произведение двух больших простых чисел p и q. В этом случае вместо прямого формирования по формуле (1) подпись формируют по частям, используя китайскую теорему об остатках [3]. Для этого предварительно определяют инверсию r согласно соотношению:
(r•p) mod q = 1.
Вычисление инверсии производят обобщенным алгоритмом Евклида для наибольшего общего делителя [4]. Тогда подпись B формируют следующим образом:
s1 = s mod (p - 1), (3)
s2 = s mod (q - 1), (4)
B = (((B2 -B1)•r) mod q)• p+B1, (7)
где s1, s2, B1, B2 - вспомогательные величины. Самым трудоемким здесь являются возведения в степень по модулю (5) - (6), остальные действия выполняются в сотни раз быстрее. При прямом возведении в степень по модулю в соответствии с формулой (1) длина всех чисел: A, s и B составляет n знаков (для двоичного представления информации n бит). Время вычислений при больших n пропорционально n3. При вычислении по формулам (2) - (7) длина чисел p, q, r, s1, s2, B1, B2 составляет n/2 знаков, поэтому два возведения в степень по модулю (5) - (6) выполняются почти в 4 раза быстрее, чем одно в (1).
Наиболее совершенный способ электронного подписывания в настоящее время предоставляет метод RSA [2], который реализует две функции: шифрование сообщений открытым ключом и электронное подписывание. Функция подписывания реализована следующим образом. Открытый ключ содержит пару целых чисел: модуль m и открытый показатель степени e. Модуль m выбирают равным произведению двух секретных простых чисел p и q. Открытый показатель степени e выбирают удовлетворяющим соотношению:
НОД (e, (p -1)•(q - 1)) = 1, (8)
где НОД - наибольший общий делитель.
Секретный ключ содержит секретный показатель степени s и секретные простые числа p, q. Секретный показатель выбирают согласно соотношению:
(s•e) mod ((p - 1)•(q - 1)) = 1. (9)
При формировании подписи B возводят исходное сообщение A в степень s по модулю m по формуле (1):
B = As mod m
Затем исходное сообщение A и подпись B пересылают по линии передачи сообщений получателю. Получатель проверяет подпись путем возведения принятой подписи - числа Bt в степень e по модулю m:
G = B
и проверки на совпадение величины G с принятым исходным сообщением At. Если искажений при передаче исходного сообщения и подписи не было (Bt = B, At = A), то благодаря тождеству
A(p-1) (q-1) mod (p•q) = 1
G будет совпадать с At:
G = (As mod m)e mod m = Ase mod m = AK(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 = As 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 = ((Bt•A
D = Az mod m (14)
причем числа e и m образуют открытый ключ, и в случае равенства проверочных величин C и D принимают решение, что подпись подлинная.
При совпадении посланного и принятого сообщений и подписи (Ai = A, Bi=B) проверочные величины C и D будут равным между собой благодаря тождеству (11) и соотношению (12):
C = ((As •Ax)e) mod m = A(s+x)e+y mod m = Az mod m = D.
Другой вариант изобретения, как и прототип, включают формирование цифрового сигнала подписи из цифрового сигнала исходного сообщения, пересылку подписи и исходного сообщения по линии передачи и последующую проверку подлинности принятой подписи и принятого исходного сообщения.
В отличие от прототипа в этом варианте заявляемого изобретения величину секретного показателя s выбирают из соотношения (12):
((s + x)•e + y) mod ((p - 1)•(q - 1)) = z,
где секретный показатель s и простые числа p, q образуют секретный ключ, e - открытый показатель, x, y, z - заданные числа, формирование цифрового сигнала подписи производят путем формирования величины B1 по формуле (5):
где величина s1 равна s mod (p - 1), формирования величины B2 по формуле (6):
где величина s2 равна s mod (q - 1), и последующего формирования подписи B по формуле (7):
B = (((B2 - B1 )•r) mod q) • p + B1,
где r - инверсия, выбранная из соотношения (r•p) mod q = 1, а указанную проверку осуществляют путем формирования двух проверочных величин C и D по формулам (13) и (14):
где At и Bt - соответственно принятые по линии передачи сообщение и подпись, m - произведение чисел p и q, причем числа m и e образуют открытый ключ, и сравнения указанных проверочных величин между собой.
При этом целесообразно числа p, e, z и y выбрать таким образом, чтобы отношения (z - y)/e и (p - 1)/e были целыми числами. В этом случае величина s2 оказывается равной:
s2 = (z - y)/e - x,
так как секретный показатель s ввиду (12) равен:
где K - некоторое целое. Числа x, y, z следует выбирать небольшими, тогда величина s2 будет также небольшой и основное время при формировании подписи будет тратиться на одно n/2 - битовое возведение в степень по формуле (5). Поэтому в настоящем способе по сравнению со способом RSA формирование подписи ускоряется практически в два раза при той же длине ключа, обеспечивающей высокую надежность.
Далее изобретение поясняется описанием работы системы электронного подписывания сообщений, представленной в виде блок-схемы на чертеже на примере осуществления способа в предпочтительном воплощении. Блок-схема содержит последовательно соединенные блок 1 формирования подписи, линию передачи 2 и блок 3 проверки подписи. В свою очередь блок 1 формирования подписи содержит параллельно соединенные подблок 4 формирования величины B1 по формуле (5) и подблок 5 формирования величины B2 по формуле (6), выходы которых соединены с входами подблока 6 формирования подписи по формуле (7). Блок 3 проверки подписи содержит параллельно соединенные подблоки 7 и 8 формирования проверочных величин соответственно по формулам (13) и (14), выходы которых соединены с входами блока сравнения 9.
В подблоках 4, 5, 7 и 8 выполняется операция возведения в степень по модулю, алгоритм ее эффективной реализации приведен в [5]. Другие операции, применяемые в этих подблоках (сложение, вычитание, умножение и вычисление остатка от деления) для многоразрядных чисел, приведены в [6]. Все эти подблоки могут быть реализованы в виде программно-управляемых микропроцессоров, в памяти которых (например, ПЗУ) записаны соответствующие алгоритмы.
Входами системы электронного подписывания сообщений являются входы блока 1 формирования подписи для сигнала исходного сообщения A и сигнала секретного ключа (p, q, r, s1, s2), а также входы блока 3 проверки подписи для сигналов открытого ключа (m, e). Выходами системы являются выходы "да" и "нет" блока 3 - результат проверки подписи.
Сигнал исходного сообщения A поступает на подблоки 4 и 5 блока 1 формирования подписи и через 1-й выход блока 1 - на линию 2 передачи сообщений. Сигнал секретного ключа, содержащий два секретных простых числа p и q, инверсию r, величины s1, s2, поступает на подблоки блока 1 в следующем порядке: сигнал простого числа p - на блоки 4 и 6, сигнал простого числа q - на подблоки 5 и 6, сигнал величины s1 - на подблок 4, сигнал величины s2 - на подблок 5, сигнал инверсии r - на подблок 6. Сформированные в подблоках 4 и 5 сигналы величин B1 по формуле (5) и B2 по формуле (6) соответственно поступают на входы подблока 6, в котором формируется сигнал подписи B по формуле (7). Из выхода подблока 6, являющимся 2-м выходом блока 1, сигнал сформированной подписи B поступает на линию 2 передачи сообщений. Из линии передачи сообщений принятый сигнал исходного сообщения At поступает на подблоки 7 и 8 блока 3, а сигнал подписи Bt на подблок 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 бит, что увеличит надежность в 106 раз (подсчеты сделаны на основании формулы сложности разложения большого числа на два простых множителя, приведенной в [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.
Изобретение относится к технике связи и предназначено для обеспечения подлинности сообщений, пересылаемых по линиям передачи. В предлагаемом способе цифровой сигнал подписи B формируют путем возведения цифрового сигнала исходного сообщения A в секретную степень s по модулю m, являющемуся произведением двух секретных простых чисел p и q: B = As mod m. Затем цифровые сигналы исходного сообщения и подписи пересылают получателю и проверяют на подлинность с помощью открытого ключа. В отличие от метода RSA в нем величину секретного показателя s выбирают из соотношения: ((s + x) • e + y) mod ((р - 1) • (q - 1)) = z и указанную проверку осуществляют путем формирования двух проверочных величин C и D:
где e - открытый показатель, x, y, z - заданные числа, At и Bt - соответственно принятые по линии передачи сообщение и подпись, и последующего сравнения указанных проверочных величин между собой. По сравнению с методом RSA формирование подписи ускоряется в два раза при одинаковой разрядности ключа и такой же надежности. 2 с. и 1 з.п.ф-лы, 1 ил.
В = Asmod m,
где m - произведение секретных простых чисел p и q;
s - секретный показатель, образующие секретный ключ,
пересылку цифровых сигналов исходного сообщения и подписи по линии передачи и последующую проверку подлинности подписи, отличающийся тем, что в нем величину секретного показателя выбирают из соотношения
((s + x) • e + y) • mod ((p - 1) • (q - 1)) = z
и указанную проверку осуществляют путем формирования двух проверочных величин C и D:
где e - открытый показатель;
x, y, z - заданные числа;
At и Bt - соответственно принятые по линии передачи сообщение и подпись, причем числа e и m образуют открытый ключ,
и последующего сравнения указанных проверочных величин между собой.
((s + x) • e + y) mod ((p - 1) • (q - 1)) = z,
где секретный показатель s и простые числа p • q образуют секретный ключ;
e - открытый показатель;
x, y, z - заданные числа,
формирование цифрового сигнала подписи производят путем формирования величины B1 по формуле
где величина s1 равна smod(p - 1),
формирования величины B2 по формуле
где величина s2 равна s(q - 1),
и последующего формирования подписи B по формуле
B = (((B2 - B1) • r) modq) • p + B1,
где r - инверсия, выбранная из соотношения (r • p)mod q = 1,
а указанную проверку осуществляют путем формирования двух проверочных величин C и D
где At и Bt - соответственно принятые по линии передачи сообщение и подпись;
m - произведение чисел p и q, причем числа m и e образуют открытый ключ,
и сравнения указанных проверочных величин между собой.
| EI Gamal T.Apublic key criptosystem and a signature scheme bassed on dusarete logarithms | |||
| IEEE Trans Inform | |||
| Theory, v.31, N 4, p.469-472, July, 1985 | |||
| US, патент, 4405829, кл | |||
| Очаг для массовой варки пищи, выпечки хлеба и кипячения воды | 1921 |
|
SU4A1 |
