
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.
An elliptic curve is a curve described by an equation that can be written in the following form:
y2=x3+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.
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:
y2=x3+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.
In order to use the curves for cryptography, we need a few more parameters associated with the named curve.
These are:
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:
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:
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 (2255), and that is the private key.
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.
The signature operation using elliptic algorithms has the flollowing steps:
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:
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.
© 2023 Microsec Ltd. | Company registration number: 01-10-047218 | Tax number: 23584497-2-41