Re: Comments on ECC draft

[[e-mail] (Bodo Moeller)]

[e-mail]>:

[...]
> We suggest the initial draft use only prime fields, descriptor 3,
> and trinomial/pentanomial binary fields, descriptors 11 and 12. These
> three are enough to cover all the NIST curves.  They seem to provide
> the advantages which we seek from ECC without multiplying the options
> excessively.
> 
> If the group does want to pursue additional field types, we would like
> to see some rationale for the use of prime extension field types 4-9. Our
> concern with the special primes 1-2 is that this area seems to be covered
> by patents.

[Field decriptors 1 and 2 are for pseudo-Mersenne prime fields.]

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.)


>              And descriptors 14-16 are for normal bases, where we see
> two problems.  First, they cannot be efficiently implemented in software;
> and second, we do not think it is possible to convert from a normal basis
> into a polynomial basis representation without additional information
> regarding the specific normal basis chosen.  Hence using normal bases
> as an interchange format is not a good choice.  So we would like to see
> more discussion of that aspect if the group wishes to pursue it.

Also, this is an area where patents really appear to be a severe issue.


> (One organizational point: section 4.4 actually describes custom curves,
> and we would prefer to see the draft focus on predefined curves.  We have
> ideas on how to reorganize the draft to define specific coordinate
> fields and curves based on them, which we are getting into shape to
> present shortly.)

The draft obviously intends to provide a lot of flexibility, while in
the sake of efficiency and interoperability it would be better to
sacrifice flexibility and limit the class of allowed curves.