Commentaires sur :

Steven Levy "Crypto" Viking 2001

10 juin 2001

Steven Levy est l'auteur de "Hackers", qui retraçait la vie, les idées et les travaux des pionniers de l'informatique des années 60 et 70. Dans "Crypto", il décrit l'aventure de ceux qui ont conçu les systèmes de cryptographie. Il aime les personnages qui, s'intéressant à une question dont ils ne sont pas les spécialistes les plus "pointus",  l'abordent avec un regard neuf et trouvent la solution "hérétique" à laquelle personne d'autre n'aurait pu penser. 

La cryptographie, c'est cet art que nous avons tous pratiqués au lycée lorsque nous adressions à nos copains des lettres écrites selon un alphabet secret. C'est aussi la branche des mathématiques qui sert à chiffrer (ou déchiffrer) les messages des militaires et des espions. L'un des sommets de son histoire est le déchiffrage de la machine allemande Enigma par Alan Turing, pionnier de l'informatique, héros de la victoire contre le nazisme conduit après la guerre au suicide par les persécutions qu'exerçait la "justice" de la prude Angleterre envers les homosexuels. 

Levy décrit un procédé que j'utilise depuis des années, puisqu'il équipe Lotus Notes, mais auquel je n'avais rien jamais compris : la "clé publique" découverte par James Ellis en 1969 et par Whitfield Diffie en 1975.C'est un procédé hérétique (ce sont les meilleurs), puisqu'il suppose de publier la clé de codage alors que la tradition voulait que la clé fût gardée secrète.

Voici l'affaire en quelques mots et selon mes notations. Il faut, pour que cela marche, disposer d'une fonction mathématique unidirectionnelle ("one-way function") munie d'une porte arrière ("trapdoor"). Une fonction unidirectionnelle, c'est une fonction y = f(x) telle que, si l'on connaît la valeur y, il est pratiquement impossible de calculer la valeur x (c'est-à-dire d'inverser la fonction f). On dit que cette fonction est munie d'une porte arrière s'il existe une fonction x = g(y, z) telle que, si l'on connaît z, il soit au contraire facile de calculer x à partir de y. 

Vous suivez ? Sinon, relisez le paragraphe qui précède avant de continuer : dès que les notations mathématiques apparaissent, il faut diviser la vitesse de lecture par trois. Conservez cette vitesse lente pour lire les paragraphes suivants. 

Supposons que Bob veuille recevoir des messages codés d'Alice, et qu'il souhaite que ces messages soient indéchiffrables pour Ève qui a pourtant accès à leurs échanges. Bob et Alice connaissent la fonction unidirectionnelle f ; Bob fournit à Alice sa "clé publique" c. f et c, pouvant être connus de tout le monde, sont bien sûr connus d'Ève. Alice va coder le message M en utilisant l'algorithme f et la clé c ; ceci fournit un texte T chiffré ayant les apparences d'une suite de caractères au hasard :

T = f(M, c). 

Comme f est une fonction unidirectionnelle, Ève sera incapable de reconstituer le message même si elle connaît l'algorithme f, la clé publique c et le texte T. 

Par contre Bob, lui, possède la "clé privée" z qui est, elle, absolument secrète. z ouvre la porte arrière de la fonction f et permet de déchiffrer le message en appliquant la fonction g au triplet (T, c, z) :

M = g(T, c, z).

Pour que le procédé soit utilisable, il faut bien sûr avoir défini le couple des fonctions f et g ; cela demande une maîtrise des mathématiques que ni Ellis, ni Diffie ne possédaient. Le système à clé publique n'a donc d'abord été qu'une idée dont la faisabilité restait à démontrer. Puis des mathématiciens ont mis au point les algorithmes : certains utilisent le fait que la factorisation du produit de deux grands nombres entiers demanderait un temps de calcul de plusieurs millions d'années. Le problème était ainsi résolu (supposez que la clé publique c soit le produit de deux grands nombres entiers, que la clé privée z soit l'un de ces deux nombres entiers, et que g comporte la factorisation de c : seul Bob, qui connaît z, pourra factoriser c et donc déchiffrer T).

Le système de chiffrement à clé publique devient universel si chacun publie sa clé publique dans un annuaire : pour envoyer un message chiffré à Bob, il suffit de trouver sa clé publique dans l'annuaire et de s'en servir pour chiffrer le message avant de le lui envoyer ; seul Bob pourra déchiffrer le message. Il faut bien sûr que l'annuaire soit fidèle : il se pourrait que la perfide Ève ait substitué sa propre clé publique à celle de Bob afin de pouvoir lire les messages destinés à Bob : des procédés ont été inventés pour traiter ce risque.

Si j'ai publié ma clé publique dans l'annuaire, et que je reçois un message signé "Bob", qui me garantit que ce n'est pas Ève qui a imité la signature de Bob ? ici l'on rencontre une astuce d'une grande beauté : le système peut servir non seulement à chiffrer les messages, mais aussi à authentifier la signature de l'expéditeur. Voici comment : 

1) Bob chiffre sa signature avec sa propre clé privée ; puis il chiffre avec ma clé publique l'ensemble formé par son message M et sa signature déjà chiffrée. Cela donne le texte chiffré T.

2) Lorsque je reçois T, je trouve en utilisant ma clé privée le message M et la signature chiffrée de Bob ; je peux ensuite déchiffrer la signature en utilisant la clé publique de Bob. Cela me garantit que c'est Bob qui a envoyé ce message, puisque seul Bob peut chiffrer un texte en utilisant sa propre clé privée. 

Le chiffrement à clé publique apporte ce dont on a besoin pour communiquer en toute sécurité sur l'Internet, faire du commerce, protéger des travaux confidentiels etc. Ce système a beaucoup contrarié la National Security Agency (NSA),  qui est chargée d'une part d'espionner tout le monde pour le compte des États-Unis (comme nous l'a bien montré le système Echelon installé en Grande-Bretagne pour espionner l'Europe), et d'autre part de protéger les secrets des États-Unis contre tout le monde. Il y a eu des disputes, dans le style juridique typique des américains, entre tenants de la sécurité nationale et tenants de la confidentialité privée. Pendant un temps, les industriels du logiciel n'ont pas eu le droit d'exporter hors des États-Unis la version la plus efficace des algorithmes mais seulement une version qui, utilisant une clé plus courte, pouvait être déchiffrée dans un temps de calcul plus court (le temps de calcul double chaque fois que l'on ajoute un bit à la clé).

Pourquoi le système à clé publique a-t-il été découvert deux fois ? parce que les travaux réalisés par la NSA ou ses homologues étrangers étaient secrets. Les recherches sur la cryptographie étaient donc menées dans deux mondes : les chercheurs des services secrets, et les chercheurs de l'université ou de l'industrie. Ellis travaillait chez l'homologue britannique de la NSA, et sa découverte est restée longtemps secrète. Lorsque Diffie découvrit le procédé, il n'avait jamais entendu parler des travaux d'Ellis. 

Les algorithmes f et g étaient de gros consommateurs de puissance informatique. Pour qu'ils puissent être utilisés sur l'Internet, il restait à les adapter au PC : ce fut le travail de Philippe Zimmermann qui publia "Pretty Good Privacy" (PGP) en  1991, non sans encourir les foudres de la NSA. Le travail de Zimmermann a demandé plusieurs années, et sa description constitue l'un des passages les plus intéressants du livre : elle montre les difficultés que doit surmonter celui qui produit un logiciel pour traiter de délicats problèmes d'optimisation.