christianb93

A primer on elliptic curve cryptography: practice

In the last post, we have looked a bit at the theory behind elliptic curves. In this post, we will now see how all this works down to earth and use Python to actually run some calculations.

The first thing that we need is an explicit formula for the addition of two points on an elliptic curve. We will not derive this here, but simply give you the result – see for instance [1] for more details. Given two points $(x_1, y_1)$ and $(x_2, y_2)$ , the coordinates of their sum $(x_3, y_3)$ can be determined as follows.


inv = inv_mod_p(x2 - x1, p)
x3 = ((y2 - y1)*inv)**2 - x1 - x2
y3 = (y2 - y1)*inv*(x1 - x3) - y1

Here we assume that we have a function inv_mod that will give us the inverse modulo some prime number p which is the number of elements of our base field. Typically, this can be done using the so-called extended euclidian algorithm.

However, there are a few special cases we need to consider. This is apparent if we look at this formula in more detail – what happens if the inverse does not exist because the points $x_1$ and $x_2$ are equal?

This happens if we want to add two points that have the same x-coordinate. There are two cases we need to consider. First, the y-coordinates could be equal as well. Then we are trying to add a point to itself, and we need to apply the formula provided in [1] for that special case. Or the y-coordinate of the second point is minus the y-coordinate of the first point. Then we try to add a point to its own inverse. The result will be the neutral element of the group which is usually called the point at infinity (there is a reason for this: if we embedd the curve into a projective plane, this point will in fact be the intersection of its completion with the line at infinity in the projective plane…).

To describe points on an elliptic curve, we need both coordinates, the x and the y-coordinate. Thus it makes sense to implement a class for this purpose. Instances of this class need to store the x- and y-coordinates and – for convenience – a boolean that tells us whether a point is the point at infinity. So our full code for this class looks as follows.


class CurvePoint:

    def __init__(self, x, y, infinity = False):
        self.x = x
        self.y = y
        self.infinity = infinity

    def __add__(self, other):
        #
        # Capture trivial cases - one of the points is infinity
        #
        if self.infinity:
            return other
        if other.infinity:
            return self
        #
        # First check whether we are adding or doubling
        #
        x1 = self.x
        x2 = other.x
        y1 = self.y
        y2 = other.y
        infinity = False
        if (x1 - x2) % p == 0:
            #
            # Are we talking about doubling or addition
            # of the inverse?
            #
            if (y1 + y2) % p == 0:
                infinity = True
                x3 = 0
                y3 = 0
            else:
                inv = inv_mod_p(2*y1, p)
                x3 = (inv*(3*x1**2 + a))**2 - 2*x1
                y3 = (inv*(3*x1**2 + a))*(x1 - x3) - y1
        else:
            #
            # Standard case
            #
            inv = inv_mod_p(x2 - x1, p)
            x3 = ((y2 - y1)*inv)**2 - x1 - x2
            y3 = (y2 - y1)*inv*(x1 - x3) - y1

        return CurvePoint(x3 % p, y3 % p, infinity)

As already mentioned, that assumes that you have a function inv_mod_p in your namespace to compute the inverse modulo p. It also assumes that the variables p, a and b that describe the curve parameters are somewhere in your global namespace (of course you could introduce a class to represent a curve that stores all this, but let us keep it quick and dirty at this point).

Now having these routines, we can actually do a few example and verify that the outcome is as expected. We use a few examples with low values of p from [1] .

#
# Define curve parameters
#

p = 29
a = 4
b = 20
#
# and add a few points
#
A = CurvePoint(5,22)
B = CurvePoint(16, 27)
O = CurvePoint(0,0,infinity=True)
C = A + B
assert(C.x == 13)
assert(C.y == 6)
assert(C.infinity == False)
C = A + A
assert(C.x == 14)
assert(C.y == 6)
assert(C.infinity == False)
A = CurvePoint(17,19)
B = CurvePoint(17,10)
C = A + B
assert(C.infinity == True)
A = B + O
assert(A.x == B.x)
assert(A.y == B.y)
assert(A.infinity == B.infinity)
A = O + B
assert(A.x == B.x)
assert(A.y == B.y)
assert(A.infinity == B.infinity)

For the sake of demonstration, we have shown how to build elliptic curve arithmetic from scratch. We could now proceed to implement multiplication and the ECDS algorithm ourselves, but as so often, there is a Python library that will do this for us. Well, there is probably more than one, but I like the Python ECDSA library maintained by Brian Warner.

The most basic classes in this library are – you might have guessed that- curves and points. Curves are initialized providing the basic parameters p, a and b. Then points are created by specifying a curve and the x and y coordinates of the points. Thanks to operator overloading, points can then be added and multiplied with integers using standard syntax. Here is a code snippet that reproduces the first of our examples from above using the ECDSA library.


import ecdsa

