*[Last revision: 2005.07.08]*

The fundamental assumption on which public key cryptosystems
are based is their property that obtaining private values from
public ones is computationally infeasible. Examples of
public values are the generator *g* used in Diffie-Hellman
key negotiation, or the coefficients *a* and *b* of an
elliptic curve equation *y*^{2}* =
x*^{3}* + ax + b*.

In the SPEKE variant of Diffie-Hellman, David Jablon proposes using a
private generator *g*. It occurred to me that an
elliptic curve analog of Diffie-Hellman could use not only a
secret base point *G* (corresponding to *g*), but
secret curve equation coefficients as well.

Obviously, this idea cannot be naively applied. Erik De Win (who has since passed out) immediately pointed out that the curve equation is linear in its coefficients, hence the coordinates of only two curve points is enough to recover the coefficients.

However, when point compression is used one does not know but
a single bit from the *y*-component of a curve point; it is
even possible to discard the *y*-components entirely in a
cryptosystem (*). At first, this
seemed to thwart the trivial attack described above.

But is it enough? As it turns out, no. Richard Schroeppel suggested
deriving equations for (some of) the bits of the *y*-coordinate of
a point *P* from the *x*-coordinates of *P*, *2P*, *3P*,
... *kP* for some *k*, and then recovering *a* and
*b* with the procedure above. Working out the details
for curves over **F**_{2}*m*, I was
amazed to discover that only the *x*-coordinates of *P* and *2P*
are needed to recover *b* (**).
In this case I didn't try to derive a formula for *a*, but a
little more calculations showed that only three points (*P*,
*2P*, and *4P*) are needed to recover *a* and *b* for
curves over **F**_{p} where *p*
> 7. Generalizations are left as an exercise.

This is a kind of "chosen ciphertext" attack, but it
might be possible to mount a similar attack with three known
curve points (i.e. with *k*_{1}*P*, *k*_{2}*P*,
and *k*_{3}*P*, where the *k*_{i}
and *P* are known).

**Moral: let the
coefficients of an elliptic curve be public; making them secret
is futile.**

* The following trick was first described
to me by Richard Schroeppel
(he calls it the *DropY* technique). Suppose Alice and
Bob are performing Diffie-Hellman, and Bob sends Alice only the
*x*-coordinate *x* of his public key *Q* = (*x*, *y*).
Alice guesses the value of *y* (there are only two), and
recovers either *Q* or -*Q*, i.e. either (*x*, *y*)
if the guess was right, or (*x*, -*y*) otherwise (for
curves over **F**_{p}, else (*x*, *x*+*y*)
for curves over **F**_{2}*m*).
Hence, if the shared point as evaluated by Bob is *P* = (*u*,
*v*), Alice would end with either *P* or -*P*
(i.e. either (*u*, *v*) or (*u*, -*v*)) after
multiplying the recovered *Q* or -*Q* by her private
value. Now they both use only the *x*-coordinate *u* of
the computed point as effective shared value.

** Let *P* = (*x*, *y*)
and *2P* = (*u*, *v*). Define *λ*
= *x* + *y*/*x*, so that *λ*^{2}
= *x*^{2} + *y*^{2}/x^{2}
(squaring is linear over **F**_{2}*m*).
The point doubling formula tells that *u* = *λ*^{2}
+ *λ* + *a* = *x*^{2}+ *y*^{2}/*x*^{2}
+ *x* + *y/x* + *a*, hence *ux*^{2}
= *x*^{4}* *+ *y*^{2}
+ *x*^{3} + *xy* +*ax*^{2}.
Now *y*^{2} + *xy* + *x*^{3}
+ *ax*^{2} = *b*, so *ux*^{2}
= *x*^{4} + *b*, and hence *b* = *ux*^{2}
+ *x*^{4}. This is also an alternative
doubling formula, since *u* = *x*^{2} + *b/x*^{2}.

*Copyright © 1997, 2005 by
Paulo S. L. M. Barreto. All rights reserved.*