Deux clés valent mieux qu'une

Hubert Quirin

Tous les codes secrets ont la même faiblesse : ils ont une clé. une clé qui est nécessairement connue de l'envoyeur et du destinataire. Et éventuellement par le secretaire, l'officier de transmission, le responsable informatique... Sans compter les fois où elle est inscrite sur un Post-it collé au bureau. Bref, la clé se promène un peu partout. Comment être certain qu'elle n'a pas été recopiée et transmise à des tiers ? Conscients du problème, deux chercheurs américains, Whitfield Diffie et Martin Hellman, ont proposé une approche radicalement différente : au lieu d'avoir une seule clé qui est nécessairement partagée par l'envoyeur et le destinateur, le système en possède deux. L'une, publique, sert à chiffrer, l'autre, privée, à déchiffrer.
imaginons que 007 soit en mission chez les Shans, en Birmanie. Il garde sur lui l'algorithme de chiffrement et la clé publique. Mais il ne possède pas la clé privée, restée au pays de Sa Gracieuse Majesté. 007 peut donc chiffrer, mais il ne peut pas déchiffrer son propre message ! Et si les Shans réussissent à s'emparer de la clé publique, ils ne seront pas plus avancés que lui. Pour déchiffrer, il faut la clé privée. L'avantage du système ? La clé privée ne voyage pas et court donc moins de risque d'être captée par des indiscrets. C'est un peu le principe de la boîte aux lettres : tout le monde peut y glisser quelque chose, mais seul celui qui en a la clé peut retirer le courrier. Le système à double clé le plus connu est RSA (du nom de ses auteurs : Rivest, Shammir et Adleman) inventé, en 1978, au Weizmann Institute en Israël.
Schématiquement, un algorithme de chiffrement est une fonction. Dans le cas de RSA, il s'agit de trouver une fonction telle que la réciproque (qui permet le déchiffrment) soit très difficile à calculer. Il existe malgré tout un lien mathématique entre les deux, faute de quoi le déchiffrement serait impensable, mais ce lien est quasiment impossible à établir. Si, par exemple, je fais une réussite, j'utilise des règles qui me permettent de mettre à la fin les cartes dans un certain ordre. Mais j'aurai bien du mal à établir les règles réciproques qui, partant de l'ordre final me permettraient de retrouver précisemment l'état initial du jeu de cartes. En ce qui concerne RSA, l'astuce repose sur la difficulté de décomposer les grands nombres en facteurs premiers. 22 par exemple, se décompose en deux nombres premiers, 11 et 2. L'opération, triviale pour les petits nombres, devient effroyablement longue et fastidieuse pour les très grands. A titre d'exemple, une équipe constituée de 600 utilisateurs a mis six mois à casser un nombre de 129 chiffres !
RSA part donc de deux nombres premiers, x et y, assez grands. On les multiplie l'un par l'autre pour trouver P qui devient la clé publique tandis que x et y forment la clé secrète. Comme P est très grand, il est extrêmement difficile de retrouver la clé secrète. Les spécialistes considèrent que la factorisation des grands nombres est impraticable pour des nombres de plus de 512 bits (2^512 zéros et un les uns à la suite des autres, ce qui symbolise en système binaire un nombre qui dépasse le milliard de milliards).
Philipp Zimmermann s'est inspiré de RSA pour écrire, en 1984, son fameux PGP (Pretty Good Privacy, ou "plutôt bonne intimité"), le code secret qui circule aujourd'hui librement sur les réseaux informatiques comme Internet. Contrairement à la légende, PGP n'est pas inviolable. C'est une question de temps et d'argent. Si une organisation veut vraiment casser un texte chiffré avec PGP, elle peut y arriver à condition de mobiliser une dizaine de supercalculateurs pendant plusieurs semaines. Coût de l'opération : 500 millions de francs au minimum. De plus, l'inviolabilité de PGP repose sur notre ignorance de la factorisation des grands nombres. Or, depuis l'arrivée de PGP, les mathématiciens se sont remis, un peu partout dans le monde, à travailler sur les moyens de trouver les très grands nombres premiers. A leur manière, les codes secrets font avancer la théorie des nombres...

Texte paru dans Sciences et Avenir.