Cet article constiue la suite du texte sur la cryptologie du n° 4 de Progressistes.
La cryptologie est dĂ©sormais incontournable pour lâenvoi dâun simple courriel, un paiement bancaire ou pour protĂ©ger des informations personnelles. Elle repose sur la thĂ©orie des nombres, discipline pourtant jugĂ©e abstraite, mais qui sâavĂšre essentielle pour de multiples aspects de la vie quotidienne. Elle constitue un des fondements de la rĂ©volution numĂ©rique.
La thĂ©orie des nombres fut longtemps considĂ©rĂ©e comme une discipline abstraite, pure, sans aucune application pratique. Pour Gauss : « La MathĂ©matique est la reine des sciences, et lâArithmĂ©tique est la reine des mathĂ©matiques », selon Kronecker (1823-1891), lâun des concepteurs de la thĂ©orie des corps : « Dieu a créé les nombres entiers. Tout le reste est lâĆuvre de lâhomme » (Warusfel, 1961), et enfin pour le mathĂ©maticien anglais Hardy (1877-1947) la thĂ©orie des nombres est « inutile », et donc sans effet sur les « occupations quotidiennes des hommes » et sur « lâorganisation de la sociĂ©tĂ© » : elle relĂšve des « vraies mathĂ©matiques » (Hardy 1985). Mais la nature discrĂšte des informations manipulĂ©es par les ordinateurs, le problĂšme dâĂ©change de clĂ© en cryptographie et les travaux acharnĂ©s de certains mathĂ©maticiens et informaticiens dans les annĂ©es 1970 vont investir, avec la cryptographie Ă clĂ© publique, un autre champ de la thĂ©orie des nombres, celui des propriĂ©tĂ©s des nombres premiers. Les applications concrĂštes de la thĂ©orie des nombres dĂ©veloppĂ©es en cryptologie induisent un profond changement dans lâorganisation de la sociĂ©tĂ©, et la cryptographie occupe actuellement une place centrale dans notre vie quotidienne.
LE PROBLĂME DâĂCHANGE DE CLĂS DĂBOUCHE SUR LA NOTION DE CRYPTOGRAPHIE Ă CLĂ PUBLIQUE
Parmi les cryptologues qui sâattaquĂšrent au problĂšme de la distribution des clĂ©s, le plus original fut sans doute Whitfield Diffie. Ce mathĂ©maticien, nĂ© en 1944, diplĂŽmĂ© du MIT (Massachussetts Institute of Technology) travaillait pour le compte de plusieurs entreprises dans la sĂ©curitĂ© informatique. Le problĂšme de la distribution des clĂ©s occupa une grande partie de son carnet de notes personnelles, oĂč il consigna ses rĂ©flexions sur des ProblĂšmes pour une thĂ©orie ambitieuse de la cryptographie. Les recherches de Diffie sâappuyĂšrent sur sa vision dâun monde oĂč les ordinateurs seraient reliĂ©s entre eux par des lignes tĂ©lĂ©phoniques. Il pensa alors que, si des personnes pouvaient un jour Ă©changer des courriels, elles auraient besoin de pouvoir Ă©changer des clĂ©s pour assurer la confidentialitĂ© de leurs messages.
Diffie fit la connaissance, en 1974, dâun chercheur en cryptographie qui sâintĂ©ressait Ă©galement au problĂšme de lâĂ©change des clĂ©s : Martin Hellman. Ce professeur de lâuniversitĂ© de Stanford, nâayant pas de budget pour recruter Diffie sur un poste permanent, lui proposa une bourse de thĂšse pour quâils puissent se consacrer ensemble Ă la recherche dâun moyen permettant la distribution des clĂ©s tout en Ă©vitant le fastidieux et fragile systĂšme de transport physique. Les deux hommes travaillĂšrent dans lâisolement car la majeure partie de la communautĂ© des cryptologues ne croyait pas Ă ce rĂȘve considĂ©rĂ© comme impossible. La difficultĂ© du problĂšme rĂ©sidait dans le fait que, pour partager un secret (le message), les correspondants doivent au prĂ©alable partager un autre secret (la clĂ© secrĂšte). Cette particularitĂ© donne au problĂšme une allure de cercle infernal. La solution trouvĂ©e par Diffie et Hellman est aujourdâhui prĂ©sentĂ©e sous la forme dâune histoire (fig. 1 ci dessous), illustrant la possibilitĂ© dâĂ©changer un message en toute sĂ©curitĂ© sans distribution de clĂ©.
Soit Alice et Bernard (1) deux personnes voulant communiquer sans échanger de clé, alors :
1. Alice met sa lettre dans un coffre, quâelle ferme avec sa clĂ©, et lâenvoie Ă Bernard.
2. Bernard renvoie Ă Alice le coffre oĂč il a ajoutĂ© son propre cadenas, quâil a fermĂ© avec sa propre clĂ©.
3. Alice reçoit le coffre, elle ĂŽte son cadenas et renvoie Ă Bernard le coffre qui nâest plus fermĂ© quâavec le cadenas de ce dernier.
4. Bernard reçoit le coffre et nâa plus quâĂ ouvrir son cadenas pour lire la lettre.
Cette opĂ©ration est sĂ»re, mais nĂ©cessite plusieurs trajets. Pour permettre un Ă©change sĂ©curisĂ© en un seul trajet, Bernard peut alors, dans un premier temps, distribuer beaucoup dâexemplaires de son cadenas (dont il est le seul Ă dĂ©tenir la clĂ©) : Alice peut alors sâen procurer un pour envoyer son message Ă Bernard. Le principe semble simple, mais il est difficile, dâun point de vue mathĂ©matique, de trouver une fonction permettant un schĂ©ma opĂ©rationnel similaire.
RSA : LA MISE EN OEUVRE DE LA CRYPTOGRAPHIE ASYMĂTRIQUE
La premiÚre publication de cet algorithme parut en août 1977, dans la rubrique de jeux mathématiques du Scientific American, dans un article
intitulé «A New Kind of Cipher that Would Take Millions of Years to Break » («Un nouveau type de cryptage qui nécessiterait des millions
dâannĂ©es pour ĂȘtre cassé»). Ses concepteurs, Rivest, Shamir et Adelman, fournirent un schĂ©ma de chiffrement et de signature baptisĂ© RSA : acronyme de leurs trois noms (fig. 2) :
« m » : message
« CléPu » : la clé publique permettant de coder le message « m »
« CléPriv » : la clé privé, permettant de décoder le message « m »
CASSER LES CODES
LâactivitĂ© qui consiste à « casser » les codes sâappelle cryptanalyse, elle fait appel massivement Ă la thĂ©orie des nombres. On rencontre dans cette quĂȘte les noms de Pierre de Fermat, bien sĂ»r, et dâAndrew John Wiles, qui en dĂ©montra la conjecture, en faisant un thĂ©orĂšme, mais aussi de Carl Friedrich Gauss, Leonardo Fibonnacci, Jacques Hadamard et Sophie Germain. Tous nâĂ©taient effectivement pas vraiment chinois, mais câest dans le traitĂ© chinois des neuf procĂ©dures, datĂ© sensiblement du IIe siĂšcle de notre Ăšre quâon en trouve la plus ancienne trace. Ce thĂ©orĂšme, dit «mĂ©thode des restes chinois» (voir encadrĂ©), et tout le travail qui a Ă©tĂ© fait dessus â dont Ă©noncĂ© et dĂ©monstration sortent du cadre de cet article â permet si on est aidĂ© dâordinateurs trĂšs puissants, de retrouver les nombres p et q car il faut quand mĂȘme faire de trĂšs nombreux essais, surtout si les clĂ©s RSA sont de grande longueur. En effet, sachant quâil nâexiste pas de code incassable, lorsquâon veut protĂ©ger une information, il faut savoir pendant combien de temps on veut la protĂ©ger, et on choisit la longueur de la clĂ© du code en fonction de la durĂ©e de vie voulue de lâinformation, sachant que le temps de calcul pour casser la clĂ© double chaque fois quâon ajoute un chiffre Ă la clĂ©. Connaissant ainsi la puissance des superordinateurs les plus rapides au monde, on peut choisir un couple de nombres premiers de longueur voulue.
*SOUFIAN BEN AMOR est maĂźtre de confĂ©rences, HDR au laboratoire PRiSM (UMR CNRS 8144), universitĂ© de Versailles – Saint-Quentinen-
Yvelines.
(1) Alice, Bernard (Bob chez les anglophones) et Ăve (Charlie chez les anglophones) sont des acteurs cryptographique imaginaires adoptĂ©s dans le monde entier.
(2) On dit que deux nombres sont premiers entre eux sâils nâont pas dâautres diviseurs communs que 1.
(3) Lâalgorithme dâEuclide Ă©tendu permet de calculer le PGCD notĂ© D, non seulement de deux entiers a et b mais aussi de x et de y vĂ©rifiant la relation ax + by = D. Dans le cas du cryptosystĂšme RSA e et Ï sont premiers entre eux, donc D =1 et on dĂ©termine ainsi lâinverse d de e par identification puisque, dans lâĂ©quation ed + Î»Ï =1, d et Ï sont connus.
Références :
G.H. Hardy, LâApologie dâun mathĂ©maticien, Paris, Belin, 1985.
A. Warusfel, Les Nombres et leurs mystĂšres, Paris, Seuil, 1961.
LE PROBLEME DES PIRATES
Une bande de 17 pirates possĂšde un trĂ©sor constituĂ© de piĂšces dâor dâĂ©gale valeur. Ils projettent de se les partager Ă©galement, et de donner le reste au cuisinier chinois. Celui-ci recevrait alors 3 piĂšces. Mais les pirates se querellent, et 6 dâentre eux sont tuĂ©s. Un nouveau partage donnerait au cuisinier 4 piĂšces. Dans un naufrage ultĂ©rieur, seuls le trĂ©sor, 6 pirates et le cuisinier sont sauvĂ©s, et le partage donnerait alors 5 piĂšces dâor Ă ce dernier.
Quelle est la fortune minimale que peut espĂ©rer le cuisinier sâil dĂ©cide dâempoisonner le reste des pirates ?
(Réponse dans le prochain numéro)