Comment la factorisation principale rompt-elle l'ECDSA?

Question

J'ai entendu dire que l'ECDSA sera brisé dans un avenir pas si lointain (environ 15 à 25 ans) par les ordinateurs quantiques exécutant l'algorithme de Shor. Cependant, à ma connaissance, le seul but de l'algorithme de Shor est de trouver rapidement les facteurs premiers de très grands nombres. Bien que prenant du temps, une telle factorisation n'est en aucun cas impossible sur les ordinateurs modernes. Les facteurs premiers des clés publiques sur la courbe Secp256k1 peuvent être trouvés en quelques heures avec l'algorithme approprié. Existe-t-il une formule capable de dériver une clé ECDSA privée d'une clé publique si les facteurs premiers de cette clé publique sont révélés, ou y a-t-il un autre aspect de la factorisation qui pose un si grand risque de sécurité? Je n'ai pu trouver aucune information sur les moyens par lesquels ces attaques quantiques seraient capables de briser le cryptage à clé publique malgré la grande inquiétude à ce sujet. Toute explication, en particulier avec des exemples mathématiques, serait grandement appréciée.

Answer 1

Cependant, à ma connaissance, le seul but de l'algorithme de Shor est de trouver rapidement les facteurs premiers de très grands nombres.

Votre compréhension est incorrecte. L'algorithme de Shor est utilisable à la fois pour factoriser des entiers et pour trouver des logarithmes discrets.

L'algorithme de Shor fonctionne en deux parties. Premièrement, il transforme le problème (factorisation ou log discret) en un problème de recherche de la période d'une fonction. Cette première étape n'est pas quantique. Ensuite, il trouve la période en utilisant la transformée quantique de Fourier (QFT). Une fois que vous avez la période de la fonction, la première étape peut être inversée pour trouver la solution au problème d'origine.

L'algorithme de Shor peut être utilisé sans la partie Quantum et en simulant le QFT, bien qu'il soit alors nettement plus lent que les algorithmes classiques les plus connus. Cette implémentation python simule le QFT et peut faciliter la compréhension.