L'algorithme RSA

Matthias VIRY

Ce qui fait la force de cet algorithme, c'est avant tout sa simplicité. Comme nous allons le voir, il est basé sur la théorie de congruences et sur la factorisation des grands nombres entiers, ce qui rend cet algorithme extrêmement calculatoire mais facile à assimiler. Pour illustrer le fonctionnement des algorithmes à clé publique comme RSA, nous allons imaginer une situation dans laquelle 3 personnages vont intervenir :

• Jacques sera la personne cherchant à envoyer un message confidentiel.

• Bill sera l'unique personne qui doit pouvoir décrypter le message de Jacques.

• Boris lui mettra tous les moyens en œuvre pour intercepter et lire le message de Jacques.

Le principe des algorithmes à clé publique est assez simple. Le problème majeur des cryptages classiques, c'est que la personne qui crypte le message doit fournir à son destinataire le moyen de le décrypter. Si on prend pour exemple l'algorithme de Jules César, il faut que le centurion sache de combien de lettres il faudra qu'il décale l'ordre de l'alphabet pour comprendre ce qu'a voulu dire Jules. C'est là où se situe le problème. D'une façon ou d'une autre il va bien falloir communiquer par des voies par toujours très sûres, la façon de décoder le message. Et c'est précisément à ce moment là, qu'un éventuel espion peut intervenir pour s'emparer du code de décryptage.

Les algorithmes à clé publique présentent l'avantage de ne pas avoir ce défaut. Je veux dire par-là que la personne qui crypte son message ne sait pas comment le décrypter mais seule la personne à qui est destiné le message sait comment le déchiffrer. Exemple : Pour coder son message, Jacques va utiliser ce que l'on va appeler par la suite la clé publique de Bill. La clé publique est un ensemble de lettres et de chiffres qui vont permettre à quiconque veut envoyer des messages confidentiels à Bill de les crypter. Cela veut dire que tout le monde peut connaître cette clé publique, on s'en fout ce qui compte, c'est que c'est qu'elle permet de crypter des messages uniquement pour Bill. Et il n'y a que Bill qui détient ce que l'on appelle la clé privée et qui pourra servir à déchiffrer ce qui à été codé avec sa clé publique. Il n'y a donc à aucun moment transmission du moyen de décrypter.

Donc Jacques a la clé publique de Bill. Il écrit alors son message avec son transportable et en quelques cliques de "bulot" passe à la "moulinette" la clé publique de Bill et ressort non pas avec un gros "coin !!! ", mais avec un fichier totalement incompréhensible, même pour lui. Il "pute on zizo" son modem qu'il a pour 7 ans et hop! il envoie son fichier à l'adresse Bill@WhiteHouse.Gov. Mais au même moment, grâce à ses écoutes secrètes, Boris intercepte le Mail de Jacques. Mais pas de chance, Boris ne comprend que le russe et se demande en quelle langue est rédigé ce message. Il met alors ses meilleurs agents sur le coup et pendant ce temps, quelque part aux Etats Unis, Bill reçoit tranquillement son mail qu'il va de ce pas décrypter en trois coups de "mouse" grâce à sa clé privée.

Voilà comment fonctionne de façon abstraite un algorithme à clé publique.  Maintenant nous allons entrer dans le vif du sujet. RSA est basé sur 2 principes mathématiques fondamentaux : la factorisation des grands entiers et l'arithmétique des congruences. Mais déjà là, je sens qu'il y en a qui décrochent. Rassurez-vous, j'ai seulement dit cela pour les Matheux, qui, s'ils désirent vraiment entrer dans l'intimité de cet algorithme, devront lire le superbe ouvrage : "Cryptographie : méthodes et pratique" aux éditions Thomson Publishing. Je vous épargnerai donc les discours sur de magnifiques notions mathématiques qui sont cachées derière cet algorithme.

