<div dir="ltr">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.<div><br></div><div><img src="cid:ii_1502ac5e1e083262" alt="Inline image 1" width="336" height="324" style="margin-right:0px"><br></div><div><br></div><div>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:</div><div><br></div><div>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.</div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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:</div><div><br></div><div>    G(a, b, d) = sn(F(a; d) + F(b; d))</div><div><br></div><div>I've proven this.  The function F(a; d) is the <a href="https://en.wikipedia.org/wiki/Elliptic_integral" target="_blank">Incomplete Elliptic Integral of the First Kind</a>.  The 'd' is the same constant d used in<a href="https://en.wikipedia.org/wiki/Edwards_curve" target="_blank"> Edwards curves</a>.  It is one-to-one and invertable.  It's inverse function is sn(u, m), the <a href="https://en.wikipedia.org/wiki/Jacobi_elliptic_functions" target="_blank">Jacobi Elliptic Sine</a> 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.</div><div><br></div><div>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 <a href="https://en.wikipedia.org/wiki/Jacobi_elliptic_functions#Addition_theorems" target="_blank">well know addition theorem</a>.</div><div><br></div><div>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:</div><div><br></div><div>The Edwards addition law is the _same_ law as the ellipse addition law.</div><div><br></div><div>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.</div><div><br></div><div>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 <a href="http://www.und.edu/instruct/schwalm/MAA_Presentation_10-02/handout.pdf" target="_blank">ellipse we all studied in high-school</a>.</div><div><br></div><div>I've attached python code demonstrating the equivalence of crypto on Edwards curves and ellipses.  Enjoy!</div><div><br></div><div>Bill</div></div>