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.