The Joy of Secs: Part 3

Posted by Mark Hornsby on 08/08/2019

One of the most widely deployed asymmetric cryptographic algorithms used today (driven by the popularity of blockchain technology) is based on elliptic curves over finite fields. Like all good engineers I struggled to just accept how they work. I needed to dig deeper to better understand the mathematics and in doing so decided to share my experience ...

This is part 3 in a series. You can also read part 1 about the basics of Finite Fields and part 2 about more advanced operations and non-prime Finite Fields.

The general equation for an elliptic curve is:

y2=x3+ax+by^2 = x^3+ax+b

In addition to having this equation, the curve must also satisfy the requirement to be non-singular:

16(4a3+27b2)016(4a^3+27b^2) \ne 0

If this equation isn’t satisfied then the curve will produce a weak form of elliptic curve that is unsuitable for use in elliptic curve cryptography.

Now we know what the general form of the equation looks like we’ll review the parameters for the curves we’re going to investigate, secp256r1 and secp256k1 (remember that both of these use coefficients in a prime field):

Name Coefficient Field Equation
secp256r1 (aka NIST P-256) Z22562224+2192+2961\Bbb{Z}_{2^{256}-2^{224}+2^{192}+2^{96}-1} y2=x33x+b1y^2= x^3-3x+b_1
secp256k1 Z2256232977\Bbb{Z}_{2^{256}-2^{32}-977} y2=x3+7y^2=x^3+7
b1=0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFCb_1=\textnormal{0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC}

Now we know the equation for these two curves we have everything we need to calculate yy given xx. Here are some sample values for secp256k1:

x=0y=03+7=7x=1y=13+7=8x=2y=23+7=15\begin{aligned} x=0 & \xRightarrow{} y = \sqrt{0^3+7} = \sqrt{7} \\ x=1 & \xRightarrow{} y = \sqrt{1^3+7} = \sqrt{8} \\ x=2 & \xRightarrow{} y = \sqrt{2^3+7} = \sqrt{15} \end{aligned}

Similar principles can be applied to secp256r1, but due to the large value of b1b_1 the maths isn’t as neat. Rather than try to do the maths by hand it’s a lot easier to switch to some (Typescript) code at this point:

import { ec as EC } from 'elliptic';
import BN from 'bn.js';

const ec = EC('secp256k1');

console.log("G.y=" + ec.curve.g.y.toString('hex'));
console.log("(G.x^3+7)^0.5=" + 
  new BN(ec.curve.g.x).
    pow(new BN(3)).
    add(new BN(7)).
    toRed(BN.red('k256')).
    redSqrt().toString('hex'));

This code loads the secp256k1 curve from the elliptic library. Every curve has a point, GG, called the generator point, which is the starting point for all cryptographic operations on this curve. We’ll talk more about what this value is momentarily, but for now just notice that when you run the code above it prints the same value twice:

G.y=483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
(G.x^3+7)^0.5=483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

This proves that if you take the yy coordinate of GG, as defined in the library or calculate it yourself using the equation listed above, they both produce the same value. We could change the code above to calculate yy for any arbitrary value of xx.

We had to utilise the bn.js library to do our calculations for two reasons. Firstly, remember that we are working in a finite field here, so every operation we do to xx to calculate yy must be done using modular arithmetic; Secondly, our values can be much larger than the native number variables available in Typescript (and most other general purpose languages) and so we need a ‘big number’ library to be able to handle arbitrary precision numbers.

So back to the generator point, GG, what exactly does it represent? When we previously talked about number lines, we would always start our operations at 00. We require a similar concept for our elliptic curve, a point from which to start operations, but we shouldn't draw any further parallels, because as you’ll see shortly there is another point on an elliptic curve which is much more representative of 00.

