RSA est un système de chiffrage de données qui fut inventé en 1977 par trois informaticiens du MIT de Boston (USA) : Rivest, Shamir et Adleman (d'où le nom de l'invention).

Il repose sur un système de clés :

  • une publique connue de tous, en particulier de celui/celle qui veut chiffrer (on entend souvent crypter dans le langage courant, mais il s'agit d'un anglicisme !) des informations ;
  • une privée, qui n'est possédée que par le récepteur.

On choisit deux très grands nombres entiers premiers \(p\) et \(q\).
On calcule alors le module de chiffrement \(n = pq\), ainsi que \(\phi(n)=(p-1)(q-1)\), appelé indicatrice d'Euler de \(n\). On choisit ensuite \(e\) premier (sans diviseurs communs à part 1) avec \(\phi(n)\) (appelé module de chiffrement) ; on sait alors qu'il existe \(d\), appelé indice de déchiffrement, tel que \(\phi(n)\) divise \(ed\).
Le couple \((n,e)\) est la clé publique et \((n,d)\) est la clé privée.

L'intérêt du système est qu'un ordinateur normal aura un mal fou à « casser » \(n\) en \(p\) et \(q\), car le temps nécessaire croît exponentiellement avec la taille de \(p\) et \(q\).
Par exemple, pour casser une clé de longueur 512 bits en un temps raisonnable (moins d'une semaine), il faut faire travailler conjointement plusieus centaines d'ordinateurs, or, les clés font plutôt 1 024 ou 2 048 bits. Comme le temps croît exponentiellement avec la taille des clés, multiplier la longueur par 4 multiplie, pour un même nombre d'ordinateurs, le temps par \((e^{512})^3\).

Malheureusement (ou heureusement, tout dépend du point de vue) les ordinateurs du futur seront assez puissants pour y parvenir facilement, car il existe un algorithme d'attaque (l'algorithme de Shor) pour les ordinateurs quantiques qui casse \(n\) en un temps non exponentiel.