Can ECC be used without infringing on patents?

Question

Can ECC (Elliptic Curve Cryptography) be safely used without infringing on Certicom's patents?

I would like to make use of ECC in an embedded system to establish a secure channel. But, I am concerned about patent infringement.

Are there open source ECC implementations which are patent-free?

Answer 1

According to Wikipedia, it shouldn't be a problem (if you're careful):

At least one ECC scheme (ECMQV) and some implementation techniques are covered by patents.

(Which of course implies that other schemes are patent-free.)

As for opensource implementations, that same WP article has a good list.
Though you didn't specify what language/platform you're on, I would recommend going with OpenSSL, the most well-known and most reviewed package in the bunch.
Though I've also heard good feedback on some others, such as BouncyCastle, OpenSSH, ...
Depending on what platform, Java and .NET both have built-in support, as do the latest versions of Windows - so you won't have to worry about patents there. (That is to say, it is a safe assumption that these are either patent-free or legally licensed.)

Answer 2

The ECC implementation in OpenSSL has been contributed by Sun (now Oracle) and was, supposedly, written that way precisely to avoid any patented method. Otherwise, as AviD suggests, using an implementation which is already provided by the platform you use (Java, .NET...) is a neat way to avoid any patent trouble: if there was such trouble, it would first strike the platform provider (i.e. Oracle, Microsoft), not you.

To my knowledge (but I am not entitled, in any way, to give law-related advice), parts of ECC cryptography which may still be patented are:

• implementation of curves over binary fields using normal bases;
• point compression;
• acceleration of Koblitz curves using the Frobenius endomorphism;
• various optimization tricks on dedicated hardware architectures (FPGA, ASIC).

If you do not know what any of the above means, then do not worry, you are in the unpatented realm and things are fine.

Answer 3

This is more of a comment than an answer, but the fact that point compression is patented is utterly ridiculous. In essence, it's patenting the process of storing point (x, y) by storing x, and the using y = f(x).

Anyway:

Another thing that's interesting, regarding the 'if you use an implementation provided by someone else, you're fine' argument: At least one hardware security module provider, which includes an ECC implementation, will not guarantee people who use their modules against patent claims. That's food for thought.

Of course, it's also important to note that in some countries (like Japan, iirc) ECC is completely unencumbered, and that many of the other patents only apply in the U.S.

Answer 4

Some resources:

• ECC patents - Wikipedia

• Irrelevant patents on elliptic-curve cryptography - djb and Ed25519#Patents - djb

  Argues that no valid patents cover Curve25519 and Ed25519. There are patents with similar topics, but djb claims there is prior art for them.

• Fundamental Elliptic Curve Cryptography Algorithms - RFC6090

  An RFC collecting ECC algorithms that are believed to be patent free. (by being older than those patents)