[Cryptography] Why is ECC secure?

[Bill Cox]

On Fri, May 29, 2015 at 5:21 PM, Tony Arcieri <bascule at gmail.com> wrote:

> On Fri, May 29, 2015 at 12:26 PM, Bill Cox <waywardgeek at gmail.com> wrote:
>
>> Why do we believe this is secure, other than the fact that in EEC's short
>> life, no one has cracked it?  Compared to DLP and integer factorization, I
>> doubt many people have tried.
>>
>
> For what it's worth, you can say the same thing about factorization. The
> only reason RSA is secure is because factoring large numbers is generally
> considered a hard problem.
>

Is the following problem hard?  I'm still trying to grok the basics of what
make ECC hard to attack.  The simplified system I'm trying to attack is
just the unit circle, which is basically an Edwards Curve with d = 0.  I
think I might be able to find the discrete log on the circle if I could
just map the (x, y) mod p point back to a rational point on the circle.

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).  The (x, y) point satisfies:

    x^2 + y^2 = 1 mod p

This point corresponds to a rational point on the unit circle, (l/n, m/n),
where

    (l/n)^2 + (m/n)^2 = 1   (not modular arithmetic)

or equivalently:

    l^2 + m^2 = n^2

At the same time:

    l/n = x mod p
    m/n = y mod p

or equivalently:

    l = n*x mod p
    m = n*y mod p

There are three unknowns (l, m, and n) and three equations restricting
their values.  I would expect to be able to find a solution in most similar
cases.  I have not figured out any better way to compute l, m, and n given
x and y than the giant-step/baby-step algorithm.  Is this problem known to
be hard?  Have I simply failed to find the known solution?

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