ANSI X9.62

In 1998, the Accredited Standards Committee X9, an organization accredited by the American National Standards Institute (ANSI), developed a standard with the title Public Key Cryptography for Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA) [1] (approved in 1999). This standard defines methods for digital signature using the Elliptic Curve Digital Signature Algorithm (ECDSA). The standard doesn't define any specific elliptic curves (it only presents six curves for users to ensure the correctness of implementation), but it provides a method of generation of an elliptic curve and a base-point. This method has then been standardized and referenced by SECG, FIPS 186 and IEEE. Both prime fields and binary fields are considered.

The algorithm for generating curves, described by the standard as verifiably at random, works roughly as follows. From a given seed and prime $p$, the algorithm Algorithm 1 generates an integer $r$. According to the standard, one then should choose $a,b$ which define a Weierstrass form of an elliptic curve over $\mathbb{F}_p$ satisfying $rb^2=a^3\pmod p$ Algorithm 2. This process is repeated until the curve satisfies the security conditions mentioned below Algorithm 3. The seed should always be provided together with the curve in order to be verifiable. A base point is not generated Verifiably at Random in x962 as it is found by generating random points until the point has the correct order, see algorithms Algorithm 4 and Algorithm 5.

Security - 1998 version

• The order $n$ of the prime-subgroup should be at least $\min\{2^{160},4\sqrt{p}\}$. Furthermore, the cofactor should be $l$-smooth where $l$ is a small integer (as a guide $l=255$ is proposed). The standard denotes these two conditions as "near primarility" and provides an algorithm for testing this (see the algorithm Algorithm 6).
• The embedding degree shall be greater than 20. The standard also specifies how to check for this condition by simply checking all possible exponents $e\leq 20$ that $p^n\neq 1 \pmod n$.
• The trace can't be equal to 1.

Several steps remain unexplained. Firstly, Algorithm 1 is based on concatenating hashes of incremented values of seed. Together with the fact that no guidance on how to choose the seeds or how to update them (when curve not satisfying security conditions is found) is given, can lead to undesired behaviour as in the Brainpool standard which also adopts this algorithm (for generating both the curve and the base field with one slight change).

Secondly, the relation $rb^2=a^3\pmod p$ in Algorithm 2 is given no comments at all. However, there is a connection to discriminant and $j$-invariant of an elliptic curve: the $j$-invariant is defined as $$j(E) = 1728\frac{4a^3}{4a^3+27b^2}=1728\frac{4r}{4r+27}$$ and defines the isomorphism class of curve. Hence by choosing $r$, we define the isomorphism class. The order of the curve is not determined by this, since there is still the choice of a twist.

In 2005, a revised version of the standard had been published [2]. As opposed to the 1998 edition of this standard, this version recommends fifteen elliptic curves, five of which are verifiably random over a prime field (the rest are 5 Koblitz binary curves, and 5 are verifiably random binary curves). The five curves are the same as the SECG and FIPS 186 standard recommend: P-192, P-224, P-256, P-384, P-521 for five security level. The standard denotes these curves as ansix9pXXXr1 where XXX stands for the bit-length. Although these curves were not generated as part of this standard, they are consistent with the security condition and the method of generation. For more about these curves, see the SECG or FIPS standard. The proposed generation of curves changed in the 2005 version only in base point generation (it defines a verifiably random algorithm which is almost identical to the algorithm in version 2 of SEC 1.) and the security conditions:

Security - 2005 version

• Again similar "near primality" condition is present: the cofactor $h$ should be $l$-smooth where $l$ is a small integer (as a guide $l=255$ is proposed) but there is another condition that $h\leq 2^{s/8}$ where $s$ is the security level. The order $n$ of the prime-subgroup should satisfy $n\geq \max\{2^{2s-1},2^{160}\}$.
• The embedding degree shall be greater than 100.
• The trace can't be equal to 1.

In 2015, after 10 years, the standard ANSI X9.62 (2005) has been withdrawn [3] due to lack of revision within a time limit and was replaced by ANSI X9.142.