Peter Gutmann <pgut001(_at_)cs(_dot_)auckland(_dot_)ac(_dot_)nz>:
Florian Weimer <Florian(_dot_)Weimer(_at_)RUS(_dot_)Uni-Stuttgart(_dot_)DE>:
IIRC, not all ECC stuff is patented, only curves over GF(q), q even, which
can
be implemented efficiently using two-valued logic.
The rule of thumb for ECC is something like "ECC curves are divided into three
groups, weak curves, inefficient curves, and curves patented by Certicom".
While Certicom certainly would like everybody to believe this, there
is few evidence that it is true. Apart from patents on specific
cryptographic schemes, most patents relevant for ECC are on normal
bases for GF(2^m), which were originally thought to be useful because
they allow for very efficient implementation in custom-made hardware,
but turned out to be pretty irrelevant in practice. (None of the
recommended curves in Certicom's recent SEC2 specification uses normal
bases.)
Curves over finite prime fields or curves over GF(2^m) when field
elements are represented using polynomial bases do not appear to have
such patent problems. (Major manufacturers of cryptographic
coprocessors for smartcards implement these without worrying about
Certicom licences.) For software implementations, they are not
automatically more time efficient than using conventional public key
cryptography in DSA-style groups, though. The two important speed-up
techniques that can be used for the NIST recommended curves are due to
Jerry Solinas (NSA, not Certicom): All NIST recommended curves over
prime fields are based on specifically chosen primes (pseudo-Mersenne
primes) to allow for fast modular reduction; some of the NIST
recommended curves over GF(2^m) are Koblitz curves to allow for fast
point multiplication (see Jerry Solinas' CRYPTO '97 paper).
This makes ECC efficient in software without, as far as I am aware,
requiring any Certicom patent licences.
A caveat is that we do not know about additional pending patents that
Certicom may have. Specifically, Certicom claims to have a patent
application covering point compression, and noone else really knows
what is in it. So it may be prudent to avoid compressed point
representations.