Edwards Curves



On the second day of 29c3, we talked about the group law on an elliptic curve based on our old script (in German) called "Das Gruppengesetz auf Elliptischen Kurven". Today, we explained to some people how elliptic curves can be used to factorize the product of two primes, i.e. attack weak RSA keys. When we were done, we let the flipchart paper taped to the wall and sat down. Few minutes passed before two people in passing showed an unusual interest in our notes. A few words into the conversation, I bluntly asked them about their mathematical background, which was met with an amused > I'm a math professor, does that suffice? These people turned out to be Tanja Lange and Daniel Bernstein, two scientists who are rather big shots in mathematical cryptography. I am ashamed to say that I did not even know that, but I certainly understood that they knew a lot more about elliptic curves than me and they were willing to share. To be precise, they were really friendly, and good at explaining it. That's rare. Of course, I eagerly listened as they began elaborating on the advantages of Edwards coordinates on elliptic curves. The two of them had attended the talk by Edwards introducing the concept in 2007 and observed the cryptographic potential: Basically (and leaving out some details), it's all about the fact that \[ x^2+y^2 = 1+dx^2y^2 \] defines an elliptic curve, with all relevant points visible in the affine plane; check out the picture. Choosing $(0,1)$ as your neutral element, a group law on this curve is given by \[ (x_1,y_1) \oplus (x_2,y_2) := \left( \frac{x_1y_2+x_2y_1}{1+dx_1x_2y_1y_2}, \frac{y_1y_2+x_1x_2}{1+dx_1x_2y_1y_2}\right). \] With this shape, you never have to mention projective coordinates, the group law can be explained in a very elementary kind of way — and then it turns out that this shape also yields faster algorithms for point multiplication. In short: If you're into curves, cryptography or both, I thoroughly encourage you to check out their summary page about Edwards coordinates.

Leave a Reply

Your email address will not be published.