RE: Elliptic Curves

[John Marchioni <johnmarc@xxxxxxxxxx>]

Here are Cylink's comments per Lily Chen.  Other than its narrow view on 
curve selection methods we find X9.62 acceptable.

- John 

ANSI X9.62 seems not to have been written in the same spirit of
flexibility as other ANSI X9 standards. For example, X9.42 and 
X9.52 both allow for several variants of Diffie-Hellman and Triple 
DES respectively.

Thinking about what should be considered for inclusion of ANSI X9.62
(in the EC DSA area) in the PKIX RFC, the first is to add other curve 
selecting methods. 

Currently, ANSI X9.62 specifies the way to select curves "randomly".
This can be done by using a random SEED as an input of hash function 
H such that one of the parameters b = H(SEED). If an "a" can be 
found such that the curve defined by (a, b) has a "nearly prime" order, 
then it will be used in EC DSA. The curve can be verified to be 
generated randomly, given SEED and hash function H. 

However, there is no reasonable execuse for excluding two other
methods which have been used by people:

1. Weil Theorem: It starts by choosing a curve over GF(2^k) where k is
small, i.e. both "a" and "b" are in GF(2^k). Then by considering this curve
is a curve over a larger field GF(2^{k*n}), the order of the curve can be 
calculated by Weil Theorem. If the order is "nearly prime", take it. 
Otherwise, start to get another.

2. Complex Multiplication (CM) method: it starts by choosing the order 
of the curve. Then construct a curve with the order. 

Both of the above methods are effective and efficient.  A paper 
authored by Jerry Solinas will be presented at Crypto'97, Santa 
Barbara, August. In this paper, the curves are selected with CM 
structure. 

There are many efficient implementations of EC cryptographic 
algorithm  with curves selected by either Weil Theorem  and 
CM method. 

Furthermore, IEEE standard draft P1363 mentioned three 
approaches in selecting curves: (1) random;(2) Weil Theorem; 
and (3) CM.

If Weil Theorem is included, the field operations over GF(2^m)
by coefficients over GF(2^k) where m = n * k should be added
However, the current ANSI X9.62 doesn't exclude this situation 
since the operation of GF(2^m) is not specified. This should be 
a field representation problem-so we conclude it is up to 
implementor, however, such an example in X9.62 and PKIX 
would be useful.. 

The representation should be generalized as GF(q^n), where q = p,
a prime, or q =2^k. 

This is what I can see about this problem.

Lily


-----Original Message-----
From:	Housley, Russ [SMTP:housley@spyrus.com]
Sent:	Monday, June 16, 1997 6:20 AM
To:	ietf-pkix@tandem.com
Subject:	Elliptic Curves


Since we began work on PKIX part 1, Elliptic Curve thecnology has become 
more and more mature.  In fact, ANSI X9.62 looks pretty close to final.  
How do people feel about ading the ECDSA algorithm to the list of signature 
algorithms in part 1?

Russ