Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Why order "u" of an elliptic curve "E" defined over a finite field "GF (q)" (u = | E / GF (q) |) must be divisible by a large prime number r to be appropriate for cryptographic purposes?

share|improve this question
up vote 1 down vote accepted

You want to work in a large subgroup of prime order because you want that for the ECDLP in the subgroup you are working in the generic bounds for solving the ECDLP (only square root attacks) apply and thus the security parameter can be chosen accordingly.

If you would work in the entire group the ECDLP is attackable by algorithms such as Pohlig-Hellman, Pollards' $\rho$ method or the babystep-giantstep algorithm. Additionally one avoids curves (such as supersingular ones) that are susceptible to the MOV and SSSA attack (such that you can even use subexponential algorithms).

share|improve this answer
Don't forget to mention Silver--Pohlig--Hellman which really targets implementations with smooth order. :) – BlackAdder May 26 '14 at 9:04
@BlackAdder surely, thanks! :) – DrLecter May 26 '14 at 9:55

Your Answer


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.