Re: Comments on ECC draft

[Bodo Moeller <[e-mail]>]

On Wed, Oct 03, 2001 at 01:24:36PM -0500, Jivsov, Andrey wrote:

>> From: [e-mail]

>>> 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 <[e-mail]>
PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html
* TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt
* Tel. [phone], Fax [phone]