Irrelevant patents on elliptic-curve cryptography D. J. Bernstein
Authenticators and signatures
A state-of-the-art Diffie-Hellman function

Irrelevant patents on elliptic-curve cryptography

Popular rumor states that elliptic-curve cryptography is a patent minefield. However, I'm not aware of any patents that apply to Curve25519.

Special primes

Bender and Castagnoli in 1990.06 wrote ``2^{127}+24933 is prime'' and commented that this was ``convenient in computer arithmetic,'' in particular for elliptic-curve cryptography. My prime 2^{255}-19 is convenient for the same reasons.

Popular rumor states that convenient primes are covered by a subsequent Crandall patent: US patent 5159632, filed 1991.09.16, granted 1992.10.27. What the patent actually claims is elliptic-curve cryptography with primes p ``such that mod p arithmetic is performed in a processor using only shift and add operations.'' Similar comments apply to US patent 5271061, filed 1991.09.17, granted 1993.12.14; and US patent 5463690, filed 1991.09.17, granted 1995.10.31.

Reduction modulo NIST's primes 2^{224}-2^{96}+1 et al. is often handled with shift and add operations, raising the question of whether the patent is valid; but reduction modulo my prime 2^{255}-19 is handled with multiplications, which the patent does not claim to cover. It should, in any case, be obvious to the reader that a patent cannot cover prime shapes published two years before the patent was filed.

Point compression

Miller in 1986, in the paper that introduced elliptic-curve cryptography, suggested compressing a public key (x,y) to simply x: ``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.'' This is exactly the compression method that I use.

Popular rumor states that point compression is covered by a subsequent Vanstone-Mullin-Agnew patent: US patent 6141420, filed 1994.07.29, granted 2000.10.31. What the patent actually claims are (1--28) encryption using an elliptic curve over a finite field of characteristic 2 with elements represented on a normal basis; (29, 36) communicating (x,y) on a curve by communicating x and having the receiver somehow compute y; (30--35, 37--41) communicating x and ``identifying information'' of y, such as one bit; and (42--52) some secret-key encryption mechanisms.

My Curve25519 software never computes y, so it is not covered by the patent. It should, in any case, be obvious to the reader that a patent cannot cover compression mechanisms published seven years before the patent was filed.

Fixed-base exponentiation

Yao in 1976 published a fast algorithm to compute many powers of a fixed base. Pippenger in 1976 published an even faster algorithm.

Yao's algorithm, with two slight improvements published later by Knuth, was reinvented by Brickell, Gordon, McCurley, and Wilson in 1993 and patented: US patent 5299262, filed 1992.08.13, granted 1994.03.29. A very small part of Pippenger's algorithm was also reinvented by Brickell, Gordon, McCurley, and Wilson. A slightly larger part of Pippenger's algorithm was then reinvented by Lim and Lee in 1994 and patented: US patent 5999627, filed 1995.06.06, granted 1999.12.07.

My Curve25519 software does not use any of these algorithms.