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

 

Изобретение относится к технике связи и вычислительной технике и предназначено для обеспечения конфиденциальности сообщений, пересылаемых по линиям связи. Технический результат - ускорение процесса дешифрования. Сущность способа заключается в том, что цифровой сигнал зашифрованного сообщения В формируют путем возведения цифрового сигнала исходного сообщения А в открытую степень е по модулю m, являющемуся произведением двух секретных простых чисел p и q B = A^emodm Затем зашифрованное сообщение пересылают получателю и дешифруют с помощью секретного ключа. Секретный показатель степени S для дешифрования определяют из соотношения: (S · e)mod(p - 1) = 1, причем (p - 1) должно быть взаимно простым числом, а при дешифровании формируют остаток дешифрованного сообщения B₁; B₁ = Bmodp, после чего формируют цифровой сигнал дешифрованного сообщения At: A_t = B^S₁modp. Система шифрования содержит блок 1 шифрования, линию 2 передачи, блок 3 дешифрования, подблок 4 формирования остатка, полученного зашифрованного сообщения, подблок 5 формирования дешифрованного сообщения. 2 с.п. ф-лы. 1 ил.

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

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

В качестве составной части открытого ключа задают число m-модуль и е-открытый показатель степени. Для форсирования цифрового сигнала зашифрованного сообщения реализуют операцию возведения исходного цифрового сообщения А в степень по модулю m: B=A^emod m, (1) где В зашифрованное сообщение.

Зашифрованное сообщение пересылают получателю. Формирование цифрового сигнала дешифрованного сообщения производят как возведение полученного зашифрованного сообщения В_t в степень S по модулю m: A_t = B^S_tmodm, (2) где А_t дешифрованное сообщение, S секретный показатель степени, входящий в состав секретного ключа.

Недостатком известного способа является недостаточно быстрый процесс дешифрования.

Шифрование в известном способе выполняется быстро, так как открытый показатель степени е выбирают небольшим. Дешифрование для больших многоразрядных чисел выполняется очень медленно. Иногда m представляют как произведение двух больших простых чисел р и q.

В этом случае вместо прямого вычисления по формуле (2) дешифрованное сообщение формируют по частям, используя китайскую теорему об остатках. Для этого предварительно вычисляют инверсию 1-го простого числа по модулю 2-го согласно соотношению: (r · q mod q 1 (3) где r инверсия.

Вычисление инверсии производится обобщенным алгоритмом Евклида для НОД (наибольшего общего делителя). Тогда дешифрование осуществляется путем проведения следующих вычислений:
S₁ Smod(p 1), (4)
S₂ Smod(q 1), (5)

A_t (((A₂ A₁) · r)vodq) · p + A₁ (8)
где S₁, S₂ 1-й и 2-й остатки секретного показателя степени, А₁, A₂ 1-й и 2-й остатки сообщения, А_t - дешифрованное сообщение.

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

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

Секретный текст содержит другой (секретный) показатель степени S, вычисленный как инверсия е по модулю ((p 1) · )(q 1)):
(S · e)mod((p 1) · (q 1)) 1 (10).

При шифровании возводят число А в степень е по модулю m согласно формуле (1), в результате чего получают зашифрованное сообщение В, которое пересылают по линии передачи сообщений получателю. Получатель дешифрует полученное сообщение B_t путем возведения числа B_t в степень S по модулю m согласно формуле (2) или (3) 8). Если искажений при передаче зашифрованного сообщения не было (B_t B) то благодаря тождеству
A^{(p - 1)} · ^{(q - 1)}mod(p · q) 1 (11)
дешифрованное сообщение будет совпадать с исходным сообщением
A_t (A^smodm)^emodm A^semodm A^{к(p - 1)(q - 1) +1}modm A
Шифрование в известном способе по формуле (1) осуществляется быстро, обычно за доли секунды, так как длина открытого показателя степени имеет порядок 3-5 бит. Однако дешифрование по формулам (2) или (3) (8) составляет десятки секунд для микропроцессоров. Основным недостатком метода RSA является большое время дешифрования.

Технический результат ускорение процесса дешифрования и повышение надежности шифрования.

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

Открытый показатель степени е для шифрования выбирают так, чтобы (p 1) и е были взаимно простыми, секретный показатель степени S для дешифрования определяют согласно соотношению:
(S · e)mod(p 1) 1 (12)
а дешифрование производят путем формирования остатка полученного дешифрованного сообщения B_t по модулю p:
B₁ B_tmodp (13)
и возведения остатка B₁ в секретную степень S
A_t B₁modp (14)
При совпадении посланного и принятого сообщений (B_t B), дешифрованное сообщение A_t будет равно исходному сообщению благодаря тождеству
A^{p - 1}modp 1 (15)
Действительно, с учетом (12):
A_t ((A^emodm)modp)^smodp A^esmodp A^k(p-1)+1modp A
Для высокой надежности длина чисел n должна быть порядка 500 1000 бит.

Таким образом, вместо двух n/2 разрядных возведений в степень по модулю при дешифровании остается только одно. Поэтому в настоящем способе по сравнению со способом RSA дешифрование ускоряется в два раза при той же надежности.

На фиг. 1 приведена блок-схема системы шифрования сообщений открытым ключом.

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

Система шифрования сообщений открытым ключом работает следующим образом.

На блок 1 шифрования поступают исходное сообщение А и открытый ключ, содержащий произведение двух секретных чисeл m и открытый показатель степени е. Зашифрованное в блоке 1 по формуле (1) сообщение В поступает из него на линию 2 передачи сообщений. Секретный ключ, содержащий секретное 1-е простое число и секретный показатель, поступает на подблоки 4 и 5 блока 3 в следующем порядке: секретное 1-е простое число Р на подблоки 4 и 5, секретный показатель S на подблок 5. Из линии 2 передачи сообщений полученное зашифрованное сообщение B_t поступает в подблок 4 блока 3, сформированный в котором по формуле (13) остаток полученного зашифрованного сообщения B₁ поступает на подблок 5 блока 3. Сформированное в подблоке 5 по формуле (14) дешифрованное сообщение A_t поступает на выход системы.

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

1. Способ шифрования сообщений открытым ключом, включающий формирование цифрового сигнала зашифрованного сообщения B из цифрового сигнала исходного сообщения A с помощью открытого ключа по формуле
B A^e mod m,
где e открытый показатель,
m p · q, где p, q секретные простые числа,
причем e и m образуют открытый ключ, передачу защифрованного сообщения по линии передачи и последующее дешифрование принятого зашифрованного сообщения B_t с помощью секретного ключа, отличающийся тем, что в качестве открытого показателя e выбирают число, взаимно простое с числом р 1, секретный показатель S выбирают согласно соотношению
(S · e) mod (p 1) 1,
дешифрование осуществляют путем формирования остатка B₁ принятого зашифрованного сообщения B_t по формуле
B₁ B_t mod p
и формирования дешифрованного сообщения A_t по формуле
A_t= B^S₁modp,
причем s и p образуют секретный ключ.

2. Система шифрования сообщений открытым ключом, содержащая последовательно соединенные блок шифрования, формирующий зашифрованное сообщение по формуле
b A^e mod m,
линию передачи сообщений и блок дешифрования, отличающаяся тем, что блок дешифрования содержит последовательно соединенные подблок формирования остатка полученного зашифрованного сообщения по формуле
B₁ B_t mod p,
и подблок формирования дешифрованного сообщения по формуле
A_t= B^S₁modp.

РИСУНКИ

Рисунок 1