[Cryptography] Why is ECC secure?

Viktor Dukhovni cryptography at dukhovni.org
Sat May 30 04:07:49 EDT 2015


On Fri, May 29, 2015 at 12:26:25PM -0700, Bill Cox wrote:

> Why do we believe this is secure, other than the fact that in EEC's short
> life, no one has cracked it?

The RSA cryptosystem is not that much older.  And the study of the
arithmetic of elliptic curves dates back to Abel, Weierstrass, ...

> Compared to DLP and integer factorization, I doubt many people have tried.

Your doubt are is not evidence of lack of effort.

> and that as d ==> 0, this morphs into a unit circle.

This is not a meaningful limit to take.

> The security relies on
> the warping done by the d parameter.  However, what if we say:
> 
>     z^2 = -d*x^2*y^2

This does not simplify the arithmetic.  When the characteristic is
1 mod 4, and d is not a square, there is no such z for any x,y on
the curve.

> 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.

Compute what?  EC point addition is a rather non-trivial transformation
on the x, y (and possibly your z) coordinates.

> 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.

Effectve reduction of arithmetic in a cyclic group to modulular
addition is essentially solving the DLP for that group.  Good luck
doing that for general elliptic curves.

> 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.

The claims that the keys are too short is baseless.

> Should we be concerned?

Always with any cryptosystem, but not particularly more for ECC
than for RSA or other well-designed systems.

-- 
	Viktor.


More information about the cryptography mailing list