Алгоритм rsa (Rivest, Shamir, Adleman)

Алгоритм RSA является одним из первых алгоритмов шифрования с открытым ключом, который нашел практическое применение. Он был предложен в 1978 г. тремя авторами: Рональдом Райвестом (Ronald Rivest), Ади Шамиром (Adi Shamir) и Леонардом Адлерманом (Leonard M. Adlerman), и получил название по первым буквам их фамилий.

Алгоритм RSA использует следующий факт: нахождение больших (например, 100-битных) простых чисел в вычислительном отношении осуществляется легко, однако разложение на множители произведения двух таких чисел в вычислительном отношении представляется невыполнимым.

Алгоритм RSA принят в качестве следующих международных стандартов: ISO/IEC/DIS 9594-8 и X.509. В настоящее время Международная сеть электронного перечисления платежей SWIFT требует от банковских учреждений, пользующихся ее услугами, применения именно этого алгоритма криптографического преобразования информации.

Алгоритм работает так 2.2:

1. Отправитель выбирает два очень больших простых числа P и Q и вычисляет два произведения N = PQ и M =

=(P-1)(Q-1).

2. Затем он выбирает случайное целое число D, взаимно простое с M, и вычисляет E, удовлетворяющее условию DE =

= 1 mod M.

3. После этого он публикует D и N как свой открытый ключ шифрования, сохраняя E как закрытый ключ.

4. Если S — сообщение, длина которого, определяемая по значению выражаемого им целого числа, должна быть в интервале (1, N), то оно превращается в шифровку возведением в степень D по модулю N и отправляется получателю S₁ = S^D mod N.

5. Получатель сообщения расшифровывает его, возводя в степень E по модулю N, так как S = S₁^E mod N = S^DE mod N.

Таким образом, открытым ключом служит пара чисел N и D, а секретным ключом число E.Смысл этой системы шифрования основан на так называемой малой теореме Ферма, которая утверждает, что при простом числе P и любом целом числе K, которое меньше P, справедливо тождество K^P-1 = 1 mod P. Эта теорема позволяет определить, является ли какое-либо число простым или составным.