Home
One-A-Day 2: Elliptic Curves in Clojure
25 March 02021
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:
- Implement the actual key exchange/messaging code
- Fix the problem of the points not looping back to zero when you've multiplied out the whole group. In the code the 9*[2 3] should equal [0 0], but instead spits out [6 12] for some reason that I wasn't able to figure out. Every number before 9 works though.
Lessons learned:
- I was reminded that when working in modular arithmetic, you can't do a division sign, instead you need to multiply by the inverse (see the inverseMod function).
- Derivatives can be easy to implement in computers if you have predictable structure.
- Working with elliptic curves is not very intuitive.
- How to work with default variables in clojure (see inverseMod and multiply functions).
- I may need to scale back these projects in the future, I have other stuff I want to do and this is kind of dominating my time.
