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)