D. J. Bernstein
Authenticators and signatures


As far as I know, using nistp224 poses no risk of patent infringement.

If you are a patent holder, and you believe that use of nistp224 may infringe your patent, please let me know.

The rest of this page explains why I'm not worried about several specific patents.

The Diffie-Hellman patent

The Diffie-Hellman patent, US patent 4200770, covers nistp224. Fortunately, the patent expired in 1997. So there's nothing to worry about.

The Crandall patents

Crandall has US patents 5159632, 5271061, and 5463690 on elliptic-curve crytography with primes p ``such that mod p arithmetic is performed in a processor using only shift and add operations.'' These patents are reportedly now owned by Apple.

From context it's apparent that the quoted phrase refers to primes of small signed binary weight, such as primes near 2^k, for which division is particularly easy. The patent arguably covers the NIST curves. NIST P-224, for example, uses the prime 2^224-2^96+1.

Fortunately, the Crandall patents are clearly invalid, because the ``invention'' appeared in a printed publication more than a year before the patent application. So there's nothing to worry about.

Point-compression patents

Vanstone, Mullin, and Agnew have US patent 6141420 on, among other things, transmitting only one coordinate of an elliptic-curve point. This patent is owned by Certicom.

To the extent that this patent applies to nistp224, it is clearly invalid, because nistp224 uses exactly the compression mechanism suggested in Victor Miller's CRYPTO '85 article introducing elliptic-curve cryptography. So there's nothing to worry about.

Fixed-base-exponentiation patents

Brickell, Gordon, and McCurley have US patent 5299262 on ``a method for transforming a first signal into a second signal in a manner infeasible to invert'' by various methods of adding (or multiplying) precomputed multiples (or powers) of a fixed base. The patent is reportedly now owned by RSA.

nistp224 does compute public keys as multiples of a fixed base, but it doesn't bother with precomputation. (You do fixed-base multiplication only once, to compute your public key; you do variable-base multiplication many times, to compute a shared secret for every communications partner.) So there's nothing to worry about.

In case anyone cares about this patent for other reasons: I've located prior art.

Similar comments apply to patent 5999627.