SECG

Standards for Efficient Cryptography Group (SECG) SECG is a consortium of companies (including, for example, NIST, Visa, Motorola and Fujitsu) formed by Certicom in 1999 specifically for the development of standards for ECC cryptosystems implementations. It was the first organization devoted exclusively to developing ECC standards. The first two published standards were SEC 1 [1] and SEC 2 [3] in 2000. The SEC 1 standard describes elliptic curve domain parameters for eight levels of security $t\in \{56,64,80,96,112,128,192,256\}$ such that taking discrete logarithms should approximately take $2^t$ operations. The bit-length of the prime base field corresponds in the following way $$\lceil \log_2{p} \rceil = 2t \text{ if $t\neq 256$, otherwise } \lceil \log_2{p}\rceil =521.$$

The SEC 1 document doesn't provide a specific method (only general tips) for generating elliptic curves and refers the reader to X9.62 (1998 version). However, the companion document SEC 2 provides a list of elliptic curve domain parameters, which are divided into two categories: verifiably at random (as in X9.62) and Koblitz curves (these are curves over a prime field that possess an efficiently computable endomorphism [6]). The curves were named secpXXXrY, and secpXXXkY, where XXX stands for the bit-length and $r$ (resp. $k$) means verifiably at random (resp. Koblitz curves).

All of the curves are defined over base-field primes of special form for more efficient arithmetic, i.e., generalized Mersenne primes. The security conditions for the elliptic curves are specified as follows:

Security (2000)

• Cofactor is at most 4
• Trace is not equal to 1
• Embedding degree is at least 20

The Koblitz curve parameters are claimed to have been chosen by repeatedly selecting parameters admitting an efficiently computable endomorphism until a prime order curve was found. The verifiably random curves were chosen according to the X9.62 standard using a specified seed. These curves were then standardized in FIPS 186, X9.62 (2005), and others. The choice of the seed was not explained but looking at the seeds of secp112r1, secp112r2, secp128r1, secp128r2, secp160r1, secp160r2 we can spot a common segment:

The segment has a meaning, and encoded in ASCII it stands for "MinghuaQu" which is the name of one of the inventors of MQV protocol who apparently [7] is the author of these seeds. Further discussion about the topic can be found here.

In 2009 the SEC 1 standard was updated [2] with three changes that are relevant to the standardization of elliptic curves. Firstly, the recommended levels of security were reduced to just six levels, $t\in \{80, 96,112,128,192,256\}$ and the security/bit-length correspondence was updated with $\lceil \log_2{p} \rceil = 192$ if $t=80$. Secondly, security conditions were changed to:

Security (2009)

• Cofactor is at most $2^{t/8}$
• Trace is not equal to 1
• Embedding degree is at least 100
• If $n$ is the prime-subgroup order then $n-1$ and $n+1$ should each have a large prime factor $r$ which is large in a sense that $\log_n(r)>19/20$.

The choices were not explained enough, especially the last condition (one explanation might be the attacks described in [5]). The third change to the original document was a recommendation to the base-point selection with Algorithm 1.

The SEC 2 document was updated [3] in 2010 by removing curves with small bit-length according to SEC 1. However, since no further changes were made, none of the curves satisfy the last security condition and the base-point selection algorithm. All the standards are available on the temporary SECG website. The previous official website was shut down for repairs in July 2014.