Ordinateur quantique & cryptographie

Performance de l'algorithme de Shor

Une clé de chiffrement RSA est un nombre de 2048 bits (617 chiffres) qui est le produit de deux grands nombres premiers.

Une recherche brutale, bête et méchante, qui consisterait à essayer tous les nombres, correspondrait à trouver une aiguille dans une botte de foin de 22048 brins, ce qui est vraiment beaucoup, inimaginable.

Pour vous donner une idée, le nombre d’atomes dans l’univers est estimé à 1080 = 2266. Il manque un sacré facteur!
Et l'âge de l’univers c'est 13 milliards d’années = 258 secondes, donc inutile d'espérer quoi que soit en cherchant vite.

Sauf qu'on est plus malin que la force brute qui essaye toutes les combinaisons. Nos mathématiciens ont trouvé des algorithmes dits classiques pour factoriser un nombre. Le meilleur résultat actuel est en eN/3 où N est le nombre de bits. Cela fait e692 soit … vraiment beaucoup. C'est cuit avec un ordinateur classique, et pour longtemps.
Nota : l'algorithme GNFS un peu mieux que eN/3, mais ça ne change pas grand-chose.

Un ordinateur quantique possède également des algorithmes particuliers. L'algorithme de recherche de Grover pourrait marcher, il propose une solution en √√N soit 2512 : c'est encore bien trop.

Shor propose une solution en N³ soit 2048³ = une dizaine de milliards ! Une broutille... quand l'ordinateur quantique marchera avec beaucoup de qubits.

En 2025, l'algorithme le plus rapide est la méthode du crible algébrique (Number Field Sieve ou GNFS en anglais). Et pour donner un ordre de grandeur, pour factoriser un nombre de 2048 bits, il faudrait :

  • Bien plus de 10³⁴ années avec une bonne machine actuelle
  • 10¹⁶ années en optimisant les choses sur du matériel dédié avec des puces ad-hoc.
  • Et on parle de jours sur un ordinateur quantique avec l'algorithme de Shor.