Elliptic curve cryptography is a PKI cryptography based on elliptic curves over finite fields. This may seem complicated at first reading, but in reality it is not necessarily so. To make it easier to understand, this article has been prepared.

1. What is an elliptic curve?

An elliptic curve is a curve described by an equation that can be written in the following form:

y²=x³+ax+b

Depending on the values of a and b, the shape of the curve will be different; the curves in the pictures below are all elliptic curves.

2. What curves are used for PKI?

For elliptic curve cryptography, we use named curves. This means that there are associated a and b values and additional parameters (to be used for the calculations) for the curves and the calculations performed on them. These values are published: for example, for digital signatures, we use NIST-accepted curves. The curves are defined in the Standards for Efficient Cryptography.

Let’s have a known example: for the SEC256K1 curve used by Bitcoin keys, the values are a = 0; b = 7. So the formula for Bitcoin keys is:

y²=x³+7

This curve looks like this:

The a and b values of the SEC256R1 curve used for digital signatures (also known as NIST P256 curve) are much larger than this, so for ease of understanding we will now demonstrate EC cryptography with the curve used by Bitcoin.

3. What other parameters are associated with the curves?

In order to use the curves for cryptography, we need a few more parameters associated with the named curve.

These are:

• Generator point (G)
  This is a point on the curve that everyone uses when creates (or verifies) a signature.

• parameter p defining the end of the finite field (Fp)
  A finite field is a number field that contains integers between two endpoints. The Fp is a finite field of integers between 0 and p-1, mathematically described as:
  
  F_p={0,…, p-1}
  
  Since our curve is used on a finite field, the formula for this curve is also modified:
  
  y²=x³+ax+b (mod p)
  
  This is what the Bitcoin curve looks like:
  
  y²=x³+7 (mod p)

• parameter n defining the maximum key value
  This specifies the maximum value of a private key. The private key value must be between 0 and n-1 This value n is the order of G.

• the cofactor h
  This parameter is used for signature and signature verification, and its value should be small (h ≤ 4), preferably h=1.

4. Operations on the elliptic curve

To understand how elliptic curve cryptography works, you need to know the basic mathematical operations that can be performed on an elliptic curve.

Basic operations that can be performed are:

• point negation
• addition of two points
• duplication of a point (adding a point to itself)
• multiplication by a number (scalar value) can be achieved by repeating addition.

An important property of elliptic curves is that the division operation can not be interpreted.

4.1 Negation of a point

The negation of a point is nothing more than its reflection on the horizontal axis.

4.2 Addition of two points

By definition connecting two points with a line gives a third point with a negative sign.

P+Q= -R

(The definition of elliptic curve addition is different from the traditional addition.)

This looks like this:

To obtain +R, the reflection on the horizontal axis (negation) must be carried out.

The result is the point R.

4.3 Duplicating a point

This is the special case of point addition, when a point is added to itself.

In this case, the two points are actually coincident, so the tangent line must be drawn. The line is intersecting the cuve at point -2P, which needs to be mirrored to get the double of the point, 2P, on the elliptic curve.

4.4 Multiplying a point by a numeric value

Since we can add two points together, or duplicate a point (adding it to itself), we can combine this multiple times. This means that we can multiply our point by any number.

In the example below, the point P is multiplied by 3:

1. a tangent is drawn to point P and the resulting intersection -2P is mirrored to get 2P.
2. the points P and 2P are connected and the resulting intersection -3P is mirrored to obtain 3P

In this example, we made a multiplication by 3, but multiplying by a larger value obviously means that the addition and duplication operations have to be repeated.

For example, if we wanted to multiply by 6, we would use the 3P we just obtained and need to draw a tangent line to the duplication and then mirror it to get 6P.

In elliptic curve cryptography, the number used for multiplication is 256 bits long (2²⁵⁵), and that is the private key.

5. How is a key pair created? Why is it secure?

The private key (privkey) is a random integer between 0 and n-1, this is what we generate.

The public key is the generator (G) point multiplied by this generated random number on the elliptic curve.

pubkey = privkey * G

This means that we have to perform the multiplication with the point G as described in the previous section.

The fact that the division on the elliptic curve is not interpreted makes it impossible to determine the random number representing the private key from the public key, which is a point on the curve.

6. How do we sign?

The signature operation using elliptic algorithms has the flollowing steps:

1. Compute the hash (h) of the document.
2. Generate a random number k, where k must be between 0 and n-1.
3. Compute the point R associated with the number k by multiplying the point G.
   R=k*G
4. Take the value of the x-coordinate of the point R, let it be r:
   r=R.x
5. Calculate the value of the signature evidence, denoted by s.
   s=k^-1*(h+r*privKey)(mod n)
6. Our signature is the r and s value.

7. How do we validate a signature?

Az ellenőrzés általános alapelve, hogy helyreállítjuk a véletlen pontot a publikus kulcs segítségével, és ha az megegyezik  az aláíráskori ponttal, akkor az aláírás helyes. Az ellenőrzés lépései az elliptikus algoritmussal a következők:

1. Calculate the hash (h) of the document.
2. Calculate the value of s1: s1=s^-1  (mod n)
3. Determine the random point used in the signature:
   R’=(h*s1)*G+(r*s1)*pubKey
4. Take the value of the x-coordinate of point R’ let it be r’ r'=R'.x
5. If r at signature time and r’ at verification time are equal, the signature has been successfully verified.

7.1 The maths behind the signature and the verification

Although the correlation between signature and verification is not obvious at a glance, the correctness of the correlation can be checked by sorting the equations.

Let’s restructure the formula of point R' by substituting the pubKey with its formula (pubKey = privKey * G):

R'=(h*s1)*G+(r*s1)*pubKey= (h*s1)*G+(r*s1)*privKey * G= (h+r*privKey)*s1*G

If we take the value of s used in the signature, we can calculate the value of s1 as follows:

s=k^-1*(h+r*privKey)(mod n)

s1=s^-1  (mod n)= (k^-1*(h+r*privKey))^-1 (mod n)=k*(h+r*privKey)^-1 (mod n)

The value s1 is then substituted into the formula in R' above:

R'=(h+r*privKey)*s1*G= (h+r*privKey)*k* (h+r*privKey)^-1  (mod n)*G= k*G

The resulting formula is:

R'=k*G

If we compare this with the formula used for the signature, we can see that it matches:

R=k*G

This means that if the points R and R' match each other (which for convenience we just compare with the x coordinate), the signature is OK.