<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Aug 18, 2015 at 8:36 AM, Bill Cox <span dir="ltr"><<a href="mailto:waywardgeek@gmail.com" target="_blank">waywardgeek@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra">I think I'm finally getting the basics of why we like elliptic curve crypto.  Here's my attempt to explain it in regular English.</div><div class="gmail_extra"><br></div><div class="gmail_extra">These are curves such that they fit into this form:</div><div class="gmail_extra"><br></div><div class="gmail_extra">    a @ b = Finv(F(a) + F(b))</div><div class="gmail_extra"><br></div><div class="gmail_extra">The @ is the group "addition" operator and the + is some group operation, likely addition or multiplication.  In the case of Edwards elliptic curves, F(a) is a line integral along a path on the unit sphere.</div><div class="gmail_extra"><br></div><div class="gmail_extra">These would all be trivially broken except:</div><div class="gmail_extra"><br></div><div class="gmail_extra">1) F(a) is a transcendental function, with no modular arithmetic equivalent</div><div class="gmail_extra">2) Finv(F(a) + F(b)) is algebraic</div><div class="gmail_extra"><br></div></div></blockquote><div><br></div><div>A few weeks ago, I managed to prove what I'm sure is already well known: that for Edwards curves, Finv(a) is just sn(a, k), where sn is the Jacobi Elliptic sine function.  The whole Edwards curve addition rule, at least in one quadrant, can be restated (in Wolfram Alpha language) as:</div><div><br></div><div><span style="font-size:12.8000001907349px">    x3 = JacobiSN[EllipticF[ArcSin[</span><span style="font-size:12.8000001907349px">x1], d] + EllipticF[ArcSin[x2], d], d]</span><br></div><div><br></div><div>or more simply in regular notation:</div><div><br></div><div>    x3 = sn(F(arcsin(x1), d) + F(arcsin(x2), d), d)</div><div><br></div><div>The 'd' is the same 'd' as the Edwards curve definition on Wikipedia.  It turns out that sn(a, d) is the inverse of F(arcsin(x), d), so this is just Finv(F(a) + F(b)).  The x coordinates map to an actual ellipse.  I probably had multiple mistakes (I often do), but I had a plausible mapping to the circle group figured out, so I coded it in Python to see if it worked, and naturally it failed.  The error was a little funny.  I relied on what is surely the very well known Farooque equation for arc length of an ellipse:</div><div><br></div><div>    L = pi/(2*sqrt(2))*sqrt((x2-x1)^2 + (y2 - y1)^2).</div><div><br></div><div>Other than the constant pi, that's all modular arithmetic friendly, and we can eliminate the pi by working in degrees rather than radians.  As you probably know, the arcsin of any algebraic number results in an algebraic fraction of pi, and I suspect there is a similar thing going on here.  After a bit of geometric hand-waving, I had a potential mapping.  Of course, the Farooque formula turned out to be wrong.  There's no known closed form solution for the arc-length of an ellipse.  Well, duh, I guess I know that now :-p</div><div><br></div><div>By the way, the u parameter in elliptic integrals can be thought of as the average radius over the sector, times the angle, which I think of as an "effective arc length".  It would be the arc length along a circle of the average radius.  Not sure how that helps, but it's a nice geometric image.  Also, we can easily map Edwards curve points onto the ellipse and work there.  Oddly, it seems like we just need to leave out the y coordinate, unless I've made a mistake, which is likely, though I did check several points, and the Edwards addition law matched the one above to many decimal places.  The X coordinate appears to follow this equation exactly, at least in the upper right quadrant.</div><div><br></div><div>I'm beginning to feel better about the security of ECC (though I was worried when writing that Python code yesterday.  The linear techniques used against the circle group seem to fail here, and I don't know what to try next.  I worry there's some magical "Complex Elliptic Analysis" mathematics we haven't discovered yet which will succeed in mapping this to regular DLP, but I also worry we haven't found the most awesome factoring and regular DLP solving algorithms yet.  Even I was able to come up with several ad-hoc speed-ups for factoring, though none as good as the best algorithms known.  Like everyone else, I have not found any heuristic to speed up attacks on ECC.</div><div><br></div><div>I admit it is difficult.</div><div><br></div><div>Bill<br></div></div></div></div>