[Cryptography] Why is ECC secure?

[Viktor Dukhovni]

On Wed, Jun 10, 2015 at 09:13:17PM -0700, Bill Cox wrote:

> 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.

But d=0 is NOT an Edwards curve, the d=0 degeneracy makes it a very
different beast.

> 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).

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.

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".

-- 
	Viktor.