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.

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

1 Answer 1

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 at 9:04
    
@BlackAdder surely, thanks! :) –  DrLecter May 26 at 9:55

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.