[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