Nous allons maintenant voir en détails la façon de calculer les clés publiques et privées et la façon de crypter et décrypter des messages. Reprenons notre exemple : Pour pouvoir communiquer sa clé publique, Bill a du la calculer. Comment s'y est-il pris ?

1^ère Etape : La base de l'algorithme RSA, c'est le nombre n. Ce nombre doit être le produit de deux nombres premiers p et q, très grands et ayant sensiblement le même nombre de chiffres. Pourquoi ?. La raison en est simple. La puissance du cryptage RSA est basée sur la difficulté de factoriser un grand entier. En bref, si un jour quelqu'un arrive à factoriser le n qui a servi à constituer vos clés, c'est à dire à découvrir les nombres p et q, alors il n'aura aucun mal à reconstituer votre clé privée... C'est pour cela que l'on choisit des nombres premiers p et q d'environ 100 chiffres, pour rendre la factorisation hors de portée, même des meilleurs ordinateurs. Pour notre exemple, Bill vous simplifie la vie, il va choisir :
  p = 47   q = 71   n = 47 x 71 = 3337 
Il est très important de garder secret ces deux nombres p et q. Eux seuls garantissent la sécurité de votre cryptage. En aucun cas ils ne doivent être conservés après le calcul de vos clés. D'ailleurs la plupart des logiciels du marché les choisissent pour vous et ne vous les communiquent jamais. Ils ne servent qu'aux calculs des clés.

2^ème Etape : Une fois n calculé, Bill cherche à déterminer la fonction d'Euler Phi associée à n avec la formule : Phi = ( p - 1 ) x ( q - 1 )   Phi = 46 x 70 = 3220
Pour la petite histoire, la fonction d'Euler Phi donne le nombre de nombres qui sont relativement premiers avec n et inférieurs à n. On remarquera que si n est un nombre premier comme 7, la fonction d'Euler Phi(7) = (7 - 1) = 6. Plus généralement, si n est le produit de k nombres premiers noté n_i, la fonction d'Euler Phi(n) = (n₁ - 1) (n₂ - 1)...(n_i - 1)...(n_k - 1). Mais cette théorie ne nous sera pas utile, il faut simplement que Bill choisisse sa clé publique qui est le nombre e compris entre 2 et la fonction d'Euler Phi associée à n,  et qui soit premier relativement à Phi. Pour poursuivre notre exemple, nous allons prendre : e = 79

3^ème Etape : Il reste à calculer la clé privée. Et c'est à partir d'ici que cela devient un peu plus délicat. En effet, si l'on voulait aller au bout des choses, cela impliquerait l'utilisation de notions mathématiques relativement pointues. Je vais essayer de vous éviter cela. En gros, pour calculer la clé privée d, il faut résoudre l'équation suivante : d = e^-1 mod ( Phi ) qui provient de la relation :  ed = -1 mod ( Phi ). En effet, c'est cette dernière relation qui garantit la bijectivité du cryptage. Pour déterminer d on va utiliser l'algorithme d'Euclide étendu qui sera décrit un peu plus loin. On obtient alors :   d = e^-1 mod ( Phi )   d = 79^-1 mod ( 3220 )   d = 1019 
Et voilà, Bill possède maintenant toutes les clés nécessaires au cryptage des messages qui lui seront destinés. Il faut maintenant qu'il conserve précieusement sa clé privée d, et surtout qu'il oublie à tous jamais les deux nombres p et q qui ont servi aux calculs. Il ne lui reste plus qu'à diffuser sa clé publique e et le nombre n. Et nous allons voir maintenant comment grâce à ces clés, nous allons réaliser le cryptage d'un message ainsi que le décryptage.
Comme vous avez pu le constater, RSA est un algorithme qui, sur le principe, est relativement simple. La seule difficulté réside dans le fait que pour atteindre un niveau de sécurité optimal, il faut que le nombre n soit suffisamment grand. On estime aujourd'hui qu'une clé constituée de 200 chiffres est quasi inviolable. Or, pour arriver à réaliser un logiciel capable de crypter avec de si grandes clés, il faut réécrire toutes les unités de calcul sur les grands entiers et trouver des algorithmes rapides et efficaces...  Ce n'est pas une mince affaire !. ( Je rappelle qu'en C++, le type d'entier le plus grand n'est constitué que de 10 chiffres... ). Je vais bientôt écrire une page qui vous proposera quelques solutions et quelques algorithmes de calculs. Mais pour le moment, voyons comment nous allons pouvoir coder et décoder les messages avec nos précieuses clés :

