[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 y2 = x3 + 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 F2m, 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 Fp 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 k1P, k2P, and k3P, where the ki 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 Fp, else (x, x+y) for curves over F2m). 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
= x2 + y2/x2
(squaring is linear over F2m).
The point doubling formula tells that u = λ2
+ λ + a = x2+ y2/x2
+ x + y/x + a, hence ux2
= x4 + y2
+ x3 + xy +ax2.
Now y2 + xy + x3
+ ax2 = b, so ux2
= x4 + b, and hence b = ux2
+ x4. This is also an alternative
doubling formula, since u = x2 + b/x2.
Copyright © 1997, 2005 by Paulo S. L. M. Barreto. All rights reserved.