Accueilretour

Systèmes modernes à clé publique

3. Le cryptage RSA (1)

Généralités

Stéganographie

Cryptanalyse

Littérature

Transpositions

Subs. monoα

Subs. polyα 1 - 2

One-time pad

DES 1 - 2

Clef publique

Knapsack

Diffie-Hellman

RSA 1 - 2

histoire

mathématiques

mise en place
chiffrage
déchiffrage

sécurité

exemple

signature

faiblesses

Grands noms

Références


 Voilà bien l'acronyme le plus connu de la cryptographie contemporaine ! Ronald Rivest, Adi Shamir et Leonard Adleman : trois chercheurs du MIT aux talents complémentaires qui ont fini par donner une réponse élégante au problème du cryptage asymétrique.

La trouvaille décisive est le fait d'un seul (Rivest), mais il a tenu à associer ses deux collègues à la publication début 1978 après de longues vérifications (la découverte proprement dite remontant à avril 1977). Adleman, à qui revenait la première place par ordre alphabétique, a souhaité que son nom figure en fin de liste. Il ne croyait pas au succès de l'article...

Pour l'histoire

La véritable paternité du système RSA ne revient pas en fait à ses découvreurs "officiels", mais à James Ellis et Clifford Cocks, qui  en 1969 travaillaient (en secret) pour le compte du renseignement Britannique.

retour

Les mathématiques du RSA

Revenons à nos héros Alice et Bob, toujours aussi soucieux de communiquer en sécurité.

mise en place du système

Alice souhaite recevoir des messages chiffrés en RSA.
  1. Elle choisit aléatoirement (c'est très important, voir plus loin) deux entiers premiers distincts p et q. Elle calcule ensuite

        n = p × q

    ainsi que son indicateur d'Euler :

        φ(n) = (p−1)(q−1).

  2. Elle choisit un une base d'exponentielle e sans facteur commun avec φ(n) :

        e∈]1, φ(n)[, e∧φ(n) = 1

  3. Elle diffuse (n, e) qui constituent sa clef publique.

  4. Elle détermine enfin l'inverse modulaire de e modulo φ(n) [1] (dont l'existence est assurée par l'étape 2.) :

        d = e−1 (mod. φ(n)).

    d est la clef secrète d'Alice.
Alice est maintenant prête à recevoir des messages cryptés.

retour

chiffrage

Bob souhaite transmettre le message M à Alice. Comme dans le cas de Diffie-Hellman, M est généralement un unique caractère transcrit en notation binaire. On suppose que M < n.

Il suffit à Bob de calculer

C = Me (mod. n)

et de transmettre le message chiffré C à Alice.

retour

déchiffrage

Alice reçoit C de la part de Bob. Elle calcule

M' = Cd (mod. n)

... et, miracle :

théorème : M' ≡ M (mod. n)

preuve. En effet, M' = Cd ≡ Med (mod. n). Or par construction de d (étape 4.), ed ≡ 1 (mod. φ(n)) ; écrivons ed = 1 + kφ(n). Alors :
M' ≡ M1+kφ(n) ≡ M × Mkφ(n) ≡ M × M(p−1)(q−1)k (mod. n)
     ≡ M × (Mp−1)(q−1)k (mod. n) ≡ M × (Mp−1)(q−1)k (mod. p) a fortiori (puisque p divise n).
Maintenant, selon le petit théorème de Fermat, Mp−1 ≡ 1 (mod. p) [2], donc M' ≡ M × 1(q−1)k (mod. p) ≡ M (mod. p). Mais p et q jouent le même rôle, donc de la même manière : M' ≡ M (mod. q). Enfin, comme p et q sont premiers distincts, a fortiori premiers entre eux : M' ≡ M (mod. pq), ce qui est bien le résultat cherché (pq = n).


Alice a ainsi pu reconstituer le message original de Bob.

retour

Sécurité du processus

On peut reconduire le même type de remarque qu'au sujet de Diffie-Hellman. Il est difficile d'inverser la "fonction à sens unique" exponentielle de base e si l'on ne connaît pas d -- la trappe -- et d est introuvable sans e. D'un autre côté, p et q (ainsi que φ(n) = (p−1)(q−1)) pourraient conduire à la détermination de d. La sécurité du RSA est ainsi liée à la difficulté de la factorisation des entiers. On estime que le RSA est aussi solide que ce problème de factorisation.

Quantitativement, un nombre de 140 chiffres est aujourd'hui impossible à factoriser en pratique. Le record de factorisation actuel, noté RSA-640, compte 193 chiffres. Il a été factorisé le 12 décembre 2009 lors d'un calcul parallèle équivalent à 2000 ans de calcul d'un ordinateur simple. C'est pourquoi l'organisation RSA recommande des clés de 200 a 600 chiffres, et estime qu'avec 2048 chiffres, la sécurité sera garantie jusqu'en 2030.

Il va de soi que l'exemple ci-dessous ne satisfait pas ces contraintes...

retour

Exemple

Alice opte pour p = 23 et q = 17 d'où n = 23 × 17 = 391 et φ(n) = 22 × 16 = 352.

Elle sélectionne en outre e = 47 comme base d'exponentielle. Elle publie n et e.

Elle en déduit d = e−1 (mod. φ(n)) = 15 (puisque 47 × 15 = 705 = 1 mod. 352).

Bob souhaite envoyer le message "X" à Alice (car il a de la suite dans les idées).

Le codage binaire de "X" est M = 88. Bob doit donc calculer donc Me = 8847 mod. 391. Comme lors de l'utilisation du protocole Diffie-Hellman, il procède par exponentiation rapide dans ℤ/nℤ (47 = 32 + 8 + 4 + 2 + 1) :
  • M2 = 882 = 7744 ≡ 315 mod. n, d'où M3 = M×M2 = 88×315 = 27720 ≡ 350 mod. n ;
  • M4 = 3152 = 99225 ≡ 302 mod. n, d'où M7 = M3×M4 = 350×302 = 105700 ≡ 130 mod. n ;
  • M8 = 3022 = 91204 ≡ 101 mod. n, d'où M15 = M7×M8 = 130×101 = 13130 ≡ 227 mod. n ;
  • M16 = 1012 = 10201 ≡ 35 mod. n (nécessaire uniquement pour accéder à M32) ;
  • M32 = 352 = 1225 ≡ 52 mod. n d'où finalement C = Me = M47 = M15×M32 = 227×52 = 11804 ≡ 74 mod. n.
C'est ce nombre qu'il transmet à Alice.

Alice reçoit le message chiffré C = 74 et doit donc former Cd = 7415 mod. 391. Elle procède de même (15 = 8 + 4 + 2 + 1) :
  • C2 = 742 = 5476 ≡ 2 mod. n, donc C3 = C×C2 = 74×2 = 148 mod. n ;
  • C4 = 22 = 4 mod. n, donc C7 = C3×C4 = 148×4 = 592 ≡ 201 mod. n ;
  • C8 = 42 = 16 mod. n et finalement Cd = C15 = C7×C8 = 16×201 = 3216 ≡ 88 mod. n = M.
Elle a ainsi déchiffré le message de Bob.

retour

Signature

Supposons qu'Alice veuille expédier un message M "signé" à Bob. Elle veut qu'il n'ait aucun doute sur sa provenance. Elle utilise une fonction de hachage H. Elle calcule h = H(M) et l'élève à la puissance de sa clef secrète d :

h' = hd (mod. n)

Elle envoie (M, h') à Bob (en chiffrant éventuellement cet envoi à l'aide de la clef publique de Bob, ce n'est pas le problème). Bob reçoit (et déchiffre, le cas échéant) (M, h'). Il élève ensuite h' à la puissance e (la clef publique d'Alice), obtenant

