RE: Comments on ECC draft

"Jivsov, Andrey" <Andrey_Jivsov@NAI.com> Wed, 03 October 2001 18:45 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 OAA25694 for <openpgp-archive@lists.ietf.org>; Wed, 3 Oct 2001 14:45:14 -0400 (EDT)
Received: by above.proper.com (8.11.6/8.11.3) id f93IP4s18878 for ietf-openpgp-bks; Wed, 3 Oct 2001 11:25:04 -0700 (PDT)
Received: from nairelaymail.nai.com (relay2.nai.com [161.69.213.4]) by above.proper.com (8.11.6/8.11.3) with ESMTP id f93IP0D18874 for <ietf-openpgp@imc.org>; Wed, 3 Oct 2001 11:25:00 -0700 (PDT)
Received: from txwsout1.nai.com ([161.69.96.120]) by nairelaymail.nai.com with SMTP (Microsoft Exchange Internet Mail Service Version 5.5.2653.13) id TYFZCK13; Wed, 3 Oct 2001 13:23:07 -0500
Received: FROM tx-ex-bridge1.nai.com BY txwsout1.nai.com ; Wed Oct 03 13:25:20 2001 -0500
Received: by DAL-96-124.nai.com with Internet Mail Service (5.5.2653.19) id <TF4CCKCH>; Wed, 3 Oct 2001 13:24:46 -0500
Message-ID: <55E02B6F8FA8D311985300902740BB2004C5748C@SNC-5-88.nai.com>
From: "Jivsov, Andrey" <Andrey_Jivsov@NAI.com>
To: "'moeller@cdc.informatik.tu-darmstadt.de'" <moeller@cdc.informatik.tu-darmstadt.de>, hal@finney.org
Cc: Dominikus.Scherkl@biodata.com, ietf-openpgp@imc.org
Subject: RE: Comments on ECC draft
Date: Wed, 3 Oct 2001 13:24:36 -0500
MIME-Version: 1.0
X-Mailer: Internet Mail Service (5.5.2653.19)
Content-Type: text/plain; charset="iso-8859-1"
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>

> -----Original Message-----
> From: bmoeller@hrzpub.tu-darmstadt.de
> [mailto:bmoeller@hrzpub.tu-darmstadt.de]
> Sent: Monday, September 10, 2001 12:50 PM
> To: hal@finney.org
> Cc: Dominikus.Scherkl@biodata.com; ietf-openpgp@imc.org;
> andrey_jivsov@NAI.com; hal_finney@NAI.com
> Subject: Re: Comments on ECC draft
...
> > 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. While there are some patents with J. Solinas as an
inventor and NSA as an assignee covering Koblitz curves, there are no
similar patents for the 2^m-C.

The 1999 paper "Generalized Mersenne Numbers" by J. Solinas has
abovementioned patent 5,159,632 in a reference section. 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. 

In contrast with Mersenne prime fields, binary fields were around for a long
time, patent-free for software implementation, sufficiently fast for
software and superior for hardware implementations, allow Koblitz curve
optimizations and are the only current choice for IKE ECC DH groups.