[Cryptography] Edwards curves are just ellipses - and why ECC works

[Bill Cox]

I assume this is all well known, but it's new to me and may help people on
this list understand modern ECC.  One of the best recent curves is
curve25519, with an excellent signing algorithm, Ed25519.  I wanted to know
"why this works".  Here's why.

[image: Inline image 1]

It turns out that anyone can trivially create "addition laws" to create new
ways to add "group elements" together, forming an "Abelian group ".
Here's how:

1) Pick _any_ one-to-one function, so that an inverse exists, even if it is
hard to compute, Call this function F, and it's inverse Finv.
2) Write out the function G(a, b) = Finv(F(a) + F(b)).  This is the "group
addition law" that shows how to add elements of the group.

Give it a try.  I'm sure you can easily convince yourself that this
generally works.  For example, if F(a) = 1/a, then G(a, b) = 1/(1/a + 1/b)
.  This can be though of as the "parallel resistor group", where elements
are resistors and the addition operator puts them in parallel.

So, what is the "addition law" for one of the most awesome recent curves,
the "Edwards curve"?  For Edwards curves without the "twist", the addition
law is simply:

    G(a, b, d) = sn(F(a; d) + F(b; d))

I've proven this.  The function F(a; d) is the Incomplete Elliptic Integral
of the First Kind <https://en.wikipedia.org/wiki/Elliptic_integral>.  The
'd' is the same constant d used in Edwards curves
<https://en.wikipedia.org/wiki/Edwards_curve>.  It is one-to-one and
invertable.  It's inverse function is sn(u, m), the Jacobi Elliptic Sine
<https://en.wikipedia.org/wiki/Jacobi_elliptic_functions> function.  The
proof basically projects an Edwards curve onto a unit hemisphere, by adding
a variable z^2 = d*x^2*b^2.  If you integrate 1/sqrt(xy) along this path on
the unit hemisphere, you get the exact same integral that defines the sn(u,
d) function.  This integral defines the "formal group law" for the Edwards
curve, I think.  By the way, "d" in the Edwards curve formula is equal to
"m" on the ellipse, which is the "eccentricity" squared.

Now that's all scary, but these are just functions like sine and cosine.
The important thing is we _don't_ know how to do modular arithmetic with
them, but we _do_ know how to compute the addition law G(a, b, d)
algebraically, in a modular arithmetic friendly way.  It was proven maybe
200-ish years ago that the "group addition law" for a regular ellipse (the
actual squished circle we all know and love) can be written.  Here's a link
to the well know addition theorem
<https://en.wikipedia.org/wiki/Jacobi_elliptic_functions#Addition_theorems>.

So, that's it.  That's what ECC is, and why it works.  Here's something
cool I found that may or may not be known:

The Edwards addition law is the _same_ law as the ellipse addition law.

Anyone who tries to tell you that Elliptic Curve Crypto has nothing to do
with ellipses is wrong.  The above G group law is in fact the "exponential
map" for _both_ Edwards curves and regular point addition on an actual
ellipse.

The mapping from an Edwards curve to an ellipse is funny.  The "x"
coordinate on an Edwards curve is _identical_ to the "y" coordinate on the
ellipse!  AFAIK, there is no good reason to hurt our brains with overly
complex mathematics, when we can do the exact same crypto on the same ellipse
we all studied in high-school
<http://www.und.edu/instruct/schwalm/MAA_Presentation_10-02/handout.pdf>.

I've attached python code demonstrating the equivalence of crypto on
Edwards curves and ellipses.  Enjoy!

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20151002/df477271/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image.png
Type: image/png
Size: 89800 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20151002/df477271/attachment.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ellipse_basic.py
Type: text/x-python
Size: 2615 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20151002/df477271/attachment.py>