1
$\begingroup$

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?

| improve this question | | | | |
$\endgroup$
1
$\begingroup$

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).

| improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Don't forget to mention Silver--Pohlig--Hellman which really targets implementations with smooth order. :) $\endgroup$ – BlackAdder May 26 '14 at 9:04

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.