Chiffrement : Apocalypse ou intox ?

Par Jerome Saiz, le 28 mars 2002 à 13:18:00.

Le jour que beaucoup de spécialistes du chiffrement craignaient est peut-être arrivé : un chercheur indépendant et un éditeur de solutions de chiffrement clament simultanément avoir découvert une méthode de factorisation rapide des nombres premiers. De quoi rendre caduques toutes les clefs asymétriques dans le monde, jusqu'à une longueur de 1024 bits.

Le chiffrement asymétrique de type RSA est au coeur de la sécurité informatique aujourd'hui. Il est un élément essentiel des PKI et des identités numériques.
Jusqu'à présent, il était réputé "quasi" inviolable pour des longueur de clefs supérieures à 1024 bits, et c'est donc ainsi que se sont vendues une nuée d'applications de sécurité (SSH, PKI, IPSEC). Cela devra toutefois peut-être changer à la lueur de deux annonces scientifiques concurrentes : on connaîtrait désormais une méthode de factorisation rapide des grands nombres premiers.
Pour bien comprendre l'enjeu d'une telle découverte, il est nécessaire de se pencher sur ce qui fait la force du chiffrement asymétrique employé par RSA. Techniquement, l'algorithme RSA tire sa robustesse de la quasi-impossibilité mathématique, à partir d'un grand nombre premier seulement, d'en retrouver un second qui lui a été associé arbitrairement.
Sauf que... depuis des années des hordes de mathématiciens travaillent à trouver une solution élégante à ce problème. Elégante, car la seule praticable jusqu'à aujourd'hui (hormis les méthodes linéaires ou différentielles) était une attaque frontale, qui devait essayer tous les nombres premiers dans un certain espace en les associant à celui connu. Et cela prend trop de temps, et demande trop de ressources, si l'espace à explorer dépasse 1024 bits (même s'il ne s'agit pas d'explorer 2^1024 possibilités, car toutes ne sont pas des paires de nombres premiers valables). Cela était irréalisable... avec les moyens actuels.
Arrive Daniel Bernstein, un professeur de mathématique à l'université de l'Illinois, aux Etats-Unis. Dans un article scientifique publié récemment, Daniel Bernstein indique comment, à l'aide d'un ordinateur taillé pour la tâche, il devient possible de factoriser une clef RSA de 1024 bits en quelque mois. Certes, la machine n'existe pas, et selon ses détracteurs, elle coûterait près d'un milliard de dollars (1,14 milliards €) à construire. Mais ces mêmes opposants, en revanche, confirment bien la validité scientifique de la méthode. Ce qui déplace alors le problème de la sécurité des clefs RSA sur le seul terrain de l'argent, et non plus de l'impossibilité mathématique. Et un milliard de dollars, ce n'est finalement qu'une fraction du prix d'un satellite d'observation militaire.
Simultanément, à l'autre bout du monde, la société britannique nCipher annonce, elle, être parvenue à factoriser, sans ordinateur à un milliard de dollars cette fois, une clef RSA de 512 bits en six semaines. Là aussi, s'il est vérifié, l'exploit est troublant. Car autant les clefs RSA de 1024 bits n'étaient généralement utilisées que dans des applications critiques, en raison de la charge qu'un tel chiffrement fait peser sur le système, autant les clefs à 512 bits sont beaucoup plus courantes dans l'industrie.
Il ne reste donc plus aux paranoïaques qu'à révoquer leurs clefs et à en créer de nouvelles d'une longueur de 2048 bits... elles devraient bien être sûres quelques mois encore !

La technique...

Voici, pour les curieux, le résumé de "l'explication" de Daniel Bernstein. Le reste est disponible sur son site personnel.

The number field sieve takes time L^{1.901...+o(1)} on a general-purpose computer with L^{0.950...+o(1)} bits of memory; here L is a particular subexponential function of the input size. It takes the same time on a parallel trial-division machine, such as Cracker or TWINKLE, of size L^{0.950...+o(1)}. It takes time only L^{1.185...+o(1)} on a machine of size L^{0.790...+o(1)} explained in this paper. This reduction of total cost from L^{2.852...+o(1)} to L^{1.976...+o(1)} means that a ((3.009...+o(1))d)-digit factorization with the new machine has the same cost as a d-digit factorization with previous machines.

• 1
• 2
• » Suivant

A voir aussi

• Chiffrement : le gouvernement s'aligne sur l'Europe. (06 déc 2000)
• Le chiffrement par courbes elliptiques cassé à 109 bits. (07 nov 2002)
• Chiffrement : les espions américains font leurs emplettes. (04 nov 2003)
• Le chiffrement nouveau est arrivé ! (03 oct 2000)
• Chiffrement : fin de la liberté ? (19 mai 2006)