ECC patents
Encyclopedia
Patent
-related uncertainty around elliptic curve cryptography
(ECC), or ECC patents, is one of the main factors limiting its wide acceptance. For example, the OpenSSL
team accepted an ECC patch only in 2005 (in OpenSSL version 0.9.8), despite the fact that it was submitted in 2002.
According to Bruce Schneier
as of May 31, 2007, "Certicom certainly can claim ownership of ECC. The algorithm was developed and patented by the company's founders, and the patents are well written and strong. I don't like it, but they can claim ownership." Additionally, NSA has licensed MQV
and other ECC patents from Certicom in a US$25 million deal for NSA Suite B
algorithms. (ECMQV is no longer part of Suite B.)
However, according to RSA Laboratories, "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." Additionally, Daniel Bernstein has stated that he is "not aware of" patents that cover the Curve25519 elliptic curve Diffie–Hellman algorithm or its implementation. RFC 6090, published in February of 2011, documents ECC techniques which were published so long ago that even if they were patented, any such patents would now be expired.
According to the NSA, Certicom holds over 130 patents relating to elliptic curves and public key cryptography in generalhttp://www.nsa.gov/ia/industry/crypto_elliptic_curve.cfm.
It is difficult to create a complete list of patents which are related to ECC, but a good starting point is Standards for Efficient Cryptography Group (SECG)
– a group devoted exclusively to developing standards based on ECC. There is controversy over the validity of some of the patent claims.
in United States District Court for the Eastern District of Texas
Marshall
office, claiming that Sony's use of ECC in Advanced Access Content System
and Digital Transmission Content Protection
violates Certicom's patents for that cryptographic method. In particular, Certicom alleged violation of and . The lawsuit was dismissed on May 27, 2009.
As the prior art
Sony claimed :
Patent
A patent is a form of intellectual property. It consists of a set of exclusive rights granted by a sovereign state to an inventor or their assignee for a limited period of time in exchange for the public disclosure of an invention....
-related uncertainty around elliptic curve cryptography
Elliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...
(ECC), or ECC patents, is one of the main factors limiting its wide acceptance. For example, the OpenSSL
OpenSSL
OpenSSL is an open source implementation of the SSL and TLS protocols. The core library implements the basic cryptographic functions and provides various utility functions...
team accepted an ECC patch only in 2005 (in OpenSSL version 0.9.8), despite the fact that it was submitted in 2002.
According to Bruce Schneier
Bruce Schneier
Bruce Schneier is an American cryptographer, computer security specialist, and writer. He is the author of several books on general security topics, computer security and cryptography, and is the founder and chief technology officer of BT Managed Security Solutions, formerly Counterpane Internet...
as of May 31, 2007, "Certicom certainly can claim ownership of ECC. The algorithm was developed and patented by the company's founders, and the patents are well written and strong. I don't like it, but they can claim ownership." Additionally, NSA has licensed MQV
MQV
MQV is an authenticated protocol for key agreement based on the Diffie–Hellman scheme. Like other authenticated Diffie-Hellman schemes, MQV provides protection against an active attacker...
and other ECC patents from Certicom in a US$25 million deal for NSA Suite B
NSA Suite B
Suite B is a set of cryptographic algorithms promulgated by the National Security Agency as part of its Cryptographic Modernization Program. It is to serve as an interoperable cryptographic base for both unclassified information and most classified information. Suite B was announced on 16...
algorithms. (ECMQV is no longer part of Suite B.)
However, according to RSA Laboratories, "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." Additionally, Daniel Bernstein has stated that he is "not aware of" patents that cover the Curve25519 elliptic curve Diffie–Hellman algorithm or its implementation. RFC 6090, published in February of 2011, documents ECC techniques which were published so long ago that even if they were patented, any such patents would now be expired.
Known patents
- Certicom holds a patent on efficient GF(2n) multiplication in normal basis representation.
- Certicom holds multiple patents which cover the MQV (MenezesAlfred MenezesAlfred Menezes is co-author of several books on cryptography, most notably the Handbook of Applied Cryptography.Menezes is a professor in the Department of Combinatorics & Optimization at the University of Waterloo. He is also the Managing Director of the Centre for Applied Cryptographic...
, Qu, and VanstoneScott VanstoneScott A. Vanstone is a cryptographer who co-authored the Handbook of Applied Cryptography. He is currently on faculty at the University of Waterloo's Faculty of Mathematics and a member of the school's Centre for Applied Cryptographic Research. He is also the founder of Certicom. In 1998, he was...
) key agreement technique. - Certicom holds on technique of validating the key exchange messages using ECC to prevent a man-in-the middle attack
- Certicom holds on techniques for compressing elliptic curve point representations.
- Certicom holds on calculating the x-coordinate of the double of a point in binary curves via a Montgomery ladder in projective coordinates.
- US National Security AgencyNational Security AgencyThe National Security Agency/Central Security Service is a cryptologic intelligence agency of the United States Department of Defense responsible for the collection and analysis of foreign communications and foreign signals intelligence, as well as protecting U.S...
holds , , , on efficient GF(2n) calculations in normal basisNormal basisIn mathematics, a normal basis in field theory is a special kind of basis for Galois extensions of finite degree, characterised as forming a single orbit for the Galois group. The normal basis theorem states that any finite Galois extension of fields has a normal basis...
(terms of some patents have expired) - RSA Data SecurityRSA SecurityRSA, the security division of EMC Corporation, is headquartered in Bedford, Massachusetts, United States, and maintains offices in Australia, Ireland, Israel, the United Kingdom, Singapore, India, China, Hong Kong and Japan....
holds on efficient basis conversion - Hewlett-PackardHewlett-PackardHewlett-Packard Company or HP is an American multinational information technology corporation headquartered in Palo Alto, California, USA that provides products, technologies, softwares, solutions and services to consumers, small- and medium-sized businesses and large enterprises, including...
holds on compression and decompression of data points on elliptic curves
According to the NSA, Certicom holds over 130 patents relating to elliptic curves and public key cryptography in generalhttp://www.nsa.gov/ia/industry/crypto_elliptic_curve.cfm.
It is difficult to create a complete list of patents which are related to ECC, but a good starting point is Standards for Efficient Cryptography Group (SECG)
SECG
In cryptography, the Standards for Efficient Cryptography Group is an international consortium founded by Certicom in 1998. The group exists to develop commercial standards for efficient and interoperable cryptography based on elliptic curve cryptography .Members of the consortium include...
– a group devoted exclusively to developing standards based on ECC. There is controversy over the validity of some of the patent claims.
Certicom's lawsuit against Sony
On May 30, 2007, Certicom filed a lawsuit against SonySony
, commonly referred to as Sony, is a Japanese multinational conglomerate corporation headquartered in Minato, Tokyo, Japan and the world's fifth largest media conglomerate measured by revenues....
in United States District Court for the Eastern District of Texas
United States District Court for the Eastern District of Texas
The United States District Court for the Eastern District of Texas is the Federal district court with jurisdiction over the eastern part of Texas and is a part of the Fifth Circuit. The court's headquarters are in Tyler, Texas and has five subdivision offices in Beaumont, Lufkin, Marshall,...
Marshall
Marshall, Texas
Marshall is a city in Harrison County in the northeastern corner of Texas. Marshall is a major cultural and educational center in East Texas and the tri-state area. As of the 2010 U.S. Census, the population of Marshall was about 23,523...
office, claiming that Sony's use of ECC in Advanced Access Content System
Advanced Access Content System
The Advanced Access Content System is a standard for content distribution and digital rights management, intended to restrict access to and copying of the "next generation" of optical discs and DVDs. The specification was publicly released in April 2005 and the standard has been adopted as the...
and Digital Transmission Content Protection
Digital Transmission Content Protection
Digital Transmission Content Protection, or DTCP, is a digital rights management technology that aims to restrict "digital home" technologies including DVD players and televisions by encrypting interconnections between devices...
violates Certicom's patents for that cryptographic method. In particular, Certicom alleged violation of and . The lawsuit was dismissed on May 27, 2009.
As the prior art
Prior art
Prior art , in most systems of patent law, constitutes all information that has been made available to the public in any form before a given date that might be relevant to a patent's claims of originality...
Sony claimed :
- For '870 patent: Alfred J. Menezes, Minghua Qu and Scott A. Vanstone, IEEE P1363 Standard, Standard for RSA, Diffie–Hellman and Related Public-Key Cryptography, Part 6: Elliptic Curve Systems (Draft 2) (October 30, 1994)
- For '928 patent: Scott A. Vanstone, G. B. Agnew and R. C. Mullin, An implementation of elliptic curve cryptosystems over F2155, IEEE Journal on Selected Areas in Communications, Volume 11, Issue 5, Jun 1993 p. 804 - 813