La cryptographie moderne

La cryptographie entre dans son ère moderne avec l'utilisation intensive des ordinateurs, c'est-à-dire à partir des années septante. Dans la cryptographie moderne, on utilise aussi des problèmes mathématiques que l'on ne sait pas (encore) résoudre, par exemple factoriser des grands nombres (chiffre RSA) ou résoudre le problème général du sac à dos (chiffre de Merkle-Hellman).
Plus anecdotique, on voit aussi apparaître les deux personnages récurrents les plus célèbres de la cryptographie: Alice et Bob (ou Bernard en français).

   
 
Alice
  
Bob

Le chiffrement par blocs

Les algorithmes de chiffrements par blocs, pour la plupart basés sur des réseaux de Feistel, sont actuellement les algorithmes à clef secrète les plus courants. Cependant, depuis l'invention du DES en 1977, la puissance de calcul des ordinateurs a incroyablement progressé, si bien que la longueur des clefs est maintenant insuffisante. L'AES (Advanced Encryption Standard) est destiné à prendre la relève du DES, réputé peu sûr depuis quelques années. Après une mise au concours, le NITS (censé définir la norme pour le territoire américain, mais dont l'influence dépasse les frontières du pays), a choisi parmi de nombreux candidats pour l'AES un algorithme nommé Rijndael, conçu par des cryptologues belges, Vincent Rijmen et Joan Daemen. Rijndael n'est pas un réseau de Feistel et peut-être sonnera-t-il le glas de la suprématie des algorithmes basés sur ces schémas.

Les systèmes à clefs publiques

Depuis les origines de la cryptographie, et jusqu'à récemment, tous les procédés étaient basés sur une même notion fondamentale: chaque correspondant était en possession d'une clef secrète, qu'il utilisait pour chiffrer et déchiffrer. Cela a un inconvénient majeur: comment communiquer la clef au correspondant? Il faut pour cela utiliser un canal sûr, par exemple une valise diplomatique (ou de manière plus amusante, un "téléphone" composé de deux boîtes de conserve et d'un fil bien tendu). De toute manière, il faut un contact préalable avec la personne qui devra (dé)chiffrer nos messages.

Le milieu des années septante a vu l'avènement d'une nouvelle méthode de cryptage: le système à clefs publiques. L'idée de ce système a été proposée en 1976 par Diffie et Hellman, qui ont proposé une méthode totalement nouvelle: une clef pour chiffrer et une autre pour déchiffrer.


Merkle, Hellman et Diffie

Bien entendu, il existe un lien mathématique entre ces deux clefs, mais ce lien est constitué par ce que les deux inventeurs appellent une «fonction trappe à sens unique». Cette fonction permet de calculer aisément la clef de chiffrement en connaissant la clef de déchiffrement. En revanche, l'opération inverse est pratiquement impossible.
L'intérêt de ce système est considérable. En effet, toute personne ou toute entreprise disposant de moyens informatiques peut élaborer sa clef de déchiffrement - qu'elle garde secrète pour son usage exclusif - puis en déduire la clef de chiffrement correspondante. Tous les utilisateurs de ce système agissant de même, les clefs de chiffrement peuvent ensuite être groupées dans une sorte d'annuaire mis à la disposition du public. Ainsi deux correspondants peuvent-ils communiquer secrètement sans aucun contact préalable. Les systèmes à clefs publiques les plus connus sont RSA et PGP, mais il en existe d'autres, par exemple le chiffre de Merkle-Hellman et le chiffre de Rabin.

Comme souvent dans l'histoire de la cryptographie, les vrais découvreurs ne sont pas toujours ceux que l'on pense. En effet, l'histoire a retenu les noms de Merkle, Hellman et Diffie car ils ont été les premiers a publié leur invention. En fait, on a appris plus tard que les trois premiers inventeurs de l'idée du système à clef publique était James Ellis, Clifford Cocks et Malcom Williamson, qui travaillaient au Government Communications Headquarters (GCHQ) de Cheltenham, établissement anglais top secret fondé sur les ruines de Bletchley Park après la Seconde Guerre mondiale.

Ellis Cocks Williamson

Ellis posa les bases dès 1969. Puis, en 1973, Cocks eut une idée de ce qui serait plus tard connu sous le nom de chiffre asymétrique RSA. Il ne put mettre en oeuvre son idée, car les ordinateurs de l'époque n'étaient pas encore assez puissants. En 1974, Cocks expose son idée à Williamson. Ce dernier, qui pense que cela est trop beau pour être vrai, reprend tout à zéro pour trouver une faille. Au lieu de cela, il trouve le système d'échange de clef de Diffie-Hellman-Merkle, à peu près en même temps que Martin Hellman. En 1975, Ellis, Cocks et Williamson avaient donc découvert tous les aspects fondamentaux de la cryptographie à clef publique, mais les trois anglais se turent, secret militaire oblige. L'histoire complète est présentée dans le livre de Simon Singh, pp. 302-317.

Références

  Didier Müller, 24.1.21