Что такое RSA

RSA (авторы: Rivest, Shamir и Alderman) это система с открытым ключом (public-key) предназначенная как для шифрования, так и для аутентификации была разработана в 1977 году. Она основана на трудности разложения очень больших целых чисел на простые сомножители.

RSA очень медленный алгоритм. Для сравнения, на програмном уровне DES по меньше мере в 100 раз быстрее RSA, на апаратном аж в 1,000-10,000 раз, в зависимости от выполнения.

RSA алгоритм:

1. Берутся два очень больших целых числа P и Q и находятся N=PQ и M=(P-1)(Q-1)
2. Выбирается случайное целое число D, взаимно простое с M и вычисляется E=(1 MOD M)/D
3. Потом публикуется D и N как открытый ключ, E сохраняется в тайне.
4. Если S - сообщение, длина которого, определяемая по значению выражаемого им целого числа, должна быть в интервале (1,N), то оно превращается в шифровку возведением в степень D по модулю N и отправляется получателю S'=S^D MOD N
5. Получатель сообщения расшифрорвывает его, возведя в степень E (число E ему уже известно) по модулю N, т.к. S=(S'^E MOD N)=S^(DE) MOD N