Samedi sécurité : quand les ordinateurs quantiques casseront-ils le RSA 2048 bits ?
Image ChatGPT, manque d'imagination Philippe
TL;DR
Comme la plupart des titres posant une question, la réponse est "non"...
Ça va être un peu plus technique après.
Mais retenez-le: non, les ordinateurs quantiques ne casseront pas le RSA, enfin pas à ce rythme et de notre vivant!
RSA en 1977, une avancée cryptographique incroyable
Commençons par le commencement, la sécurité par la paire de clé publique/privée RSA, amené en 1977 par Ron Rivast, Adi Shamir et Leonard Adleman, et qui a changé le monde! Ces trois chercheurs ont changé la face de la sécurité informatique via les chiffrements asymétriques, et pour longtemps!
Il faut noter que par extension ça a changé aussi les chiffrements symétriques, par transfert de la clé de chiffrement symétrique elle-même chiffrée par la clé publique et donc uniquement déchiffrable par la clé privée.
Mais aussi de l'authentification par la clé privée, via un hash chiffré par celle-ci, vérifiable par tous ceux ayant la clé publique. La signature électronique.
Je ne saurais trop dire à quel point leur impact est essentiel aujourd'hui, énormément de choses dérivent de leur travail, que j'avais découvert dans Science & Vie qui était à l'époque une revue de vulgarisation scientifique. (ils ont gardé le vulgaire dans différents sens, pas le scientifique)
Comment le RSA fonctionne
La sécurité RSA fonctionne comme une boîte fermée avec une clé spéciale : tout le monde peut la fermer avec une clé publique, mais seul celui qui a la clé privée peut l’ouvrir.
Cette sécurité repose sur un secret mathématique : la clé est créée à partir du produit deux grands nombres premiers.
Multiplier ces nombres est facile, mais les retrouver à partir du résultat (les factoriser) est très difficile, même pour les ordinateurs. C’est cette difficulté qui protège le message.
Aujourd'hui le minimum est 4096 bits typiquement, avec nombre d'entre nous utilisant du 8192 bits.
Pourquoi la force-brute ne sert à rien
On considère qu'un supercalculateur d'aujourd'hui peut casser une seule clé RSA 1024 bits en un an. Soit plus que l'âge de l'univers pour du vieux 2048 bits.
Ou à l'inverse un supercalculateur dans deux millénaires devrait être capable de casser un seule clé RSA 2048 bits en 1 an si la Loi de Moore n'est pas cassée entre-temps (elle le sera) et si deux fois plus de transistors amènent à deux fois plus de performances (ça n'est pas le cas).
Bref, la force-brute ne fonctionne absolument pas, et c'est un point-clé du RSA.
Pour donner un facteur d'échelle, créer une clé RSA de 1024 bits par le produit de deux grands nombres premiers (connus) pour un Commodore C64 prend quelques secondes, contre une année pour la casser pour les meilleurs supercalculateurs d'aujourd'hui, qui est l'opération inverse!
C'est cette asymétrie de puissance de calcul qui est essentielle...
La "suprématie quantique"
La "suprématie quantique" est la supériorité des ordinateurs quantiques face aux superordinateurs traditionnels, résolvant en théorie certains problèmes bien plus rapidement, et plus le problème étant complexe plus l'écart augmentant.
Un nouvelle technologie éclatant l'ancienne.
Mais ça n'a été observé jusqu'à présent que pour des problèmes qui ne concernent pas grande-monde... Et quasiment aucun intérêt réel.
En général, à chaque bond en avant, des chercheurs ont obtenus les mêmes résultats et des fois bien plus rapidement, avec des superordinateurs traditionnels!
Les fausses prétentions des ordinateurs quantiques
On nous annonce l'apocalypse chaque fois qu'on peut avec des progrès apparents de factorisation de grands nombres premiers par des ordinateurs quantiques.
Ça vend bien, tant dans les parutions de papiers de recherche que pour les médias.
Sauf que rien de tout cela est vrai, le plus grand nombre factorisé par un ordinateur quantique à ce jour semble être 35. Pas un nombre à 35 chiffres en notation décimale, pas un nombre sur 35 bits (des microsecondes sur un Mac), mais bien "35" (trente cinq) soit 5x7, un nombre codé sur 6 bits, pas 4096 bits! Si vous avez plus de 8 ans vous savez le faire de tête!
C'est ce qu'explique un papier passionnant des chercheurs Peter Gutmann et Stephan Neuhaus, ainsi qu'un petit PDF amusant "bollocks" utilisé lors d'une présentation par Peter Gutmann. Tout est en Anglais, mais permettez-moi de résumer...
Essentiellement les seuls essais fiables et vérifiables de factorisation de nombres premiers par des ordinateurs quantiques ont été sur de très petits nombres, comme 15, 21 ou 35.
Le reste est constitué d'arnaques, de tours de magie informatiques ou mathématiques, de nombres "magiques", de nombres (résultats) préalablement connus, d'usages de "compilateurs" connaissant le résultat, des arnaques! Trop relayées!
Quand certains prétendent casser des clés RSA de 892 bits avec un ordinateur quantique, ça n'est pas de la force brute, mais de la farce brute...
On est tous des suprémacistes quantiques
L'auteur, facétieux, a choisi de reproduire les expériences de factorisation quantiques réussies, grâce à un chien qui malheureusement nous a depuis quitté, ainsi qu'un boulier et un Commodore C64 (émulé certes).
Plaçant ces trois dispositifs au même niveau que les meilleurs ordinateurs quantiques!
Je n'ai pu reproduire toute l'expérience car ayant des chats, qui bien qu'étant l'animal le plus quantique depuis Schrödinger tient plus du générateur aléatoire quantique coté miaulement, sauf quand il est activé en continu quand il a faim.
Par rapport aux chiens, il y a ce qu'on nomme dans notre jargon informatique une "inversion de contrôle" (IoC) qui peut s'associer à une injection de dépendance pour les personnes seules.
Mais je pourrais prétendre factoriser un nombre premier de 4096 bits si le produit d'un nombre premier de 4095 bits et d'un second qui serait "2" (deux) techniquement sur 2 bits. Un Commodore C64 de base ferait ça les doigts dans le nez. Et moi sur une feuille de papier avec un crayon en moins d'une heure... Je suis la suprématie quantique!
Au pire je peux utiliser une grande règle à calcul. Un outil de suprématie quantique.
Les recommandations des auteurs
Outre les critiques justifiées, les auteurs font des propositions constructives pour pouvoir valider les futures expériences de factorisation de grands nombres (en leur deux facteurs premiers) par un ordinateur quantique.
La plus importante étant la fourniture par un tiers indépendant d'une dizaine de ces nombres (produits de paires de grands nombres premiers non proches), sans évidemment fournir ceux ayant permis de les générer et même en les éliminant de leurs systèmes: aucun besoin des deux facteurs premiers si l'expérience quantique fonctionne!
En conclusion
En utilisant les seuls points de données fiables en terme de factorisation de nombres issus du produit de deux nombres premiers, la courbe pointe sur l'année 4000 plus ou moins un siècle, pour du RSA 1024 bits, au rythme observé actuellement en informatique quantique.
Donc vers l'an 10 000 pour les actuels RSA 4096 bits.
Même si on est pas à l'abri d'une découverte, probablement mathématique, on est en sécurité pour longtemps. Tout comme César était immortel, pour longtemps...
Ça rassure non?!?