The Joy of Secs: Part 3
Posted by Mark Hornsby on 2019-08-08
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 …
The general equation for an elliptic curve is:
In addition to having this equation, the curve must also satisfy the requirement to be non-singular:
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):
|secp256r1 (aka NIST P-256)|
Now we know the equation for these two curves we have everything we need to calculate given . Here are some sample values for secp256k1:
Similar principles can be applied to secp256r1, but due to the large value of 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:
This code loads the secp256k1 curve from the elliptic library. Every curve has a point, , 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:
This proves that if you take the coordinate of , 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 for any arbitrary value of .
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 to calculate 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, , what exactly does it represent? When we previously talked about number lines, we would always start our operations at . 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 .
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 coordinates and the 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):
- Closure - adding any two points on our curve must produce another point on the curve (this is where our naive solution failed)
- Associativity - the order of adding points should not effect the result
- Additive identity - any point added to the additive identity point should equal itself (this is must more like our numerical concept of )
- 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 , and , we would have , but also and , implying that . If instead we were to reflect the third point in the axis and treat this as the sum of the other two points this does actually satisfy most of our rules:
- Closure - our third point will always be on the curve
- Associativity - i.e. switching the definition of the existing two points still produces the same third point
- Inverse - because our elliptic curve is symmetric about the 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:
The first diagram show what we would consider normal addition, adding points and would result in a point directly below , let’s call this for now. If we were to then try to add and 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 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 . 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 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 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 ) you’ll eventually visit every point on the curve before returning to the starting point . Given a point on the curve, it is very hard to know how many times you have to add 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, , 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 . If you were to pick 2 then your public key would simply be . So an elliptic curve public key is just a point, expressed as the and 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 you can calculate , 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 . 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 ). Let . We have to differentiate the curve equation to get the slope at any point:
And putting this in to the equation of a line through point :
To find where this intercepts the curve equation we can simply set them equal to each other:
To make the maths easier we can square both sides:
Now move the line equation to the left hand side:
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 is on the curve):
So we can simply find the term in the expansion of our equation and set it equal to to get the answer:
And we know that two of the points are :
Now we have the coordinate of our third point (the point ) expressed in terms of the and coordinates of , so we can translate this in to code:
If you run this code it produces the following output:
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:
This is the compressed form of public key, so dropping the 02 byte at the start you can clearly see that the 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 coordinate from any given coordinate and then finally shown how point addition works on an elliptic curve and calculated the coordinate of the public key that corresponds to the private key . 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.