To understand how to add points on an elliptic curve, it is helpful to disregard anything you’ve learnt about addition of numbers. You could be forgiven for thinking that to add two points together you would simply add the xx coordinates and the yy coordinates together. The problem with this is that generally the resultant point wouldn’t be on the curve (i.e. it wouldn’t satisfy the curve equation for that particular curve). So we need to find a different way to ‘add’ points. Some important features of addition (if you did some additional reading around mathematical groups earlier these will be familiar):

  1. Closure - adding any two points on our curve must produce another point on the curve (this is where our naive solution failed)
  2. Associativity - the order of adding points should not effect the result
  3. Additive identity - any point added to the additive identity point should equal itself (this is must more like our numerical concept of 00)
  4. Inverse - any point should have an inverse point - I.e. when you add a point to it’s inverse it produces the additive identity point above

One of the nice features of an elliptic curve is that if you pick any two points and draw a line through them you will generally find that that line intercepts the curve in exactly one other spot. (This feature of elliptic curves has been known about for over 1700 years and was mentioned by Diophantus in some of his mathematical works.) If we were to use this principle to represent addition i.e. the third point is considered the sum of the other two, we would certainly fix our issue where the point doesn’t lie on the curve (the third point here always lies on the curve by definition). However this definition of ‘addition’ still fails the inverse property, taking a triple of three points aa, bb and cc, we would have a+b=ca+b=c, but also a+c=ba+c=b and b+c=b+c=, implying that a=b=c=additive identitya=b=c=\textnormal{additive identity}. If instead we were to reflect the third point in the xx axis and treat this as the sum of the other two points this does actually satisfy most of our rules:

  1. Closure - our third point will always be on the curve
  2. Associativity - a+b=b+aa+b=b+a i.e. switching the definition of the existing two points still produces the same third point
  3. Inverse - because our elliptic curve is symmetric about the xx axis, ever point always has an inverse

The only thing missing is the additive identity. We solve this conundrum by inventing a new point, called the point at infinity. This point, when added to any other point, has no effect. Adding this extra point allows us to satisfy all 4 rules we defined and therefore we have a fully functioning concept of addition on our elliptic curve (which you’ll no doubt agree bares no resemblance to addition in normal arithmetic).

There are a few scenarios where drawing a line through two points doesn’t produce a third and this is where the point at infinity becomes relevant:

Eliptic curve catalog

The first diagram show what we would consider normal addition, adding points PP and QQ would result in a point directly below RR, let’s call this SS for now. If we were to then try to add RR and SS our line would be a perfectly vertical line like in diagram 3. In this scenario we define our third point to be the point at infinity. Another possible awkward situation occurs when two of our points are coincident like in diagram 2 - if you add the point QQ to itself then you have to draw a line through two points which are the same, so how do we decide where to draw the line? In this situation we define the line to be tangent to the curve at that point. As you can see in diagram 2 this results in point PP. The final scenario is the combination of having both points the same (see diagram 4) and the line being perfectly vertical and so our third point is again the point at infinity.

So returning to our definition of what an elliptic curve is, we now know all the possible points on our curve (there is one point for every possible value of xx in the finite field) and we can add the points together. If we take our generator point as our start point and add it to itself using our addition rules, we get another point on the curve. If you add GG once again you’ll get yet another point. If you keep doing this again and again (remember the order of our finite field is close to 22562^{256}) you’ll eventually visit every point on the curve before returning to the starting point GG. Given a point on the curve, it is very hard to know how many times you have to add GG to itself to get that point and this is what makes elliptic curves useful for cryptography. This challenge has a lot of parallels with the discrete logarithm problem for finite fields that we discussed in part 2 and is appropriately known as the Elliptic Curve Discrete Logarithm Problem.

To translate this in to the terms of public and private keys you will be familiar with, an elliptic curve private key is a number which tells you how many times the generator point, GG, needs to be added to itself, to produce a public key, which is just the resulting point of the additions. Therefore, if you pick a private key of 1 (a very bad idea, always pick private keys randomly!), the resultant public key is simply the point GG. If you were to pick 2 then your public key would simply be G+GG+G. So an elliptic curve public key is just a point, expressed as the xx and yy coordinates. You’ll often see elliptic curve public keys can be expressed in a compressed form. We can do this because we know the curve equation, so if you know xx you can calculate yy, but the only thing you won’t know is if it is the positive or negative solution to the square root, so that also needs to be specified.

