Neither the NSA nor anybody else has a patent on ECC. (And no, there is no reasonable justification for government agencies to hold patents, except to make them free to the public.) There are some patents on particular ECC techniques, as explained in http://cr.yp.to/ecdh/patents.html, but they do not cover the currently most popular ECC systems, and in any case they are mostly expired.
> You may be surprised to hear that NSA seeks patents.
However, many of the technologies developed by NSA not only satisfy mission requirements, but also have great potential for commercial use. Following extensive review, NSA may seek patent protection for such technologies as a way to protect and build on the US government’s (USG) investment in research and development.
That's not what you said. You said NSA had patents, demanded licenses for their commercial use, and then more or less implied that the condition they imposed on the use of those curves was to backdoor or subvert software that use them.
I've updated it for clarification. The NSA did have patents, though. After those expired, they licensed Certicom's and their web site even mentions that this only applies to products conforming to their expectations. As in, they control those to quite a degree. The alternative was paying Certicom a licensing fee.
It appears to be free, but your use needs to pass some fairly specific restrictions. Not sure if the PLA is available at any cost if your use does not pass.
You do not need a patent license to use ECDH or ECDSA on a NIST P-curve, nor do you need one to negotiate keys with Curve25519 or to sign with Ed25519.
This covers more or less everything a normal developer would ever do with elliptic curves.
Is there some wacky curve nobody uses that is patent-encumbered, or for which the point multiplication formula is based on patented math code? Maybe. Is there some wacky protocol --- not ECDH, not ECDSA, not EdDSA --- that's similarly encumbered. Yes! For instance: you need a license from Certicom to safely deploy ECMQV. NSA likes ECMQV, and licensed it.
You are not going to use MQV.
The same thing is true of conventional multiplicative group DH and RSA: there are variants and wacky protocols that are patented. Nobody uses them, nobody cares. They're the same kind of patent minefield as putting a shopping cart on a web page is: somebody somewhere has some godawful paper on it maybe, but you can't avoid it and still have a career.
The specifics of this situation aren't very complicated, but they're just complicated enough for people to spread mistrust of curve software. You've gotten a pageful of that on this thread. That's sad, because curve software is much more secure than RSA/DH. Every new system that requires public key crypto should be using curves.
Sure, I'm with you there. I was surprised to learn that NSA held patents at all.
It looks like NSA bought their ECC patents (the ones they license on the forelinked ECC PLA page) from Certicom. I'm still confused as to why NSA would buy a portfolio of patents and then license them restrictively (albeit at no cost).
Just seems a weird thing for a govt agency to do. Not suspicious or nefarious. Just weird.
Yeah that's the one. It has to be FIPS 140-2 compliant or approved by NSA. Outside Type 1 devices or FIPS Level 3-4, both of those seem to suck in practice for security. One way or another, it doesn't get unless they approve it.
Edit to add: That covers the small selection of patents NSA licensed for use in their implementations (esp FIPS 140-2 products). There's around a hundred more of unknown effect. I'd love to see a detailed breakdown of those and risk posed in various ECC use cases.
Who knows NSA's purpose. Certicom's was money from licensing: so much that their company (mainly patents) sold for over a hundred million dollars to Blackberry. I have details in comment above.
Wow, I was not aware that it was even possible for government agencies to hold patents.
Is there any reasonable justification for that?