[[chapter_elliptic_curve cryptography]] == Elliptic Curve Cryptography
The previous two chapters covered some fundamental math. We learned how Finite Fields work and we also learned what an Elliptic Curve is. In this chapter, we’re going to combine the two concepts to get Elliptic Curve Cryptography. Specifically, we’re going to build the primitives needed to sign and verify messages, which is at the heart of what Bitcoin does.
We discussed in the last chapter what an Elliptic curve looks like visually because we were plotting the curve over real numbers. Specifically, it’s not just integers or even rational numbers, but all real numbers. Pi, sqrt(2), e+7th root of 19, etc are all part of real numbers.
What’s interesting is that real numbers are also a field. Note unlike a finite field, there are an infinite number of real numbers, but otherwise the same properties hold:
-
if a and b are in the set, a+b and a⋅b is in the set. We call this property closed
-
The additive identity, 0 exists. This means a + 0 = a
-
The multiplicative identity, 1 exists. This means a ⋅ 1 = a
-
If a is in the set, -a is in the set. -a is defined as the value that makes a + (-a) = 0. This is what we call the additive inverse.
-
If a is in the set and is not 0, a-1 is in the set. a-1 is defined as the value that makes a ⋅ a-1 = 1. This is what we call the multiplicative inverse.
Clearly, all of these are true as normal addition and multiplication apply for the first part, additive and multiplicative identities 0 and 1 exist, -x is the additive inverse and 1/x is the multiplicative inverse. Normal math applies to everything here.
The nice thing about real numbers is that we can easily plot what’s going on and see the whole thing visually as we did in the last chapter. For example, y2=x3+7 can be plotted like this:
What’s interesting is that we can use this equation over any field, including the Finite Fields we explored in Chapter 1. The only difference is that we have to use the addition/subtraction/multiplication/division as we defined them, not the "normal" versions that the real numbers use.
For example, we can see what to do for the equation y2=x3+7 over F103. Let’s see if the point (17,64) is on the curve:
642%103=79 (173+7)%103=79
Indeed, that point is on the curve using the Finite Field math.
Because we’re evaluating the equation over a Finite Field, the plot of the equation looks vastly different:
As you can see, it’s very much a scattershot of points and there’s no smooth curve here. This is not surprising since the points are discrete. About the only pattern is that the curve is symmetric right around the middle, which is due to the fact that the graph is symmetric, not over the x-axis as in the curve over reals, but about half-way up the y-axis.
What’s important here to realize is that we can evaluate the same equation using the addition, subtraction, multiplication, division and exponentiation as we defined them for Finite Fields and everything still works. This may seem surprising, but abstract math has regularities like this despite being different than the traditional modes of calculation you may be familiar with.
Because we defined an Ellptic curve point and utilize the +,-,* and / operators for Finite Fields, we can actually just combine the two classes to evaluate Elliptic Curve Points over a Finite Field.
>>> from ecc import FieldElement, Point
>>> a = FieldElement(num=0, prime=223)
>>> b = FieldElement(num=7, prime=223)
>>> x = FieldElement(num=192, prime=223)
>>> y = FieldElement(num=105, prime=223)
>>> p1 = Point(x, y, a, b)
Point(192, 105)_223When initializing Point, we will run through this part of the code:
class Point:
def __init__(self, x, y, a, b):
self.a = a
self.b = b
self.x = x
self.y = y
if self.x is None and self.y is None:
return
if self.y**2 != self.x**3 + self.a*self.x + self.b:
raise ValueError('Point ({},{}) is not on the curve where a,b={},{}'.format(x,y,a,b))The addition (+), multiplication (), exponentiation (*) and equality (!=) here will end up utilizing the __add__, __mul__, __pow__ and __ne__ methods from FiniteField respectively and not the integer equivalents. As we will see, being able to do the same equation but with different definitions for the basic arithemtic operators is what will allow us to construct an Elliptic Curve Cryptography library.
We’ve already coded the two classes that we need to implement Elliptic Curve points over a Finite Field. However, to check our work, it will be useful to create a test suite. We will do this using the results of the previous exercise.
from unittest import TestCase
class ECCTest(TestCase):
def test_on_curve(self):
prime = 223
a = FieldElement(0, prime)
b = FieldElement(7, prime)
valid_points = ((192,105), (17,56), (1,193))
invalid_points = ((200,119), (42,99))
# iterate over valid points
for x_raw, y_raw in valid_points:
x = FieldElement(x_raw, prime)
y = FieldElement(y_raw, prime)
# Creating the point should not result in an error
Point(x, y, a, b) # (1)
# iterate over invalid points
for x_raw, y_raw in invalid_points:
x = FieldElement(x_raw, prime)
y = FieldElement(y_raw, prime)
# check that creating the point results in a ValueError
with self.assertRaises(ValueError):
Point(x, y, a, b) # (1)-
We pass in
FieldElementobjects into thePointclass for initialization. This will, in turn, utilize all the overloaded methods inFieldElement
We can now run this test like so:
>>> import ecc
>>> from helper import run_test # (1)
>>> run_test(ecc.ECCTest('test_on_curve'))
.
----------------------------------------------------------------------
Ran 1 test in 0.001s
OK-
helper is a module with some very useful utility functions, including the ability to run unit tests individually.
We can use all the same equations over finite fields, including the linear equation:
y=mx+b
It turns out that a "line" in a finite field is not quite what you’d expect, either:
Still, the equation works and we can calculate what y should be for a given x.
Remarkably, point addition works over finite fields as well. This is because the elliptic curve and line equations still work! The same exact formulas we used to calculate Point Addition over Reals work just as well over Finite Fields. Specifically:
when x1≠x2
P1=(x1,y1), P2=(x2,y2), P3=(x3,y3)
P1+P2=P3
s=(y2-y1)/(x2-x1)
x3=s2-x1-x2
y3=s(x1-x3)-y1
when P1=P2
P1=(x1,y1), P3=(x3,y3)
P1+P1=P3
s=(3x12+a)/(2y1)
x3=s2-2x1
y3=s(x1-x3)-y1
All of the equations for Elliptic Curves work over Finite Fields and that sets us up to create some Cryptographic primitives.
Because we coded FieldElement in such a way as to define __add__, __sub__, __mul__, __truediv__, __pow__, __eq__ and __ne__, we can simply initialize Point with FieldElement objects and point addition will work:
>>> from ecc import FieldElement, Point
>>> a = FieldElement(num=0, prime=223)
>>> b = FieldElement(num=7, prime=223)
>>> x1 = FieldElement(num=192, prime=223)
>>> y1 = FieldElement(num=105, prime=223)
>>> x1 = FieldElement(num=17, prime=223)
>>> y1 = FieldElement(num=56, prime=223)
>>> p1 = Point(x1, y1, a, b)
>>> p2 = Point(x2, y2, a, b)
>>> print(p1+p2)
Point(170,142)_223Because we can add a point to itself, we can introduce some new notation:
(170,142) + (170,142) = 2⋅(170,142)
Similarly, because we have associativity, we can actually add the point again:
2⋅(170,142) + (170,142) = 3⋅(170, 142)
We can actually do this as many times as we want. This is what we call Scalar Multiplication. That is, we have a scalar number in front of the point. We can do this because we have defined point addition.
What’s interesting about scalar multiplication is that it’s really hard to predict without actually calculating:
TODO: graph of where the point ends up when scalar is 2, 10, 17, etc
This is because point addition is non-linear. That is, not easy to calculate. In fact, doing the scalar multiplication is more or less straightforward, but doing the opposite, scalar division, is not.
This is called the Discrete Log problem and is the basis of Elliptic Curve Cryptography.
The interesting thing about Scalar Multiplication is that at a certain number, we get to the point at infinity (remember, point at infinity is the additive identity or 0). If we imagine a point G and scalar multiply until we get the point at infinity, we end up with a set like this:
{ G, 2G, 3G, 4G, … nG }
It turns out that this set is called a Group and because n is finite, we have a Finite Group. Groups are interesting mathematically because they behave a lot like addition:
G+4G=5G or aG+bG=(a+b)G
When we combine the fact that scalar multiplication is easy to go in one direction but hard in the other and the mathematical properties of a Group, we have exactly what we need for Elliptic Curve Cryptography.
You may be wondering why the problem of scalar multiplication is referred to as the discrete log problem.
We called the operation between the points "addition", but we could easily have called it a point "operation". Typically, a new operation that you define in math utilizes the dot operator (⋅). The dot operator is also used for multiplication, and it sometimes helps to think that way:
P1⋅P2=P3
When you do lots of multiplying, that’s the same as exponentiation. Scalar multiplication when we called it "point addition" becomes scalar exponentiation:
P7=Q
The discrete log problem is really the ability to reverse this:
logPQ=7
The log equation on the left is not analytically calculatable. That is, there is no known formula that you can plug in to get the answer generally. This is all a bit confusing, but it’s fair to say that we could call the problem the "Discrete Point Division" problem instead of Discrete Log.
The key insight to set up Public Key Cryptography is the fact that scalar multiplication on Elliptic Curves is very hard to reverse. Note the previous exercise. Most likely, you calculated the point s⋅(47,71) in F223 for s from 1 until 21. Here are the results:
>>> from ecc import FieldElement, Point
>>> prime = 223
>>> a = FieldElement(0, prime)
>>> b = FieldElement(7, prime)
>>> x = FieldElement(47, prime)
>>> y = FieldElement(71, prime)
>>> p = Point(x, y, a, b)
>>> for s in range(1,21):
>>> result = s*p
>>> print('{}*(47,71)=({},{})'.format(s,result.x.num,result.y.num))
1*(47,71)=(47,71)
2*(47,71)=(36,111)
3*(47,71)=(15,137)
4*(47,71)=(194,51)
5*(47,71)=(126,96)
6*(47,71)=(139,137)
7*(47,71)=(92,47)
8*(47,71)=(116,55)
9*(47,71)=(69,86)
10*(47,71)=(154,150)
11*(47,71)=(154,73)
12*(47,71)=(69,137)
13*(47,71)=(116,168)
14*(47,71)=(92,176)
15*(47,71)=(139,86)
16*(47,71)=(126,127)
17*(47,71)=(194,172)
18*(47,71)=(15,86)
19*(47,71)=(36,112)
20*(47,71)=(47,152)If we look closely at the numbers, there’s no real discernible pattern to the scalar multiplication. The x-coordinates don’t always increase or decrease and neither do the y-coordinates. About the only pattern in this set is that between 10 and 11, the x coordinates seem to be aligned (10 and 11 have the same x, as do 9 and 12, 8 and 13 and so on).
Scalar Multiplication looks really random and that’s what we’re going to use for what we call an assymetric problem. An assymetric problem is one that’s easy to calculate in one direction, but hard to reverse. For example, it’s easy enough to calculate 12⋅(47,71). But if we were presented this:
s⋅(47,71)=(194,172)
Would you be able to solve for s? We can look up the table above, but that’s because we have a small field. We’ll see later that when we have numbers that are a lot larger, this becomes problematic.
Unlike fields, groups have only a single operation. In our case, Point Addition is our operation. We also have a few other properties like closure, invertibility, commutativity and associativity. Lastly, we need the identity.
It turns out that we have all of these things with Point Addition. Let’s look at each property
If you haven’t guessed by now, the identity is defined as the point at infinity. This is the point, when added to any other point produces the other point. So:
0 + P = P
We call 0 the point at infinity because visually, it’s the point that exists to help the math work out:
This is perhaps the easiest to prove since we generated the group in the first place by adding G over and over. Thus, two different elements look like this:
aG + bG
We know that the result is going to be:
(a+b)G
How do we know if this element is in the group? If a+b < n, then we know it’s in the group by definition. If a+b >= n, then we know a < n and b < n, so a+b<2n so a+b-n<n.
(a+b-n)G=aG+bG-nG=aG+bG-O=aG+bG
So we know that this element is in the group, proving closure.
Visually, invertibility is easy to see:
Mathematically, we know that if aG is in the group, (n-a)G is also in the group. You can add them together to get 0.
Again, this is very easy to see visually:
Clearly, P+Q=Q+P because they end up drawing the same line.
The equations for figuring out the third point also make this clear:
P1=(x1,y1), P2=(x2,y2), P3=(x3,y3)
x3=s2-x1-x2
y3=s(x1-x3)-y1=s(x2-x3)-y2
You can swap P1 and P2 to get the exact same equation.
This is the hardest to prove but can be seen visually from the last chapter:
Mathematically, this is a bit more involved, but the math can be proven given the definition that we have.
TODO: write out the proof for associativity.
What we’re trying to do with the last exercise is something like this:
>>> from ecc import FieldElement, Point
>>> prime = 223
>>> a = FieldElement(0, prime)
>>> b = FieldElement(7, prime)
>>> x = FieldElement(15, prime)
>>> y = FieldElement(86, prime)
>>> p = Point(x, y, a, b)
>>> 7*p
Point(infinity)We want to be able to scalar multiply the point with some number. Thankfully, there’s a method in Python called __rmul__ that can be used to override the front multiplication. A naive implementation looks something like this:
class Point:
...
def __rmul__(self, coefficient):
product = self.__class__(None, None, self.a, self.b) # (1)
for _ in range(coefficient): # (2)
product += self
return product-
We start the
productat "zero", which in case of Point Addition is the point at infinity. -
We loop
coefficienttimes and add the point each time
This is fine for small coefficients, but what if we have a very large coefficient? That is, a number that’s so large that we won’t be able to get out of this loop in a reasonable amount of time? If coefficient is 1 trillion, this is going to take a really long time, for example.
It turns out there’s a really fun technique called binary expansion. If bits is the number of bits required to represent the number coefficient, we only have to loop bits times. Note that 1 trillion is still only 40 bits, so we only have to loop 40 times for a number that’s generally considered very large.
import math
class Point:
...
def __rmul__(self, coefficient):
bits = math.ceil(math.log(coefficient, 2))
current = self # (2)
result = Point(None, None, self.a, self.b) # (3)
for _ in range(self.bits): # (4)
if coefficient & 1: # (5)
result += current
current += current # (6)
coefficient >>= 1 # (7)
return result-
We can calculate how many bits a number takes up by doing a log and then taking the ceiling of that number.
-
currentrepresents the point that’s at the current bit. First time through the loop it represents 1*self, the second time, it will be 2*self, third time, 4*self, then 8*self and so on. We double the point each time. In binary the coefficients are 1, 10, 100, 1000, 10000, etc. -
We start the result at "zero", or in Point Addition, the point at infinity.
-
We need to double the point until we’re past how big the coefficient can be.
-
This is a bitwise and, which tells us if the last binary digit is a 1. If so, we add the point corresponding to that bit (1*self, 2*self, 4*self, etc)
-
This is how we double the point.
-
We need to bit shift the coefficient to the right.
This is an advanced technique and if you don’t understand bitwise operators, think of representing the coefficient in binary and only adding the point where there are 1’s.
With __add__ and __rmul__, we can now start defining some more complicated Elliptic Curves.
While we’ve been using relatively small primes for the sake of examples, we are not restricted to such small numbers. Small primes mean that we can use a computer to search through the entire Group. That is try every single point in the group. That is, if the group has a size of 301, the computer can easily do 301 computations to figure out what the scalar multiple was.
But what if we made the prime larger? It turns out that we can choose much larger primes than we’ve been using. Indeed the security of Elliptic Curve Cryptography depends on computers not being able to go through the entire space of the group.
Any Elliptic Curve has to be defined with the following parameters:
-
We have to define a, b of the curve y2=x3+ax+b.
-
We also define the prime of the finte field, p.
-
We define the x and y coordinates of the generator point G
-
We also have the order of the group generated by G, n.
These numbers are known publicly and together form the curve. There are many curves and they have different security/convenience tradeoffs, but the one we’re most interested in is the one defined for Bitcoin. Specifically, the curve secp256k1. The parameters for secp256k1 are thus:
-
a = 0, b = 7, making the equation y2=x3+7
-
p = 2256-232-977
-
G = (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
-
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
The numbers starting with '0x' indicate this is a hexadecimal number.
There are a few things to notice about this curve. First, the equation is relatively simple. Many curves have a and b that are 256 bits long. secp256k1 has a really simple equation.
Second, p is really, really close to 2256. This means that most numbers under 2256 are in the prime field. n is also very close to 2256. This means most points on the curve are in the group. The curve was chosen, in part, because n is so close to P.
Third, 2256 is a really big number (See the sidebar to see just how huge). Amazingly, any number below 2256 can be stored in 32 bytes. This means that we can still store the private key relatively easily.
Lastly, the curve itself is one that was published by Centcom, and is not a NIST curve. NIST stands for xxx and is published by the NSA and Satoshi apparently didn’t trust any curves chosen by the NSA.
2256 doesn’t seem that big because we can express it succinctly, but in reality, it is an enormous number. To give you an idea, here are some relative scales:
2256 ~ 1077
Number of atoms in and on earth ~ 1050 Number of atoms in the solar system ~ 1057 Number of atoms in the Milky Way ~ 1068 Number of atoms in the universe ~ 1080
A trillion (109) computers doing a trillion computations every trillionth (10-9) of a second for a trillion years is still only 1056 computations. It’s simply infeasible to brute force a private key.
Think of finding a private key this way. It is a billion times easier to find a particular atom in the Milky Way than to find a private key in Bitcoin.
Since we know all of the parmeters for secp256k1, we can verify in Python whether the generator point, G, is on the curve y2=x3+7:
>>> gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
>>> gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
>>> p = 2**256 - 2**32 - 977
>>> gy**2 % p == (gx**3 + 7) % p
TrueFurthermore, we can verify in Python whether the generator point, G, has the order N.
>>> from ecc import FieldElement, Point
>>> gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
>>> gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
>>> p = 2**256 - 2**32 - 977
>>> n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
>>> x = FieldElement(gx, p)
>>> y = FieldElement(gy, p)
>>> seven = FieldElement(7, p)
>>> zero = FieldElement(0, p)
>>> G = Point(x, y, zero, seven)
>>> n*G
Point(infinity)Since we know the curve we will work in, this might be a good time to create a subclass in Python to work exclusively with the parameters for secp256k1. We’ll define the equivalent FieldElement and Point objects, but specific to the secp256k1 curve. Let’s start by defining the field we’ll be working in.
P = 2**256 - 2**32 - 977
class S256Field(FieldElement):
def __init__(self, num, prime=None):
super().__init__(num=num, prime=P)
def __repr__(self):
return '{:x}'.format(self.num).zfill(64)We’re really only just subclassing the FieldElement so we don’t have to pass in P all the time. We also want to have a nice way to display a 256-bit number and we do this by using the hexadecimal representation and make sure it fills 64 characters so we can see any leading zeroes.
Similarly, we can define a point on the secp256k1 curve and call it S256Point.
A = 0
B = 7
class S256Point(Point):
zero = S256Field(0) # (1)
def __init__(self, x, y, a=None, b=None):
a, b = S256Field(A), S256Field(B)
if type(x) == int:
super().__init__(x=S256Field(x), y=S256Field(y), a=a, b=b)
else:
super().__init__(x=x, y=y, a=a, b=b) # (2)
def __repr__(self):
if self.x is None:
return 'Point(infinity)'
else:
return 'Point({},{})'.format(self.x, self.y)-
zeroneeds to be defined as aS256Fieldobject so that the equality in the __add__ method still works. -
In case we initialize with the point at infinity, we need to let x and y through directly instead of using the
S256Fieldclass.
This should give us an easier way to initialize a point on the secp256k1 curve, without having to define the a and b every time like we have to with the Point class.
We can also define __rmul__ a bit more efficiently since we know the order of the group, N.
class S256Point(Point):
bits = 256 # (1)
...
def __rmul__(self, coefficient):
coef = coefficient % N # (1)
current = self
result = S256Point(None, None)
for i in range(self.bits):
if coef & 1:
result += current
current += current
coef >>= 1
return result-
We know N has 256 bits so any coefficient will be below N after being modded by N.
-
We can mod by N because
N*G==Point(infinity). That is, every N times we add G to itself or any member of this group, we effectively go back to zero (Point at infinity).
We can also define G directly and keep it around since we’ll be using it a lot going forward. We’ll also define N since that’s very useful.
G = S256Point(
0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8,
)
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141Now checking that the order of G is N is trivial:
>>> from ecc import G, N
>>> N*G
Point(infinity)To set up the motivation for why public key cryptography exists, imagine this scenario. You want to prove that you know a secret, say, a medicine for regrowing hair, that you want to sell. The buyer (a giant pharmaceutical company) is rightfully skeptical and demands some proof that the medicine works. How would you do this?
If you reveal your formula to the buyer, the buyer might just take the formula and not pay you. What can you do?
Essentially, you want to reveal possession of the secret without revealing the secret itself. How can that be achieved? In our example, the pharmaceutical company can choose several bald people and give you some time with them to apply the medicine. They know it’s very difficult to regrow hair on bald people’s heads, so being able to do so would prove you have the formula. Once the hair regrows, voila, you’ve proven you’ve got the formula and you can start negotiations to sell the formula.
This is the same problem we’re trying to solve in public key cryptography, except the secret isn’t some hair regrowth medicine, but a 256-bit number. We want to prove possession of the secret without revealing the secret itself. In order to do this, you have to have a difficult problem that only the possessor of the secret would be able to solve. In the above example, the difficult problem was regrowing hair on bald people. The difficult problem, in our case, is this:
uG+vP where u,v≠0
We already know G as the generator point. P=eG where e is the secret. The question becomes, can you manipulate this sum? That is, can you make the result some point R=kG that is chosen beforehand?
If you know the secret e, you can do this:
R = uG + vP
R = uG + veG
kG = (u+ve)G
You can choose u and v in a way as to get
d = u+ve
If you don’t know e, you are now forced to solve this equation:
kG = uG + vP (k-u)G = vP
Remember, at this point that Discrete Scalar division is impossible (you can’t divide both sides by v as that’s the same as the Discrete Log Problem). To solve this equation, you either have to choose u in a way as to get the (k-u)G result to be vP or choose v in a way as to get vP to be (k-u)G. In other words, you have to be able to solve one of two discrete log problems!
At this point, you might be wondering what point we choose, or what k we utilize in the equation kG = R. We’ll be revealing what u and v are to the person we’re proving, so it’s important not to reveal k. Otherwise:
(k-u)G = veG (k-u) = ve (k-u)*1/v = e
TODO: sidebar - calculating 1/v
Means that we’ll be revealing our secret, which would defeat the whole purpose of the signature. We can, however, reveal R. In addition, we can also choose u and v in such a way as to show that R is not some random point, but one that proves we know e.
But how do we show that R is not some random point? After all, if we choose u=1 and v=1 and reveal R, that doesn’t actually prove anything. R = G + P is a perfectly fine point in the group. We have to choose u and v in a way as to show knowledge of R beforehand.
We can do this by incorporating R into the calculation of u and v. We just need some part of R to be used and given that it’s a point, we know R has x and y coordinates. We’ll utilize the x coordinate of R since that neatly fits into 256 bits and can also be used as a scalar for G.
Since we intend to use the x coordinate as a scalar for G we will, for the sake of clarity, call the x coordinate of R, r. If r can be utilized to calculate u and v, and the resulting point R has r as the x coordinate, we would successfully prove that we know e without revealing it. This is exactly the strategy around how we do signature and verification.
If it helps, this is the ability for us to start with some number r and come back to the same number r in the final result. We are circling back to the same number that we started with and we can’t do that unless we know the secret e.
It seems somewhat counter-intuitive, but we’ll go over how to verify a signature first. Generally, signatures sign some fixed-length value, in our case something that’s 32 bytes. The fact that 32 bytes is 256 bits is not a coincidence as the thing we’re signing needs to be a scalar for G.
In order to guarantee that thing we’re signing is 32 bytes, we hash the document first. In Bitcoin, the hashing function is double-sha256. this guarantees the thing that we’re signing is exactly 32 bytes. We will call the result of the hash, z.
TODO: sidebar - why double-sha256?
The actual signature that we are verifying has two components, (r, s). The r is as above, it’s the x-coordinate of some point R that we’ll come back to. s is going to be defined as this:
s = (z+re)/k
Keep in mind that we know e (eG = P, or what we’re proving we know in the first place), we know k (kG = R, remember?) and we know z.
We will now construct R=uG+vP by defining u and v this way:
u = z/s v = r/s
Thus:
uG + vP = (z/s)G + (r/s)P = (z/s)G + (re/s)G = ((z+re)/s)G
We know s = (z+re)/k so:
uG + vP = z+re)/((z+re)/kG = kG = R
We’ve successfully chosen u and v in a way as to generate R as we intended. Furthermore, we used r in the calculation of v proving we knew what R should be. The only way we could know the details of R beforehand is if we know e, proving we know e.
To whit, here are the steps:
-
We are given (r, s) as the signature, z as the hash of the thing being signed and P, the public key (or public point) of the signer.
-
We calculate u = z/s, v = r/s
-
We calculate uG + vP = R
-
If R’s x coordinate equals r, the signature is valid.
We already have a class S256Point which is the publc point for the private key. For a variety of reasons, we’re going to create a Signature class that houses the r and s values:
class Signature:
def __init__(self, r, s):
self.r = r
self.s = sWe will be doing more with this class later.
We can create an actual verify method on S256Point based on the above.
class S256Point(Point):
...
def verify(self, z, sig):
# 1/s = pow(s, N-2, N)
s_inv = pow(sig.s, N-2, N)
# u = z / s
u = z * s_inv % N
# v = r / s
v = sig.r * s_inv % N
# u*G + v*P should have as the x coordinate, r
total = u*G + v*self
return total.x.num == sig.rSo given a public key (or point on the elliptic curve), we can verify whether a signature is valid or not.
Given that we know how verification should work, signing is more or less straightforward. The only missing step is figuring out what k, and thus R=kG to use.
It turns out that we can choose k at random and everything still works. We do this by choosing a random k.
Signing Procedure:
-
We are given z. We know e and eG=P.
-
Choose a random k
-
Calculate R=kG and r=x-coordinate of R
-
Calculate s = (z+re)/k
-
Signature is (r,s)
Note that the pubkey P and z have to be transmitted to whoever wants to verify as well. We’ll see later that z is computed and P is sent along with the signature.
In order to program message signing, we first need to create a PrivateKey class which will house our secret/scalar/private key.
class PrivateKey:
def __init__(self, secret):
self.secret = secret
self.point = secret*GWe keep around the public key (self.point) for convenience. We can now create the sign method.
from random import randint
...
# class PrivateKey
def sign(self, z):
# get a random number
k = randint(0, N) # (1)
# r is the x coordinate of the resulting point k*G
r = (k*G).x.num
# remember 1/k = pow(k, N-2, N)
k_inv = pow(k, N-2, N)
# s = (z+r*secret) / k
s = (z + r*self.secret) * k_inv % N
if s > N/2:
s = N - s
# return an instance of Signature:
# Signature(r, s)
return Signature(r, s)-
randint chooses a random integer from [0,N).
TODO: sidebar - importance of k being really random
TODO: sidebar - deterministic k values