CRYPTOGRAPHIE                                                                                           
Les nombres et leurs secrets
par Claude Crépeau
Aux siècles de Fermat, d'Euler et de Gauss, la théorie des nombres était vraiment la reine des mathématiques. Reconnue pour sa beauté et son élégance intrinsèque, elle a longtemps joui d'une réputation de théorie «pure», ayant peu d'applications pratiques.

L'auteur

Claude Crépeau est professeur à l'École d'informatique de l'Université McGill.

 

 

Mais depuis un quart de siècle, elle est de plus en plus utilisée dans un domaine jusque-là inattendu : la cryptographie (la science du codage secret). La théorie des nombres prend tout à coup des airs mystérieux. Depuis les travaux novateurs de Diffie et Hellman, puis ceux de Rivest, Shamir et Adleman, la sécurité d'une grande partie des informations confidentielles repose sur la difficulté légendaire de certains problèmes de la théorie des nombres. Les plus connus de ces problèmes sont la factorisation entière, l'extraction des racines discrètes et des logarithmes discrets. Ces problèmes ont l'étonnante propriété d'Ítre plus faciles à générer qu'à résoudre. Prenons un exemple, avec deux nombres : 3 251 et 5 939. Au bout d'une petite minute de calcul, on peut facilement trouver leur produit : 3 251 x 5 939 = 19 307 689. Par contre, résoudre le problème inverse (trouver deux nombres entiers tels que leur produit sera égal à 19 307 689, c'est ce qu'on appelle la factorisation) demande beaucoup, beaucoup plus de temps.

La cryptographie

Le système RSA (conçu dans les années 70 par Rivest, Shamir et Adleman, trois chercheurs du MIT), repose essentiellement sur le mÍme principe. Ce système, qui est le plus couramment utilisé pour le chiffrement d'informations que l'on veut garder secrètes, est d'autant plus difficile à percer que les nombres qu'il utilise ont de 200 à 300 chiffres. Les méthodes actuelles permettent de factoriser des nombres comptant au plus 155 chiffres. Les nombres de plus de 200 chiffres sont totalement hors de portée des méthodes de factorisation connues aujourd'hui. Il faudrait des millions d'années à tous les ordinateurs du monde pour accomplir cette tâche !

Comme l'enjeu est de taille - il en va de la sécurité des transactions bancaires et des diverses applications commerciales de la cryptographie - les cracks sont à l'oeuvre, qu'ils soient chercheurs universitaires ou cyberfraudeurs. Dans ce domaine, en effet, tout progrès technologique ou théorique avantage autant les « bons » que les « méchants »! D'ailleurs, la National Security Agency américaine emploierait à elle seule une véritable armée de mathématiciens. Par conséquent, de nouveaux records sont établis de temps en temps. Le dernier date du mois d'août 1999, c'est le nombre RSA-155. Sa factorisation a nécessité le travail de 300 ordinateurs personnels pendant une période de sept mois. Soit l'équivalent de 35 ans de calcul par une seule machine !

De nouvelles méthodes

Les recherches sur la factorisation ont également favorisé l'émergence de méthodes radicalement nouvelles et tout à fait surprenantes. Il y a quelques années, l'Américain Peter Shor a développé une méthode très simple et très efficace pour factoriser les grands nombres ou résoudre les deux autres problèmes déjà cités. Alors, qu'attend-on pour l'utiliser ? C'est que cette méthode fonctionne sur un ordinateur qui n'existe pas encore ! Il s'agit bel et bien d'une idée révolutionnaire de dompter l'étrange nature de la mécanique quantique afin de la mettre au profit des services secrets. Des fonds considérables sont aujourd'hui consacrés à la mise au point de cet « ordinateur quantique », supermachine pleine de promesses, mais dont la réalisation est semée de difficultés techniques.

Si cette machine n'existe pas encore, la cryptographie de demain est pourtant née. On étudie déjà les problèmes difficiles qui résisteront à ce futur ordinateur quantique. L'enjeu est de découvrir un problème dont il est facile de générer des exemplaires, comme la factorisation, mais dont la résolution est la plus difficile possible. On pourrait alors générer une méthode secrète de chiffrement virtuellement impénétrable.

La théorie des nombres, considérée pendant des siècles comme une théorie pure, belle et élégante, mais sans véritables applications pratiques, est donc devenue essentielle pour les transactions financières les plus courantes, comme pour les opérations des services secrets partout dans le monde.

retour vers le haut