[Cryptography] Why is ECC secure?

[Bill Cox]

On Sat, Jun 13, 2015 at 6:41 AM, Viktor Dukhovni <cryptography at dukhovni.org>
wrote:

> On Wed, Jun 10, 2015 at 09:13:17

> For a given prime p, the given integer x, y point mod p satisfies
> >
> >     (x, y) = s*G mod p
> >
> > where G is a generator point, and s is a secret value.  I'm trying to
> find
> > s, which looks doable if I can map (x, y) back to a rational point on the
> > circle, (l/n, m/n).
>
> Since circle arithmetic is just multiplication of complex numbers
> on the unit circle the relevant formula is:
>
>         (a,b)*(c,d) = (ac - bd, ad + bc)
>
> It is easy to verify that if norm((a,b)) = (a^2 + b^2) = 1 =
> norm((c,d)), mod p or not, then also norm((a,b)*(c,d)) = 1.  The
> inverse of any point (a,b) is (a,-b) and the identity is (1,0).
>

Yes, this is correct.


> In this context, a useful mapping from the circle mod p to the
> characteristic 0 (rational) circle needs to preserve the product,
> (that is it needs to be a group homomorphism), otherwise the mapping
> is of no use in mapping the DLP from (mod p) to the rationals.
>

The homomorphism is simply taking each rational point in the rational group
mod p.  If we have P = s*G in the rational group, then we will also have P
= s*G mod p.  If we find an s that works in the rational group, it also
works mod p.  Further, we don't even have to represent P in the rational
group very accurately.  If we have a 2*n digit approximation of m/n, we can
trivially solve for s in the circle group (just divide by G), and I believe
we can also easily solve for s on an Edwards curve.

Since there are only finitely mod p points, each point has a finite
> order, i.e. (x,y)^n = 1 for for some n.  The same would have to be
> true for any image of (x,y) under a homomorphism into the rational
> circle.  However, there are only four rational points on the circle
> with finite order:
>
>         1, -1, i, -i
>
> all other rational (p, q) with p^2 + q^2 = 1 have infinite order.
> Otherwise, there'd be a primitive n^th root of unity for n > 2,
> with rational real and imaginary parts, but all such numbers
> have degree 2 over the rationals.
>
> So the only viable homorphisms are into Z_4, and cannot be injective
> for all but the smallest primes.
>
> So this approach is a dead-end even for the circle, which is much
> simpler than an actual Edwards curve with a non-zero "d"
>

That's the shortest proof I've seen for why all but a few rational points
generate infinite groups on the unit circle.  I Googled that the other day,
and maybe this is a standard proof, but I failed to find such a succinct
proof.  Nice!

In reality, we typically do not do elliptic curve crypto on groups
homomorphic to rationals over an elliptic curve.  We always extend the
rationals by certain irrationals and sometimes i, but the math basically
seems to work out the same.  Given a rational coordinate x, I haven't seen
a curve where y is rational, though I've only looked at some NIST curves
and curve25519, and a few toy curves I made up.

However, I'm not trying to map a finite group mod p to another finite
group.  I was just wondering if we already knew what the difficult problem
is in doing the reverse-mapping of the homomorphism from rationals on the
unit circle to points mod p.  I was guessing this is already well known.  I
was just wondering if anyone had a useful link where I could learn more
about the problem.

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150615/cbec04fe/attachment.html>