1
$\begingroup$

I have heard that ECDSA will be broken in the not-to-distant future (roughly 15-25 years) by Quantum Computers running Shor's Algorithm. However, to my understanding, the only purpose of Shor's Algorithm is quickly finding the prime factors of very large numbers. Though time consuming, such factorization is by no means impossible on modern computers. The prime factors of public keys on the Secp256k1 curve can be found in a matter of hours with the proper algorithm. Is there a formula capable of deriving a private ECDSA key from a public one if the prime factors of that public key are revealed, or is there some other aspect of factorization which poses such a great security risk? I have been unable to find any information on the means through which these quantum attacks would be capable of breaking public key encryption despite the great concern over it. Any explanation, especially with mathematical examples, would be greatly appreciated.

$\endgroup$
1
$\begingroup$

However, to my understanding, the only purpose of Shor's Algorithm is quickly finding the prime factors of very large numbers.

Your understanding is incorrect. Shor's Algorithm is usable for both factoring integers and finding discrete logarithms.

Shor's algorithm works in two parts. First, it turns the problem (factoring or discrete log) into one of finding the period of a function. This first step is non-quantum. Then it finds the period using the Quantum Fourier Transform (QFT). Once you have the period of the function the first step can be reversed to find the solution to the original problem.

Shor's algorithm can be used without the Quantum part and simulating the QFT, though then it will be substantially slower than the best known classical algorithms. This python implementation simulates the QFT and may aid understanding.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the explanation and for the python implementation. That does help clarify Shor's algorithm quite a bit. So, even if a public key is successfully broken into its prime factors, it still doesn't compromise its security because getting the private key would require solving the Discrete Logarithm problem for that curve, correct? Or does some other formula also pose a security risk if the prime factors of the public key were to be exposed. This still assumes the ECDSA algorithm, as I'm aware RSA uses a different formula, hence the need for its larger key sizes. $\endgroup$ – Alexander Pellegrino Sep 16 at 20:31
  • $\begingroup$ "So, even if a public key is successfully broken into its prime factors, it still doesn't compromise its security because getting the private key would require solving the Discrete Logarithm problem for that curve, correct?" Incorrect. Shor's algorithm can directly solve the discrete log problem. Both factoring and discrete log can be turned into period finding problems, and period finding is solved easily with the QFT. If a public RSA key were broken into prime factors that gets you the private key directly. If a public ECDSA key gets its log taken that gets the private key directly. $\endgroup$ – SAI Peregrinus Sep 18 at 12:55
  • $\begingroup$ Alright, that was the last thing I was unsure of. Thank you for confirming it for me. $\endgroup$ – Alexander Pellegrino Sep 18 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.