Analyse

En mémoire d’Anthony Genot[1]

Depuis que les êtres humains communiquent, ils cherchent à le faire en toute discrétion. César a sécurisé un des plus grands empires de l’histoire en décalant dans ses messages les lettres de l’alphabet de 3 positions. Ainsi VENI VIDI VICI aurait été chiffré ZHQM ZMGM ZMFM dans l’alphabet romain de 23 lettres du 1er siècle avant notre ère. Cela suppose que Jules César, qui envoie un message, et une réceptrice, disons Cléopâtre, possèdent un secret en commun : Jules César décale de trois lettres, Cléopâtre décale de trois lettres dans le sens inverse. Cette introduction est bien sûr un peu romancée pour motiver la lecture de la suite, mais elle introduit le concept clé de la cryptographie : le secret partagé.

Sept siècles plus tard, l’analyse de la fréquence des lettres — un A est plus fréquent qu’un Z par exemple — introduite par le mathématicien Al-Kindi, permet de casser ce type de code. L’avènement de l’informatique a révolutionné non seulement le besoin de chiffrement, mais également les techniques permettant de trouver les failles logiques dans les méthodes de chiffrement -la cryptanalyse -. Cela signifie que le chiffrement de César aurait été cassé en une fraction de seconde par un ordinateur de bureau.

Les communications numériques actuelles chiffrent chaque seconde des milliards de transactions, de messages, de données médicales, de secrets d’État, de transactions bancaires, et de navigations internet. Essentiellement, c’est ce que veut dire le petit cadenas vert à gauche de votre barre de navigation. Mais la nature du problème n’a pas changé : comment deux personnes séparées par des milliers de kilomètres peuvent-elles s’accorder sur un secret commun sans que personne ne l’intercepte et que ce secret commun soit incassable par n’importe quelle attaque logique ?

La réponse qu’ont trouvée les informaticiens depuis les années 1970 repose sur la difficulté calculatoire de certains problèmes mathématiques. Factoriser un gr