The elliptic curve is something I used to hear a lot about and I was almost ashamed for knowing practically nothing about it. Now the time has arrived to clear myself of my ignorance and finally learn what is it all about, and as usual, I wish to share this knowledge on my tech-blog. The use of elliptic curves in cryptography has been independently discovered (Koblitz, 1987; Miller, n.d.). So why the curve? Why elliptic? What does it have to do with cryptography? Let us start with some definition. As for cryptography usage, the elliptic curve is defined as

y2=x3+ax+b.\begin{aligned} y^2 &= x^3 + ax + b. \end{aligned}

Points belonging to the above equation form a group. The elements of such group are the points of an elliptic curve; the identity element is the point at infinity 00; the inverse of a point is the one symmetric about the -axis; addition is given by the following rule: given three aligned, non-zero points P=(xp,yp)P = (x_p, y_p) and Q=(xq,yq)Q = (x_q, y_q) their sum is R=(xr,yr)R = (x_r, y_r).

xr=m2xpxqyr=yp+m(xrxp)\begin{aligned} x_r &= m^2 - x_p - x_q \\ y_r &= y_p + m(x_r - x_p) \end{aligned}

where mm is the slope of the line joing the above points

m={ypyqxpxq,if PQ3xp2+a2yp,else if P=Q.m = \begin{cases} \frac{y_p - y_q}{x_p - x_q}, & \text{if}\ P \neq Q \\ \frac{3 x_p^2 + a}{2 y_p}, & \text{else if}\ P = Q. \end{cases}

Here below please find few examples of curves with points that demonstrate geometric addition on the curve.

We have a well defined addition of two points on the curve, including adding a point to itself. The multiplication by a scalar nn follows from the rule of adding a point nn times

nP=k=1nP.\begin{aligned} n P &= \sum_{k=1}^n P. \end{aligned}

That was the elliptic curve in real space R\mathbb{R}. For cryptographic purposes it is more practical to define the elliptic curve over the finite field Fp\mathbb{F}_p where pp is a prime number. Using the modular arithmetic this allows us to perform computation on the curve with finite number of values pp. In the finite field representation number of points on the curve is no longer infinite so we do not need to worry about numerical precision. The modular arithmetic provides an equivalence relation, hence we can solve the elliptic curve in the modpmod p representation and operate on discrete space consisting of a set of pp points. The reason why pp has to be a prime number is that is a requirement for Fp\mathbb{F}_p to satisfy the field axioms. The figures below compare same curve secp256k1 over real space R\mathbb{R} and over finite field Fp\mathbb{F}_p where p=17p = 17.

As visible on the figure, the finite field Fp\mathbb{F}_p representation looks nothing like a curve. It does inherit the label “curve” but it does not have to look like a curve. It does solve curve equation over finite field and that is the only reason we call it this way. The point belongs to the curve over finite field if it satisfies the following equation

(y2x3axb)modp=0\begin{aligned} (y^2 - x^3 - ax - b) \mod p &= 0 \end{aligned}

The addition and multiplication by a scalar still work in the modular arithmetic. For calculating the inverse we use the modular multiplicative inverse which relies on the Extended Euclidean algorithm. As an example, here below we add points labeled by DD and FF in order to compute D+F=BD + F = B.

We can add points that lay on the curve in the Fp\mathbb{F}_p space and resulting point will always remain in this space. It is the same in with multiplying them by a scalar nn. The addition is implemented in Python as follows

def eccFiniteAddition(Px, Py, Qx, Qy, a, b, p):
    if None in [Px, Py]:
        return Qx, Qy
    if None in [Qx, Qy]:
        return Px, Py
    if Px == Qx and Py != Qy:
        # point1 + (-point1) = 0
        return None, None
    if Px == Qx:
        m = (3*Px**2 + a)*inverse(2*Py, p)
    else:
        m = (Py - Qy)*inverse(Px - Qx, p)
    Rx = np.mod(m**2 - Px - Qx, p)
    Ry = np.mod(-(Py + m*(Rx - Px)), p)
    return Rx, Ry

and multiplication follows from it

def eccScalarMult(k, Px, Py, a, b, p):
    assert onCurve(Px, Py, a, b, p)
    if np.mod(k, p) == 0:
        return None, None
    if k < 0:
        # k * point = -k * (-point)
        Rx, Ry = eccNegation(Px, Py)
        return eccScalarMult(-k, Rx, Ry)
    rx, ry = Px, Py
    for i in range(k):
        rx, ry = eccFiniteAddition(rx, ry, Px, Py, a, b, p)
    return rx, ry

where eccNegation negates the point on the curve and the inverse implements the modular multiplicative inverse algorithm. Those are defined in gist dedicated for this article.

We can also control the size of this discrete space by choosing pp prime number of appropriate magnitude. Now what is the motivation of that? What is so great about it? The advantage of that is, we can efficiently calculate sums and products, but we cannot efficiently divide points from this space. If you wonder why, I challenge you to pick two points PP and QQ on the elliptic curve in finite field graph and try to find a constant number of additions kk such that kP=Qk P = Q. You will end up blindly trying all possible values of kk until you find one that works, which is not a deterministic approach. This indicates group formed by the elliptic curve implements a trapdoor function which works efficiently one way around but not the other way around. A bit similar as we did in our satisfiability article but much more efficietly! Let us illustrate a practical use-case of that by introducing the Diffie-Hellman Key Exchange protocol (Merkle, 1978; Diffie & Hellman, 1976).

Let us imagine Alice and Bob want to establish a secure communication via an unsafe channel. A third participant - Charlie - is constantly checking all their messages (yes, Charlie the unicorn). Both Alice and Bob agree on the key size which in this case is the prime number pp. The larger, the better security as it increases the size of the Fp\mathbb{F}_p space. They also agree on a generator GG which is a point in the Fp\mathbb{F}_p space. They also both chose their private key, which is simply a scalar number, for Alice let us call it kAk_A and for Bob kBk_B. In principle, because addition is associative we can expect the following to hold

kA(kBG)=(kAG)kB\begin{aligned} k_A (k_B G) &= (k_A G) k_B \end{aligned}

and this is what makes the Diffie-Hellman key exchange work! So Alice and Bob both calculate their public keys pAp_A and pBp_B using elliptic curve arithmetics

pA=kAGpB=kBG\begin{aligned} p_A &= k_A G \\ p_B &= k_B G \end{aligned}

and they exchange their public keys via the insecure channel. Lets say that the generator point G=QG = Q in our Fp\mathbb{F}_p with p=17p = 17. Computation process is demonstrated by a series of transitions kAk_A or kBk_B in the Fp\mathbb{F}_p space originating at the generator point G=QG = Q (in green) and leading to the public key point (in orange).

So in this space Alice public key is pA=Hp_A = H and Bobs pB=Op_B = O. Charlie listened to everything and he knows GG, pp, pAp_A, pBp_B but he does not know kAk_A nor kBk_B. Now both Alice and Bob multiply each others public keys by own private key which is again visualized using series of transitions.

As visible on the figure, both Alice and Bob found exactly the same point CC through completely different paths! Charlie does not know the point CC. In Elliptic Curve Cryptography it is not possible to use public key directly for encryption, however both Alice and Bob can use the shared secret for bulk encryption algorithms such as AES.

Now Charlie could try to brute-force the private key from the public key

def bruteForceKey(Px, Py, pub_x, pub_y, a, b, p):
    for k in range(p):
        _, _, public_x, public_y = eccScalarMult(k, Px, Py, a, b, p)
        if public_x == pub_x and public_y == pub_y:
            return k

which applied to our above example gives the following (correct) result

Bob private key:  13
Alice private key:  4

In practice, however, the key size pp is supposed to be a huge number eliminating the possibility of brute-forcing the key. If you find a deterministic algorithm that finds the multiplication scalar based on two points on the elliptic curve you would solve the discrete logarithm problem.

To wrap it up I would like to share few excellent articles that I used while learning about the elliptic curve and preparing the coding examples. I recommend the Practical Cryptography for Developers book as well as the gentle introduction, finite fields and the excellent interactive tool by Andrea Corbellini. My examples and code are heavily based on those materials and I hihly recommend you check read them for more information. The repository with source-code that renders all the plots is available in this public gist repository. As usual, if you find typos, errors, something is not clear, something is wrong, do not hesitate to let me know and feel free to tweet me!

  1. Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of Computation, 48(177), 203–203. https://doi.org/10.1090/s0025-5718-1987-0866109-5
  2. Miller, V. S. Use of Elliptic Curves in Cryptography. In Lecture Notes in Computer Science (pp. 417–426). Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-39799-x_31
  3. Merkle, R. C. (1978). Secure communications over insecure channels. Communications of the ACM, 21(4), 294–299. https://doi.org/10.1145/359460.359473
  4. Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6), 644–654. https://doi.org/10.1109/tit.1976.1055638

[Back to Top]