Криптосистема 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) так как в настоящее время эффективного способа поиска сомножителей не существует.

Ниже описывается использование системы RSA для шифрования информации и создания цифровых подписей (практическое применение немного отличается).