On appellera Marie la personne qui désire recevoir un message codé, et Patrick la personne qui envoie le message.
Marie choisit deux grands entiers naturels premiers p et q (d'environ 100 chiffres chacun ou plus) et fait leur produit n = pq. Puis elle choisit un entier E tel que E soit premier avec (p - 1)(q - 1). Enfin, elle publie dans un annuaire par exemple l'information (R.S.A., n, E).
Patrick veut donc envoyer un message à Marie. Il cherche dans l'annuaire le système de codage et la clé de chiffrement qu'elle a publiés. Il sait maintenant qu'il doit utiliser le système R.S.A. avec les deux entiers n et E (prenons par exemple n = 1073 = 29 x 37 et E = 5, premier avec 28 x 36). Il transforme en chiffre son message en remplaçant par exemple chaque lettre par son rang dans l'alphabet.
Au tableau
devient : 01 21 20 01 02 12 05 01 21
.
Puis il le découpe en tronçons de même longueur représentant chacun un nombre plus petit que n.
Son message devient : 012 120 010 212 050 121
.
Il élève ensuite chaque tronçon B à la puissance E et appelle C le reste de la division euclidienne BE par n. C constitue un tronçon du message codé que Patrick envoie tel quel à Marie.
Le message codé est : 969 589 211 788 553 544
.
Marie calcule à partir de p et q qu'elle a gardés secrets la clé D de déchiffrage. Celle-ci est donnée par la formule DE = 1 mod (p - 1)(q - 1). Ici, D = 605 par exemple. Puis elle élève chacun des tronçons C du message codé à la puissance D et retrouve B en prenant le reste de la division euclidienne de CD par n.
Elle retrouve : 012 120 010 212 050 121
.
Puis en groupant les chiffres deux par deux et en remplaçant les nombres ainsi obtenus par les lettres correspondante, elle sait enfin qu'elle doit aller au tableau, sans que personne d'autre ne soit au courant.
L'efficacité du système R.S.A. repose sur le fait qu'à l'heure actuelle il est pratiquement impossible de retrouver p et q à partir de n si celui-ci est très grand. Marie est donc la seule à pouvoir calculer D. De plus, comme elle n'a jamais à transmettre les entiers p et q, le risque que Paul ou Pierre les interceptent est nul.