La méthode de cryptographie RSA a été inventée en 1977 par Ron Rivest, Adi Shamir et Len Adleman, à la suite de la découverte de la cryptographie à clé publique par Diffie et Hellman. Le RSA est encore le système cryptographique à clé publique le plus utilisé de nos jours. Il est intéressant de remarquer que son invention est fortuite : au départ, Rivest, Shamir et Adleman voulaient prouver que tout système à clé publique possède une faille.

1. Création des clés : Bob crée 4 nombres p,q, e et d :
   • p et q sont deux grands nombres premiers distincts. Leur génération se fait au hasard, en utilisant un algorithme de test de primalité probabiliste.
   • e est un entier premier avec le produit (p-1)(q-1).
   • d est tel que ed=1 modulo (p-1)(q-1). Autrement dit, ed-1 est un multiple de (p-1)(q-1). On peut fabriquer d à partir de e, p et q, en utilisant l'algorithme d'Euclide.
2. Distribution des clés : Le couple (n,e) constitue la clé publique de Bob. Il la rend disponible par exemple en la mettant dans un annuaire. Le couple (n,d) constitue sa clé privée. Il la garde secrète.
3. Envoi du message codé : Alice veut envoyer un message codé à Bob. Elle le représente sous la forme d'un ou plusieurs entiers M compris entre 0 et n-1. Alice possède la clé publique (n,e) de Bob. Elle calcule C=M^e mod n. C'est ce dernier nombre qu'elle envoie à Bob.
4. Réception du message codé : Bob reçoit C, et il calcule grâce à sa clé privée D=C^d (mod n). D'après un théorème du mathématicien Euler, D=M^de=M (mod n). Il a donc reconstitué le message initial.

Et encore, dans la cryptographie expliquée...

• La cryptographie à clé publique.
• Discussion sur la sécurité du système RSA.
• L'algorithme d'Euclide étendu, et son application à la génération des clés RSA.
• Le plan de la partie : Méthodes modernes de cryptographie.