Le Cryptage
Bill a donc mis à disposition sa clé publique e et n sur sa page Web. Jacques qui veut lui envoyer un message "Top Secret", se connecte sur la page de Bill à www.billpages.gov puis prend la clé publique e et le n de Bill. Il utilise alors son transportable pour crypter son message de la façon suivante :
Il convertit son message alphanumérique en une suite de nombres ( facile avec les codes ASCII ). Ce qui lui donne, par exemple, un message de la forme :  m = 688232687966668 
Il va alors le découper son message en morceaux de taille inférieure à celle du petit n de Bill avec lequel il va devoir crypter. Ce qui le conduit donc à faire des paquets de 3 chiffres car n en avait 4.
  m₁ = 688   m₂ = 232   m₃ = 687   m₄ = 966   m₅ = 668   
Jacques crypte alors chaque petit bloc de message à l'aide de la formule suivante : c_i = m_i^e mod n 
Ce qui lui donne (de tête...) : c₁ = 688⁷⁹ mod 3337 = 1570   c1 = 1570   c2 = 2756   c3 = 2091   c4 = 2276   c5 = 2423
Ne chercher pas à vérifier avec votre calculatrice pour vous donner une bonne raison, rien que le calcul de 688⁷⁹ donne environ :
147 736 096 754 175 303 230 053 677 431 108 078 993 422 779 056 521 621 788 516 135 638 187 994 995 899 192 814 258 977 221 160 914 022 825 628 299 180 402 236 602 527 982 600 775 671 266 557 420 283 463 691 946 979 929 718 178 787 089 203 370 822 514 764 608 144 873 171 356 044 647 950 190 641 152
 
Et rappelez-vous qu'il vous faut faire encore la division par 3337 pour obtenir le reste tant attendu : 1570.
Je vous rappelle que ceci est un exemple ! Bill a voulu vous simplifier la vie, il a choisi de très petits nombres p et q et la clé publique e était ridiculement petite. Imaginez les calculs avec une clé à 100 chiffres, il me faudrait un paquet de pages pour vous montrer ce que cela donne.
Mais en mathématiques, il existe toujours des petites choses qui vous simplifient la vie ( du moins théoriquement... ). Alors au lieu de calculer bêtement  688⁷⁹, on aurait pu écrire que 79 = 5 * 14 + 4, avec 688⁵ = 154149525127168, ce qui équivaut encore à 2175 mod 3337. On aurait ensuite regrouper les modulos pour obtenir au final 1570 mod 3337. Cela évite les multiplications et les divisions fastidieuses... Il y a encore beaucoup de petits avantages dans l'arithmétique des congruences. Si vous voulez en savoir plus, soit vous envoyez un mail, soit vous achetez un livre de Maths. ( la 2^ème solution est de loin beaucoup plus sage... )
Voilà Jacques a enfin son message codé :      c = 1570 2756 2091 2276 2423

Le Décryptage
Bill vient de recevoir le mail de Jacques. Il s'empresse donc d'entrer sa clé privée pour pouvoir décoder le message de Jacques. Pour cela, il va pratiquer quasiment de la même façon que Jacques mais avec la formule "inverse", soit : m_i = c_i^d mod n. Ce qui lui donne :
  m₁ = 1570¹⁰¹⁹ mod 3337 = 688   m₁ = 688   m₂ = 232   m₃ = 687   m₄ = 966   m₅ = 668
Bill obtient donc le message :   m = 688 232 687 966 668 003