4 ms·
A method to efficiently factor large numbers will also break the ECDSA.
by cyberax 1y ago
A method to efficiently factor large numbers will also break the ECDSA.
- CamperBob2 1y agoNo, ECDSA relies on the hardness of the discrete logarithm problem. Nothing to do with factoring, at least not in the classical sense. On a quantum computer, my understanding is that Shor's algorithm could potentially target both problems, though.
- cyberax 1y agoBoth systems are an example of a hidden Abelian subgroup problem. That is also why Shor's algorithm equally applies to both: https://en.m.wikipedia.org/wiki/Shor%27s_algorithm#Shor's_algorithm_for_discrete_logarithms https://en.m.wikipedia.org/wiki/Shor%27s_algorithm#Shor's_al... So a hypothetical classic algorithm that breaks the RSA is also highly likely to break the ECDSA.