 Cryptography

# How Does Prime Factorization Break ECDSA?

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. ## Solution

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.