Depuis le début de l’année, la communauté de la cryptographie se déchire en public au sujet de l’avenir du célèbre algorithme à clés publiques RSA. La controverse a été déclenchée en fin 2001 par un document de recherche publié par Daniel Bernstein, professeur de mathématiques à l’université de Chicago. Dans ce texte intitulé “Circuits for Integer Factorization : a Proposal”, il décrit un mécanisme de factorisation qui permettrait de casser des clés RSA d’une taille de 1 024 bits en divisant par trois les temps de calcul nécessaires. Jusqu’alors, seules des clés de 512 bits avaient été brisées.Les conséquences d’une telle découverte sont lourdes. En effet, l’algorithme RSA est le standard de facto pour les infrastructures à clés publiques, ainsi que pour la quasi-totalité des protocoles de sécurité d’internet ?” IPsec, SSH, S/Mime, etc. Plusieurs mois durant, des débats d’experts ont fait rage sur la crédibilité à accorder aux travaux de Bernstein. Certains cryptographes, et non des moindres, ont solennellement annoncé la mort des communautés PGP bâties sur des clés RSA de 1 024 bits.Mais il a fallu attendre cet été pour que paraisse la première analyse de fond. Rédigée par une équipe d’éminents spécialistes(*), elle démontre que, en réalité, les calculs de Bernstein n’améliorent que d’un facteur 1,7 le temps nécessaire pour factoriser une clé RSA de 1 024 bits. De plus, les affirmations du mathématicien sont fondées sur une évaluation de coût non standard et qui, de plus, est asymptotique. “Bernstein estime qu’il existe une taille de clé au-delà de laquelle sa méthode a un coût moindre que celle standard. Mais personne ne sait quelle est cette limite”, explique Thomas Pornin, fondateur de Cryptolog.
Des méthodes astucieuses, quand même !
Par ailleurs, la méthode de factorisation de clés RSA utilisée par le mathématicien s’appuie sur l’algorithme General Number Field Sieve (GNFS). Employé depuis plusieurs années, celui-ci se fonde sur une méthode d’attaque mathématique pour venir à bout de clés RSA de taille importante. L’innovation des travaux de Bernstein porte sur l’amélioration de GNFS. La première phase de cet algorithme passe au crible des nombres dit “lisses”, qui sont en relation avec le nombre que l’on cherche à factoriser. Bernstein propose ici de recourir à une factorisation à base de courbes elliptiques. Cela réduit les demandes de mémoire exorbitantes engendrées par GNFS. Mais cette approche n’est pas neuve, et elle s’avère coûteuse et complexe à appliquer.En réalité, la découverte de Bernstein porte sur l’amélioration de la deuxième phase de GNFS. Il s’agit ici de résoudre le système de matrices constitué à partir des nombres lisses obtenus. “Bernstein propose des méthodes astucieuses pour la résolution des matrices, qui pourraient aboutir à une mise en ?”uvre concrète”, reconnaît Burt Kaliski, directeur des laboratoires RSA. “Prises dans leur ensemble, les propositions de Bernstein ne sont pas applicables à un cas réel. Même si, d’un point de vue scientifique, cela reste un travail intéressant”, conclut, pour sa part, Thomas Pornin.(*) ” Analysis of Bernstein’s Factoring Circuit “, par Arjen K. Lenstra, Adi Shamir, Jim Tomlinson et Eran Tromer ; juin 2002.
🔴 Pour ne manquer aucune actualité de 01net, suivez-nous sur Google Actualités et WhatsApp.
