ECC patents
{{Short description|Software patents of elliptic curve cryptography}}
{{update|date=August 2018}}
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."{{cite web
| url=http://betanews.com/2007/05/30/certicom-patent-suit-against-sony-threatens-to-unravel-aacs/
| title=Certicom Patent Suit Against Sony Threatens to Unravel AACS
| first=Scott M.
| last=Fulton, III
| date=2007-05-30
| publisher=betanews.com
| accessdate=2013-08-12}} Additionally, NSA has licensed MQV and other ECC patents from Certicom in a US$25 million deal for NSA Suite B algorithms.{{cite web
| url=https://www.certicom.com/news-releases/314-certicom-sells-licensing-rights-to-nsa
| title=Certicom Sells Licensing Rights to NSA
| date=2003-10-24
| publisher=Certicom
| accessdate=2013-08-12}} (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."{{cite web
| url=http://www.rsasecurity.com/rsalabs/node.asp?id=2325
| title=Are elliptic curve cryptosystems patented?
| publisher=RSA Security
| archiveurl=https://web.archive.org/web/20130524001754/http://www.rsa.com/rsalabs/node.asp?id=2325
| archivedate=2013-05-24
| url-status=dead
| accessdate=2013-08-12}} Additionally, Daniel J. Bernstein has stated that he is "not aware of" patents that cover the Curve25519 elliptic curve Diffie–Hellman algorithm or its implementation.{{cite web
| url=http://cr.yp.to/ecdh/patents.html
| title=Irrelevant patents on elliptic-curve cryptography
| first=Daniel J.
| last=Bernstein
| authorlink=Daniel J. Bernstein
| date=2006-05-23
| accessdate=2013-08-12}} {{IETF RFC|6090}}, published in February 2011, documents ECC techniques, some of which were published so long ago that even if they were patented, any such patents for these previously published techniques would now be expired.
Known patents
- Certicom holds a patent on efficient GF(2n) multiplication in normal basis representation; {{US patent|5787028}} expired in 2016.
- Certicom holds multiple patents which cover the MQV (Menezes, Qu, and Vanstone) key agreement technique:
- {{US patent|5761305}} expired in 2015
- {{US patent|5889865}} expired in 2015
- {{US patent|5896455}} expired in 2015
- {{US patent|6122736}} expired in 2015
- {{US patent|6785813}} expired in 2017
- {{patent|EP|0739105}}/[https://patents.google.com/patent/EP0739105B1 EP0739105B1] expired in 2016
- Certicom holds {{US patent|6563928}} on validating the key exchange messages using ECC to prevent a man-in-the-middle attack, which expired in 2016. Related {{US patent|5933504}}, {{US patent|8953787}}, {{US patent|8229113}} also expired in 2016 and {{US patent|7567669}} expired in 2018.
- Certicom holds {{US patent|6704870}} and {{US patent|5999626}} regarding digital signatures on a smartcard; these expired in 2017 and 2016 respectively.
- Certicom holds {{US patent|6782100}} on calculating the x-coordinate of the double of a point in binary curves via a Montgomery ladder in projective coordinates. The priority date is Jan 29, 1997, and the filing date is Oct 2, 2000. Claims disclosed in the original patent application have expired, but some claims kept going enforceable until 2020{{cn|date=August 2019}}.
- US National Security Agency holds {{US patent|4567600}}, {{US patent|4587627}}, {{US patent|6212279}}, {{US patent|6243467}} on efficient GF(2n) calculations on a normal basis (all of these patents expired or lapsed (as Google shows) due to failure to pay fees)
- RSA Data Security holds {{US patent|5854759}} on efficient basis conversion. It expired in 2017.
- Hewlett-Packard holds {{US patent|6252960}} on compression and decompression of data points on elliptic curves. It expired in 2018.
According to the NSA, Certicom holds over 130 patents relating to elliptic curves and public key cryptography in general.{{cite web
|url=http://www.nsa.gov/business/programs/elliptic_curve.shtml
|title=The Case for Elliptic Curve Cryptography
|publisher=NSA
|date=2009-01-15
|accessdate=2013-08-12
|url-status=dead
|archiveurl=https://web.archive.org/web/20090117023500/http://www.nsa.gov/business/programs/elliptic_curve.shtml
|archivedate=2009-01-17
}}
It is difficult to create a complete list of patents that are related to ECC. Still, a good starting point is the Standards for Efficient Cryptography Group (SECG) – a group devoted exclusively to developing standards based on ECC, however, https://www.secg.org/ the group's official website has an indicator that states "shut down for repairs" since 2014. It states that "The site is being restored" since then. 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 Sony 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 {{US patent|6563928}} and {{US patent|6704870}}. The lawsuit was dismissed on May 27, 2009.{{cite web
| url=http://dockets.justia.com/docket/texas/txedce/2:2007cv00216/103383/
| title=Certicom Corporation et al v. Sony Corporation et al Featured Case Has Decisions
| date=2009-05-27
| publisher=justia.com
| accessdate=2013-08-12}} The stipulation states, "Whereas Certicom and Sony have entered into a settlement agreement according to which they have agreed to a dismissal without prejudice, these parties, therefore jointly move to dismiss all claims and counterclaims asserted in this suit, without prejudice to the right to pursue any such claims and counterclaims in the future."{{cite web
| url=https://docs.justia.com/cases/federal/district-courts/texas/txedce/2:2007cv00216/103383/112
| title=Certicom Corporation et al v. Sony Corporation et al, Filing: 112
| date=2009-05-27
| publisher=justia.com
| accessdate=2023-03-20}}
As for the prior art, Sony claimed:{{cite web
| url=https://docs.justia.com/cases/federal/district-courts/texas/txedce/2:2007cv00216/103383/52
| title=Certicom Corporation et al v. Sony Corporation et al, Filing: 52
| date=2008-07-14
| publisher=justia.com
| accessdate=2023-03-20}}
- 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
Modern curves
According to Daniel J. Bernstein, the Curve25519 and efficient implementations thereof can be free from patent encumbrance.{{cite web |last1=Bernstein |first1=D. J. |title=Irrelevant patents on elliptic-curve cryptography |url=https://cr.yp.to/ecdh/patents.html |website=cr.yp.to |access-date=22 October 2023}}
See also
References
{{Reflist}}
External links
- {{cite web
| url=http://www.rsa.com/rsalabs/node.asp?id=2325
| title=Crypto FAQ: 6.3.4 Are elliptic curve cryptosystems patented?
| publisher=RSA Security
| archiveurl=https://web.archive.org/web/20130524001754/http://www.rsa.com/rsalabs/node.asp?id=2325
| archivedate=2013-05-24
| url-status=dead
| accessdate=2013-08-12}}
- {{cite web
|url=http://www.nsa.gov/business/programs/elliptic_curve.shtml
|title=The Case for Elliptic Curve Cryptography
|date=2009-01-15
|publisher=National Security Agency
|accessdate=2013-08-12
|url-status=dead
|archiveurl=https://web.archive.org/web/20090117023500/http://www.nsa.gov/business/programs/elliptic_curve.shtml
|archivedate=2009-01-17
}}
- {{cite web
| url=http://news.cnet.com/Open-source-group-gets-Sun-security-gift/2100-1001_3-958679.html
| title=Open-source group gets Sun security gift
| date=2002-09-19
| first=Stephen
| last=Shankland
| publisher=CNET
| accessdate=2013-08-12}}
- {{cite web
| url=http://article.gmane.org/gmane.comp.encryption.general/7522
| title=ECC patents?
| first=Alexander
| last=Klimov
| date=2005-10-15
| work=cryptography at metzdowd.com
| accessdate=2013-08-12
| archive-url=https://web.archive.org/web/20160409105607/http://article.gmane.org/gmane.comp.encryption.general/7522
| archive-date=2016-04-09
| url-status=dead
}}
- {{cite web
| url=http://article.gmane.org/gmane.comp.encryption.general/7528
| title=ECC patents?
| first=Bodo
| last=Moeller
| date=2005-10-17
| work=cryptography@metzdowd.com
| accessdate=2013-08-12
| archive-url=https://web.archive.org/web/20160409105607/http://article.gmane.org/gmane.comp.encryption.general/7528
| archive-date=2016-04-09
| url-status=dead
}}
- {{cite web
| url=http://www.secg.org/collateral/certicom_secg_patent.pdf
| title=SECG Patent Policy of April 26, 1999: Patents held by Certicom
| date=1999-05-27
| publisher=SECG
| accessdate=2013-08-12}}
- {{cite web
| url=http://www.secg.org/download/aid-398/certicom_patent_letter_SECG.pdf
| title=SECG Patent Policy as of February 10, 2005: Patents held by Certicom
| date=2005-02-10
| publisher=SECG
| accessdate=2013-08-12}}
- Harper, Menezes and Vanstone, Public-Key Cryptosystems with Very Small Key Lengths, EUROCRYPT '92 (LNCS 658)
- {{cite web
| url=http://buzz.spinstop.com/certicom-v-sony-complaint.pdf
| title=Certicom v Sony complaint, 2:07-cv-216
| date=2007-05-31
| accessdate=2013-08-12}}
- {{cite journal
| url=http://libtom.org/pages/toorcon8_ecc_tstdenis.pdf
| title=Elliptic Curve Cryptography Redux
| first=Tom St.
| last=Denis
| journal=Toorcon 0x08
| date=2006
| pages=24–28
| access-date=2013-04-11
| archive-url=https://web.archive.org/web/20120201025637/http://libtom.org/pages/toorcon8_ecc_tstdenis.pdf
| archive-date=2012-02-01
| url-status=dead
}}