[Cryptography] Why is ECC secure?

Viktor Dukhovni cryptography at dukhovni.org
Tue Jun 30 10:56:21 EDT 2015


On Mon, Jun 15, 2015 at 02:05:51PM -0700, Bill Cox wrote:

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

That said, with a bit more thought (and a hint from Watson Ladd I
should not have needed), there is a useful homomorphism if we're
willing to abandon the rational circle for multiplication in a
finite field.

If p == 3 mod 4, choose $i^2 = -1$ in a quadratic extension $F_{p^2}$.
If p == 1 mod 4, choose $i^2 = -1$ in the base field $F_p$.

In either case the mapping (x,y) -> (x+iy) is an injective homomorphism
(monic) from the circle group into the multiplication group of the
corresponding finite field.  In fact for the 1 mod 4 case the
mapping is an isomorphism.  

So DLP in the 1 mod 4 circle group is identical to DLP in F_p (plus
the cost of finding a square root of p-1).

DLP in the 3 mod 4 circle group is a sub-problem of DLP in F_{p^2},
which is subject to essentially the same index calculus attacks as
F_p, but now the smooth factor base uses gaussian integers.

None of this helps with d != 0 (actual Edwards curves), where the
above homomorphisms don't exist.

If DLP for Edwards curves uses ~256-bit primes for conjectured ~128
bit security, DLP on the circle would need around 3000 bits for a
similar security level.

-- 
	Viktor.


More information about the cryptography mailing list