Описание алгоритма RSA

RSA - криптографическая система с открытым ключом, разработанная в 1977 году Ривестом (R. Rivest), Шамиром (A.Shamir) и Адлеманом (L. Adleman), за­главные буквы фамилий которых и со­ставили ставшую именем алгоритма аб­бревиатуру.

Работает следующим образом. Берутся два достаточно боль­ших (не менее 60 десятичных знаков) простых числа p и q, и вычисляется их произведение n = pq. Далее выбирает­ся число e (экспонента шифрования), удовлетворяющее условию: 1< e < (p -1)(q - 1) и e не имеет общих делителей, кроме 1, с числом (p - 1)(q - 1).

Затем вычисляется число d (экспо­нента расшифрования) таким образом, что (ed - 1) делится на (p - 1)(q - 1) без остатка. Пара чисел (n, e) - объявляется от­крытым ключом, a d становится секрет­ным ключом. Делители p и q можно либо уничтожить, либо сохранить вместе с секретным ключом.

В качестве исходных текстов х берут­ся натуральные числа, удовлетворяю­щие неравенству 1<=х<=п-1. Шифрова­ние заключается в вычислении остатка от деления на n числа X^е В результате получаем число y, являющееся шифротекстом. Расшифрование осуществляется применением к числу y такого же алго­ритма с заменой экспоненты шифрова­ния е на экспоненту расшифрования d.

Стойкость этой криптографической системы определяется сложностью за­дачи разложения больших чисел на простые множители. До сих пор неиз­вестны эффективные алгоритмы реше­ния этой задачи, что и обеспечивает вы­сокую практическую стойкость системы RSA.

Собственно цифровая подпись на основе системы RSA может быть органи­зована так. Абонент А, составляющий электронный документ х для пересылки его абоненту Б, шифрует х с помощью секретного ключа d, полу­чая таким образом шифротекст y. Затем он пересылает пару (x, y) абоненту Б. Абонент Б расшифровывает y с помо­щью открытого ключа (n,e) абонента А и сравнивает полученный результат с x. Если они равны, абонент Б убеждается в том, что документ отправлен абонен­том А, а сам абонент А не может отка­заться от авторства, т.к. его секретный ключ соответствует известному публич­ному ключу и подбор секретного ключа по открытому практически невозможен.

Дата добавления: 2013-12-13