Rivest, Shamir et Adleman

J'ai choisi, dans rsa.c, de donner une illustration du cryptosystème RSA, qui n'est absolument pas réaliste dans les « détails d'implémentation », mais vise à mettre en valeur les mathématiques mises en jeu. Un aspect cependant réaliste de l'implémentation choisie est l'utilisation d'un bibliothèque de calcul sur les grands nombres, GMP. Dans le cas contraire, il aurait fallut se contenter de chiffrer des messages n'excédant pas 2 caractères, et l'hypocrisie devenait trop grande : on aurait mis en œuvre un simple chiffrement par substitution !

Il y a beaucoup à dire sur le sujet. J'essaie ci-dessous de commenter un peu les aspects illustrés par mon code, mais aussi d'évoquer ceux, soit mathématiques, soit techniques, qui n'y apparaissent pas.

Actualité

J'apprends en rédigeant cette page, notament par un article du Monde, qu'une nouvelle méthode d'attaque de RSA à été dévoilée. Elle serait basée sur une mesure fine du temps de calcul au décryptage, notament en liason avec les mécanismes de prédiction de branchement utilisés par la plupart des processeurs actuels. N'ayant pas d'information précise, je ne me permets pas de juger du sérieux de cette nouvelle et encore moins de ses conséquances réelles sur la sécurité.

Quoiqu'il en soit, il faut bien retenir l'importance capitale des choix d'implémentation jusqu'aux moindres détails pour une bonne sécurité : toutes les attaques de RSA connues à ce jour sont basées sur des éléments matériels d'implémentation, non sur des progrès quant aux problèmes mathématiques sous-jacents.

Calcul modulaire

Vous remarquerez que les calculs nécessités par la mise en œuvre de RSA font intervenir la plupart des notions et théorèmes importants du chapitre 4 du cours : inversion modulo n, petit théorème de Fermat, indicatrice d'Euler, théorème chinois. Essayez de reconnaître où et comment ils interviennent. Notez particulièrement l'usage du théorème chinois lors du décodage, qui permet des calculs pus rapide qu'une exponentiation modulaire « brutale » (même en exponentiation rapide), et conditionne la manière, différente de celle présentée en cours, dont est stockée la clé secrète.

Exercice : Remarquer la façon dont est mis en œuvre le théorème chinois dans déchiffrer(). Comprendre pourquoi elle est correcte, et pourquoi la connaissance de l'inverse de q modulo p (c'est-à-dire d'un seul des deux cœfficients de Bézout) suffit. Démontrer que le résultat ainsi obtenu est automatiquement un entier compris entre 0 et n.

Primalité probable

Les deux aspects mathématiques les plus importants cachés par l'exemple sont la notion de primalité probable, et celle de générateur pseudo-aléatoire. Générer une clef RSA revient essentiellement à choisir deux grands nombres premiers. Comme on ne peut extraire ceux-ci d'une famille connue ou de tables publiées pour des raisons évidentes, la méthode la plus sûre consiste à tirer des nombres au hasard, et à continuer jusqu'à trouver un nombre premier.

Ceci nécessite bien sûr de savoir tester (rapidement !) si un nombre est premier ou non. Or, pour les nombres n'ayant pas de petit facteur premier, déterminer sa primalité de façon certaine est une chose qu'on ne sait pas faire rapidement. On utilise donc à défaut des tests probabilistes de primalité. Le plus utilisé d'entre eux est le test de Miller-Rabin.

Vous savez que, d'après le théorème de Fermat, si p est premier, alors pour tout a premier à p, on a a^p-1 = 1 mod p, mais que cela peut aussi arriver pour des p non premiers. C'est le cas, par exemple, de 561. Les nombres que vérifient la conclusion du théorème de Fermat sans être premiers sont appelés nombres de Carmichaël ; on sait depuis 1994 qu'il y en a une infinité.

On peut regarder la propriété un peu plus précise suivante : on pose p-1 = 2^kb, avec b impair. Alors, soit a^b = 1 mod p, soit il existe un entier i tel que a^2ⁱb = -1 mod p. Cette propriété est vraie pour tout a si p est premier (exercice : le démontrer !), et on peut montrer, c'est le point important, qu'elle est fausse pour au moins 75% des a si p n'est pas premier.

Ainsi, on ne teste pas toutes les valeurs de a possibles, ce qui serait trop long ; mais on se contente de tester pour différentes valeurs choisies au hasard. L'important est qu'on contrôle ainsi la probabilité d'erreur. Par exemple, si p est un entier de 250 bits, il suffit de tester 12 valeurs de a pour que la probabilité d'erreur soit inférieure à 2^-80. C'est comparable à la probabilité d'erreur matérielle lors du calcul, et considéré comme satisfaisant d'un point de vue cryptographique.

