[Cryptography] Why is ECC secure?

[Viktor Dukhovni]

On Tue, Jun 30, 2015 at 08:57:33AM -0700, Bill Cox wrote:

> Given that the circle group seems roughy equivalent to regular DLP in
> difficulty, is it safe to say that finding a compactly representable point
> on the unit circle that maps to (x, y) mod p is equivalent in difficult to
> DLP?  This would explain why I am finding it difficult to do :-)

Can you clarify the question?  It is fairly easy to find points on
the unit circle mod p (if that's what you're asking for):

    1. Standard birational equivalence:

	t -> (x, y) = (2t, t^2-1)/c^2, where c^2 = 1/(t^2+1)

       whose inverse is t = (y+1)/x.  For p == 1 mod 4, choose any
       t in F_p with t^2 != -1, or t = infinity which maps to (0,
       1).  For p == 3 mod 4, choose any t in F_p or infinity.

       For example, if p = 37 choose t != +/-6, say t = 5, then
       (x, y) = (10, 24)/26 = (26, 18).  26^2 + 18^2 = 1000 which
       is 1 mod 37 (since 111 = 3 * 37 so 999 = 27 * 37).

    2. For p = 1 mod 4, and $i^2 = -1$, the reciprocal of r = (x + iy)
       is 1/r = (x - iy).  Therefore, take any non-zero residue $r$,
       then compute (r + 1/r) giving $2x$ and $r - 1/r$ giving $2iy$.
       Then just compute (x, y) = ((r+1/r)2, i*(1/r-r)/2).  For
       example, with p = 37, and i = 6, take r = 5, then 1/r = 15,
       giving x = 10, and y = 6*5 = 30.  Once again we get
       x^2 + y^2 = 1000 or 1 mod 37.

As for finding rational points on the ordinary unit circle that
somehow "correspond" to (x,y) mod p, it is still far from clear
what correspondence you have in mind...

-- 
	Viktor.