Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
A FAQ for an open source project makes the claim:
Indeed, an elliptic curve key of length n provides $n/2$ bits of security.
I have two questions:
The assumption for all cryptographic operations is that a random key of n bits has n bits of entropy. If it doesn't (due to PRNG defect or implementation error) then the key will be weaker than expected but the underlying assumption of all cryptographic primitives is that an n bit key has n bits of entropy. This is the same for all types of cryptographic systems. It is also why in cases where the key is derived from a password while it may be impossible to brute force the key it is possible to brute force the significantly weaker password.
An ECC key has a bit strength equal to half the key length. To understand why we need to take a step back and look at what makes ECC strong. By strong we mean that it is computationally difficult to derive the private key from the public key. Why is that difficult? Well the short version is that to go from public key to private key would require solving a discrete logarithm and no efficient solution is known. This is a mathematical assumption on which ECC is based.
So why is the bit strength equal to half the key length? It is because all of the fastest solutions for solving a discrete logarithm problem are on the order of $O(2^{n/2})$. So for a 256 bit key we are talking about $2^{128}$ operations which is the same as an exhaustive search on a 128 bit symmetric key thus it is 128 bit strength.
The ratio between key length and bit strength will vary by algorithm. For unbroken symmetric algorithms there is no solution short of an exhaustive search of possible keys to find the proper key thus a 128 bit AES key has 128 bit strength. However for asymmetric encryption there are faster solutions and as a result it takes a larger key to achieve a similar level of security but that ratio will depend on the algorithm used and the fastest known solution.
$$\begin{array} {r r r} AES\ 128\ bit\ key & = 2^{128}\ operations & = 128\ bit\ security \\ ECC\ 256\ bit\ key & = 2^{128}\ operations & = 128\ bit\ security \\ RSA\ 2,048\ bit\ key & = 2^{128}\ operations & = 128\ bit\ security \\ \end{array}$$
$$\begin{array} {r r r} AES\ 256\ bit\ key & = 2^{256}\ operations & = 256\ bit\ security \\ ECC\ 512\ bit\ key & = 2^{256}\ operations & = 256\ bit\ security \\ RSA\ 15,360\ bit\ key & = 2^{256}\ operations & = 256\ bit\ security \\ \end{array}$$
Now if tomorrow someone found a faster solution to solve the discrete logarithm problem, let say $O(2^{n/4})$ then a 512 bit ECC key would no longer be 256 bit security it would be 128 bit security. I think that is unlikely but I use it as an example to illustrate why keys of different algorithms have different lengths for the same level of security.
