Общее описание
Первым конкретным примером
системы ОШ была предложенная в 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 —> CDmоd(N)=(ME)Dmоd(N)=Mmоd(N)=M
В качестве открытого ключа
выступает пара чисел (N, E), а в качестве
секретного ключа — число D.
Электронная подпись
Система
электронной подписи RSA получается при
"смене мест" ключей E и D.
Подпись сообщения:
M —> M D
mоd (N) = S
Проверка подлинности подписанного
сообщения [M,S]:
M = S E mо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.
