au sommaire
La cryptologiecryptologie et l'informatique ont connu un développement à partir de la Seconde Guerre mondiale. Créée par Claude Shannon, la théorie de l'information, qui a conduit à la numérisationnumérisation de pans technologiques entiers, est née de la question de savoir ce que pouvait apprendre un adversaire en observant une communication chiffrée.
Le mathématicienmathématicien britannique Alan Turing, connu pour avoir modélisé la notion de calculabilité avec la machine qui porteporte son nom, a eu un rôle crucial au sein de l'équipe de Bletchley Park, chargée du décryptement des messages de l'armée allemande.
La recherche des clés devenait une tâche trop complexe pour être réalisée à la main, et il a fallu construire des machines de plus en plus puissantes pour tester les innombrables combinaisons possibles. Les techniques mises en œuvre pour réaliser ces calculs ont contribué de manière cruciale au développement des premiers ordinateursordinateurs.
L'ingénieur en téléphone Tommy H. Flowers a eu l'idée d'employer des tubes à vide, récemment utilisés pour la commutationcommutation téléphonique, afin de construire un immense calculateur, le Colossus, destiné au décryptement du téléscripteur chiffrant allemand.
Le calculateur Colossus
Les progrès réalisés par les moyens de calcul suivent une loi empirique, appelée loi de Moore, du nom du directeur de recherche du fabricant américain de circuits intégréscircuits intégrés Fairchild qui l'a énoncée la première fois en 1965. Celle-ci affirme que la puissance des calculateurs électroniques double tous les 18 mois, ce qui s'est vérifié jusqu'à aujourd'hui. Alors qu'il a fallu plus de 70 heures à l'ordinateur Eniac pour calculer 2.000 décimales du nombre π en 1949, le moindre calculateur embarqué dans un téléphone portable réalise aujourd'hui ce calcul en une fraction de seconde. En 1977, la revue Scientific American a présenté le RSARSA sous l'appellation « un nouveau système qu'on mettrait des millions d'années à casser ». Pourtant, la clé publiqueclé publique qu'il contenait a été factorisée en 1994, bien avant les délais annoncés !
Cet incroyable et constant progrès rend envisageable l'application de la force brutale pour chercher la clé d'un procédé dans des ensembles de plus en plus grands. Pourtant, c'est au chiffreur et non au décrypteur que bénéficient les progrès des moyens de calcul. Supposons que l'on utilise, à un moment donné, des nombres de 200 chiffres comme module RSA. Si la puissance de calcul double, la taille du module pourra être portée à 250 chiffres sans que l'utilisateur constate le moindre changement dans la rapiditérapidité du calcul. Le travail de l'adversaire pour factoriser ce nouveau module suit cependant une loi donnée par la formule c(n) = exp(k(ln(n))1/3(ln(ln(n)))2/3) pour un nombre de n chiffres. Ce travail devra donc être multiplié par un facteur 36. Avec sa puissance de calcul qui n'aura que doublé, il aura perdu un facteur 18 dans l'affaire. Plus les machines sont puissantes, et plus la dissymétrie entre le chiffrementchiffrement et l'attaque donne un avantage au chiffrement.
