Could classical computers end up breaking the ECDLP through prime factorization (GNFS)?

Pau T

1/10/24, 10:14 PM

Is there any way in which classical computers oculd end up breaking ECDLP. I read that GNFS could through prime factorization, but I am not sure if I understood this properly.

0 + 8

discrete-logarithm

Daniel S

1/10/24, 10:19 PM

It’s not true. For ECDSA the elliptic curve is defined modulo a large prime number.

Pau T

1/10/24, 10:21 PM

Does this mean there is no way of breaking ECDSA and ECDLP with prime factorization?

Pau T

1/10/24, 10:23 PM

Btw this: "Shor's algorithm can be used to solve the ECDLP by using a quantum computer to factorize the large composite number that defines the elliptic curve. Once the prime factors are found, the ECDLP can be easily solved using the Chinese Remainder Theorem. This allows the secret integer, or discrete logarithm, to be calculated, which would compromise the security of the cryptographic system." is not true neither then no?

Daniel S

1/10/24, 10:24 PM

Not directly, though often both problems can be attacked using related methods e.g. Pollard rho, e.g. Shor, e.g. baby-steps-giant-steps

Daniel S

1/10/24, 10:28 PM

Your quote is not a good description of how Shor’s algorithm attacks ECDLP. The author holds several misunderstandings.

Pau T

1/10/24, 10:29 PM

Is there any reliable and easy-to-comprehend document, pdf or paper, or any source that you would recommend me to understand this as a high school student? I seriously feel I'm bothering with my short knowledge in this kind of forums. Like, I want to learn, but I do not want to bother anyone for free just to do so :)

Daniel S

1/10/24, 10:54 PM

I’m afraid not; there are people with PhDs in cryptography who struggle to understand Shor’s algorithm and people with PhDs in quantum information who struggle to understand elliptic curves. OTOH I’m happy to devote some of my time to helping, particularly if you in turn are accommodating to those who can learn from you. BTW I have artificially increased your reputation so that you should now be able to use chat rooms.

Pau T

1/11/24, 5:45 PM

Totally yes!!! I do really want to learn more about cryptography and understand (or try to) what all these algorithms are about. Yes, I just answered the message you sent through the chat room.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Could classical computers end up breaking the ECDLP through prime factorization (GNFS)?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.