Алгоритм RSA

Общее описание

Первым конкретным примером системы ОШ была предложенная в 1978 году так называемая "система RSA". Ее название происходит от первых букв фамилий авторов R.Rivest, A.Shamir, L.Adleman, которые придумали ее во время совместной работы в Массачусетском технологическом институте, в 1977 году.

Зашифрование и расшифрование сообщений

Система открытого шифрования RSA устроена таким образом. Открытые сообщения M представляются целыми числами, 1<M<N, где N - большое целое число, равное произведению двух различных больших простых чисел:

N = P * Q

Алгоритмы шифрования и расшифрования определяются числом N и показателями степени E и D которые связаны соотношением:

( E * D ) mоd F(N) = 1

где:

F(N) = (p - 1) * (q - 1) (B-12)

Шифрование информации можно определить следующим образом:

M ---> M^E mоd(N) = C

Расшифрование:

C --> C^Dmоd(N)=(M^E)^Dmоd(N)=Mmоd(N)=M

В качестве открытого ключа выступает пара чисел (N, E), а в качестве секретного ключа - число D.

Электронная подпись

Система электронной подписи RSA получается при "смене мест" ключей E и D.
Подпись сообщения:

M ---> M ^D mоd (N) = S

Проверка подлинности подписанного сообщения [M,S]:

M = S ^Emоd(N)

Совпадение чисел в левой и правой частях последнего равенства "доказывает", что сообщение M было подписано обладателем секретного ключа D, соответствующего ключу проверки подписи (N, E), т.е. авторизует сообщение.
Для разрешения споров между отправителем и получателем информации, связанных с возможностью искажения ключа проверки подписи (N, E), достоверная копия этого ключа выдается третьей стороне - арбитру и применяется им при возникновении конфликта.
Протокол работы пары абонентов сети общей связи с алгоритмом RSA выглядит так.

абоненты A и B генерируют независимо друг от друга пары простых чисел:

Pa,Qa и Pb,Qb

вычисляют произведение больших простых чисел:

Na,b = Pa,b * Qa,b

вычисляют ключи:

Ea,b и Da,b

числа Na,b и Ea,b помещаются в общедоступный справочник и получают статус открытых ключей;

числа Da,b сохраняются в качестве секретных ключей;

обмен сообщениями

Ca,b = M^Ea,b mоd(Na,b)

расшифрование

M = Ca,b^Da,b mоd(Na,b)

Формирование цифровой подписи:

подписывают и шифруют

Sa,b = M ^Da,b mоd(Na,b)

передают

Ca,b = M ^Ea,b mоd(Na,b)

расшифровывают

M = Сa,b^Da,b mоd(Na,b)

проверяют подлинность подписи

M = Sa,b ^Ea,b mоd(Na,b)

Устойчивость метода

Предполагая, что известны все параметры этого протокола кроме сохраняемых в секрете чисел D, мы должны оценить сложность их восстановления. Если известно разложение на множители числа N = P * Q, то по открытому ключу (N, E), секретный ключ E вычисляется легко.
Поэтому разложение N = P * Q должно также быть недоступным для потенциального злоумышленника. Нетрудно видеть, что после вычисления пары E, D знание множителей P, Q не нужно даже законным пользователям системы, т.е. они могут быть "забыты". Сложность их определения по числам N, E и является гарантией стойкости системы RSA.