Principe du chiffrement RSA : énoncé (Maths expertes)
Principe du chiffrement RSA
Soient $p$ et $q$ deux nombres premiers distincts, $n = pq$, et $e$, $d$ deux entiers naturels non nuls tels que $ed \equiv 1 \;[(p-1)(q-1)]$. Alors pour tout entier $m$ : $$m^{ed} \equiv m \;[n].$$ On chiffre un message $m$ (avec $0 \leqslant m < n$) en calculant le reste $c$ de $m^e$ modulo $n$. On déchiffre en calculant le reste de $c^d$ modulo $n$, qui redonne $m$. Le couple $(n, e)$ est public, $d$ est secret.
Démonstration : Principe du chiffrement RSA
Preuve
On écrit $ed = 1 + k(p-1)(q-1)$ avec $k \in \mathbb{N}$.
- Si $p \nmid m$, le petit théorème de Fermat donne $m^{p-1} \equiv 1 \;[p]$, donc $m^{ed} = m \times \left(m^{p-1}\right)^{k(q-1)} \equiv m \;[p]$.
- Si $p \mid m$, alors $m \equiv 0 \;[p]$ et $m^{ed} \equiv 0 \equiv m \;[p]$.
Dans tous les cas, $p \mid m^{ed} - m$. De même, $q \mid m^{ed} - m$. Comme $p$ et $q$ sont des nombres premiers distincts, ils sont premiers entre eux, donc $pq \mid m^{ed} - m$ (corollaire de Gauss).
Un RSA miniature
$p = 5$, $q = 11$, $n = 55$, $(p-1)(q-1) = 40$. On choisit $e = 3$ ; on cherche $d$ tel que $3d \equiv 1 \;[40]$ : $3 \times 27 = 81 = 2 \times 40 + 1$, donc $d = 27$.
Chiffrement de $m = 7$ : $7^3 = 343 = 6 \times 55 + 13$, donc $c = 13$.
Déchiffrement : on calcule $13^{27}$ modulo $55$. $13^2 = 169 = 3 \times 55 + 4$, donc $13^{27} = 13 \times (13^2)^{13} \equiv 13 \times 4^{13} = 13 \times 2^{26}$. Or $2^{10} = 1024 = 18 \times 55 + 34$ et $34^2 = 1156 = 21 \times 55 + 1$, donc $2^{20} \equiv 1 \;[55]$. Ainsi $2^{26} \equiv 2^6 = 64 \equiv 9 \;[55]$ et $13^{27} \equiv 13 \times 9 = 117 \equiv 7 \;[55]$. On retrouve bien $m = 7$.
Sécurité
Connaître $d$ revient en pratique à connaître $p$ et $q$. La sécurité du RSA repose sur la difficulté de factoriser $n$ lorsque $p$ et $q$ ont plusieurs centaines de chiffres, alors que les calculs de puissances modulo $n$ restent rapides. Le chiffrement affine, lui, se casse facilement : il n'y a que $12 \times 26 = 312$ clés possibles. Le RSA n'est pas un attendu du programme, il illustre l'usage du petit théorème de Fermat.