On Wed, Oct 03, 2001 at 01:24:36PM -0500, Jivsov, Andrey wrote:
From: bmoeller(_at_)hrzpub(_dot_)tu-darmstadt(_dot_)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(_at_)cdc(_dot_)informatik(_dot_)tu-darmstadt(_dot_)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