Inattendu, c'est le mot : le système de chiffrement RSA peut être décrypté en quelques dizaines de minutes selon une équipe de scientifiques. Une intelligence artificielle a en effet réussi ce tour de force, mais uniquement sur des clés de 2048 bits au maximum pour le moment.

Alors que scientifiques et mathématiciens pensaient que cela prendrait encore de nombreuses décennies avant qu'une machine ne parvienne à casser dans un délai raisonnable le chiffrement RSA sur 2048 bits, c'est finalement déjà arrivé. Il s'agit d'une annonce importante puisque le RSA est largement utilisé pour chiffrer des données et des communications, notamment sur internet. À qui doit-on cette découverte ? Une intelligence artificielle.

Factoriser un nombre, si simple en apparence et finalement si compliqué

Comme nous l'avions expliqué dans cet article, le principe de base du chiffrement RSA repose sur un jeu de clés. Pour faire simple, p et q sont des nombres premiers et permettent à un utilisateur de générer des clés privées (basées sur p et q) et publiques (basées sur leur produit pxq).

Sans entrer dans les détails, sachez que ce système de chiffrement est robuste et qu'il repose sur un principe : en partant du produit pxq, retrouver les nombres premiers p et q (et donc la clé privée) prend un temps extrêmement long lorsque les nombres sont grands (on parle ici de plusieurs centaines de chiffres). L'exercice qui parait simple en apparence, ne l'est pas tant que cela car il n'existe pas de formule « magique » pour trouver la solution.

La manière la plus aisée, mais pas la plus efficace, est de tester toutes les combinaisons de nombres premiers : peut-on le diviser par 2, 3, par 5, par 7, par 11, 13, 17, 19, etc. Il faut tester toutes les possibilités pour trouver la bonne. Il existe des méthodes permettant d'aller plus vite, comme le crible algébrique, mais rien qui permette de réduire drastiquement le temps nécessaire.

Une compétition est ouverte depuis plusieurs années et l'actuel record de factorisation concerne RSA-768 (il est composé de pas moins de 232 chiffres). Il a été résolu en décembre 2009. RSA-1024 mesure 309 chiffres de long et une récompense de 100 000 euros attend celui qui le factorisera. Avec RSA-2048 on passe à respectivement 617 chiffres et 200 000 dollars.

Quoi qu'il en soit, afin de s'assurer d'un minimum de sécurité, l'ANSSI recommande d'utiliser des clés de 2048 bits minimum, voire 4096 bits. Normalement cela devrait vous laisser plusieurs années de répits.

Une intelligence artificielle à double entrée résout ce casse-tête

Avec l'attrait des récompenses et des retombées médiatiques qui en découlent, de nombreuses équipes s'attèlent à factoriser des nombres de plus en plus grands depuis plusieurs années. Pour y arriver, des mathématiciens se sont associés à des informaticiens afin d'éduquer, via l'apprentissage profond (deep learning), un réseau de neurones. Son objectif ? La fameuse factorisation.

Pour cela, la machine calcule d'un côté le produit de deux grands nombres premiers, tandis qu'elle essaye de le factoriser de l'autre. Bien évidemment, les deux instances ne communiquent pas entre elles, sinon cela n'a aucun intérêt. La machine tourne ainsi en boucle fermée, s'améliorant un peu plus chaque jour. Une manière de faire qui est exactement la même que celle utilisée par DeepMind pour AlphaGo, l'intelligence artificielle qui a battu le champion Lee Sedol.

Et sans trop que l'on s'y attende, cette intelligence artificielle s'est mise à factoriser des nombres extrêmement grands de plus en plus rapidement. De plusieurs semaines, la machine est passée à plusieurs jours, puis heures et enfin dizaines de minutes, et ce, avec des nombres toujours plus grands. Cela s'est fait progressivement, au fil de l'apprentissage. La situation semble désormais stabilisée.

Dans tous les cas, cela ne fonctionne que sur des nombres de 2048 bits au maximum expliquent les chercheurs qui cherchent encore à expliquer le phénomène. Ils n'ont pas encore détaillé la manière de fonctionner de l'IA et les algorithmes qu'elle a mis au point, mais sont en train d'étudier cela de près et devraient publier leurs conclusions d'ici quelques mois.

Pour rappel, ce n'est pas la première fois que le chiffrement des données est mis à mal. En août 2014, une équipe de l'INRIA expliquait qu'elle avait développé un algorithme qui « secoue la cryptographie » car il permet de casser des systèmes de chiffrement basés sur le logarithme discret. Un problème présenté comme « aussi dur que la factorisation (RSA) » par le laboratoire de recherche.

Que faire ? 

Quoi qu'il en soit, l'équipe à l'origine de cette découverte a décidé de l'annoncer dès maintenant afin de permettre à la communauté de rapidement mettre à jour ses systèmes de chiffrement. Ils ont par contre fait part de leur intention de ne pas dévoiler le reste des détails tout de suite, car cela aurait des conséquences bien trop fâcheuses.

On se retrouve un peu dans la même situation qu'avec des failles majeures qui se multiplient ces derniers temps : on prévient dans un premier temps, puis on donne les détails une fois qu'une majorité des personnes touchées a pu se mettre à jour. Si un chiffrement RSA sur 2048 bits n'est donc plus vraiment sécurisé, en passant à 4096 bits l'intelligence artificielle se casse les dents... « pour le moment » glisse un des chercheurs, un brin provocateur.

On peut donc changer ses clés pour les passer en 4096 bits, mais avec le risque de devoir recommencer plus tard, le jeu n'en vaut donc pas forcément la chandelle. Que faire alors ? Pour le moment par grand-chose malheureusement, si ce n'est attendre de plus amples informations de la part des spécialistes et de nouvelles recommandations de l'ANSSI par exemple.

Il semblerait que l'équipe de chercheurs soit pour le moment la seule à avoir découvert cette technique. Néanmoins, des groupes moins bien intentionnés pourraient également être arrivés au même résultat, et ne pas prévenir la communauté pour en profiter au maximum. Des yeux commencent d'ores et déjà à se pointer vers les agences de renseignement...