Re: PLEASE HELP - Question about elliptic curve cryptography

From: Tom St Denis (tomstdenis_at_gmail.com)
Date: 01/03/05 

Date: Sun, 02 Jan 2005 19:09:35 -0500

Gregory G Rose wrote:
> In article <1104633777.443786.182220@c13g2000cwb.googlegroups.com>,
> <cpptutor2000@yahoo.com> wrote:
>
>>As the domain parameters corresponding to a curve and its associated
>>finite field are system-wide values, could one say that a single curve
>>can supply the cryptographic keys to a number of users? As I am new to
>>ECC, I am a bit confused.
>
>
> Yes, basically everyone could use the same curves,
> without too much danger. NIST FIPS 186-2 has
> recommended curves, for example.
>
> The little caveat to that is that most attacks on
> Discrete-log based systems will end up with the
> attacker having the ability to calculate arbitrary
> discrete logarithms in the group with
> comparitively little effort. So basically they'll
> break "the curve" and not "a particular key". But
> the hypothetical attack that breaks a NIST curve
> will probably apply to other curves too, just with
> a bit of extra effort. All of this is, of course,
> speculation.

The attack does apply to all sorts of "discrete log" problems. The jist
of the sqrt attack is [I've mirror'ed a hard to find paper at
http://iahu.ca:8080/ecc_attack.pdf]

if F(g,x) is your group operator, e.g.

F(g,x) == g^x for DH
F(g,x) == xG for ECC

you're given a generator P and an output Q = F(P, k) for some unknown k.

You compute a list of points

Zi = F(P, Ci) + F(Q, Di)

Since Q = F(P, K) we get Zi = F(P, Ci) + F(F(P, k), Di)

... now turning this into say ECC math [makes it a bit easier]

Zi = Ci*P + Di*Q = Ci*P + Di*k*P = (Ci + Di*k)P

now if for some (Ci, Di) != (Cj, Dj) we have Zi == Zj it follows that

Ci*P + Di*Q = Cj*P + Dj*Q

and

(Ci - Cj)P = (Dj - Di)Q

and finally

(Ci - Cj)/(Dj - Di)P = Q

The quotient on the left is equal to k. With DH you can write

Zi = g^Ci * y^Di
    = g^Ci * g^k^Di
    = g^Ci * g^{k*Di}

So for Zi == Zj we have

g^Cj * g^{k*Dj} = g^Ci * g^{k*Di}
g^{Cj - Ci} = y^{Di - Dj}
g^{{Cj-Ci}/{Di-Dj}} = y

Recall that you know (Ci,Di) as they're the "distinguished points" you
collect. Actually that's what makes the attack practical. You don't
store all the pairs (Ci,Di) just specific ones [that you rate limit
based on storage]. Because if you start at (C,D) and someone else
starts at (C',D') and you collide somewhere between your next DP you
will both have the same DP [obviously].

Tom

Relevant Pages

  • Re: PLEASE HELP - Question about elliptic curve cryptography
    ... >> recommended curves, for example. ... >> The little caveat to that is that most attacks on ... >> a bit of extra effort. ... > of the sqrt attack is [I've mirror'ed a hard to find paper at ...
    (sci.crypt)
  • Re: Joining the Black Cacaus
    ... > descrimination groups are not under more attack by politicians and ... I wouldn't mind having some 'Curves' of my own. ...
    (alt.autos.toyota)
  • Re: EC over GF(p)
    ... There is no known attack. ... specific curves for which said class number is very low. ... curves with pathologically low values for that class number (where the ... word "pathologically" is really justified only if Frey's intuition ...
    (sci.crypt)
  • Re: I joined Curves
    ... I didn't join curves but I figure skate competitively (well as much as us ... adults do at adult nationals) 4 times a week and have done some intense off ... > pain in my left leg/butt from an attack in Dec 03 is most affected. ... > I'm not sure if the fatigue is from the MS or having started Beta Seron ...
    (alt.support.mult-sclerosis)
  • Re: Elliptic Curves, implementation source?
    ... >> from playing cryptographer? ... I do think that ECC ... Which ECC library would you recommend, Tom? ... affine coords and ommits GFcurves completely (including kobliz curves, ...
    (sci.crypt)