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
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 ; 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 and their sum is .
where is the slope of the line joing the above points
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 follows from the rule of adding a point times
That was the elliptic curve in real space . For cryptographic purposes it is more practical to define the elliptic curve over the finite field where is a prime number. Using the modular arithmetic this allows us to perform computation on the curve with finite number of values . 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 representation and operate on discrete space consisting of a set of points. The reason why has to be a prime number is that is a requirement for to satisfy the field axioms. The figures below compare same curve
secp256k1 over real space and over finite field where .
As visible on the figure, the finite field 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
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 and in order to compute .
We can add points that lay on the curve in the space and resulting point will always remain in this space. It is the same in with multiplying them by a scalar . 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
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 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 and on the elliptic curve in finite field graph and try to find a constant number of additions such that . You will end up blindly trying all possible values of 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 . The larger, the better security as it increases the size of the space. They also agree on a
generator which is a point in the space. They also both chose their
private key, which is simply a scalar number, for Alice let us call it and for Bob . In principle, because addition is associative we can expect the following to hold
and this is what makes the Diffie-Hellman key exchange work! So Alice and Bob both calculate their
public keys and using elliptic curve arithmetics
and they exchange their public keys via the insecure channel. Lets say that the generator point in our with . Computation process is demonstrated by a series of transitions or in the space originating at the generator point (in green) and leading to the public key point (in orange).
So in this space Alice public key is and Bobs . Charlie listened to everything and he knows , , , but he does not know nor . 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 through completely different paths! Charlie does not know the point . 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
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 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. I also recommend these animated examples by @xargsnotbombs Michael Driscoll. My examples and code are heavily based on those materials and I highly 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!
- Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of Computation, 48(177), 203–203. 10.1090/s0025-5718-1987-0866109-5
- Miller, V. S. Use of Elliptic Curves in Cryptography. In Lecture Notes in Computer Science (pp. 417–426). Springer Berlin Heidelberg. 10.1007/3-540-39799-x_31
- Merkle, R. C. (1978). Secure communications over insecure channels. Communications of the ACM, 21(4), 294–299. 10.1145/359460.359473
- Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6), 644–654. 10.1109/tit.1976.1055638