US patent 6141420, Vanstone Mullin Agnew, elliptic-curve cryptography

This patent is known as a patent on elliptic-curve point compression. However, this patent has never been fought in court and will clearly not survive in court, for two reasons:

• Point compression for binary Weierstrass curves in ECC was spelled out in detail in a paper published in 1992, more than a year before the patent was filed. This patent claims point compression for general curves, but patent law does not allow patenting generalizations of the prior art.
• The patent "inventors" were indisputably aware of this prior art (Vanstone was a coauthor of the paper) but hid it from the patent office. This is what patent lawyers call "inequitable conduct"; it invalidates the entire patent.

The contents of the patent are as follows.

Claims 1 through 28 are for encryption using an elliptic curve over a finite field of characteristic 2 with elements represented on a normal basis.

Claim 29 is for point compression: "A method of transferring the coordinates of a point on an algebraic curve defined by a function of two variables between a pair of correspondents connected by a data comunications link comprising the steps of forwarding from one correspondent to another a coordinate of said point, providing at said other correspondent parameters of said algebraic curve, and computing at said other correspondent said other coordinate from said one coordinate and said algebraic curve." This claim includes many systems published more than a year before the patent was filed, and is therefore invalid. For example, in the CRYPTO '85 article introducing elliptic-curve cryptography, Victor Miller suggested transmitting only the x coordinate for elliptic-curve Diffie-Hellman:

Finally, it should be remarked, that even though we have phrased everything in terms of points on an elliptic curve, that, for the key exchange protocol (and other uses as one-way functions), that only the x-coordinate needs to be transmitted. The formulas for multiples of a point cited in the first section make it clear that the x-coordinate of a multiple depends only on the x-coordinate of the original point.

Claims 30 through 41 are on more specific techniques involving "forwarding with said one coordinate identifying information of said other coordinate." (Exception: claim 36 is claim 29 for elliptic curves over finite fields of characteristic 2.) This is a waste of time in the context of elliptic-curve Diffie-Hellman, but is useful for elliptic-curve signatures. Bodo Moeller points to page 171 of the Harper-Menezes-Vanstone paper "Public-key cryptosystems with very small key lengths" at Eurocrypt '92, published more than a year before the filing of this patent:

The key length can be shortened to n+1 bits as follows. Observe first that the change of variables (x,y) -> (x,xz) transforms equation (1) to z^2 + z = x + a + bx^(-2). (3) Given the x-coordinate of a point P = (xbar,ybar), we can compute the right hand side of (3). Then (3) has precisely 2 solutions, namely z' and z'+1, and these solutions can be easily found. We can then select the correct solution zbar (and hence reconstruct ybar as ybar = xbar zbar) if we know the least significant bit of zbar. Thus to transmit P it is sufficient to transmit xbar and the least significant bit of ybar/xbar.

Claims 42 through 52 are on some secret-key encryption mechanisms.