Le protocole RSA

Le protocole RSA

Structures algébriques usuelles · Niveau ★★★ — approfondissement · niveau 3 (difficile)

Énoncé

Soient $p \neq = q$ premiers, $n = pq$ , et $e$ premier avec $φ (n) = (p - 1) (q - 1)$ ; soit $d$ l'inverse de $e$ modulo $φ (n)$ . Montrer que pour tout message $m$ premier avec $n$ : $(m^{e})^{d} \equiv m [n],$ et dérouler le protocole sur $p = 3$ , $q = 11$ , $e = 3$ , $m = 4$ .

Corrigé

Par construction $e d = 1 + k φ (n)$ pour un $k \in N$ . Le théorème d'Euler ( $m \land n = 1$ ) donne $m^{φ (n)} \equiv 1 [n]$ , d'où $(m^{e})^{d} = m^{1 + k φ (n)} = m (m^{φ (n)})^{k} \equiv m [n] .$ Le chiffrement $m \mapsto m^{e} [n]$ (clef publique $(n, e)$ ) est inversé par $c \mapsto c^{d} [n]$ (clef privée $d$ ) — et calculer $d$ exige $φ (n)$ , donc la factorisation de $n$ : toute la sécurité tient à la difficulté de factoriser.

Exemple : $n = 33$ , $φ (33) = 2 \times 10 = 20$ , $e = 3$ ( $3 \land 20 = 1$ ), $d = 7$ (car $3 \times 7 = 21 \equiv 1 [20]$ ). Chiffrement de $m = 4$ : $c = 4^{3} = 64 \equiv 31 [33]$ . Déchiffrement : $31 \equiv - 2 [33]$ , donc $c^{7} \equiv (- 2)^{7} = - 128 \equiv - 128 + 4 \times 33 = 4 [33] : m est retrouv e ˊ . ✓$ (Le RSA « miniature » entrevu en première année repose donc exactement sur Euler — c'est-à-dire sur Lagrange dans $(Z / n Z)^{\times}$ : trois chapitres d'algèbre dans une carte bancaire.)

Énoncé

Corrigé

Exercices semblables