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?
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:
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.
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.)
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.
Some resources:
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)
Both RHEL and Fedora have long restrained from shipping OpenSSL with it's ECC support activated, out from concern about infringing patents.
As of RHEL 6.5 Beta, and the 14 October 2013 update to Fedora Core 18, 19, and 20, this is no longer the case, and ECC is activated by default on those two OS, the associated bug is resolved.
IMPORTANT EDIT : Finally Fedora will only include support for a specific subset of ECC NIST Suite B curves, which means they probably rely on the various agreements by which Certicom releases it's IPR on ECC in some specific cases, and not on an analysis of the OpenSSL code concluding that it does not infringe the ECC patent.
