RE: Comments on ECC draft

["Jivsov, Andrey" <[e-mail]>]

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