[Cryptography] Why is ECC secure?

[Viktor Dukhovni]

On Sun, Aug 16, 2015 at 05:56:19PM -0700, Bill Cox wrote:

> This is simple linear matrix based crypto.  This has been shown to be
> equivalent to regular DLP.  You take the characteristic equation of the
> matrix, and using this compute an equivalent regular DLP problem with some
> polynomial manipulation magic.

No matrix algebra is needed here.  See my messages from June 30th.

    Message-ID: <20150630145621.GF14121 at mournblade.imrryr.org>
    Message-ID: <20150630182121.GG14121 at mournblade.imrryr.org>

For p = 1 mod 4, the circle group is isomorphic to the multiplication
group in F_p, which is cyclic of order p-1.  For p = 3 mod 4, the
circle group is isomorphic to a cyclic subgroup of order p+1 of
F_{p^2}.  DLP for both is IIRC believed roughly comparable in
difficulty to RSA with moduli of the same size.

> This is good news to me for the security of elliptic curve crypto.

That's not so clear.  A reduction of EC to circle arithmetic would
substantially weaken EC, because the primes in EC are much smaller
than the primes in regular finite-field DLP (or degree-2 extensions
thereof).  Also, it is hypothetically possible that EC groups are
easier to attack than the circle group, and we just have not figured
out how just yet.

> My fear
> was that we simply have not yet figured out how to do invsin(x) mod p.

That's just one dead-end, a failure of naive intuition from "real"
analytic geometry to carry over to the discrete case.  This does
not rule out more sophisticated attacks, based on deeper theory.

Now for the discrete circle, we have computationally efficient
isomorphisms from the circle group to the finite-field DLP problem,
so any successful attack on the circle group is a successful attack
on finite-field DLP with primes of the same size.

For elliptic curves, there is no analogous isomorphism, which is
a feature, not a bug, since we're trying to avoid giving the attacker
a leg up via "smooth bases".

> In particular, we're leaning towards P256 as the default.  What do we know
> about this curve?  Should there be any concern that there may be a back
> door of any kind?  For example, what happens if the prime modulus minus 1
> has factors that are only known to the NSA?  What if they are purposely
> small?  Do we know enough about P256 to know this sort of thing is not the
> case?

Folks like Adam Langley at Google should be able to provide better
guidance than you'd get from naive analysis of circle groups and
EC.

New curves (newer than P256) for EC are under development in CFRG.
The ECDH curves are done IIRC, but the signature scheme is still
under discussion.  Depending on your timetable, you might be better
off going with the new CFRG curves.

There is no published weakness in P256, just implementation pitfalls.
Of course there's no way to know that the curve is not "cooked" by
an adversary with a much deeper theoretical grasp of EC crypto.

-- 
	Viktor.