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