------------------------------------------------------------------------------ Un chercheur de l'INRIA assisté de 195 internautes du monde entier relève avec succès un défi cryptographique proposé par l'entreprise canadienne Certicom ------------------------------------------------------------------------ Paris, le 28 septembre 1999 Le défi cryptographique ECC2-97 à base de courbes elliptiques proposé par l'entreprise Certicom depuis deux ans vient de tomber après 40 jours de calcul distribué sur 740 ordinateurs et stations de travail répartis dans vingt pays. Dirigé par Robert Harley depuis le projet Cristal de l'Institut National de Recherche en Informatique et en Automatique (INRIA - Rocquencourt), le calcul a démontré qu'un système cryptographique de 97 bits à base de courbes elliptiques est plus difficile à casser qu'un système de 512 bits à base de factorisation d'entiers comme RSA-155. Les crypto-systèmes à base de courbes elliptiques sont connus depuis une quinzaine d'années mais n'ont été adoptés par les entreprises leaders du domaine, comme RSA Security Inc, que depuis peu de temps. Dès novembre 1997, le canadien Certicom a lancé son « ECC Challenge » qui consiste en une série de défis de difficulté croissante récompensés par des prix allant jusqu'à 100 000 US$. Ce challenge a pour but de stimuler la recherche dans le domaine des courbes elliptiques et de leurs applications cryptographiques et de donner au « Elliptic Curve Cryptography » des arguments de poids face au système à base de factorisation d'entiers. La difficulté à relever ces défis est un gage de sécurité offerte par les solutions cryptographiques à base de courbes elliptiques. Le défi dénommé « ECC2-97 » se place dans un ensemble d'environ 10^29 points sur une courbe elliptique choisie par Certicom. Pour le résoudre les participants ont d'abord calculé 119 248 522 782 547 de ces points (plus de 10^14) avec un logiciel libre développé par Robert Harley. Parmi ceux-ci, ils ont criblé 127 492 points « distingués » qui ont été recueillis sur une station Alpha Linux à l'INRIA où une dernière phase de traitement a découvert deux points jumeaux. Enfin, Robert Harley a calculé la solution à partir d'informations rattachées à ces points, apportant ainsi le coup de grâce au problème. La solution a été trouvée après un tiers seulement du calcul initialement prévu. La probabilité de trouver aussi tôt des points jumeaux était inférieure à une chance sur dix. Deux autres jumeaux ont même été détectés quelques heures après les premiers, ce qui avait moins d'une chance sur cent de se produire! Néanmoins la quantité de calcul, environ 16 000 MIPS-années, reste deux fois plus importante que celle utilisée lors de la factorisation de RSA-155 annoncée par Herman Te Riele du CWI (Amsterdam) et ses collègues, le 26 août 1999. « Ces résultats renforcent notre confiance en la difficulté du logarithme discret sur les courbes elliptiques, et il faudra en tenir compte dans les standards utilisés pour garantir la confidentialité sur Internet, » a commenté Robert Harley. De son côté, Andrew Odlyzko, Directeur de Recherche Mathématiques et Cryptographie chez AT&T Labs, a déclaré : « Cette opération de "craquage" du code est une réalisation superbe qui démontre comment on peut exploiter de manière fructueuse le potentiel informatique extraordinaire de l'Internet, qui reste en général totalement inutilisé ». Et il a ajouté : « Ainsi se trouvent validées des prédictions théoriques en termes de sécurité. Il faut continuer à augmenter les tailles de clés cryptographiques pour se protéger contre des menaces toujours plus fortes. » Arjen K. Lenstra, vice-président de la Direction de la Technologie à la Citibank à New York et l'un des principaux contributeurs à l'attaque réussie contre RSA-155, a comparé les deux calculs et remarque que ce nouveau résultat améliore la perspective des clés elliptiques de 160 bits par rapport aux clés RSA de 512 bits, du point de vue de la sécurité. « L'idéal serait de trouver de nouvelles avancées théoriques qui permettraient de renforcer ces résultats pratiques, mais de telles avancées paraissent hors de portée pour l'instant. » Sur les 5000 US$ du prix, les participants en donneront 4000 à la « Free Software Foundation », pour encourager la création de nouveaux logiciels libres. Les 1000 US$ restants sont destinés aux participants ayant trouvé les points jumeaux. En fait ils ont été trouvés tous deux par M. Paul Bourke avec un réseau de stations Alpha Unix, dont l'utilisation principale est d'étudier les pulsars au Centre d'Astrophysique de Swinburne University en Australie. Les équipes participantes les plus actives ont été: Astrophysics & Supercomputing Australie INRIA France University of New South Wales Australie L'équipe « Amis de Rohit Khare » États-Unis et France École Polytechnique France Compaq États-Unis et Italie Technischen Universität de Vienne Autriche University of Vermont États-Unis L'équipe «WinTeam» Internationale British Telecom Labs Royaume-Uni Internet Security Systems Royaume-Uni Rupture Dot Net États-Unis « Jabberwocky » États-Unis École Normale Supérieure de Paris France Pour la liste complète des participants et pour plus d'information, consulter les pages Web suivantes : The ECDL Project http://cristal.inria.fr/~harley/ecdl/ The Certicom ECC Challenge http://www.certicom.com/chal/ Contact scientifique : Robert Harley, INRIA, 01 39 63 51 57 Robert.Harley@inria.fr Contact médias : Christine Genest, INRIA : 01 39 63 55 18 Christine.Genest@inria.fr Sylvie Baranger, ALA : 01 43 22 79 56 sylvie@ala.com ------------------------------------------------------------------------------