Perhaps, this is a really obvious question, but I am still having trouble understanding how this all fits together. Why is knowing the number of points on an Elliptic Curve helpful in cracking it?

Because it can help factor $n$ (as in “mod $n$”) if it's composite? Is it because knowing the order of different points is helpful, and the order divides the number of points total?

Why is so much effort put into finding an efficient way to count points?


Actually, we don't count points to attempt to break Elliptic Curves, a major reason we count points is to ensure that we can't.

If the number of points on the curve is $n$, then we know how to solve the ECCDLP problem in $\sqrt{n}$ time. However, if we know a factorization $n = pq$, then we can use that factorization to solve the ECCDLP problem in $\sqrt{p} + \sqrt{q}$ time. Note that this is distinctly smaller; if $n$ is 256 bits, then $\sqrt{n}$ is 128 bits; we believe that no one has the computational resources to do $2^{128}$ work. On the other hand, if $p$ and $q$ is 128 bits, then $\sqrt{p} + \sqrt{q}$ is about 65 bits; we know that performing $2^{65}$ work is achievable in practice.

To avoid this potential problem, we generate curves until we find one with a prime number of points on it (or, a prime times a small cofactor); once we have that, the above observation is of no use to an attacker.

Now, that's not the only reason knowing the number of points on a curve is useful, however it is a major one.


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.