So our final task is now to prove that this method of addition does actually work and produces results that match the elliptic curve library. We’ll try to calculate the public key when our private key is 2 as described above. This simply requires us to calculate G+GG+G. To implement this ‘addition’ we’ll need to be able to find the third point on a line that intercepts the curve. Firstly we need the equation for the line (remember that the slope is the tangent to the curve at point GG). Let G=(xG,yG)G=(x_G,y_G). We have to differentiate the curve equation to get the slope at any point:

y2=x3+7y^2=x^3+7 dydx=3x22x3+7=3x22y\frac{dy}{dx}= \frac{3x^2}{2\sqrt{x^3+7}} = \frac{3x^2}{2y}

And putting this in to the equation of a line through point GG:

y=3xG22yG(xxG)+yGy = \frac{3x_G^2}{2y_G}*(x-x_G)+y_G

To find where this intercepts the curve equation we can simply set them equal to each other:

x3+7=3xG22yG(xxG)+yG\sqrt{x^3+7}=\frac{3x_G^2}{2y_G}*(x-x_G)+y_G

To make the maths easier we can square both sides:

x3+7=(3xG22yG(xxG)+yG)2x^3+7=\Big(\frac{3x_G^2}{2y_G}*(x-x_G)+y_G\Big)^2

Now move the line equation to the left hand side:

x3+7(3xG22yG(xxG)+yG)2=0x^3+7-\Big(\frac{3x_G^2}{2y_G}*(x-x_G)+y_G\Big)^2=0

Now before we go multiplying out all the terms this is a cubic and there is a neat way to solve a cubic equation if you already know two of the roots (which we do because GG is on the curve):

(xx1)(xx2)(xx3)=x3(x1+x2+x3)x2+(x1x2+x1x3+x2x3)xx1x2x3(x-x_1)(x-x_2)(x-x_3) = x^3 - (x_1+x_2+x_3)x^2 + (x_1x_2+x_1x_3+x_2x_3)x - x_1x_2x_3

So we can simply find the x2x^2 term in the expansion of our equation and set it equal to (x1+x2+x3)(x_1+x_2+x_3) to get the answer:

(3xG22yG)2=x1+x2+x3-\Big(\frac{3x_G^2}{2y_G}\Big)^2=-x_1+x_2+x_3

And we know that two of the points are GG:

x=(3xG22yG)22xGx=\Big(\frac{3x_G^2}{2y_G}\Big)^2-2x_G

Now we have the xx coordinate of our third point (the point G+GG+G) expressed in terms of the xx and yy coordinates of GG, so we can translate this in to code:

import { ec as EC } from 'elliptic';
import BN from 'bn.js';

const ec = EC('secp256k1');

const xG = ec.curve.g.x;
const yG = ec.curve.g.y;

const x = xG.redPow(new BN(2)).
  mul(new BN(3)).
  mul(yG.redAdd(yG).redInvm()).
  pow(new BN(2)).
  sub(xG.redAdd(xG)).
  mod(ec.curve.p);

console.log(x);

If you run this code it produces the following output:

<BN: c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5>

Now how do we validate this? There are a number of online tools that can do this for us. I used Bitcore’s Playground. Set the private key to 02 and you’ll see that the public key is:

02c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5

This is the compressed form of public key, so dropping the 02 byte at the start you can clearly see that the xx coordinate matches. Hooray!

This series of blog posts has turned out to be a lot longer than I expected, but I hope it has helped you to better understand the mathematics of elliptic curve cryptography. We have learnt how finite field maths works (including the more complex polynomial form that we didn’t strictly need), applied this to the coefficients in our elliptic curve equation to prove that we can calculate the yy coordinate from any given xx coordinate and then finally shown how point addition works on an elliptic curve and calculated the xx coordinate of the public key that corresponds to the private key 22. Now that you know how these calculations were done for secp256k1 you should be able to apply the same set of principles to convince yourself that they also work on secp256r1.