4
$\begingroup$

I've looked around and couldn't find a direct answer. As a general rule, I've read from various sources (here here, and here) that the strength of an elliptical curve key is half of the size of the prime field. I.e. for a 256-bit prime field (like a secp256r1 curve) the we have 128 bits of security and for a 384-bit prime field the symmetrical equivalent strength is 192 bits.

Why is this the case? As I understand it, an $n$-bit symmetric key has $2^n$ bits of security, and an ECC public key is some point $P$ such that $P=k \cdot G (\text{ mod }p)$ where $k$ is the private key and $p$ is the modulus prime field.

secp256r1 has a 256 bit prime field who's prime is a Mersenne prime. So what's going on? Do we use only half the field or...?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ There is no '(mod p)' in the ECC computation; the scalar multiplication operation $k \cdot G$ already takes both x and y coordinates of the point(s) separately mod p. Note in general ECC strength is half the size of the order of the curve subgroup not the underlying field, but the X9/NIST prime curves in particular are chosen so the subgroup order equals the curve order, and by Hasse's theorem the curve order, although not equal to p, is the same size as p. The former is not true for some other curves, notably Curve25519 and Curve448. $\endgroup$
    – dave_thompson_085
    Commented May 3, 2019 at 1:41

1 Answer 1

Reset to default
5
$\begingroup$

This is essentially because the best known generic algorithms for discrete logarithm, e.g., baby step giant step, have complexity $$O(\sqrt{G})=O(2^{n/2})$$ where $n$ is the number of bits to represent the elements of the elliptic curve group $G$.

If the elliptic curve group is carefully chosen, that is. So, avoid anomalous curves, for example.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you. Are the NIST-curves (secp256r1, or P-521 curve) safe? $\endgroup$
    – THG
    Commented May 2, 2019 at 23:49
  • $\begingroup$ I believe so, but I am not an expert up to those specifics. Maybe search or ask a specific question regarding those curves. $\endgroup$
    – kodlu
    Commented May 2, 2019 at 23:51
  • 1
    $\begingroup$ @TLane: see crypto.stackexchange.com/questions/10263/… and more linked there, but to come to a fully informed evaluation will probably take you months. Alternatively, stay with the herd. $\endgroup$
    – dave_thompson_085
    Commented May 3, 2019 at 2:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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