Subject: RE: Comments on ECC draft

From: "Jivsov, Andrey" <[email-masked]>
Date: Wed, 3 Oct 2001 13:24:36 -0500

> -----Original Message-----
> From: [email-masked]
> [mailto:[email-masked]]
> Sent: Monday, September 10, 2001 12:50 PM
> To: [email-masked]
> Cc: [email-masked]; [email-masked];
> [email-masked]; [email-masked]
> 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.

---

From: Bodo Moeller <[email-masked]>
Date: Mon, 15 Oct 2001 16:02:32 +0200

> NeXT as an assignee. [...]

Thanks for the pointers.

> 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

... 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 <[email-masked]>
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

---

From: David Hopwood <[email-masked]>
Date: Mon, 15 Oct 2001 03:29:57 +0100

-----BEGIN PGP SIGNED MESSAGE-----

"Jivsov, Andrey" wrote:
> [email-masked] wrote:

<http://cr.yp.to/patents/us/5159632.html> says that there is prior art
for all the interesting claims of this patent, in a CRYPTO '89 article
published more than one year before the patent was filed.
5,271,061 and 5,463,690 are continuations of 5,159,632.

- -- 
David Hopwood <[email-masked]>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5  0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip