One-A-Day 2: Elliptic Curves in Clojure

25 March 02021

Github link

For my second one-a-day, I decided to try to implement an example of an elliptic curve Diffie-Hellman key exchange. Unfortunately, I ran out of time so wasn't able to implement the full key exchange, so settled for just being able to add and multiply the points on an elliptic curve. Also I forgot to mention last time that you can test out the code by cloneing it and typing "lein run" in the root of the particular project.

I first learned about elliptic curve cryptography from a math class that I took my senior year which was taught by my advisor Jay Daigle. I ended up using his most recent course notes to help jog my memory of how to do stuff with elliptic curves, which proved really useful. In short, elliptic curves are equations with the form y^2 = x^3 + Ax + B for some constant A and B. You can add points on any elliptic curve, but only when working in the projective plane. The projective plane is a standard euclidian plane, but with the addition of a point called O that represents infinity in any direction. These 4 pictures from wikipedia do a pretty good job explaining how addition is done.

From picture 1, you can see that P + Q = -R, and -R is just the reflection of R across the y axis. Now, because of the limitations of computers, elliptic curve cryptography has to be done in a finite field, specifically we want to do it in the intergers mod some prime. So instead of a smooth curve we get a set of points. For example:

Because of some convinient math, we can add points on the elliptic curve the same way we do with elliptic curves on an infinite field, draw a line between them and find the third point (x_3 and y_3) on the line, then reflect it across the y axis. You can do some factoring tricks to make finding x_3 easy, and you just need to plug that into the equation for the line to find y_3. From there, you just need to take -y_3 mod p, and that's your third point. You can also do multiplication by just doing repeated addition. If you want to do actual cryptography, you can do a Diffie-Hellman key exchange, the steps for which you can find on page 98 of Daigle's course notes linked above.

Things to do if I had more time:

Lessons learned: