0
$\begingroup$

this is maybe a basic question but I'm trying to better understand elliptic curve cryptography at a fundamental level.

I understand that a finite field is required in order to define a boundary for an elliptic curve.

Then, x,y values that satisfy the curve over this field represent the ec group of the curve.

My question is simple, how are the finite fields defined? They seem so arbitrary...

Example,

The finite fields for secp256k1 and curve25519 are

2^256 - 2^32 - 977

and

2^255 - 19 respectively...

My naive question is, how are these fields defined? The seem to be arbitrary bounds on the size of the ec group for the curves defined inside them.

I'm not asking why they are prime, but more why these numbers are chosen, and how the right size group is selected?

I did consider it was something to do with all of the elements satisfying some criteria, but really the values seem too large and arbitrary for that.

$\endgroup$
  • $\begingroup$ One easy observation is that point can be represented by 256-bit integers. And thinking about the generic attack on discrete log hints the security level! $\endgroup$ – kelalaka Nov 19 '19 at 11:54
3
$\begingroup$

First, the size: the best attacks for breaking elliptic curve cryptography are algorithms that break the discrete log (given a point $P = kG$, find the integer $k$; which in ECC translates to: given the public key, find the private key). These attacks have complexity of $O(2^{n/2})$, where $n$ is the size of the field. So, in a 256-bit field (i.e. with a 256-bit $p$), the best attacks can break the algorithm with $2^{128}$ steps, which is similar to what is needed to break a single instance of a 128-bit key symmetric algorithm by brute force. This is usually called "128-bit level of security". In short: the field size must be the double of the desired security level. (I've omitted some details about cofactors, but they don't change the picture that much for commonly used curves)

Now, the particular primes chosen: the computationally expensive part of ECC is field multiplication, which is composed of integer multiplication followed by reduction modulo $p$. Depending on the structure of $p$ this reduction can be computed faster. One example are primes having the form $2^k-c$ for small $c$ (Crandall primes), which is the case of secp256k1 and curve25519. The best case is a Mersenne prime, $2^k-1$, which is used by the NIST curve P-521 ($2^{521}-1$). Other common case is when the prime is composed of powers of multiples of a word size, such as P-256 ($2^{256}-2^{224}+2^{192}+2^{96}-1$), which are all multiple of 32. The reason why these lead to a faster implementation would probably required another question on the site, though; but for example, when $p = 2^k-1$, then $2^k \equiv 1 \pmod p$. If you write the result of the integer multiplication as $H + 2^kL$, then the reduction modulo $p$ will be simply $H + L \bmod p$.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Makes perfect sense @Conrado, thank you for taking the time to help me! $\endgroup$ – Woodstock Nov 19 '19 at 12:15
  • 1
    $\begingroup$ thanks @conrado! appreciate it my friend. $\endgroup$ – Woodstock Nov 19 '19 at 15:30
  • 1
    $\begingroup$ @SqueamishOssifrage I guess he wanted to say $O(2^{n/2})$. $\endgroup$ – corpsfini Nov 19 '19 at 16:25
  • 2
    $\begingroup$ ‘So, in a 256-bit field (i.e. with a 256-bit p), the best attacks can break the algorithm with $2^{128}$ steps, which is similar to what is needed to break a 128-bit key symmetric algorithm by brute force.’—This is not accurate. If the group order is around $2^{256}$, then the cost to compute discrete logs is much higher than the cost of recovering a 128-bit symmetric cipher key as long as there are multiple targets to attack. $\endgroup$ – Squeamish Ossifrage Nov 19 '19 at 16:31
  • 2
    $\begingroup$ Repeated claims that the security of Curve25519 is comparable to the security of AES-128 are tiresome. Have a thousand target users? It's a thousand times cheaper to find one of their AES-128 keys than to find one of their Curve25519 keys. For clarity, you shouldn't give the false impression that a 256-bit curve provides security comparable to a 128-bit symmetric cipher. You don't have to talk about multi-target attacks; I'm just asking that you not claim it's as expensive to break a 128-bit symmetric cipher as it is to compute a discrete log in Curve25519. $\endgroup$ – Squeamish Ossifrage Nov 19 '19 at 19:23

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.