An Introduction to Elliptic Curve Cryptography - Introduction to Cryptography with Maple - page 659

a curve with this order and there is also the possibility of choosing the curve from
some special family for which the order is easily computable. The preferred method,
however, is to generate the curve at random and then to count the number of points
using the SEA algorithm and to repeat this process until a curve is found for which
this number is 'nearly prime', i.e., the product of a prime by a small cofactor. Since the
probability that a random curve is vulnerable to one of the known reduction attacks
is negligible, these attacks are also prevented, although the curve can additionally
be checked to ensure that this is indeed the case. Moreover, generating the curve at
random also offers a probabilistic protection against future special purpose attacks
and hence is the most conservative choice from a security point of view.
A variation on the random method of generating elliptic curves is to select them
in such a way that the parameters are verifiable , which is accomplished by choosing
the coefficients of the curve from the outputs of a one-way function—SHA-1 is
often used in practice for this purpose—by means of some specified algorithm. This
guarantees that these parameters cannot be predetermined, which is verifiable with
the help of the input seed of the function used and provides evidence that the elliptic
curve was not intentionally constructed with some hidden weaknesses that could
subsequently be used to break the cryptographic schemes. Algorithms to generate
and to validate these parameters are given in [97, 173].

11.4.2 The Elliptic Curve Digital Signature
Algorithm (ECDSA)

ECDSA is the elliptic curve variant of DSA (see 9.4.1 ) and is perhaps the most-used
EC scheme, having been included in several standards. We next give a description
of this scheme.

11.4.2.1 Definition of ECDSA

We will assume that EC domain parameters ( p , a , b , G , n , h ) , corresponding to an

elliptic curve E over a prime field F p , are given. In ECC the domain parameters are

often selected from the choices available in standards like [75] or [174]. This has
the advantage that, besides making interoperability easier, it provides parameters
that meet the security requirements established by the designers of the standard.
In addition, this frees the user from having to implement the domain parameter
generation algorithm which may include point-counting algorithms and hence be
relatively costly. For simplicity, wewill denote the x -coordinate of a point P

∈ E ( F p )

by x .

In addition to the EC domain parameters, ECDSA also uses, like DSA, a hash
function H such as one of the NIST-approved functions specified in [74], namely,
either SHA-1 or one of the SHA-2 variants, SHA-224, SHA-256, SHA-384 or SHA-

( P )