### Re: Comments on ECC draft

Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de> Mon, 15 October 2001 19:07 UTC

Received: from above.proper.com (above.proper.com [208.184.76.39])
by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA09801
for <openpgp-archive@odin.ietf.org>; Mon, 15 Oct 2001 15:07:05 -0400 (EDT)

Received: from localhost (localhost [[UNIX: localhost]])
by above.proper.com (8.11.6/8.11.3) id f9FIuUg13940
for ietf-openpgp-bks; Mon, 15 Oct 2001 11:56:30 -0700 (PDT)

Received: from cdc-info.cdc.informatik.tu-darmstadt.de
(cdc-info.cdc.informatik.tu-darmstadt.de [130.83.23.100])
by above.proper.com (8.11.6/8.11.3) with ESMTP id f9FIuSD13936
for <ietf-openpgp@imc.org>; Mon, 15 Oct 2001 11:56:28 -0700 (PDT)

Received: from cdc-ws1 (cdc-ws1 [130.83.23.82])
by cdc-info.cdc.informatik.tu-darmstadt.de (Postfix) with SMTP id C089D2C8C
for <ietf-openpgp@imc.org>; Mon, 15 Oct 2001 20:56:29 +0200 (MET DST)

Date: Mon, 15 Oct 2001 16:02:32 +0200

From: Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>

To: "Jivsov, Andrey" <Andrey_Jivsov@NAI.com>

Cc: hal@finney.org, Dominikus.Scherkl@biodata.com, ietf-openpgp@imc.org

Subject: Re: Comments on ECC draft

Message-ID: <20011015160232.C7738b@cdc.informatik.tu-darmstadt.de>

References: <55E02B6F8FA8D311985300902740BB2004C5748C@SNC-5-88.nai.com>

Mime-Version: 1.0

Content-Type: text/plain; charset=iso-8859-1

Content-Disposition: inline

Content-Transfer-Encoding: 8bit

User-Agent: Mutt/1.2i

In-Reply-To: <55E02B6F8FA8D311985300902740BB2004C5748C@SNC-5-88.nai.com>;
from Andrey_Jivsov@NAI.com on Wed, Oct 03, 2001 at 01:24:36PM
-0500

Sender: owner-ietf-openpgp@mail.imc.org

Precedence: bulk

List-Archive: <http://www.imc.org/ietf-openpgp/mail-archive/>

List-Unsubscribe: <mailto:ietf-openpgp-request@imc.org?body=unsubscribe>

List-ID: <ietf-openpgp.imc.org>

Content-Transfer-Encoding: 8bit

On Wed, Oct 03, 2001 at 01:24:36PM -0500, Jivsov, Andrey wrote: >> From: bmoeller@hrzpub.tu-darmstadt.de >>> Our concern with the special primes 1-2 is that this area seems >>> to be covered by patents. >> What patents? These should be patents applied for by the NSA (the >> optimizations for pseudo-Mersenne primes are due to Jerry Solinas). >> I'm not sure how they'd handle licensing -- the patents for Jerry's >> algorithms for Koblitz curves have already been issued earlier this >> year, and presumably licensing would be similar to that, whatever this >> means. (Hopefully no restrictions, as for DSA, which is also >> patented.) >> >> (Note that the FIPS recommended curves over prime fields all are based >> on pseudo-Mersenne primes. Of course applications that want to use >> optimized modular arithmetic for these primes can do so, whether or >> not special field descriptors are used.) > US patents 5,159,632, 5,463,690 and 5,271,061 "Method and apparatus for > public key exchange in a cryptographic system" cover 2^m-C prime field with > NeXT as an assignee. [...] Thanks for the pointers. > The 1999 paper "Generalized Mersenne Numbers" by J. Solinas has > abovementioned patent 5,159,632 in a reference section. Solinas cites Knuth for efficient arithmetic modulo Mersenne numbers (m = 2^k - 1) and writes (in the introduction to his 1999 Technical Report "Generalized Mersenne Numbers") "It is [...] of interest to generalize the above technique to families of numbers containing primes. One such family is due to Richard Crandall [2], namely, the integers 2^k - c for c positive and small enough to fit into one word. In this paper, we generalize in a different direction. Although there is some overlap, many of the generalized Mersenne numbers presented here are not Crandall numbers." ([2] is Crandall's patent 5,159,632.) So while there are patent issues with efficient arithmetic for Crandall's pseudo Mersenne prime fields, it seems there is no known patent affecting Solinas' generalized Mersenne prime fields. > This paper describes > primes in the form 2^m+B_n+...+B_0 instead, where B_n+...+B_0=C is not small > (applicable to NIST curves). Therefore, group types 1 and 2 from the draft > can only be used to describe patented fields. ... where the types applicable to prime fields are defined as follows (in draft-scherkl-openpgp-ecc-00.txt): 0: Named curve (followed by curve_name) 1: Pseudo mersenne prime field F(p) (followed by r and c. p = 2^r - c, "below some twopower") 2: Pseudo mersenne prime field F(p) (followed by r and c. p = 2^r + c, "above some twopower") 3: Prime field F(p) (followed by p) Type 3 obviously covers any finite prime field, but does not indicate what optimizations may apply. Types 1 and 2 also cover any finite prime field because the definition does not impose limits on c; in the case of the Crandall patents you cited above, c would be very small (usually a single processor word), whereas in the case of NIST curves and similar curves, it would be quite long, but shorter than p. So not *all* curves using on type 1 or 2 fields would be covered by the Crandall patents. But maybe a field type more suitable for generalized Mersenne numbers should be defined. -- Bodo MÃ¶ller <moeller@cdc.informatik.tu-darmstadt.de>; PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html * TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt * Tel. +49-6151-16-6628, Fax +49-6151-16-6036

- Comments on ECC draft hal
- RE: Comments on ECC draft Dominikus Scherkl
- Re: Comments on ECC draft Bodo Moeller
- RE: Comments on ECC draft Jivsov, Andrey
- Re: Comments on ECC draft Bodo Moeller
- Re: Comments on ECC draft David Hopwood
- Re: Comments on ECC draft Len Sassaman
- Re: Comments on ECC draft David Shaw
- Re: Comments on ECC draft Peter Gutmann
- Re: Comments on ECC draft Bodo Moeller
- RE: Comments on ECC draft Dominikus Scherkl
- Re: Comments on ECC draft Dominikus Scherkl
- Why ECC? Rodney Thayer
- Re: Why ECC? Hironobu SUZUKI
- RE: Comments on ECC draft Dominikus Scherkl