RSA- Cryptographie

Le cryptosystème RSA à clés publiques Plan Le cryptosystème RSA à clés publiques 1 Plan 2 Introduction 3 1 Définitions 4 1.1 Le chiffrement symétrique 4 1.2 Le chiffrement asymétrique 4 2 Principe de fonctionnement du RSA 5 2.1 Fabrication des clés 5 La clé publique  5 La clé secrète 6 2.2 Utilisation des clés 7 Le cryptage 7 Le décryptage 8 2.3 Exemple 8 2.4 Variantes 9 Coder le message et la signature  9 Combiner RSA avec un algorithme à clé privée 9 Algorithme de hachage 11 Les certificats 11 3 Les garanties du RSA 13 3.1 Il est « facile « de fabriquer des clés? 13 Quelques observations à propos des nombres premiers 13 L'algorithme de Miller - Rabin 15 L'algorithme déterministe d'Agrawal, Kayal et Saxena (AKS) 18 Comparaison des deux tests 20 3.2 ?mais difficile, voire impossible de les « casser « 21 3.2.1 Le crible du corps des nombres (NFS)  21 3.2.2 Quelques records 22 3.2.3 Twirl : Une machine à « casser « le RSA  23 4 Les  pseudo points faibles 24 4.1 Le problème du choix des nombres  24 l'exposant e  24 les facteurs p et q 25 le nombre n  25 4.2 Précautions à prendre avec les messages  25 Taille du message 25 L'attaque par la mesure 26 L'attaque par la multiplication  26 5 ECC (Elliptic Cryptographic Curves) : un concurrent ? 27 5.1 Définition 27 5.2 Comment crypter ? 28 5.3 Comparaison entre RSA et ECC  29 Conclusion 30 Bibliographie 31 Introduction La cryptographie (du grec kryptos, secret et graphè, écriture) est l'ensemble des techniques permettant de protéger une communication au moyen d'un code graphique secret. De tous temps, les militaires y ont eu recours. Une des machines de cryptage les plus célèbres de l'histoire est sans nul doute Enigma utilisée par les allemands pendant la Seconde Guerre Mondiale. C'est dans le but de casser son code que les calculateurs électroniques virent le jour (le Kolossus de Türing). Depuis, les besoins cryptographiques ont explosé et pas seulement chez les militaires : les applications civiles du chiffrement (banques, télécommunications, informatique, cartes bleues...) deviennent un moteur fondamental de progrès. Différents procédés de cryptage ont été utilisés puis abandonnés car devenus inefficaces. Mais il en est un qui semble résister aux progrès techniques : le RSA. Le système de cryptage RSA a été inventé par Ron Rivest, Adi Shamir et Len Adleman Adi Shamir Ron Rivest Len Adleman en 1977. Ces trois chercheurs avaient décidé de travailler ensemble pour établir qu'un nouveau système de codage révolutionnaire, dénommé « système à clé publique « (nous en donnons une définition ci-après) que W.Diffie et M.Hellman venaient d'inventer, présentait des failles. Ils échouèrent mais, paradoxalement, découvrirent un nouveau système à clé publique qui supplanta vite le premier. RSA est devenu un système universel servant dans une multitude d'applications : systèmes d'exploitation (Microsoft, Apple, Sun?), cartes à puces bancaires et bien sûr le réseau Internet pour assurer la confidentialité du courrier électronique et authentifier les utilisateurs. Il est partout ! Nous expliquerons le principe de fonctionnement du RSA puis, à travers l'étude d'algorithmes et de leur complexité, nous tâcherons de mettre en évidence ce qui fait toute la force de ce cryptosystème : il est « facile « de multiplier deux nombres premiers ayant beaucoup de chiffres (>100) mais il est difficile, voire impossible avec les moyens actuels de déterminer les facteurs premiers d'un grand nombre dans un temps raisonnable. Aussi verrons-nous s'il l'on peut contourner ce problème et enfin si la méthode de cryptage grâce aux courbes elliptiques peut ébranler le colosse RSA? 1Définitions Il existe actuellement deux grands systèmes cryptographiques : ceux à chiffrement symétrique (dits à clé secrète) et ceux à chiffrement asymétrique (dits à clé publique). Une clé étant un nombre de longueur variable servant à chiffrer ou à déchiffrer un message numérique. Bien que RSA soit un système à clés publiques, il est important de savoir ce qu'est un système à clés privées car nous verrons qu'ils sont parfois utilisés simultanément pour crypter un message. 1.1Le chiffrement symétrique Si la clé est unique, elle sert à chiffrer et à déchiffrer le message ; on parle alors de chiffrement symétrique. Les algorithmes symétriques actuels utilisent une succession de transpositions et de substitutions complexes des valeurs du message, basées sur des opérations mathématiques et réalisées en plusieurs passes. La clé faisant partie intégrante de la fonction, il est impossible d'inverser l'algorithme sans elle, et les seules attaques envisageables consistent souvent à essayer toutes les valeurs de clés possibles. C'est la raison pour laquelle une clé symétrique suffisamment importante (128 bits) et bien choisie est considérée comme sûre. L'algorithme symétrique le plus célèbre est le DES (Data Encryption Standard, qui fonctionnait avec des clés de 64 bits) remplacé depuis par l'AES (Advanced Encryption System, qui fonctionne avec des clé allant jusqu'à 256 bits). Les chiffrements symétriques exigent toutefois que les deux correspondants échangent au préalable la clé secrète par un canal sûr, ce qui est quasiment impossible à grande échelle? 1.2Le chiffrement asymétrique L'algorithme asymétrique dissocie les fonctions de chiffrement et de déchiffrement en deux clés. Ce que l'une chiffre, seule l'autre peut le déchiffrer. Aucune autre clé même celle qui a réalisé le chiffrement, ne peut y parvenir. Ainsi, chacun peut diffuser librement l'une de ses deux clés (dite « publique «) afin que n'importe qui puisse chiffrer un message à son attention. Seule la clé gardée secrète (dite « privée «) permet d'en prendre connaissance. C'est là le principal avantage sur le chiffrement symétrique : les clés privées ne circulent pas et les clés publiques peuvent être publiées dans un annuaire (exemple : keyserver.com) ou demandées directement au propriétaire. Les algorithmes à clé publique les plus connus sont ECC, Diffie-Hellmann, DSA, El Gamal, Rabin et bien sûr RSA... 2Principe de fonctionnement du RSA 2.1Fabrication des clés La clé publique  Pour créer cette clé, il faut construire un quadruplet (p,q,e,d) tel que : p et q sont deux grands nombres premiers (ils ne possèdent que deux diviseurs : 1 et eux-mêmes) distincts. On pose n=pq e est un entier premier avec ?(n)= ?(p) ?(q) = (p-1)(q-1), ? étant appelée l'indicatrice d'Euler (c'est le nombre d'entiers inférieurs et premiers à n ; ?(pq)= ?(p)?(q) car p et q sont premiers entre eux ; si p est premier alors ?(p)=p-1). Voici l'algorithme servant à déterminer e : Détermination_de_e(entier p, entier q) : entier Début ?(n) ? (p-1)*(q-1) /* e > 2 on peut spécifier une valeur minimale de e */ Pour e allant de 2 à ?(n)-1 si (pgcd(e, ?(n)) = 1) alors Retourner(e) e ? e +1 finpour Fin La clé secrète d est tel que ed=1 modulo ?(n). Autrement dit, ed-1 est un multiple de ?(n). On peut fabriquer d à partir de e, p et q, en utilisant l'algorithme d'inversion modulaire basé sur l'algorithme d'Euclide étendu Algorithme servant à déterminer d : Inversion_modulaire(entier e, entier ?(n)) : tableau d'entiers Début entier r ? e modulo ?(n) entier s ? ?(n) / e Bezout = tableau de 2 entiers si r = 0 { Bezout [0] ? 0 Bezout [1] ? 1 retourne Bezout } sinon { tableau_transi ? inversion_modulaire(e,r) Bezout [0] ? tableau_transi [1] Bezout [1] ? tableau_transi [0] - Bezout[0] * s } retourne Bezout; // d est égal à Bezout [0] Fin 2.2Utilisation des clés Le cryptage Bob veut transmettre un message secret à Alice. Il commence par le transformer en un nombre entier M, inférieur à n (ou en plusieurs, si nécessaire, car sinon RSA ne fonctionne pas), en codant par exemple chaque lettre du texte par son rang dans l'alphabet (a=01, b=02, etc?). Bob calcule ensuite C = Me modulo n grâce à la méthode d'exponentiation modulaire (voir l'algorithme suivant) puis envoie C à Alice. Algorithme d'exponentiation modulaire rapide : Exponentiation_modulaire(entier a, entier e, entier n) : entier Début entier p ?1 Tant que e >=1 faire si e modulo 2 ? 0 p ? (p*a) modulo n fin si a ? (a*a) modulo n e ? e / 2 fin faire retourner p // résultat de ae modulo n Fin Le décryptage Alice décode C en calculant Cd[n] = (Me)d [n] = M ( [n] signifie « modulo n «) Démonstration : On a ed = 1 modulo ?(n) avec ?(n)= (p-1)(q-1) Donc il existe un entier k tel que ed = 1 + k(p-1)(q-1). D'où, si M ? 0 [p] : Med = M(Mp-1)k (q-1) [p] D'après le petit théorème de Fermat (que l'on retrouvera dans la 2ème partie) : Si p est premier, Mp-1-1 est divisible par p i.e. Mp-1 = 1 [p] quelque soit M entier, premier à p (c'est le cas puisque M ? 0 [p]) D'où Med = M(1)k (q-1) [p] et donc Med = M [p] Et enfin, si M=0 [p], on a bien Med = M [p]. De même, avec q : Med = M [q]. Donc d'après le théorème de Gauss, puisque p et q sont premiers entre eux, on a Med = M [p.q], d'où finalement : Med = M [n] 2.3Exemple Considérons le doublon (p, q) = (11, 19). p et q sont bien premiers entre eux et leur produit vaut n = 319. ?(n) = (p-1)(q-1) = 10*18 = 280. Choisissons e premier avec ?(n), par exemple e = 3 puis calculons d : Inversion_modulaire (e, ?(n)) retourne le tableau (-93,1) donc d = -93 [280] Ce qui revient à dire que d = 280 -93 [280] = 187 [280]. Cryptons le message suivant : « CNAM « transformé en nombre « 03140113 « en utilisant la position des lettres dans l'alphabet. Puisque 3140113 > n, nous devons le découper en tronçons inférieurs à n et de taille égale : « 03 14 01 13 « puis calculer chaque Mie = Ci pour i allant de 1 à 4  grâce à l'exponentiation modulaire ce qui donne « 27 192 01 283 «. On pourrait vérifier que Cid = Mi, pour chaque i. 2.4Variantes Coder le message et la signature  Si Bob1 souhaite qu'Alice soit sûre qu'il s'agit bien de lui, il peut coder sa signature en utilisant sa clé secrète SB : SB(signature). Il code ensuite le message et SB(signature) avec la clé publique d'Alice PA. Alice décode le tout avec sa clé secrète SA, obtient le message = SA(PA(message)) et SB(signature) = SA(PA(SB(signature)). Elle vérifie la signature de Bob en appliquant PB(SB(signature))=signature, PB étant la clé publique de Bob. Combiner RSA avec un algorithme à clé privée Les algorithmes à clé publique sont assez lents (à cause des nombreuses exponentiations modulaires à calculer). La méthode généralement utilisée pour envoyer un message volumineux, est de tirer au hasard une clé secrète, chiffrer le message avec un algorithme à clé privée en utilisant cette clé, puis chiffrer cette clé aléatoire elle-même avec la clé publique du destinataire. Ceci permet d'avoir la sécurité des systèmes à clé publique, avec la performance des systèmes à clé privée. Il existe des logiciels qui effectuent toutes ces opérations de manière transparente, et qui, de plus, sont gratuits et téléchargeables à partir de dizaines de sites de par le monde comme le PGP que nous décrivons ci-après. Un exemple : le PGP Le PGP (Pretty Good Privacy) est un algorithme de chiffrement à destination des particuliers. Il est surtout utilisé pour chiffrer des messages envoyés par courrier électronique, même s'il peut aussi être utilisé pour chiffrer tous les fichiers. PGP a été mis au point en 1991 par l'informaticien américain Philip Zimmermann, et ceci lui valut divers problèmes avec la justice. D'une part, le PGP utilise l'algorithme RSA, qui était à l'époque breveté aux Etats-Unis (le brevet a expiré en septembre 2000). D'autre part, la NSA (national security agency) a tout fait pour tenter d'empêcher la diffusion du PGP. En effet, la puissance de ce programme met à la disposition de chacun un moyen de cacher ses échanges électroniques qui résiste même aux assauts de la plus puissante des agences de renseignements du monde (c'est d'ailleurs pour cette raison que son utilisation fut formellement interdite en France jusqu'en 1999). PGP utilise le meilleur de la cryptographie symétrique (1000 fois plus rapide que le cryptage à clé publique, selon N.Dausque du CNRS « Certificats (électroniques) : Pourquoi? Comment ? «) et de la cryptographie asymétrique (sécurité de l'échange de clés). Il fonctionne comme suit : Le logiciel commence par compresser le texte ce qui permet de réduire le temps de transmission des données, et d'améliorer également la sécurité. En effet, la compression détruit les modèles du texte (fréquences des lettres, mots répétés) or ces modèles sont souvent utilisés dans les analyses cryptographiques. Ensuite PGP génère une clé de session (nombre aléatoire) qui ne sera utilisé qu'une seule fois et qui va servir à chiffrer le message. La clé de session est chiffrée en utilisant la clé publique du destinataire avec l'algorithme RSA. Enfin, le message ainsi que la clé de session cryptés sont envoyés au destinataire. Celui-ci récupère d'abord la clé de session, en utilisant sa clé privée, puis il décrypte le message grâce à la clé de session. Algorithme de hachage Un algorithme de hachage est une fonction mathématique qui convertit une chaîne de caractères d'une longueur quelconque en une chaîne de caractères de taille fixe appelée digest ou empreinte. Cette fonction est dite à sens unique pour les raisons suivantes : 2 messages différents (même à 1 bit) ne produiront "jamais" la même empreinte Il est impossible de trouver le message lorsqu'on connaît l'empreinte Ce type de fonction cryptographique est conçu de façon qu'une modification même infime du message initial entraîne une modification de l'empreinte. Si Alice veut signer un message M, elle commence par calculer h(M), où h désigne cette fonction de hachage à sens unique. Ensuite, elle signe h(M) grâce à sa clé secrète SA. Elle envoie M et SA(h(M)) à Bob. Bob peut vérifier que le message provient bien d'Alice en calculant h(M) et en le comparant à PA(SA(h(M)), où PA désigne la clé publique d'Alice. Exemples d'algorithmes de hachage : SHA1 (Secure Hash Algorithm) qui calcule un résumé de 160 bits, et le MD5, qui calcule un résumé de 128 bits. Les certificats Ils servent à simplifier la distribution des clés publiques mais aussi à garantir l'authenticité d'une clé publique. Supposons qu'Alice veuille envoyer à Bob un message authentifié. En utilisant sa clé secrète, Alice crée une signature numérique qu'elle joindra au message. Puis, en utilisant la clé publique d'Alice, Bob vérifiera cette signature. Mais comment peut-il être sûr qu'il s'agit bien de la clé publique d'Alice ? Une personne malveillante pourrait créer sa propre paire de clés et envoyer sa clé publique à Bob en se faisant passer pour Alice. Un tel scénario peut être éviter en faisant appel à une autorité de certification, qui fournira un certificat numérique sur la clé publique, reconnu par tous. Plusieurs entreprises, telles VeriSign ou GTE Cyber-Trust, délivrent des certificats numériques. Voyons le déroulement d'une telle opération : Tout d'abord Alice crée une clé secrète SA et une clé publique PA. Elle envoie cette dernière à une autorité de certification, à qui elle demande un certificat numérique. Après avoir vérifié les informations fournies par Alice, l'autorité de certification lui envoie un certificat numérique authentifiant PA. Sur ce certificat, figure la signature numérique de l'autorité. Cette dernière est le résultat de la signature du résumé du certificat (calculé par une fonction de hachage connue H) par la clé secrète de l'autorité. Ensuite Alice compose un message pour Bob. Elle peut par exemple le coder avec la clé publique PB de Bob et crypter sa signature avec sa clé privée SA puis envoyer le tout à Bob, accompagné du certificat numérique contenant sa clé publique PA. De son côté, Bob récupère la clé publique de l'autorité de certification que l'on peut trouver dans les logiciels de navigation sur Internet et dans d'autres logiciels utilisés pour les communications informatiques sécurisées. Bob utilise cette dernière pour obtenir le résumé du certificat à partir de la signature de l'autorité figurant sur le certificat envoyé par Alice. Il le compare ensuite avec le résumé du certificat calculé grâce à H. Si les deux résumés sont égaux, il est sûr que le certificat est authentique et que la clé publique qui l'accompagne appartient bien à Alice. Enfin, il n'a plus qu'à vérifier la signature d'Alice avec PA et à décrypter le message grâce à sa clé secrète SB. 3Les garanties du RSA 3.1Il est « facile « de fabriquer des clés? Nous avons vu que pour fabriquer les clés, il fallait choisir deux grands nombres premiers. Après un bref aperçu de la problématique, nous verrons deux tests permettant de savoir si un grand nombre est premier : l'un stochastique et l'autre déterministe. Quelques observations à propos des nombres premiers Nombre de mathématiciens se sont depuis fort longtemps penchés sur le problème de la primarité des nombres. Le crible d'Ératosthène (240 av JC) était une méthode déterministe qui consistait à diviser un nombre n par tous les nombres entiers inférieurs à ?n. Mais ce test est inefficace pour de grands nombres puisque sa complexité est en O(?n) (les spécialistes considèrent que seules les tâches traitées en temps polynomial sont faciles). C'est Fermat (1640) qui va être à l'origine de tests efficaces? Un test de non primarité : le critère de Fermat : Si un nombre n est premier, pour tout a < n, il vérifie : (1) an = a [n] Hélas, la réciproque n'est pas vraie ! Prenons 341 : 2341 = 2 modulo 341 et pourtant 341 = 31*11 Les nombres « a pseudo-premiers « : Ce sont les nombres pour lesquels il existe un ou plusieurs a vérifiant (1). Pour a=2, ces nombres sont appelés « Nombres de Poulet « (341 en fait partie, il est donc 2 pseudo-premier). On aurait pu espérer trouver un a pour lequel (1) n'est pas vérifiée, mais non : Les nombres « pseudo-premiers absolus «  ou nombres de Carmichaël: Ce sont les nombres n pour lesquels (1) est vérifiée pour tout a compris entre 2 et n-1. Le plus petit est 561=17*11*3. Sont-ils nombreux ? Statistiques (source : Merveilleux nombres premiers, page 266, de Jean-Paul Delahaye) Pour n jusqu'à 25 milliards Composés Pseudo premiers Pseudo premiers absolus Premiers 95,64 % Quantité de 2 pseudo premiers : 0,00009 % Moins de 1 sur 1 million 4,36 % Les pseudo-premiers sont rares ! Et encore plus rares pour n plus grand, ce qui ouvre une brèche pour les tests probabilistes.  Même si ces nombres sont rares, il fallait trouver des critères plus stricts : Soit n un nombre premier impair et soit a un entier avec 1< a 2, un nombre premier. On peut écrire p-1 = 2k t, avec t impair et soit a, un entier non divisible par p. On a soit at = 1 [p]. soit il existe i avec 0 ? i < k et a^(2it) = p-1 [p]. Corollaire 2 : Soit n>1, un entier impair. On peut écrire n-1 = 2k t, avec t impair. Supposons qu'il existe a avec 1< a < n tel que at ? 1 modulo n. et a^(2it) ? n-1 [n] pour i avec 0 ? i < k alors n est composé. Nous allons présenter trois algorithmes qui, combinés, permettent de montrer avec une très forte probabilité qu'un nombre est premier. L'algorithme Temoin est la traduction directe du corollaire de la proposition de Miller-Rabin. Il retourne vrai si le grand nombre n dont la décomposition est 2kt+1 (cf l'algorithme Decomposition) passe le test de Miller-Rabin pour la base a (ie n est composé), faux sinon, ce qui est un indice de primarité, qui devra être confirmé ou infirmé par d'autres tirages aléatoires de a entre 2 et n-1. L'algorithme Miller_Rabin() est appelé avec deux arguments, l'entier à tester et le nombre de tirages ; elle retourne vrai dès qu'un témoin est trouvé, auquel cas n est composé, et faux sinon, auquel cas n est probablement premier. Decomposition(n : entier, k : entier, tab : tableau de deux entiers): tableau Début si n modulo 2 = 1 alors tab[0]=k et tab[1]=n sinon Decomposition(n/2, k+1,tab) retourne tab Fin Temoin(entier a, entier n) : boolean Début mr : boolean = vrai tr : tableau de deux entiers tr ?Decomposition(n,0,tr) k = tr[0] ; t = tr[1] p ? exponentiation_modulaire(a, t, n) //p ? at modulo n si p=1 alors mr = faux sinon Pour i allant de 0 à k-1 faire p=exponentiation_modulaire(a,t*2^i,n) si p=n-1 mr = faux sortir de la boucle puisqu'on a trouvé un i vérifiant a^(2it) = n-1 [n] fin si fin pour fin si retourner mr Fin Miller_Rabin(entier n, entier s) Début Pour j allant de 1 à s-1 faire{ tirer a aléatoirement dans [2, n-1] si Temoin(a,n) retourner "composite"; fin faire} retourner "premier"; Fin Taux d'erreur de ce test : Préliminaire 3 : le théorème de Rabin : Soit n, un entier impair composé > 9. Posons n-1 = 2kt avec t impair. Les entiers a compris entre 1 et n et qui satisfont à la condition at =1 [n] ou à l'une des conditions a^2it = n-1[n] avec 0 ? i < k sont en nombre au plus ?(n)/4. Il en résulte que la probabilité que le test Temoin effectué s fois, nous dise qu'un nombre est premier alors qu'il est composé est inférieure à ¼s = 2-2s. En effet, chaque test a une probabilité de répondre que n est premier ? ¼ puisque sur les (n-2) a possibles, moins d'un quart vérifient l'une des deux conditions. Donc une série de s tests a une probabilité d'erreur ? ¼ s. Il est souvent préconisé de prendre s=50 ce qui donne un risque d'erreur < 10-30 ce qui est très faible ! Complexité de l'algorithme : M. Demazure considère qu'une bonne définition de la taille d'un entier en bits est logn, log en base 2, noté log2. Par exemple : log2(393831)=18.59 et taille(393831)=taille([1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1]) = 19 Cela étant posé, étudions la complexité de l'algorithme : Pour a donné, le test Temoin demande le calcul de at [n] et les k élévations au carré successives donnant les a^(2it)[n]. at[n] a un coût en (log2(t)log2²(n)) ; a^(2it)[n] a un coût en (log2(2it)log²(n)) = (i+log2(t))log2²(n) qui est majoré par (k+log2(t))log2²(n) car i < k mais puisque n = 1 + 2kt > 2kt, log2(n) > k + log2(t). Donc un test a un coût en log2(t).log2²(n)+log3(n) i.e. en 2.log23(n). Or on fait ce calcul s fois dans Miller_Rabin, donc le coût total est majoré par 2s.log23(n) ainsi la complexité est en O(log23n). Remarque : L'algorithme de Solovay-Strassen a la même complexité mais selon M.Demazure, celui de Miller-Rabin est meilleur car sa probabilité d'erreur est, pour s tests, inférieure à 2-s (2-2s pour Miller-Rabin). C'est pour cette raison que je ne l'expose pas. L'algorithme déterministe d'Agrawal, Kayal et Saxena (AKS) Cet algorithme date d'août 2002 et est le premier à s'exécuter dans un temps polynomial. Jusqu'alors, le meilleur algorithme déterministe était la version de Cohen-Lenstra du test publié par Adleman, Pomerance et Rumely en 1983 (« Sommes de Jacobi «). Sa complexité était en log2(n)O(log2(log2 (log2 (n))), ce qui est très légèrement supérieur à un temps polynomial. L'idée repose sur une généralisation du petit théorème de Fermat : Soit a ? ?, n ? N avec n ? 2 et pgcd(a,n) = 1 alors n est premier si et seulement si : (X-a)n = Xn - a modulo n. Evaluer cette expression pour un n donné et différents prendrait un temps en O(n). L'idée qu'ont eue ces trois chercheurs pour rendre ce test effectif a été d'évaluer cette identité modulo un polynôme Xr-1, c'est-à-dire tester si (1) (X-a)n = Xn - a modulo (Xr-1, n) La mention « modulo Xr-1,n « signifie « à un multiple Xr-1 près et à un multiple de n près «. Ainsi (1) est vrai s'il existe un polynôme q(X) à coefficients entiers tel que, après développement et simplification, tous les coefficients du polynôme (X-a)n-(Xn-a)-q(X)(Xr-1) sont des multiples de n. Par exemple : (X-1)3=X3-1 modulo (X-1, 3). En effet, en prenant q(X)=-9X, on obtient : (X-1)3-(X3-1)-(-9X)(X-1) = X3-3X²+3X-1-X3+9X²-9X = 6X²-6X qui est un polynôme dont les coefficients sont des multiples de 3. Voici cet algorithme (cf leur article « Primes is in P «): Soit n > 1, l'entier dont on doit tester la primarité : 1. Si n est de la forme ab avec b>1, alors répondre « n est composé « et s'arrêter. 2. Trouver le plus petit r tel or(n) > 4 log2²(n), où or(n) représente l'ordre de n [r], ie le plus petit nombre k tel que nk = 1[r]. Ce qui peut se faire de la façon suivante : Détemination_de_r (entier n) Début entier ordre = 1 entier r = 1 Tant que ordre <= 4*log2²(n) faire r ? r+1 tant que pgcd (r,n) ? 1 faire r ? r+1 ordre = 1; tant que exponentiation_modulaire (n,ordre,r) ? 1 faire ordre ? ordre+1 fin tant que retourne r Fin 3. Si 1< pgcd(a,n) < n, pour a ? r alors retourner « n est composé « 4. Si n ? r alors retourner « premier « 5. Pour tout nombre a entier entre 1 et 2log2(n)?r faire si (X-a)n ? Xn - a modulo (Xr-1, n) alors retourner « n est composé «. Fin pour 6. Retourner « n est premier «. Complexité : Ces trois chercheurs ont démonté que cet algorithme avait une complexité en O(log27.5(n)) et sont en train d'essayer de la réduire à O(log23(n)). Quoiqu'il en soit ils ont réussi à monter que le problème de la primarité d'un nombre appartient à P(*), alors que jusque-là, on savait seulement qu'il était dans Co-RP (1977, R.Solovay et V.Strassen) et dans RP (1992, L.Adleman et M.Huang). (*) - la classe de complexité P est l'ensemble des problèmes admettant oui ou non comme réponse et possédant un algorithme polynomial (réalisable en un temps raisonnable) - la classe de complexité RP (random polynomial) est l'ensemble des problèmes admettant oui ou non comme réponse et possédant un algorithme polynomial de Monte-Carlo (si la réponse est oui, l'algorithme répondra oui au moins une fois sur deux et si la réponse est non, il répondra toujours non) - la classe de complexité Co-RP est définie en considérant la question inverse (par exemple : n est-il composé ?) Comparaison des deux tests Selon H.Lehning, professeur de Mathématiques au lycée Janson de Sailly : « Du point de vue théorique, les tests déterministes ont une probabilité d'erreur nulle. Dans la pratique, si la programmation du test est délicate comme c'est le cas de celui de l'AKS, il reste une probabilité d'erreur non négligeable : la présence d'un maillon faible dans la chaîne partant du programmeur et passant par le compilateur, le système d'exploitation et finissant aux composants de l'ordinateur utilisé. Puisque l'on sait que les tests probabilistes peuvent n'être entachés que d'une probabilité d'erreur inférieure à 2-100, cette remarque relativise quelque peu l'intérêt pratique des tests déterministes. Il en reste bien sûr l'intérêt théorique ! «. Il faudra donc attendre pour voir si des implémentations de cet algorithme s'avèrent plus efficaces que celles des algorithmes probabilistes. 3.2?mais difficile, voire impossible de les « casser « « L'inviolabilité « de la méthode RSA vient de la difficulté de factoriser n pour en déduire p, q puis d. Cette idée d'inviolabilité vient de l'expérience, ce n'est ni un fait démontré, ni même pour certains spécialistes un fait démontrable. L'amélioration des méthodes de factorisation et /ou le progrès technique pourraient remettre sérieusement en cause les petites clés de RSA, comme nous le verrons après avoir décrit le principe de l'algorithme GNFS qui a conduit au record de la plus grande clé cassée. 3.2.1Le crible du corps des nombres (NFS)  L'algorithme de factorisation par crible sur corps de nombres (en anglais : number field sieve ou NFS) a été introduit par Pollard en 1988, il se divise en fait en deux algorithmes distincts : - le NFS spécialement adapté à des nombres du type n= a.rt+ b.su (alias SNFS : special NFS), - le NFS applicable à des nombres arbitraires (GNFS : general NFS). Le principe du GNFS : Soit n le nombre que l'on souhaite factoriser, on suppose que c'est un nombre composé (un test de primarité permet rapidement de trancher cette question) impair qui n'est pas une puissance de nombre premier. Il s'agit de trouver v et w tels que n soit un diviseur de v²-w². En effet, si n divise v²-w², il divise aussi (v-w)(v+w). Si n n'est pas un diviseur de v-w ou de v+w, alors un diviseur propre de n doit diviser v-w et un autre, diviser v+w. Ainsi, le plus grand diviseur commun de n et de v-w, par exemple, est plus grand que 1, et donc est l'un des diviseurs cherchés. Trouver v et w se fait grâce entre autres, à la théorie des polynômes? Complexité du GNFS : exp((c+o(1))( log2 n)1/3(log2 log2 n)2/3) où c ? 1.923. Une version améliorée du GNFS avec beaucoup plus de polynômes due à D.Coppersmith, a une complexité de exp((c+o(1))(log2 n)1/3(log2 log2 n)2/3) où c ? 1.902. C'est l'algorithme généraliste le plus rapide pour de grandes entrées. 3.2.2Quelques records Depuis des années la société RSA organise des challenges pour casser des très grandes clés. Le 22 août 1999 une équipe de l'institut national de recherche en mathématiques et sciences informatiques d'Amsterdam a réussi le challenge RSA-155 ("cassage" d'une clé de 512 bits) en factorisant un nombre de 155 chiffres en 2 nombres de 78 chiffres. L'expérience a été réalisée avec un réseau de 300 ordinateurs pour un cumul de 8 000 Mips(4) année (équivalent à environ 40 PC Pentium III à 500 Mhz pendant 1 an), l'opération a duré 3 mois et demi et a donc utilisé le GNFS. (source : JP.Delahaye, Pour la Science) Une première phase a consisté à chercher un bon jeu de paramètres pour la méthode : les spécialistes évaluent à 100 Mips année la quantité de calculs faite pour elle, qui a duré 9 semaines en utilisant une seule machine. La seconde phase, qui a été distribuée sur un réseau de 300 machines réparties dans le monde entier, est aussi la plus coûteuse en calcul. Elle a fourni les relations qui sont au c?ur de la méthode. Un total de 124 millions de relations a ainsi été engendré, dont 39 millions apparaissaient en double à cause de la méthode de calcul distribué. Le tri des relations et la préparation de la matrice du système linéaire à résoudre ont demandé un mois de travail. La matrice résultante comportait 6 699 191 lignes et 6 711 336 colonnes. La résolution du système d'équations a été faite par un ordinateur vectoriel possédant 2 giga-octets de mémoire centrale et a demandé 224 heures. Enfin, une légère amélioration de la méthode utilisée par le précédent record (140 chiffres) et réalisé 6 mois auparavant a permis d'économiser 6 000 Mips (un gain de 40%). Tout cela montre que si casser une clé RSA de 512 bits est faisable, cela demande des moyens et des compétences qui ne sont pas à la portée de n'importe qui. Les records antérieurs : Année Taille en chiffres Taille en bits 1984 71 236 1988 106 352 1993 120 399 1994 129 429 1996 130 432 Le dernier record : RSA-160 (annoncé le 1er avril 2003 !), source : http://www.loria.fr/~zimmerma/records/rsa160 3.2.3Twirl : Une machine à « casser « le RSA  A. Shamir (un des pères du RSA) et E. Tromer ont publié un article (http://psifertex.com/download/twirl.pdf) dans lequel ils décrivent une machine, Twirl. Selon eux, cette machine pourrait être construite pour un coût de 10 M$ et permettrait de factoriser une clé RSA 1024 en une année ou pour un coût de 10 K$ une clé de 512 bits en moins de dix minutes. Shamir et Tromer ont étudié la proposition des circuits NFS de Bernstein (améliorations du GNFS et création d'une machine capable de casser une clé RSA de 3072 bits aussi rapidement qu'une clé de 1024 bits avec la méthode actuelle (http://cr.yp.to/nfscircuit.html)) et proposé des solutions pour l'améliorer. Selon M.Nallino (« cryptographie: risques et précautions d'emploi «) : si Twirl était, comme Shamir et Adler le pensent, réalisable techniquement, et même si le coût (avec les frais de développement) devait être 10 fois plus cher et atteindre 100 M$, sa fabrication serait alors à la portée de gouvernements mais aussi de grands groupes industriels. Or beaucoup d'Autorités de Certification, comme Verisign, ont encore des clés principales de 1024 bits. La prudence doit donc inciter dès aujourd'hui à utiliser des clés RSA de taille minimale 3072 bits, voire même de 4096 bits (le maximum de ce que permet GnuPG). 4Les  pseudo points faibles Il faut, comme on l'a vu, d'énormes moyens (ordinateurs puissants et nombreux) pour briser le RSA par le biais des Mathématiques. Mais il n'a pas été prouvé que la difficulté du RSA soit équivalente à celle de la factorisation. Il a d'ailleurs été démontré que RSA n'était pas infaillible si certaines consignes et mises en gardes n'étaient pas respectées? mais les précautions nécessaires contre ces faiblesses sont prises en compte dans les protocoles d'utilisation de RSA : après 24 ans, on peut les considérer comme mûrs et sûrs. 4.1Le problème du choix des nombres  l'exposant e  MM Boneth et Venkatesan ont établi en 1998 que casser le RSA, lorsqu'il est utilisé avec des exposants e trop petits, est moins difficile que de factoriser n (cf exemple ci-dessous). MM K.Lestra et R.Veerheu ont recommandé en 1999 que l'exposant public soit choisi égal à 216+1 = 65737 (nombre de Fermat) plutôt que les valeurs premières 3 ou 17 longtemps utilisées mais considérées aujourd'hui comme facteur de vulnérabilité. Exemple traduit d'un extrait du chapitre 8 du livre  the Handbook of Applied Cryptography, de A. Menezes, P. van Oorschot et S. Vanstone, CRC Press, 1996 : Afin d'améliorer l'efficacité du cryptage, il est tentant de choisir un petit exposant, par exemple e=3. Supposons que 3 personnes aient choisi le même e mais 3 n différents. Si une autre personne souhaite leur envoyer le même message, elle devra crypter m comme ceci : ci = m3 mod ni, for i = 1, 2, 3. Si les ni sont premiers deux à deux, une oreille indiscrète pourrait intercepter c1,c2,c3 et utiliser l'algorithme de Gauss pour trouver une solution x, 0 ? x < n1n2n3 , au système suivant : x = c1 modulo n1 x = c2 modulo n2 x = c3 modulo n3 Si m3 < n1n2n3, le théorème des restes Chinois nous dit que x = m3. Il ne reste plus qu'à calculer la racine cubique de m3 et le tour est joué. Evidemment ça fait beaucoup de « si « (cette dernière phrase ne figurait pas dans le livre). Je l'ai essayé avec m=69, n1=15, n2=22 et n3=1081. On a bien 693 = 250047 < n1n2n3 = 356730 et x = 693 est bien solution du système : x=9 mod 15 x=5 mod 22 x=966 mod 1081 Remarque : Cela nous montre également qu'il vaut mieux éviter de chiffrer le même message avec plusieurs clés différentes? les facteurs p et q JP.Delahaye conseille de prendre p et q de taille proche et d'éviter que les nombres p+1, p-1, q+1, q-1 soient trop faciles à factoriser car alors n risquerait de l'être aussi par l'utilisation d'algorithmes spécialisés de factorisation sachant en tirer parti. le nombre n  Il ne doit pas être choisi par plus d'une entité car sinon, l'utilisation des diverses clés publiques des utilisateurs du même n risquerait de donner accès aux facteurs de n. Il ne doit pas être trop petit (au minimum 1024 bits). On se souvient qu'en 1998, l'affaire Humpich a fait la une des journaux (cet informaticien a montré qu'il était possible de fabriquer de toute pièce une fausse carte qui permettait de payer chez un commerçant). Serge Humpich avait contourné deux systèmes de sécurité : D'une part, il a fabriqué des "yes card", c'est-à-dire des cartes à puce qui, quelque soit le code secret entré, renvoie "code bon". D'autre part, il a contourné l'authentification hors-ligne RSA : en 1998, le n utilisé par le GIE (groupement interbancaire) avait pour taille 320 bits (taille inchangée depuis 1990). A cette époque, factoriser un tel entier n'était plus impossible (le record se situait à 432 bits), et Humpich, en utilisant simplement un logiciel japonais de factorisation, a réussi à factoriser le n du GIE, et à découvrir la clé secrète. Depuis, le n a changé, et est désormais long de 768 bits. 4.2Précautions à prendre avec les messages  Taille du message Lorsque le message à chiffrer est de petite taille, retrouver le message clair est alors aussi simple que d'extraire une racine cubique (toujours selon JP Delahaye). Il faut donc compléter les textes, avant de les coder, par des bouts choisis aléatoirement et surtout pas par de longues séries de blancs ou de zéros. L'attaque par la mesure Une attaque astucieuse proposée par P.Kocher consiste à mesurer minutieusement le temps de calcul (ou la consommation électrique) demandé pour le codage, ce qui permet, si l'on dispose de suffisamment de données, de retrouver les clés utilisées. Appliquée aux cartes à puces, cette méthode se révélerait catastrophique. Pour s'en prémunir, il suffit de s'arranger pour que le temps de calcul apparent soit faussé en opérant des calculs supplémentaires inutiles une fois le codage réalisé, avant d'envoyer l'information que le codage est terminé. L'attaque par la multiplication  Un attaquant récupère un message crypté à l'attention de sa cible avec un algorithme RSA. L'attaquant possède donc c (exemple : 254), le message chiffré, et recherche m = cd [n]. L'attaquant possède par ailleurs la clé publique de sa cible, (n=319, e=3). L'attaquant choisit un nombre au hasard, r < n, exemple : r = 200. Il calcule: x = re [n] = 118 y = x.c [n] = 305 t, tel que t.r = 1 [n], il trouve t = 193 L'attaquant compte sur la réciprocité de l'algorithme RSA, si x = r^e [n], alors r = xd [n]. L'attaquant fait alors signer y à sa cible, avec sa clé privée (en prétextant, par exemple, que c'est pour vérifier qu'il a bien affaire à elle : cette technique n'a rien d'incongru) et obtient : u = yd [n], u = 222. Il calcule alors t.u [n] = r-1.yd [n] = r-1.xd.cd [n] = cd [n] = m = 100, le message recherché. Pour éviter cette attaque, il ne faut jamais signer un texte aléatoire, à l'origine inconnue. 5ECC (Elliptic Cryptographic Curves) : un concurrent ? H. Lenstra a utilisé les courbes elliptiques pour factoriser de grands entiers : elle s'avère très efficace pour trouver de « petits facteurs « (jusqu'à 40 chiffres environ) et sa complexité est en exp(?(log(n)log(log(n)))))?2+o(1) (source : Introduction à l'algorithmique, T.Cormen, C.Leiserson et R.Rivest, chapitre 33.7). Mais ce qui nous intéresse ici, c'est leur utilisation en cryptographie à clé publique analogue au système RSA. 5.1Définition On appelle courbe elliptique sur R toute courbe plane d'équation y2=x3+ax+b, où le discriminant -(4a3+27b2) de x3+ax+b est non nul. On rajoute à cette courbe un point à l'infini noté O. L'intérêt de ces courbes elliptiques est qu'on peut les munir d'une opération de groupe commutatif (voir plus loin). Prenons P et Q deux points distincts de la courbe elliptique (et différents du point à l'infini O). On trace la droite (PQ). Deux cas peuvent se produire : La droite coupe la courbe en un 3ème point (on démontre qu'il y a au plus 3 points d'intersection entre une droite et la courbe). Le symétrique de ce 3ème point par rapport à l'axe des abscisses est P+Q. La droite ne coupe la courbe qu'en P et Q. Ceci n'est possible que si (PQ) est parallèle à l'axe des ordonnées. On définit alors P+Q=O (point à l'infini). Si P=Q, on considère la tangente à la courbe en P, et on définit P+P comme ci-dessus. Enfin, on prolonge la définition de + en posant P+O=O+P=P. On peut alors prouver que l'opération + définit une loi de groupe commutatif sur la courbe elliptique (+ est à la fois associative et commutative, il existe un élément neutre O et pour tout point P, il existe P' son symétrique tel que P+P'=O). On peut d'ailleurs effectuer les calculs, pour obtenir les coordonnées de P+Q en fonction de celles de P et de Q. 5.2Comment crypter ? L'idée de départ est qu'un texte peut-être transformé en une suite de points de la courbe E(a,b) d'équation y2=x3+ax+b. Cela revient à écrire dans un alphabet ayant autant de signes que la courbe a de points. La clé secrète est constituée d'un point P de la courbe et d'un entier t. On calcule ensuite P'=tP. La clé publique est alors le couple de points (P,P'). Pour crypter un point M, le chiffreur choisit un entier s et transmet le couple (U,V) défini par : U=sP et V=M+sP' La connaissance de t suffit pour retrouver M : M=v-tU Pour retrouver t connaissant Pet P', il suffit de savoir résoudre l'équation : P'=tP Ce nombre t est appelé logarithme discret et ce problème est actuellement considéré comme très difficile : c'est le pendant de la factorisation dans RSA ; l'algorithme rho de Pollard étant alors celui du GNFS. 5.3Comparaison entre RSA et ECC  Extrait du « Le journal Informatique «, avril 2000 : « La société canadienne de cryptographie Certicom avait lancé en 1997 un défi de résolution de clef publique considéré comme le plus difficile jamais réalisé. Aujourd'hui, la clef cryptographique de 109 bits vient d'être "cassée" par 4 ingénieurs de l'Inria. Afin d'y parvenir, ces derniers ont mené quatre mois de calcul distribué sur près de 10.000 ordinateurs avec l'assistance de 1.300 internautes dans une quarantaine de pays. Le système ECC, conçu par Certicom, démontre ainsi sa supériorité flagrante sur l'algorithme RSA. « Qu'en pensent les spécialistes ? Peut-être faut-il nuancer cette analyse? Tout d'abord, voici quelques chiffres concrets qui donnent incontestablement l'avantage à ECC : Taille de clé RSA Taille de clé ECC Temps nécessaire pour casser la clé en MIPS*année 512 106 104 768 132 108 1024 160 1011 2048 210 1020 21000 600 1078 Challenge ECC (Certicom) clés ECC : Année Taille en bits 1999 97 2000 109 Sources : www.certicom.com et vérifiées en partie sur www.rsa.com Selon H.Lehning, « une clé de 200 bits pour les courbes elliptiques est plus sûre qu'une clé de 1024 bits pour la méthode RSA. Comme les calculs sur les courbes elliptiques ne sont pas compliqués à réaliser, c'est un gros avantage pour les cartes à puce où on dispose de peu de puissance et où la taille de la clé publique influe beaucoup sur les performances. Mais la théorie des fonctions elliptiques est complexe et relativement récente. Il n'est pas exclu que l'on puisse contourner le problème du logarithme discret. D'autre part, cette technologie a fait l'objet du dépôt de nombreux brevets à travers le monde. Cela pourrait rendre son utilisation coûteuse ! « Il faudrait donc se montrer prudent, d'autant plus, par exemple, que le nouveau protocole de sécurisation des échanges d'informations sur Internet, le SET (mis en place par les sociétés Visa et Mastercard) qui remplace SSL, utilise RSA ! Conclusion Si aujourd'hui de nombreux logiciels (gratuits ou non) utilisant RSA semblent garantir avec suffisamment de confiance qu'une signature numérique ne peut être falsifiée, ou qu'un message chiffré ne peut être déchiffré par quelqu'un d'autre que son destinataire, qu'en sera-t-il demain? Ou dans 20 ans? L'approche la plus prudente consiste à dire : On ignore ce que sera exactement la puissance de calcul disponible dans 20 ans. Elle sera peut-être largement supérieure aux extrapolations. Il faut donc utiliser dès aujourd'hui des clés de chiffrement de la plus grande taille possible! On ignore où se feront les progrès en algorithmique et quels seront les algorithmes "cassables". L'idéal serait donc d'utiliser systématiquement RSA et ECC en redondance, ce qui obligerait à des progrès significatifs des algorithmes (GNFS, Pollard rho ou autres) pour casser la clé. Il ne faudrait donc pas voir ECC comme un concurrent mais comme un partenaire ! Si concurrent il y a, il semble qu'il faille le chercher du côté de la mécanique quantique. Tout d'abord, en 1994, P.Shor a démontré que l'on pourrait factoriser efficacement de grands nombres à l'aide d'ordinateurs quantiques, mais ils n'existent pas encore. En revanche, des chercheurs étudient actuellement la cryptographie quantique, qui permettrait d'envoyer des messages secrets impossibles à déchiffrer. Ainsi, C.Bennet et G.Brassard ont prouvé expérimentalement que l'on pouvait créer un système dont la sécurité serait absolue, indépendamment de la puissance de calcul et de la technologie utilisée par l'espion éventuel. L'idée est de s'appuyer sur une particularité quantique de la lumière : il est impossible de copier un photon donc, si un espion intercepte un message et tente de copier la clé, une partie du message décodé sera faussée... Le record de distance actuel pour la transmission des clés cryptographiques quantiques à travers un réseau de fibres optiques est de 67 km, entre Genève et Lausanne. Néanmoins, l'infrastructure en place ne favorise pas actuellement l'implantation de la cryptographie quantique sur une échelle commerciale, car cela coûterait trop cher. On peut toutefois imaginer que certains pays ont peut-être déjà commencé à se servir de la mécanique quantique pour protéger leurs secrets les plus vitaux, d'autant plus, qu'il n'est pas exclu non plus qu'ils aient déjà brisé le RSA? Bibliographie Introduction à l'algorithmique, T.Cormen, C.Leiserson et R.Rivest, chapitre 33.7, Dunod Cours d'algèbre, M.Demazure, chapitre 1&2, Cassini « La factorisation des grands nombres «, J.Buchmann, Pour la Science (Septembre 1998) « La cryptographie RSA vingt ans après «, JP.Delahaye, Pour la Science (Janvier 2000) « Savoir si un nombre est premier : facile ! «, JP.Delahaye, Pour la Science (Janvier 2003) « La cryptographie «, H.Lehning, Sciences & Info prépas, numéro 18 « Primes is in P « de M.Agrawal, N.Kayal, N.Saxena, sur le site internet : http://fatphil.org/maths/AKS/ les sites Internet www-ensimag.imag.fr/eleves.Remi.Zara/tipe.crypto/somm.html et http://mathweb.free.fr M.Nallino « cryptographie: risques et précautions d'emploi « : www.chez.com/winterminator/cryprisk.html