#
# Create a curve with parameters p,a and b
# with the ECDSA library
#
curve = ecdsa.ellipticcurve.CurveFp(p,a,b)
#
# Define two points and add them
#
A = ecdsa.ellipticcurve.Point(curve, 5, 22)
B = ecdsa.ellipticcurve.Point(curve, 16, 27)
C = A + B
assert(C.x() == 13)
assert(C.y() == 6)
assert(C != ecdsa.ellipticcurve.INFINITY)

Very easy – and very useful. And of course reassuring to see that we get the same result than our hand-crafted code for the arithmetic above gave us.

But this is not yet all, the library can of course do much more. Let us use it to create a signature. For that purpose, we obviously need a reasonable large value for the prime p, otherwise we could easily use a brute-force attack to determine our private key from the public key. In my previous post on the theoretical foundations, I have already mentioned the papers published by the SECG, the Standards for efficient cryptography group. This group has published some standard curves that we can use. One of them is the curve SECP256K1 which is a curve over a prime field $F_p$ with

$p = 2^{256} - 2^{32} - 2^{9} - 2^{8} - 2^{7}-2^{6} - 2^{4} - 1 = 115792089237316195423570985008687907853269984665640564039457584007908834671663$

This curve is the curve which is used by the bitcoin protocol. As many other standardized curves, it is hard-coded in the ECDSA library. To get it, use the following code.


#
# Get the standard curve SECP256K1
# and its parameters
#
curve = ecdsa.curves.SECP256k1
G = curve.generator
p = curve.curve.p()
a = curve.curve.a()
b = curve.curve.b()
n = G.order()

Let us now apply what we have learned about signatures. First, we need a private key and a public key determined from it. Thus we pick a random number that will be our secret and multiply the generator of the curve by it to get our public key.

#
# Determine a private key and a public key
#
d = ecdsa.util.randrange(n-1)
Q = d*G
pKey = ecdsa.ecdsa.Public_key(G, Q)
sKey = ecdsa.ecdsa.Private_key(pKey, d)

Next we need a hash value that we will sign. Usually, we would derive this value from a message using some cryptographic hash function like SHA256, but we will simply simulate this by drawing a random number h. We can then use the method sign of the ECDSA private key object to create a signature. This will return a signature object from which we can retrieve the values r and s.

h = ecdsa.util.randrange(n-1)
k = ecdsa.util.randrange(n-1)
signature = sKey.sign(h, k)
r = signature.r
s = signature.s

Let us verify that the algorithm really works as described the previous post. So we first need to multiply our randomly chosen integer k with the generator of the curve, the number r should then be the x-coordinate of this point. We then invert k modulo n and multiply the result by h + dr. This should give us s.

_r = (k*G).x() % n
assert(_r == r)

w = inv_mod_p(k, n)
_s = ((h+d*r)*w) % n
assert(_s == s)

If you run this code, you will hopefully see that the assertions pass. Our code works, and produces the same result as the ECDSA library. That is already reassuring. Having gone so far, we can now of course also verify the signature – again we do this once using the ECDSA library and once using our own code.

#
# Now we manually verify the signature
#
w = inv_mod_p(s, n)
assert(1 == (w*s % n))
u1 = w * h % n
u2 = w * r % n
X = u1*G + u2*Q
assert(X.x() == r)

#
# Finally we verify the signature using the
# lib
#
assert(pKey.verifies(h, signature) == True)

That is it for today. We have seen how elliptic curves can be used in practice to create and verify digital signatures and have looked at the ECDSA library that offers ready made functions for that purpose. The full source code can by downloaded from GitHub.

In my next post, I will look at the way how private and public ECDSA keys appear in the bitcoin protocol. If you want to learn more and play around a bit with elliptic curves in the meantime, I recommend the online tool [2]. You might also want to take a look at Andrea Corbellinis excellent post on elliptic curve cryptography.

1. D. Hankerson, A. Menezes, S. Vanstone,
Guide to elliptic curve cryptography, Springer, New York 2004
2. Elliptic curve point addition online tool at https://cdn.rawgit.com/andreacorbellini/ecc/920b29a/interactive/modk-add.html

A primer on elliptic curve cryptography: theory

Strong cryptography is at the heart of the blockchain and many other modern technologies, so it does not hurt to get familiar with the basics. In this post I will explain the foundations of one very commonly used algorithm called elliptic curve digital signature. This post will be a bit lengthy and theoretical but do not worry – we will see how all this works in practice in the next post.

First we need to understand what private and public keys are. At the end of the day, cryptography is about encoding and decoding messages. Suppose, for instance, that two parties (which we will call Alice and Bob to follow the usual naming conventions) want to exchange information, but expect that a third party is able to obtain a copy of every message that they send forth and back, for instance because Alice and Bob communicate over the internet and a third party could control some of the routers sitting between them (yes, we all know this is not just theory…).

