# How does the size of the prime affect Elliptic Curve Bit Security?

I am using the MIRACL Library to implement an Elliptic Curve Diffie Hellman based Key Exchange according to ECDH-Scheme-Wikipedia.

Referring to the Miracl Docs they suggest a few curves. Each curve is with respect to a prime p which is n bits in length Miracl Docs EC suggestions. How does the n bit length of the prime e.g. from the ssc-192 suggestions refer to the provided bit-security?

Elliptic curve security relies on the hardness of discrete logarithm on that curve. (Well, that's a simplification, but this will do for this answer.) When the curve contains N points, it takes an effort of roughly sqrt(N) "elementary operations" to break discrete logarithm.

A prime p of "k bits" means that p is less than 2k, but greater than 2k-1. The number of points on a curve defined over the field of integers modulo p will be close to p (that's Hasse's theorem). Thus, if the prime p has length k bits, the breaking effort will be on the order of the square root of 2k operations, i.e. about 2k/2. It is usually considered that the current, absolute barrier on that which is technologically feasible is between 280 and 2100, so a safe curve would need a prime size of at least 160 to 200 bits. The "ssc-192" curve falls in that domain, so it could be deemed "probably secure".

Cryptographers are fashion victims, and thus always want powers of 2; thus, they will usually ask for "128-bit security" which then translates to a 256-bit prime p.

See this site for a lot of pointers to information on the concept of key strength.

• The answer is only valid for curves with cofactor 1. If your generator point has a cofactor c with size l bits, then you have to subtract l from k to get the security.
– user27950
Nov 5 '15 at 17:59

The [very] simplified answer is that one of the parameters for an elliptic curve is a prime p, the addition and multiplication in your elliptic curve is done (mod p), so the larger your p, the larger the set of integers you're working with, the more guesses an attacker has to make to break your key. For example, if your prime was 3, then the only possible integers are {0,1,2}, I only need to make 3 guesses and I'm done!

This is a super over-simplification of the ECC math; ECCs are actually over polynomials, not integers, but the general concept is the same. It's hard to give a more detailed how, or why without using some abstract algebra concepts, which are off-topic here. The folks over at crypto.SE would probably give you a more in-depth answer if you're looking for it.

• I was not aware of the significance of modulo, thanks. In this case, a large prime would be super handy. May 21 '19 at 1:39