RSA et la cryptographie à clé publique
Partie 2 sur 4
3Fabriquer une paire de clés
Voici les cinq étapes, avec des nombres assez petits pour que vous puissiez les vérifier à la main (ou à la calculette). La figure 1 les résume.
- Choisir deux grands nombres premiers distincts, p et q, tenus secrets. Exemple : p = 61 et q = 53.
- Calculer le module
n = p × q. Ici n = 3 233. Ce nombre sera public. - Calculer
φ(n) = (p − 1) × (q − 1)= 60 × 52 = 3 120. Ce nombre doit rester secret : qui le connaît peut calculer la clé privée. - Choisir l’exposant public e, un nombre sans diviseur commun avec φ(n). Ici e = 17. Dans la pratique, on prend presque toujours e = 65 537 (qui vaut 216 + 1), choisi parce qu’il est premier et rend le calcul de chiffrement rapide.
- Calculer l’exposant privé d, l’inverse de e modulo φ(n). Ici d = 2 753, car 17 × 2 753 = 46 801 = 15 × 3 120 + 1.
On obtient :
- la clé publique est le couple (n, e) = (3 233 ; 17) ;
- la clé privée est l’exposant d = 2 753, ainsi que, selon les logiciels, p et q.
Une nuance : on appelle souvent « clé privée » le triplet (p, q, d). C’est exact dans l’esprit, mais en pratique les logiciels conservent d, p, q et quelques valeurs précalculées pour aller plus vite. Après avoir fabriqué la paire, p, q et φ(n) n’ont plus d’utilité pour la publication : il faut éviter qu’ils traînent dans une mémoire ou dans un fichier.
Dans la vraie vie, p et q sont des nombres d’environ 300 chiffres chacun (pour une clé « de 2 048 bits », ce qui est la taille de n). Pour les trouver, le logiciel tire au hasard un grand nombre impair et vérifie, par des tests probabilistes très rapides, s’il est premier ; les nombres premiers sont assez fréquents pour que quelques centaines d’essais suffisent. Tout repose donc sur un bon tirage au hasard : si le tirage est prévisible, un attaquant peut refaire le même tirage (voir la partie 8).
Pour s’exercer
Exercice 3 : pourquoi il ne faut pas garder φ(n)
Avec n = 3 233 et e = 17, un curieux apprend par erreur que φ(n) = 3 120. Que peut-il en faire ?
Voir la réponse
Il peut calculer d, l’inverse de 17 modulo 3 120, et obtient 2 753 : la clé privée. Connaître φ(n) équivaut à connaître p et q. C’est pour cette raison que p, q et φ(n) sont détruits après la fabrication de la clé et que seule la clé privée complète est conservée, dans un endroit protégé.
4Chiffrer et déchiffrer
Reprenons les deux personnages classiques de la cryptographie : Alice (qui possède la paire de clés) et Bob (qui veut lui écrire). Un « message » est ici un nombre M compris entre 0 et n − 1 : n’importe quel texte peut être converti en nombres, comme l’explique l’article sur les caractères. Prenons M = 65 (qui est le code de la lettre « A »).
4.1Bob chiffre
Bob se procure la clé publique d’Alice (3 233 ; 17). Il calcule c = Me mod n, c’est-à-dire 6517 modulo 3 233. Le nombre 6517 est gigantesque, mais en réduisant à chaque multiplication, tous les calculs restent petits. Le résultat est c = 2 790. Bob envoie 2 790 à Alice ; qu’un curieux le lise en chemin ne change rien.
4.2Alice déchiffre
Alice calcule M = cd mod n, c’est-à-dire 2 7902 753 modulo 3 233. Le résultat est 65 : le message d’origine. Un curieux qui connaît n = 3 233 et e = 17 et voit passer 2 790 devrait trouver d. Pour cela il lui faut φ(n), donc p et q, donc factoriser 3 233. Ici c’est évident, mais avec un n de 617 chiffres (2 048 bits), c’est inaccessible.
4.3Et si le message est trop long ?
Un message M doit être plus petit que n. Avec une clé de 2 048 bits, cela représente environ 256 octets, soit à peu près 256 lettres. On conseille parfois de « découper le message en morceaux » plus petits que p et q. Ce découpage naïf n’est pas une bonne méthode (voir la partie 7) : on n’applique RSA qu’à de très petites données, typiquement une clé de 16 à 32 octets, pas à des documents.
5Pourquoi ça marche
On peut se contenter de vérifier que l’exemple tombe juste, mais la raison est jolie et courte. Après deux opérations, Alice obtient (Me)d = Me × d mod n. Or e et d ont été choisis pour que e × d = 1 + k × φ(n) pour un certain entier k (dans l’exemple : 46 801 = 1 + 15 × 3 120). On a donc :
Me × d = M × (Mφ(n))k
Le théorème d’Euler dit que Mφ(n) = 1 mod n, donc le tout vaut M × 1k = M. Les deux opérations s’annulent : ce qui a été fermé par l’une se rouvre par l’autre.
On pose parfois comme condition que « M soit premier avec n ». Cette condition vient de ce que le théorème d’Euler s’énonce ainsi. En réalité, comme n est le produit de deux nombres premiers distincts, le calcul reste juste même si M a un facteur commun avec n. Mais cette situation est si rare, avec de grands nombres, qu’elle n’a pas de conséquence pratique. Le vrai problème n’est pas là, c’est celui du bourrage (partie 7).
Notez enfin une symétrie utile : on peut échanger les rôles. Si Alice calcule Md mod n avec sa clé privée, n’importe qui peut retrouver M en calculant (Md)e mod n avec la clé publique. Ce n’est plus du secret (tout le monde peut lire), mais cela prouve que l’auteur possède la clé privée : c’est le principe de la signature. Avec les nombres ci-dessus, signer le nombre 123 donne 1232 753 mod 3 233 = 2 746, et la vérification 2 74617 mod 3 233 redonne 123.