h = h' e (mod. n)

Il retrouve ainsi h et s'assure en calculant H(M) de sa bonne adéquation avec le message M.

Seule Alice connaît sa clef privée. Bob s'est ainsi assuré
  • de l'authenticité de l'expéditeur ;
  • de l'intégrité du message reçu.
Notons une caractéristique supplémentaire de cette signature : la non-répudiation. En effet, Alice ne peut plus nier a posteriori avoir envoyé le message.

retour

Faiblesses et attaques

Commençons par enfoncer quelques portes ouvertes :
  • si Me < n, le décryptage est trivial (il suffit de prendre la racine e-ième)... Donc le RSA est adapté au chiffrage de messages suffisamment longs -- mais ceci fournit à l'ennemi d'autant plus de matériel à cryptanalyser.
  • le RSA est très utilisé (il est p. ex. présent dans la norme SSL d'Internet). Donc, il y a beaucoup de clés publiques en circulation. Donc, il est crucial d'utiliser un générateur aléatoire efficace de nombres premiers ! Car en effet, si n = p × q et n' = p × q', un simple calcul de PGCD (grâce à l'algorithme d'Euclide) donne p !
Voyons maintenant deux bonnes raisons de ne pas utiliser d'exposants trop petits.
  • une remarque (Hastad 1988) montre que tout secret disparaît si quelqu'un envoie le même message crypté à e destinataires qui utilisent le même exposant e. Supposons que Bob connaisse e = 3 Alice (le veinard) qui utilisent les clés publiques (n1, e), (n2, e) et (n3, e). Il leur adresse le même message M, expédiant Ci = M3 mod ni à chaque Alice. L'ennemie Eve peut résoudre le système de congruences x ≡ Ci mod ni en utilisant le théorème des restes chinois, obtenant M3 mod (n1n2n3). Mais comme 0 < M3 < n1n2n3, elle obtient gratuitement M3, et donc M.
  • Plus subtilement, un article de 1998 (Boneh-Venkatesan) a montré que le RSA n'était pas équivalent à la factorisation en présence d'un petit exposant e.
En guise de parade partielle à ces faiblesses, l'utilisation du cryptosystème RSA est parfois assortie de "rembourrage" (padding) des messages, càd l'insertion de bits excédentaires selon un schéma approprié.

retour

Nous en arrivons au pire ennemi du RSA, les techniques de crible quadratique (page suivante).

Notes

[1]  Pour ceci, elle peut appliquer l'algorithme d'Euclide à e et (p−1)∨(q−1) (le PPCM de p−1 et q−1), ou le théorème des restes chinois, ce qui revient essentiellement au même.

[2]  en supposant M ≢ 0 (mod. p), sinon il n'y a rien à prouver