[Cryptography] Why is ECC secure?

[Bill Cox]

I just realized what is either an obvious attack against the circle group -
probably the usual attack, or maybe I'm making a mistake.  In short,
represent the group generator g as a 2x2 rotation matrix.  In computing
m*g, we just raise the matrix to the power of m and multiply it by (1, 0).
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.

This is good news to me for the security of elliptic curve crypto.  My fear
was that we simply have not yet figured out how to do invsin(x) mod p.  If
we did, we'd reduce the circle group to a regular additive group with zero
bits of security.  Showing it is equivalent to regular DLP means that we
can never invert arcsin mod p, at least not in less effort than it would
take to solve DLP.  This inverse is well defined once you scale the circle.

The reason I care about the security of elliptic curves is that I'm now in
a group at Google that is working on Token Binding, and we have to pick a
default prefered encryption mode.  It is not the end of the world if Token
Binding gets broken, and we have the flexibility to switch, but pretty much
any crypto decision made at Google impacts a billion people.

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?

Thanks,
Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150816/12980aa0/attachment.html>