Cette technique, comme d'autres, nécessite de disposer d'une bonne source de suites de nombres pseudo-aléatoire. Les générateurs pseudo-aléatoires (PRNG pour nos amis saxons) sont un domaine riche et actif, sur lequel je ne m'étendrai pas, faute de compétence.

Schéma de remplissage

Vous l'aurez remarqué, un des aspects le moins réaliste du code est qu'il ne permet de coder que des messages de longueur fixée. En vrai, on doit découper le message en monceaux s'il est trop long, et le ralonger s'il est trop court, et de façon moins naïve que ce qui est fait ici (rajouter des espaces). C'est en effet un des aspects sensibles du système, et qui a déjà été la source d'attaques réussies, connu sous le nom de schéma de remplissage.

Cet aspect est, heureusement, bien standardisé de nos jours. On utilise notament, le schéma OAEP, qui a le mérite de faire l'objet d'une preuve de sécurité, sous certaines hypothèses. Les laboratoires RSA ont publié d'ailleurs des « standards » de mise en œuvre de certaines méthodes cryptographique, et l'un d'entre eux, le PKCS#1, a inclut OAEP dans sa dernière version, suite aux attaques évoquées précédemment.

Il est à noter que l'implémentation du schéma de remplissage est encore une étape nécessitant de disposer d'un bonne source de nombres (pseudo-)aléatoires.

Sur la taille de la clef

Les tailles de clef courantes aujourd'hui sont de l'ordre de 2048 bits. La taille recommandée évolue constamment en fonction de la puissance des processeurs. Par exemple, dans le Zémor (ed. 2000), on peut lire : « Pendant longtemps RSA fut considéré comme sûr lorsque n est un entier de 512 bits : ce n'est plus cas aujourd'hui et l'on préconise de prendre des entiers de 768 ou 1024 bits. » Six ans après, c'est le double.

Une compétition de factorisation est organisée par les laboratoires RSA security. Elle porte sur une liste de nombres allant jusqu'à 2048 bits. À ce jour, le plus grand entier factorisé est RSA-200, d'une longueur de 200 chiffres décimaux, soit 663 bits. Le plus récent est RSA-640 (640 bits), qui a nécessité 5 mois de calcul d'un réseau de 80 processeurs.

Notons qu'il est possible sur un ordinateur personnel de factoriser des nombres de 256 bits en quelques heures. J'ai tenté sur le serveur grobner1 (CPU opteron 275) de l'IMJ, l'expérience de factoriser, avec le logiciel de calcul PARI-GP, des modules RSA tirés au hasard, à partir de 32 bits et par incrément de 32 bits, avec affichage du temps de calcul. J'ai arrêté l'expérience après la factorisation d'un nombre de 288bits en 29 heures. Vous pouvez consulter les fichiers d'entrée et de sortie du calcul.

Remarque technique

Mon code utilise la bibliothèque de calcul multi-précision GNU MP afin de pouvoir manipuler de grands entiers. Pour pouvoir compiler et exécuter le code, il vous faut disposer d'une version binaire de cette bibliothèque et de ses fichiers d'en-tête. Sous Linux, vous pouvez les installer facilement (apt-get install libgmp3c2 ou tout autre mécanisme proposé par votre distribution). Pour windows, je propose des versions (non testées personnellement) adaptées pour MinGW (ici), et Visual C++ (là). Je présente mes excuses aux utilisateurs de MacOS, à qui je ne suis en mesure de fournir aucune aide sur ce point. Par ailleurs, pour aider la lecture du code, le manuel de GMP se trouve ici.

Références

Les habituelles : pages wikipedia, dont les liens dispersés dans le texte, la page RSA, et plus généralement le portail cryptologie. Voir notament la notion importante de signature numérique, non évoquée en cours. Pour quelques méthodes de factorisation toujours intéressantes quoique dépassées depuis la dernière édition du livre, le volume 2 du Knuth.

Pour des infos actuelles sur RSA, et notament la compétition de factorisation de modules RSA, le site de RSA security. Pour aller (beaucoup) plus loin sur les aspects mathématiques de la cryptographie, le « Cours de cryptographie » de Zémor. Pour une discussion de niveau assez élevé sur les algorithmes modernes de factorisation et/ou tests de primalité, « A course in Computational Number Theory » de Cohen (pour plus tard si vous continuez en maths).