10. Алгоритм rsa.

RSA – криптографическая система открытого ключа, обеспечивающая такие механизмы защиты как шифрование и цифровая подпись (аутентификация – установление подлинности). Криптосистема RSA разработана в 1977 году и названа в честь ее разработчиков Ronald Rivest, Adi Shamir и Leonard Adleman.

Алгоритм RSA работает следующим образом: берутся два достаточно больших простых числа p и q и вычисляется их произведение n = p*q; n называется модулем. Затем выбирается число e, удовлетворяющее условию 1< e < (p - 1)*(q - 1) и не имеющее общих делителей кроме 1 (взаимно простое) с числом (p - 1)*(q - 1). Затем вычисляется число d таким образом, что (e*d - 1) делится на (p - 1)*(q – 1).

• e – открытый (public) показатель

• d – частный (private) показатель.

• (n; e) – открытый (public) ключ

• (n; d). – частный (private) ключ.

Делители (факторы) p и q можно либо уничтожить либо сохранить вместе с частным (private) ключом.

Если бы существовали эффективные методы разложения на сомножители (факторинга), то, разложив n на сомножители (факторы) p и q, можно было бы получить частный (private) ключ d. Таким образом надежность криптосистемы RSA основана на трудноразрешимой – практически неразрешимой – задаче разложения n на сомножители (то есть на невозможности факторинга n) так как в настоящее время эффективного способа поиска сомножителей не существует.

Шифрование

Предположим, Алиса хочет послать Бобу сообщение M. Алиса создает зашифрованный текст С, возводя сообщение M в степень e и умножая на модуль n: C = M^**e* (mod n), где e и n – открытый (public) ключ Боба. Затем Алиса посылает С (зашифрованный текст) Бобу. Чтобы расшифровать полученный текст, Боб возводит полученный зашифрованный текст C в степень d и умножает на модуль n: M = c**^d*(mod n); зависимость между e и d гарантирует, что Боб вычислит M верно. Так как только Боб знает d, то только он имеет возможность расшифровать полученное сообщение.

Цифровая подпись

Предположим, Алиса хочет послать Бобу сообщение M , причем таким образом, чтобы Боб был уверен, что сообщение не было взломано и что автором сообщения действительно является Алиса. Алиса создает цифровую подпись S возводя M в степень d и умножая на модуль n: S = M**^d*(mod n), где d и n – частный ключ Алисы. Она посылает M и S Бобу.

Чтобы проверить подпись, Боб возводит S в степень e и умножает на модуль n: M = S**^e*(mod n), где e и n – открытый (public) ключ Алисы.

Таким образом шифрование и установление подлинности автора сообщения осуществляется без передачи секретных (private) ключей: оба корреспондента используют только открытый (public) ключ своего корреспондента или собственный частный (private) ключ. Послать зашифрованное сообщение и проверить подписанное сообщение может любой, но расшифровать или подписать сообщение может только владелец соответствующего частного (private) ключа.

Скорость работы алгоритма RSA

Как при шифровании и расшифровывании, так и при создании и проверке подписи алгоритм RSA по существу состоит из возведения в степень, которое выполняется как ряд умножений.

В практических приложениях для открытого ключа обычно выбирается относительно небольшой показатель, а зачастую группы пользователей используют один и тот же открытый показатель, но каждый с различным модулем. Если открытый показатель неизменен, то вводятся некоторые ограничения на главные сомножители (факторы) модуля. При этом шифрование данных идет быстрее расшифровывания, а проверка подписи быстрее, чем подписание. Если k — количество битов в модуле, то в обычно используемых для RSA алгоритмах количество шагов, необходимых для выполнения операции с открытым ключом, пропорционально второй степени k, количество шагов для операций частного ключа — третьей степени k, количество шагов для операции создания ключей — четвертой степени k.

Методы “быстрого умножения” (например, методы, основанные на быстром преобразовании Фурье (Fast Fourier Transform, FFT)) выполняются гораздо меньшим количеством шагов. Тем не менее, они не получили широкого распространения из-за сложности программной реализации, а также потому, что с распространенными размерами ключей они фактически работают медленнее. Однако производительность и эффективность приложений и оборудования, реализующих алгоритм RSA, быстро увеличиваются.