One approach that Alice and Bob could use is as follows. In a first step, they both agree on a key. This could be a key phrase or some other sequence of bytes, depending on the exact algorithm they use. To send a message to Bob, Alice would then take the message $m$ and encrypt it, i.e. apply a function $f_k$ that depends on the key $k$ to obtain an encrypted message $e = f_k(m)$ .

Alice would then send the encrypted message to Bob. Bob would apply a second function $g_k$ to the received message to decrypt it again. If $f$ and $g$ are chosen properly, then they will be inverses of each other, i.e.

$m=g_k(f_k(m))$

Therefore Bob will be able to obtain the original message from the key and the encrypted message. The algorithm is secure if it is virtually impossible to derive the original message from the encrypted message without knowing the key.

This class of algorithms is called symmetric because both parties, Alice and Bob, use the same key, i.e. the same key is used to encrypt a message and to decrypt it again. Unfortunately, there is an obvious challenge when using this in practice: Alice and Bob need to exchange the key and therefore need a separate secure communication channel. In a peer-to-peer network like the blockchain where the nodes can only communicate via the unsecure public internet, this is virtually impossible, and a different approach is needed.

Asymmetric algorithms and public key cryptography are designed to overcome exactly this difficulty. These algorithms uses keys that come in pairs. Every key pair consists of a public key and a private key. As the naming suggests, the public key is intended to be shared, while the private key needs to be kept secret at all times. When Alice wants to send a message to Bob, she will first need to retrieve Bobs public key. Bob could for instance publish his key on a webpage or add it to the signature of an e-mail. Alice would then encrypt the message using the public key. When Bob receives the encrypted message, he uses his private key to decrypt the message again.Knowing the public key and the encrypted message is not sufficient to perform the encryption step, the private key is needed to do this. As only Bob has access to his private key, only he can read a message that has been encrypted with his public key, even though his public key is freely available and known to an attacker.

PublicKeyCryptography

Public key cryptography relies on a mathematical operation that is easy to perform in one direction, but virtually impossible in the other direction. A classical example is the factorization of large numbers. Whereas it is easy to multiply two large prime numbers $p$ and $q$ to obtain their product $n=pq$ , it requires a lot of computing power to execute the reverse operation, i.e. to determine $p$ and $q$ from $n$ . The well known RSA algorithm is based on this.

Other algorithms with this property are certain operations in properly chosen finite groups. Recall that a group is a mathematical structure in which elements can be added and subtracted such that the usual rules like associativity that we are used to from the addition of ordinary numbers apply. In particular, given a group $g \in G$ as well as an integer $k$ , we can form the product $kg$ which is obtained by adding performing k additions.

$kg = g + \cdots + g$

In some groups, the result of this operation can easily be calculated, but given $kg$ and $g$ , it is very difficult to determine $k$ . This property can be exploited to design cryptographic algorithms, as we will see in a few minutes.

One large class of finite groups with this property are elliptic curves over finite fields. Suppose that we are given some finite field $K$ (most of the time, $K$ is the prime field $F_p$ for some prime number $p$ ). Let us also assume that the characteristic of $K$ is odd. For our purposes, an elliptic curve over $K$ is the set of points $(x,y)$ that obeys an equation of the form

$y^2 = x^3 + ax + b$

with constants $a,b$ .

Finite fields are a bit difficult to visualize. To get an idea how an elliptic curve looks like, let us take a look at an example over the reals.

SECP256K1

The curve displayed here has the parameters $a=0$ and $b=7$ and features a prominent role in the bitcoin protocol (this curve over a certain finite field is known as SECP256K1, more on this in a later post). The blue line visualizes all pairs $(x,y)$ on the curve. This picture also demonstrates the reason why elliptic curves are so useful for our purposes – points on the curve can be added, and in fact the set of points on a curve forms an abelian group.

To see how the addition works, look at the points marked as A and B in the picture above. To add these points, draw a line through A and B. This line will (ignoring a few special cases and multiplicities for the time being) intersect the curve in exactly one other point, called C in this example. Then reflect on the x-axis to arrive at the point which has the same x-coordinate as C, but minus its y-coordinate. This point is, by definition, the sum of A and B.

If you have a bit of a background in algebraic geometry and that rings a bell, you are right – it has to do with divisors. In fact, the set of points on an elliptic curve is in a one-to-one correspondence with a subgroup of the divisor class group, and the group structure inherited by this relation is the one that I have just described. See [1] for more details.

