Un nouveau record en cryptographie
© 2017 EPFL/Alain Herzog
Une collaboration entre l’EPFL et l’Université de Leipzig a permis d’établir un nouveau record dans le domaine de la cryptographie. L’équipe de chercheurs a réussi à casser un code d’une longueur exceptionnelle grâce à des méthodes mathématiques très poussées et une grande puissance de calcul.
La cryptographie, ou l’art de sécuriser des messages, est un domaine mélangeant mathématiques et informatique ayant une importance capitale dans le bon fonctionnement de nos réseaux actuels. Des mots de passe aux cartes de crédits en passant par les mails et autres messageries, tout y passe avant d’être envoyé sur un réseau. Si bien que de nombreux groupes, qu’ils soient pirates informatiques ou chercheurs, tentent sans cesse d’en trouver les failles et faiblesses.
Nombre de méthodes de cryptographie reposent sur le simple fait que la difficulté à résoudre certains problèmes mathématiques augmente lorsque les nombres traités deviennent plus grands. Les codes générés par ces méthodes sont donc très compliqués à briser, mais la tâche n’est pas impossible.
Cette fois-ci, c’est une équipe de mathématiciens et d’informaticiens de la Faculté IC et de l’Université de Leipzig qui sont à l’origine d’un nouveau record. Leur exploit porte sur le problème au doux nom de « logarithme discret », un problème très complexe à résoudre, sur lequel repose la communication sécurisée sur Internet, notamment les sites https et les Virtual Private Networks (VPN).
La résolution du problème de logarithme discret est d'une complexité comparable à la factorisation de grands nombres mais dont le principe et la définition ne sont pas des concepts faciles à comprendre. Un problème facilement solvable avec de petits nombres, comme trouver la factorisation de 15 en 3 et 5, devient une tâche d'une extrême difficulté lorsque la taille des nombres traités augmente. Dans le cas de ce record, c'est un nombre composé de 232 chiffres, ou 768 bits, qui a donné du fil à retordre aux chercheurs.
Alors que la majorité des méthodes de cryptographie utilisées sur Internet se servent des clés de chiffrement bien plus grandes que celles utilisées par les chercheurs, il existe encore beaucoup d'anciens systèmes en activité employant des clés de longueur similaire. Si vous vous demandez si la sécurité des messages est remise en question par l’accomplissement des chercheurs, vous serez rassurés de savoir qu'il a fallu plus d'un an et demi de calcul sur plus de 3'500 cores, l'équivalent de 300 ordinateurs, pour atteindre ce résultat. « On sait désormais que ces systèmes offrent encore une sécurité décente », dit le professeur IC, Arjen Lenstra du Laboratoire de Cryptologie Algorithmique.
Il sera toujours possible d'utiliser des clés plus longues afin de rendre la tâche de décodage plus difficile, mais nul ne sait ce que nous réservent les avancées algorithmiques et les progrès en puissance de calcul. Des méthodes alternatives de protection des messages, telles que le logarithme discret sur courbes elliptiques, sont déjà utilisées et, jusqu'à présent, aucune méthode efficace n'a été découverte pour les casser.
La publication Computation of a 768-Bit Prime Field Discrete Logarithm(Thorsten Kleinjung, Arjen K. Lenstra, Claus Diem, Christine Priplata, and Colin Stahlke) était présentée à Eurocrypt 2017, la conférence annuelle internationale sur la théorie et les applications des techniques de cryptographie à Paris en mai, et elle a obtenu la mention finaliste au prix du meilleur article. Pour plus d'information: Laboratoire de Cryptologie Algorithmique.
