Re: Elliptic-Curve Diffie-Hellman Key Exchange draft

[Douglas Stebila <douglas.stebila%sun.com@localhost>]

Niels Möller wrote:

> > I recently posted a draft to add support for the use of elliptic curve
> > cryptography in the form of Elliptic Curve Diffie-Hellman (ECDH) key
> > agreement to the exchange portion of the SSH Transport Layer protocol.
>
> What's the current patent status on that area? Is it possible to
> implement any cryptography on elliptic curves without getting a patent
> license from the patent holders (certicom? Others?).

Yes, it is possible and it can be easily done.

ECC as an algorithm was introduced in 1985 by Neal Koblitz and Victor 
Miller with no patents over the algorithm.  Certicom does not hold an 
umbrella patent right over the algorithm. It only holds patents on some 
peripheral implementation or optimization techniques.

RSA has a FAQ about patents related to elliptic curve cryptography at
http://www.rsasecurity.com/rsalabs/faq/6-3-4.html.  Highlights include:

"Elliptic curve cryptosystems, as introduced in 1985 by Neal Koblitz
and Victor Miller, have no general patents, though some newer elliptic
curve algorithms and certain efficient implementation techniques may
be covered by patents. ..."
and
"... In all of these cases, it is the implementation technique that is
patented, not the prime or representation, and there are alternative,
compatible implementation techniques that are not covered by the
patents."

Elliptic curve crypto can be implemented using basic school book 
techniques which have no patent infringement concern. Simple standard 
techniques such as "window table lookup", "projective coordinate space", 
and "non-adjacent form wNAF" can be used for performance optimization 
with no patent concern. These techniques are school book techniques 
commonly used for RSA optimization and other multi-precision integer 
arithmetic computation.

Sun has contributed an ECC implementation to the OpenSSL project,
and has filed some patent applications related to elliptic curve
cryptography, but has explicitly indicated in the ECC code it
contributed to the OpenSSL project that "Sun does not intend to assert
its patent rights associated with the code that was delivered to the
OpenSSL project."  (See
http://research.sun.com/projects/crypto/FrequenlyAskedQuestions.html
for more information.)

It should be noted that elliptic curve cryptography implementations
can now be found in a number of open source projects (OpenSSL,
Mozilla's Netscape Security Services, Victor Shoup's NTL, Wei Dai's
Crypto++) and there are any number of standards on ECC.  In fact, at
present an ECC in TLS draft is going through IETF's TLS working group
and to my knowledge there are no concerns on patent issues.

I hope this helps dispel some of your concerns about the patent issues 
concerning ECC.

Regards,

Douglas Stebila