Электронная цифровая подписьRSA

Шифр RSA

Электронная цифровая подпись (ЭЦП)

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

Шифр назван в честь разработчиков - Ривеса, Шамира и Адлемана. Эта система RSA использует только открытые каналы связи. Закрытых каналов ей не требуется.

Шифр RSA базируется на двух фактах из теории чисел.

1) Задача проверки целого числа на простоту (делится только на себя и на 1) является легкой.

2) Задача нахождения простых чисел P и Q по известному их произведению N=P*Q является очень трудной для больших чисел P и Q.

Система RSA состоит в следующем.

Пусть имеются абоненты A, B, C и т.д. Каждый абонент

1) Выбирает случайно два больших простых числа P и Q, вычисляет их произведение N=P*Q и открыто рассылает свое произведение N всем другим абонентам.

2) Вычисляет φ = (P-1)*(Q-1), выбирает число d<φвзаимно-простое с φ (не имеют общих делителей кроме 1) и открыто рассылаетсвое число dвсем абонентам.

3) Находит с такое, что (с*d)modφ = 1. Обозначается как с = d^-1modφ.

В результате получается следующая таблица.

Абонент	Секретный ключ	Открытый ключ
A	cA	dA, NA
B	cB	dB, NB
C	cC	dC, NC
	Каждый знает только свой	Знают все

Сеанс связи от А к В происходит по следующему протоколу. Предполагается, что блок сообщения mменьше числа N_B.

Шаг 1. Абонент A шифрует сообщение m по формуле

e = m^dB mod N_B

и пересылает его абоненту B по открытому каналу.

Шаг 2. Абонент B получает сообщение и расшифровывает его по формуле

m’ = e^cB mod N_B

Свойства протокола RSA:

1) m’ = m,т.е. получено исходное сообщение.

2) Противник не может расшифровать сообщение, т.к. не знает c_B и не может найти c_B по известному d_B, т.к. не знает φ Не может найти φ, т.к. не знает P_B и Q_B. Не может найти P_B и Q_B по их известному произведению N_B = P_B * Q_B для больших P_B и Q_B.

Заметим, что знание одного из P или Q позволяет найти секретный ключ «c». Это называется «лазейкой» или «потайным ходом»шифра. Действительно, по P и N легко найти Q. По P и Q легко найти φ = (P-1)*(Q-1). По φ и d можно найти «c» из формулы (с*d) mod φ = 1.

Рассмотренная схема RSA не вскрываема при больших P и Q, но обладает следующим недостатком: абонент A передает сообщение к B, используя только открытую информацию d_B, N_B. Противник не может вскрыть сообщение m, но он может послать сообщение к B от имени A. Избежать этого недостатка позволяет электронная цифровая подпись (ЭЦП).

Пусть А хочет передать к В сообщение m. Протокол ЭЦП RSA состоит из трех шагов.

Шаг 1. Абонент A вычисляет

e = m^cA mod N_A

Противник не может этого сделать, т.к. не знает секретного c_A.

Шаг 2. Абонент A вычисляет

f = e^dB mod N_B

и посылает его к В.

Шаг 3. АбонентВвычисляет последовательно

u = f^cB mod N_B

v = u^dA mod N_A

Утверждение:

Оказывается v = m.

Противник не может теперь послать сообщение к B от имени А, т.к. не знает секретного c_A. Абонент А в шаге 1 как бы подписал сообщение m, зашифровав его своим секретным c_A. Абонент B может теперь проверить аутентичность отправителя, т.к. корректно сообщение расшифровывается только с помощью открытого ключа N_A.

Дата добавления: 2014-01-04