[Cryptography] Why is ECC secure?

Bill Cox waywardgeek at gmail.com
Fri May 29 15:26:25 EDT 2015


>From Wikipedia: "As is the case for other popular public key cryptosystems,
no mathematical proof of security has been published for ECC as of 2009."

Why do we believe this is secure, other than the fact that in EEC's short
life, no one has cracked it?  Compared to DLP and integer factorization, I
doubt many people have tried.  BitCoin began to make me a believer, but
consider this attack:


‚Äč
As you may know Edwards curves have formulas of the form:

    x^2 + y^2 = 1 + d*x^2*y^2

and that as d ==> 0, this morphs into a unit circle.  With d == 0, addition
becomes addition of angles, and we can compute the modular inverse of a
point, and easily reveal the secret multiplicand.  The security relies on
the warping done by the d parameter.  However, what if we say:

    z^2 = -d*x^2*y^2

then we have:

    x^2 + y^2 + z^2 = 1

which is just the unit sphere.  Looking at the drawing for this EC curve,
where d == -30, you can see the angles don't add up like they do on the
circle.  However, z increases rapidly when leaving the for corners.  The
path climbs the sphere.  Visually, it looks like the path lengths may add
up just like angles do for circles, once you realize the point moves in the
positive z direction (towards us) when moving away from corners.

If the path lengths in fact add up on the sphere, then we trivially can
break EEC, simply by transforming the problem into regular integer modular
arithmetic and computing the modular inverse.

Has this been investigated?

Actually... I investigated it, and no, the path lengths do not add up.
There are other avenues to explore.  If any transformation from EEC to
regular modular arithmetic is found, it looks like it will transform into
finding m when given m*g mod P, which is trivial.  When other systems, such
as PKC based on matrix powers, were converted to regular integer
equivalents, they at least had DLP to fall back on.  ECC, even if it also
translated to regular DLP, uses keys that are far too short to be secure.

Should we be concerned?

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150529/1b6744dc/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: EC_curve.png
Type: image/png
Size: 227117 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150529/1b6744dc/attachment-0001.png>


More information about the cryptography mailing list