So now we have a finite abelian group (remember that in reality, we do not do this over the reals but over some finite field) – what can we do with it? To illustrate this, let us describe one application to cryptography called elliptic curve digital signature algorithm (ECDSA). A digital signature is like a watermark that you add to a message to allow others to verify that you have seen and approved the message and that the message has not been altered in transit. Again, most digital signatures involve public and private key pairs. When Alice wants to sign a message $m$ , she uses her private key to encode her message and obtains a signature $s$ . She then sends that signature along with the original message and her public key to Bob. Using that information, Bob can verify the signature to confirm that it has been created using the private key that belongs to the public key and that the message that he has received is identical to the message that Alice has signed. Assuming that only Alice has access to the private key, he can then deduce that Alice has actually composed and approved the message. In practice, it is not the actual message that is signed, but a hash value of the message to keep the signature short.

Let us see how this works (in addition, [2] is a readable and valuable resource for some of the details). Suppose Alice wants to sign a message $m$ . The first thing she will do is to agree with Bob on some set of elliptic curve parameters, i.e. a finite field, the parameters $a$ and $b$ and some point $G$ on the curve called the generator. In [2], a few standard sets have been defined and published, among them the standard SECP256K1, on which Alice and Bob could agree. That information is public and does not need to be protected.

Next, Alice will pick a secret or private key. In our case, this is simply a number $d$ between zero and the order $n$ of the point $G$ . Alice will then determine a public key

$Q = dG$

which is simply a point on the curve. That key can be freely published – as we have mentioned before, it is computationally very hard to determine the secret $d$ from that information.

All this only needs to be done once. Now comes the part that is specific to the message. First, Alice create a hash value of the message by applying a hash function:

$h = H(m)$

The hash function needs to be chosen such that the resulting hash value can be interpreted as a number between zero and $n - 1$ . Next Alice picks a random number $k$ between one and $n - 1$ and determines the coordinates of the point $kG$ . Let $r$ denote the x-coordinate of this point. Then Alice determines

$s = k^{-1}(h + dr) \mod n$

where the inverse is taken modulo n. The signature that Alice will publish along with the original message is then the pair $(r,s)$ .

When Bob wants to verify the signature, he would then again compute $h = H(m)$ and determine the point

$X = s^{-1} hG + s^{-1} rQ$

on the curve. Let us do a short calculation to see what the expected outcome is. First,

$X = s^{-1}(h + rd) G$

Now by the choice of $s$ , we also have

$s^{-1} = k(h+dr)^{-1} \mod n$

Therefore

$s^{-1}(h+dr) = k \mod n$

As $n$ is the order of $G$ , this implies that

$X = kG$

Thus we expect that the x-coordinate of the newly computed point $X$ is equal to the x-coordinate of $kG$ which Alice has published as $r$ . If Bob makes this comparison and arrives at this result, he can be almost sure that someone who has access to the private key has signed the message and that the message has not been altered since then.

Note that, if we knew the signature and $k$ , we could compute $h + dr$ and therefore the secret $d$ . It is therefore extremely important to treat the number $k$ with care – use a strong random number generator to obtain it, do not reuse it for further messages and delete it immediately after using it.

We have now seen how arithmetic on an elliptic curve can be used to design a secure and reliable digital signature. I admit that this was a bit theoretical, but now comes the fun part – in the next post we will see how this can be done in Python and code a few examples. Stay tuned…

1. R.Hartshorne, Algebraic Geometry, Springer, New York 1997, example 6.10.2
2. Standards for efficient cryptography 1 and 2 (SEC1, SEC2), SECG Group, available online at http://www.secg.org

What this blog is about

Over the last couple of years, I have spent a considerable part of my spare time digging deeper into some topics around computer science and mathematics, mostly driven by the desire to understand how all that really works. Many years ago, I wrote a multi-threaded Unix kernel and made it boot on my PC to understand how multitasking works. Some years later, I built a small 4-bit CPU out of standard TTL circuits to because I wanted to understand the inner workings of a CPU. And recently, I learned Python to collect hands-on experience with neural networks and explore their relation to statistical physics.

If I had tried to learn all this twenty years ago, I would have needed access to a world-class library, and even than I would have spent an incredible amount of time scanning textbooks and papers to dig out the few really valuable nuggets of information that eventually make you understand.

Fortunately, we now live in a world where an incredible amount of information at our disposal. I was always very grateful to find so many freely available resources on the web – source code, tutorials, blog posts and papers, created not for the sake of profit but simply to share ideas and thoughts, and maybe hoping that it might be of use for someone out there. Now I decided to do the same thing – giving back a bit of what I have seen, in the hope that it might be helpful for whoever is trying to learn and understand.

My interests vary quite a bit, and so will the topics of this blog. I will probably start with a few posts on the stuff that I recently looked at, namely some topics around machine learning and artificial intelligence, and the technology behind the blockchain. I will try to make this as tangible as possible, so I will also show you how to actually code these things. At the moment, the programming language of choice that I use for that is Python, so you should not be surprised to find a few Python code snippets in my posts.

So let us start – in my first post, I will explain the basics of keys and addresses in the blockchain.