Re: ECC patents?
On Sun, 11 Sep 2005, Alexander Klimov wrote:
Does anyone know a good survey about ECC patent situation?
I have made a shallow review (comments are welcome!) of the
patents that Certicom claims are pertained to ECC implementation
and it looks like there are no real road-blocks for ECDH and
ECDSA among them. In other words, IIUC it is possible to
implement EC encryption and signing without violating any patent
(of course, the implementer must be lucky enough to avoid any
patented optimization).
BTW, it looks like OpenSSL developers share this POV: README [1]
on branch OpenSSL_0_9_8-stable which implements ECDH and ECDSA
has PATENTS section which does not say a word about ECC.
In order to make this review I located two documents [2,3] in
which Certicom lists its patents related to ECC. It is
impossible to say that nobody else has patents in this area, but
the fact that the web site of SECG [4] (which is the first
working group anywhere that is devoted exclusively to developing
standards based on ECC) does not have claims by anybody else
can be viewed as a hint of this.
Let us now review these lists. The first of them [2] contains
the following patents:
[As of May 26, 1999] Certicom is the owner of the following
issued patents:
US 4,745,568 Computational method and apparatus for finite
field multiplication, issued May 17, 1988. This patent
includes methods for efficient implementation of finite field
arithmetic using a normal basis representation.
[Optimization of multiplication in GF_{2^n}]
US 5,787,028: Multiple Bit Multiplier, issued July 28, 1998.
[Multiplication in GF_{2^{nm}}, IIUC it is of no use now due to
Weil descent attack for EC(GF_{2^k}) with composite k.]
US 5,761,305 Key Agreement and Transport Protocol with
Implicit Signatures, issued June 2, 1998. This patent includes
versions of the MQV protocols.
US 5,889,865 Key Agreement and Transport Protocol with
Implicit Signatures, issued March 30, 1999. This patent
includes versions of the MQV protocols.
US 5,896,455 Key Agreement and Transport Protocol with
Implicit Signatures, issued April 20, 1999. This patent
includes versions of the MQV protocols.
[These three are about MQV protocol and so are unrelated to ECDH
and ECDSA.]
Certicom has the exclusive North American license rights to
the following issued patent:
US 5,600,725 Digital signature method and key agreement
method, issued Feb. 4, 1997. This patent includes the
Nyberg-Rueppel (NR) signature method.
[Described as pertains to PV signatures below.]
Certicom has patent applications that include the following:
* Methods for efficient implementation of elliptic curve
includes efficient methods for computing inverses.
* Methods for point compression.
* Methods to improve performance of private key operations.
* Various versions of the MQV key agreement protocols.
* Methods to avoid the small subgroup attack.
* Methods to improve performance of elliptic curve
arithmetic; in particular, fast efficient multiplication
techniques.
* Methods to improve performance of finite field
multiplication.
* Methods for efficient implementation of arithmetic modulo n.
* Methods to perform validation of elliptic curve public keys.
* Methods to perform efficient basis conversion.
The second [3] of the lists contains the following:
[As of February 10, 2005] Certicom is the owner of the
following issued patents:
EP 0 739 105 B1 (validated in DE, FR, and the UK) Method for
signature and session key generation pertains to the MQV
protocol
[Anybody knows, where it is available online?]
US 5,761,305 Key Agreement and Transport Protocols with
Implicit Signatures pertains to the MQV protocol
US 5,889,865 Key Agreement and Transport Protocol with
Implicit Signatures pertains to the MQV protocol
US 5,896,455 Key Agreement and Transport Protocol with
Implicit Signatures pertains to the MQV protocol
US 6,122,736 Key agreement and transport protocol with
implicit signatures pertains to the MQV protocol
US 6,785,813 Key agreement and transport protocol with
implicit signatures pertains to the MQV protocol
[Menezes-Qu-Vanstone (MQV) protocol -- an authenticated protocol
for key agreement based on the Diffie-Hellman scheme.]
US 5,600,725 Digital Signature Method and Key Agreement
Method pertains to PV signatures
[Pintsov-Vanstone (PV) signatures -- a scheme with partial
message recovery.]
US 5,933,504 Strengthened public key protocol pertains to
preventing the small-subgroup attack
[This one contains the following claims:
1. A method of determining the integrity of a message
exchanged between a pair of correspondents, said message
being secured by embodying said message in a function of
.alpha..sup.x where .alpha. is an element of a finite
group S of order q, said method comprising the steps of
at least one of the
Re: ECC patents?
On Wed, Sep 14, 2005 at 12:18:14PM +0300, Alexander Klimov wrote: http://www1.ietf.org/proceedings_new/04nov/slides/saag-2/sld9.htm: What is Really Covered o The use of elliptic curves defined over GF(p) where p is a prime number greater than 2^255 when the product satisfies the Field of Use conditions o Both compressed and uncompressed point implementations o Use of elliptic curve MQV and ECDSA under the above conditions This hints that indeed only some particular curves are patented. Not quite. I understand the agreement is about using MQV and other patented stuff, but limited to certain curves. This alone does not necessary imply that the *patent* situation is different for prime fields and binary fields, or for different field sizes -- it just means that the *license* to the relevant patents has been restricted accordingly. Scott Vanstone reports that Certicom would have charged more for including binary curves as well and this is why they were left out (for now). The OpenSSL team, cowards that they are, omitted MQV and other stuff that would infringe on patents. MQV is a useful protocol, but clearly covered by patents. OpenSSL does support both prime curves and (more recently thanks to the Sun contribution) binary curves, but without point compression for binary curves since this would be another patent issue. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: ECC patents?
-- Whyte, William [EMAIL PROTECTED] $25MM figure: http://lists.jammed.com/ISN/2003/10/0097.html I stand corrected. However as was pointed out previously: : : Further, the license would be limited to only : : prime field curves where the prime was : : greater than 2255. On the NIST list of curves : : 3 out of the 15 fit this field of use: the : : prime field curves with primes of 256 bits, : : 384 bits and 521 bits. Of the NIST list of fifteen, nine are 256 bits or longer. Presumably, if NSA thought certicom had a case, they would have licensed at least the other six NIST curves as well, and most likely the other twelve. The three curves that are licensed look different from the other twelve, though I have no idea of the significance of this, if any. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG ZKrN4sA2qyTNIC90h3U/8Er848IPFGfUOQyBxm8h 4xlZJBIqZwgUkOyqgxTzTBcauENSjU46x6oDgn2X4 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: ECC patents?
I'm not sure what you're trying to demonstrate here. From the fact that NSA chose to license a few curves, we can definitely deduce that they want to use those curves. You deduce from the fact that they didn't license other curves that there is no patent on those curves, but you could equally well deduce that the curves they did license are good enough and they don't need to pay extra money to license on the other curves. William -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of James A. Donald Sent: Friday, September 16, 2005 11:53 PM To: cryptography@metzdowd.com Subject: RE: ECC patents? -- Whyte, William [EMAIL PROTECTED] $25MM figure: http://lists.jammed.com/ISN/2003/10/0097.html I stand corrected. However as was pointed out previously: : : Further, the license would be limited to only : : prime field curves where the prime was : : greater than 2255. On the NIST list of curves : : 3 out of the 15 fit this field of use: the : : prime field curves with primes of 256 bits, : : 384 bits and 521 bits. Of the NIST list of fifteen, nine are 256 bits or longer. Presumably, if NSA thought certicom had a case, they would have licensed at least the other six NIST curves as well, and most likely the other twelve. The three curves that are licensed look different from the other twelve, though I have no idea of the significance of this, if any. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG ZKrN4sA2qyTNIC90h3U/8Er848IPFGfUOQyBxm8h 4xlZJBIqZwgUkOyqgxTzTBcauENSjU46x6oDgn2X4 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: ECC patents?
http://www1.ietf.org/proceedings_new/04nov/slides/saag-2/sld9.htm: What is Really Covered o The use of elliptic curves defined over GF(p) where p is a prime number greater than 2^255 when the product satisfies the Field of Use conditions o Both compressed and uncompressed point implementations o Use of elliptic curve MQV and ECDSA under the above conditions This hints that indeed only some particular curves are patented. It hints that only some particular curves have been licensed. It could be that NSA has decided not to buy a license for the other curves, or it could be that operations on those curves aren't patented. The presentation doesn't give enough information to establish which. William - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: ECC patents?
James A. Donald wrote: -- Whyte, William: It hints that only some particular curves have been licensed. It could be that NSA has decided not to buy a license for the other curves, or it could be that operations on those curves aren't patented. The presentation doesn't give enough information to establish which. If the NSA paid anything significant for any of the curves, we would be told. Therefore the NSA paid nothing or almost nothing, and therefore if the NSA licensed anything, it would have licensed everything. I doubt that the NSA paid any money whatsoever for this license, making it profoundly unimpressive as evidence that *any* curves have a plausible valid patent. If the NSA paid real money, the patent holders would be sticking it in our face as a price setting precedent. I had a recent discussion with a person in a government agency that indicated we would not be able to use them as a reference and that they would probably want an unlimited license - because there could be no reference to a number of users within the agency. They did say that they would get GSA pricing. I suspect that Certicom got GSA pricing for the deal as is, I assume, required by law. Nick -- Nick Owen WiKID Systems, Inc. 404.962.8983 (desk) 404.542.9453 (cell) http://www.wikidsystems.com https://sourceforge.net/projects/wikid-twofactor/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: ECC patents?
In message [EMAIL PROTECTED], James A. Donald writes: -- Whyte, William: It hints that only some particular curves have been licensed. It could be that NSA has decided not to buy a license for the other curves, or it could be that operations on those curves aren't patented. The presentation doesn't give enough information to establish which. If the NSA paid anything significant for any of the curves, we would be told. Therefore the NSA paid nothing or almost nothing, and therefore if the NSA licensed anything, it would have licensed everything. I doubt that the NSA paid any money whatsoever for this license, making it profoundly unimpressive as evidence that *any* curves have a plausible valid patent. If the NSA paid real money, the patent holders would be sticking it in our face as a price setting precedent. We have been told. I downloaded Certicom's 2005 annual report (http://www.certicom.com/download/aid-503/Certicom2005AR.pdf). On p. 11, it says For the year ended April 30, 2004, revenue from IP totalled $25-million represented by a licensing contract for our Elliptic Curve Cryptography (ECC) technology by the NSA, --Steven M. Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: ECC patents?
If the NSA paid anything significant for any of the curves, we would be told. You were better off not responding; you have lost your credibility on this topic. Given the NSA's history of secrecy; and the fact that it's common practice to not disclose (financial) terms (e.g., what were the terms to get RSA into early SSL?) and that either/both parties have incentive to keep it private; and the way they handled the SHA-1-Schnorr patent issues, I find it *highly significant* that the NSA announced, in a public forum, that they have a license for part of the Certicom patents. I am sure that I'm not alone. /r$ -- Rich Salz, Chief Security Architect DataPower Technology http://www.datapower.com XS40 XML Security Gateway http://www.datapower.com/products/xs40.html - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: ECC patents?
At 09:54 2005-09-15 -0700, James A. Donald wrote: I doubt that the NSA paid any money whatsoever for this license, making it profoundly unimpressive as evidence that *any* curves have a plausible valid patent. If the NSA paid real money, the patent holders would be sticking it in our face as a price setting precedent. They (NSA) did pay, and they (Certicom) did stick it in our faces. See, eg., http://www.eweek.com/article2/0,1895,1498136,00.asp . Did you miss this at the time? Greg. Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Incorporated VOICE: +1-858-651-5733 FAX: +1-858-651-5766 5775 Morehouse Drivehttp://people.qualcomm.com/ggr/ San Diego, CA 92121 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: ECC patents?
They paid $25MM. William -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of James A. Donald Sent: Thursday, September 15, 2005 12:54 PM To: cryptography@metzdowd.com Subject: RE: ECC patents? -- Whyte, William: It hints that only some particular curves have been licensed. It could be that NSA has decided not to buy a license for the other curves, or it could be that operations on those curves aren't patented. The presentation doesn't give enough information to establish which. If the NSA paid anything significant for any of the curves, we would be told. Therefore the NSA paid nothing or almost nothing, and therefore if the NSA licensed anything, it would have licensed everything. I doubt that the NSA paid any money whatsoever for this license, making it profoundly unimpressive as evidence that *any* curves have a plausible valid patent. If the NSA paid real money, the patent holders would be sticking it in our face as a price setting precedent. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG uFGgCOtWvwFnmCL5tYGLSloqyccg5nCjgOZZ2xdW 4NjnEzQaXNpdg5TTfRnBvcrjTbnHJ6AGsfz5BcvsG - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: ECC patents?
$25MM figure: http://lists.jammed.com/ISN/2003/10/0097.html More details about what's covered: http://www.nsa.gov/ia/industry/crypto_elliptic_curve.cfm http://www.nsa.gov/ia/industry/crypto_suite_b.cfm William -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of James A. Donald Sent: Thursday, September 15, 2005 12:54 PM To: cryptography@metzdowd.com Subject: RE: ECC patents? -- Whyte, William: It hints that only some particular curves have been licensed. It could be that NSA has decided not to buy a license for the other curves, or it could be that operations on those curves aren't patented. The presentation doesn't give enough information to establish which. If the NSA paid anything significant for any of the curves, we would be told. Therefore the NSA paid nothing or almost nothing, and therefore if the NSA licensed anything, it would have licensed everything. I doubt that the NSA paid any money whatsoever for this license, making it profoundly unimpressive as evidence that *any* curves have a plausible valid patent. If the NSA paid real money, the patent holders would be sticking it in our face as a price setting precedent. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG uFGgCOtWvwFnmCL5tYGLSloqyccg5nCjgOZZ2xdW 4NjnEzQaXNpdg5TTfRnBvcrjTbnHJ6AGsfz5BcvsG - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: ECC patents?
On Tue, 13 Sep 2005, Paul Hoffman wrote: At 9:32 AM -0700 9/12/05, James A. Donald wrote: It has been a long time, and no one has paid out money on an ECC patent yet. That's pretty bold statement that folks at Certicom might disagree with, even before http://www1.ietf.org/proceedings_new/04nov/slides/saag-2/sld1.htm. http://www1.ietf.org/proceedings_new/04nov/slides/saag-2/sld9.htm: What is Really Covered o The use of elliptic curves defined over GF(p) where p is a prime number greater than 2^255 when the product satisfies the Field of Use conditions o Both compressed and uncompressed point implementations o Use of elliptic curve MQV and ECDSA under the above conditions This hints that indeed only some particular curves are patented. Grepping -list_curves of the new openssl (0.9.8) which has a list of curves from SECG, WTLS, NIST, and X9.62 gives not that much: secp256k1 : SECG curve over a 256 bit prime field secp384r1 : NIST/SECG curve over a 384 bit prime field secp521r1 : NIST/SECG curve over a 521 bit prime field prime256v1: X9.62/SECG curve over a 256 bit prime field Alternatively, this coverage can be interpreted that NSA is not interested in curves which provide less security than 128-bit AES. Any idea, which alternative is true? -- Regards, ASK - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: ECC patents?
At 12:18 PM +0300 9/14/05, Alexander Klimov wrote: This hints that indeed only some particular curves are patented. It's not just curves. Certicom has patents for some optimizations and methods for validating the strength of some uses of ECC. Grepping -list_curves of the new openssl (0.9.8) which has a list of curves from SECG, WTLS, NIST, and X9.62 gives not that much: secp256k1 : SECG curve over a 256 bit prime field secp384r1 : NIST/SECG curve over a 384 bit prime field secp521r1 : NIST/SECG curve over a 521 bit prime field prime256v1: X9.62/SECG curve over a 256 bit prime field Alternatively, this coverage can be interpreted that NSA is not interested in curves which provide less security than 128-bit AES. Any idea, which alternative is true? Both are probably true. Why would anybody be interested in curves that do not support their minimum strength ciphers? --Paul Hoffman, Director --VPN Consortium - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: ECC patents?
On Mon, 12 Sep 2005 11:58:14 +0300 (IDT), Alexander Klimov said: There is also work on ECC for gnupg http://www.g10code.de/tasklist.html#gcrypt-ecc Yes, there exists an implementation for an ECC implementation for GnuPG. The problem is that OpenPGP does not define ECC and thus it does not make much sense to have it there. We have not worked on the Libgcrypt integration of that code because there is not much need for ECC in general. The costs advantage of ECC smartcards is shrinking more and more and thus why should we bother to implement the host part of ECC just for fun and try convincing the OpenPGP WG to add ECC. Salam-Shalom, Werner - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: ECC patents?
In message [EMAIL PROTECTED], Ben Laurie writes: Alexander Klimov wrote: But (potential) problem still persists: even if openssl implements ECC it does not save you from patent issues if they exist. It does if they are owned by Sun. It does if *all necessary patent rights* are owned (or licensed) by Sun. For obvious reasons, it's remarkably hard to get someone to say that they don't have a claim on some product. --Steven M. Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: ECC patents?
-- Alexander Klimov But (potential) problem still persists: even if openssl implements ECC it does not save you from patent issues if they exist. Anyone can claim to have patented anything. Someone recently patented the wheel, to show how bad the situation is. I think these guys are just blowing smoke. It has been a long time, and no one has paid out money on an ECC patent yet. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG T2A5LZ0emoxvUB9mpzAbsQaP6ZNjQpWobkfHEPls 4o11NuYw0FpVl962xoPzHTvBwM2AkgESWNKRblf9u - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: ECC patents?
On Sep 12, 2005, at 11:32, James A. Donald wrote: Someone recently patented the wheel, to show how bad the situation is. That's a bit misleading without the context. Google patented-the- wheel for details. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: ECC patents?
At 9:32 AM -0700 9/12/05, James A. Donald wrote: It has been a long time, and no one has paid out money on an ECC patent yet. That's pretty bold statement that folks at Certicom might disagree with, even before http://www1.ietf.org/proceedings_new/04nov/slides/saag-2/sld1.htm. --Paul Hoffman, Director --VPN Consortium - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: ECC patents?
Anyone can claim to have patented anything. Someone recently patented the wheel, to show how bad the situation is. I agree the system doesn't work well. I think these guys are just blowing smoke. It has been a long time, and no one has paid out money on an ECC patent yet. NSA licensed ECC patents from Certicom - that probably says something. http://www.certicom.com/index.php?action=company,press_archiveview=292 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: ECC patents?
On Sun, 11 Sep 2005, Ben Laurie wrote: Alexander Klimov wrote: ECC is known since 1985 but seems to be absent in popular free software packages, e.g., neither gnupg nor openssl has it (even if the relevant patches were created). It looks like the main reason is some patent uncertainty in this area. I don't, but it is not the case that OpenSSL does not include ECC. You are absolutely right the Sun patch was finally accepted, although there were some patent-related discussions, e.g., at http://lists.debian.org/debian-legal/2002/10/msg00100.html There is also work on ECC for gnupg http://www.g10code.de/tasklist.html#gcrypt-ecc and again there were patent-related discussions about the issue. ECC is also implemented in crypto++ and other libraries. But (potential) problem still persists: even if openssl implements ECC it does not save you from patent issues if they exist. -- Regards, ASK - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: ECC patents?
Alexander Klimov wrote: On Sun, 11 Sep 2005, Ben Laurie wrote: Alexander Klimov wrote: ECC is known since 1985 but seems to be absent in popular free software packages, e.g., neither gnupg nor openssl has it (even if the relevant patches were created). It looks like the main reason is some patent uncertainty in this area. I don't, but it is not the case that OpenSSL does not include ECC. You are absolutely right the Sun patch was finally accepted, although there were some patent-related discussions, e.g., at http://lists.debian.org/debian-legal/2002/10/msg00100.html If debian wants OpenSSL to do something, then it needs to tell OpenSSL. We aren't telepaths. There is also work on ECC for gnupg http://www.g10code.de/tasklist.html#gcrypt-ecc and again there were patent-related discussions about the issue. ECC is also implemented in crypto++ and other libraries. But (potential) problem still persists: even if openssl implements ECC it does not save you from patent issues if they exist. It does if they are owned by Sun. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
