Spécialité NSI - Année 2024 - 2025

Le chiffrement RSA est basé sur l'arithmétique modulaire. Faire des calculs modulo un entier \(n\), c'est ne garder que le reste de la division euclidienne par \(n\).

Le fait que 15 soit égal à 1 modulo 7 (car \(15 = 2 \times 7+1\)) s'écrira \(15\equiv1[7]\).

De même, \(10\equiv3[7]\), \(25\equiv4[7]\), \(32\equiv2[10]\), etc.

Étape 1

Alice choisit 2 grands nombres premiers \(p\) et \(q\). Dans la réalité, ces nombres seront vraiment très grands (plus de 100 chiffres). Dans notre exemple, nous prendrons \(p = 3\) et \(q = 11\).

Étape 2

Alice multiplie ces deux nombres \(p\) et \(q\) et obtient ainsi un nombre \(n\).

Il est très facile pour Alice de calculer \(n\) en connaissant \(p\) et \(q\), mais il extrêmement difficile pour Marc de faire le travail inverse : trouver \(p\) et \(q\) en connaissant \(n\) prend un temps exponentiel avec la taille de \(n\).

C'est sur cette difficulté (appelée difficulté de factorisation) que repose la robustesse du système RSA.

Étape 3

Alice choisit un nombre \(e\) qui doit être premier avec \((p-1)(q-1)\). On note \(\phi(n)\) le nombre \((p-1)(q-1)\).

Dans notre exemple, \((p-1)(q-1) = 20\), Alice choisit donc \(e = 3\), (mais elle aurait pu aussi choisir 7, 9, 13...).

Le couple \((e, n)\) sera la clé publique d'Alice. Elle la diffuse à qui veut lui écrire.

Dans notre exemple, la clé publique d'Alice est \((3, 33)\).

Étape 4

Alice calcule maintenant sa clé privée : elle doit trouver un nombre d qui vérifie l'égalité \(ed\equiv1[\phi(n)]\).

Dans notre exemple, comme \(7 \times 3\equiv1[20]\), ce nombre \(d\) est égal à 7.

En pratique, il existe un algorithme simple (algorithme d'Euclide étendu) pour trouver cette valeur \(d\), appelée inverse de e.

Le couple \((d, n)\) sera la clé privée d'Alice. Elle ne la diffuse à personne.

Dans notre exemple, la clé privée d'Alice est \((7, 33)\).

Étape 5

Supposons que Bob veuille écrire à Alice pour lui envoyer le nombre 4. Il possède la clé publique d'Alice, qui est \((3, 33)\).

Il calcule donc \(4^3\) modulo 33, qui vaut 31. C'est cette valeur 31 qu'il transmet à Alice.

\(4^3\equiv31[33]\)

Si Marc intercepte cette valeur 31, même en connaissant la clé publique d'Alice \((3,33)\), il ne peut pas résoudre l'équation \(x^3\equiv31[33]\) de manière efficace.

Étape 6

Alice reçoit la valeur 31.

Il lui suffit alors d'élever 31 à la puissance 7 (sa clé privée), et de calculer le reste modulo 33 :

\(31^7 = 27512614111\)

\(27512614111\equiv4[33]\)

Elle récupère la valeur 4, qui est bien le message original de Bob.

Comment ça marche ? Grâce au Petit Théorème de Fermat, on démontre (voir ici) assez facilement que \(M^{ed}\equiv{M[n]}\).

Il faut remarquer que \(M^{ed} = M^{de}\). On voit que les rôles de la clé publique et de la clé privée sont symétriques : un message chiffré avec la clé publique se déchiffrera en le chiffrant avec la clé privée, tout comme un message chiffré avec la clé privée se déchiffrera en le chiffrant avec la clé publique.