Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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