La cryptologie science du secret, Soufian Ben Amor*

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.

Bandeau_portail_crypto

 

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Ă©.

n39-

 

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) :

n40

« 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.


 

Capture d’écran 2014-11-11 Ă  17.17.28

 

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)

Laisser un commentaire

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.