[Cryptography] Why is ECC secure?

[Bill Cox]

On Tue, Aug 18, 2015 at 8:36 AM, Bill Cox <waywardgeek at gmail.com> wrote:

> 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.
>
> These are curves such that they fit into this form:
>
>     a @ b = Finv(F(a) + F(b))
>
> 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.
>
> These would all be trivially broken except:
>
> 1) F(a) is a transcendental function, with no modular arithmetic equivalent
> 2) Finv(F(a) + F(b)) is algebraic
>
>
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:

    x3 = JacobiSN[EllipticF[ArcSin[x1], d] + EllipticF[ArcSin[x2], d], d]

or more simply in regular notation:

    x3 = sn(F(arcsin(x1), d) + F(arcsin(x2), d), d)

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:

    L = pi/(2*sqrt(2))*sqrt((x2-x1)^2 + (y2 - y1)^2).

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

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.

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.

I admit it is difficult.

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150929/5981a194/attachment.html>