Re: Elliptic-Curve Diffie-Hellman Key Exchange draft

[nisse%lysator.liu.se@localhost (Niels Möller)]

Douglas Stebila <douglas.stebila%sun.com@localhost> writes:

> Niels Möller wrote:
> 
> > 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.

[...]

> "... 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."

Ok, that's good news.

> 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."

I'm always uneasy about such promises. Ok, Sun may have the best
intentions now. But even if Sun's intentions don't change over time,
the patents could be sold off to other companies with different plans.

For example, in RFC 1170, Public Key Partners, owners of RSA and
Diffie-Hellman patents at the time, promised that "licenses to
practice RSA signatures will be available under reasonable terms and
conditions on a non- discriminatory basis". A few years later, the
company I worked for tried to actually buy RSA licenses from the
patent owner, the RSA company. They were unwilling to even negotiate
the price for such a license, they could sell us their software
toolkit BSAFE, but patent licenses were out of the question.

What patents do Sun have in this area? Searching for "Sun" and
"Elliptic" I find US patent 6721771,

: Method for efficient modular polynomial division in finite fields f(2 m)
: 
: Abstract
: 
: The present invention provides a method for performing an inversion
: and multiply in a single operation as a polynomial divide operation.
: As a result, the invention reduces the number of mathematical
: operations needed to perform point doubling and point addition
: operations. An elliptic curve cryptosystem using the present invention
: can be made to operate more efficiently using the present invention.
: An elliptic curve crypto-accelerator can be implemented using the
: present invention to dramatically enhance the performance of the
: elliptic curve cryptosystem. The invention uses five registers A, B,
: U, V, and M, to accomplish a polynomial divide operation. Four
: registers A, B, U, and V are initialized with values so that the
: registers maintain a number of invariant relationships. The registers
: store initial values a(t)=x(t), u(t)=y(t), b(t)=prime(t), and v(t)=0.
: Here the polynomials in registers A, U, B, and V are denoted as a(t),
: u(t), b(t), and v(t), respectively. Register M stores the irreducible
: polynomial prime(t). By applying a series of invariant operations to
: the registers, the register values are systematically reduced until
: registers A and B have a value of one. At that point, register U
: stores a value which represents y(t)/x(t) mod prime(t), solving the
: polynomial division.

and four published applications,

: 20030212729 Modular multiplier
: 
: 20030208518 Generic implementations of ellipitic [sic] curve
:             cryptography using partial reduction
: 
: 20030206629 Hardware accelerator for elliptic curve cryptography
: 
: 20030206628 Generic modular multiplier using partial reduction

Are these the relevant patents, or am I missing something? (There are
3811 patents assigned to "Sun Microsystems" in the uspto database, and
795 published patent applications, so I really can't make an exhaustive
search).

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

Thanks for the information. I think I'd have to talk to a lawyer
before implementing any elliptic curve cryptography.

Regards,
/Niels