Recommended Elliptic Curves by Standards

Standards for recommended domain parameters

To facilitate the safe use of ECCs, there exist various standards that offer recommended domain parameters to guarantee elliptic curves that are cryptographically safe, but still very efficient. Well-known standardizations are proposed by the National Institute of Standards and Technology (NIST), the Standards for Efficient Cryptography Group (SECG), and the ECC-Brainpool. These standards propose elliptic curves that provide different levels of security (cf. this table :Table_3_1 ). However, all standards follow the security requirements that we introduced in this section :Requirements_on_Cryptographically .

National institute of standards and technology (NIST)

FIPS 186-2National Institute of Standards and Technology. FIPS PUB 186-2: Digital Signature Standard (DSS). pub-NIST, pub-NIST:adr, jan 2000. and NISTNIST. Recommended elliptic curves for federal government use. Technical report, 1999. recommend fifteen elliptic curves of three different types (random curves over prime fields $\mathbb{F}_{p}$, random curves over binary fields $\mathbb{F}_{p^{m}}$, and Koblitz curves over binary fields $\mathbb{F}_{p^{m}}$ ), whereas each type contains curves of five different security levels. The curves are designed by the NSA for U.S. federal government use.

The five prime fields $\mathbb{F}_{p}$ recommended by NIST in the FIPS 186-2 standard have a very special form since they’re based on the family of generalized Mersenne numbers (or pseudo-Mersenne primes), which were proposed by Solinas (1999)Jerome A. Solinas. Generalized Mersenne Numbers. Research report (University of Waterloo. Faculty of Mathematics). Faculty of Mathematics, University of Waterloo, 1999. Available at http://cacr.uwaterloo.ca/techreports/1999/corr99-39.ps.. These numbers are represented in the form $p=2^{m}-\omega$, where $\omega$ is the sum of some powers of two, whereas $\omega \ll 2^{m}$. This family of primes allows the implementation of fast modular reduction algorithms and hence are widely in use. NIST proposes the following five generalized Mersenne primes:

$$\begin{aligned} &p_{192}=2^{192}-2^{64}-1, \\ &p_{224}=2^{224}-2^{96}+1, \\ &p_{256}=2^{256}-2^{224}+2^{192}+2^{96}-1, \\ &p_{384}=2^{384}-2^{128}-2^{96}+2^{32}-1, \\ &p_{521}=2^{521}-1. \end{aligned}$$

In order to allow very efficient modular reduction, the primes for $\mathbb{F}_{p}$ were chosen to be represented in polynomial form with base $2^{w}$, where $w$ is the word size of the underlying 32 -bit architecture of the implementation platform, i.e., $w$ is a multiple of 32.

All proposed curves over $\mathbb{F}_{p}$ have cofactor $h=1$ and are represented in short Weierstrass form with fixed constant $A=-3$, i.e., for each prime $p$, the NIST-curves are defined by

$$E: y^{2}=x^{3}-3 x+B \quad mod \space p .$$

This choice of the parameter $A$ leads to a faster point multiplication, as shown by Brier and Joye (2003)Eric Brier and Marc Joye. Fast point multiplication on elliptic curves through isogenies. In Marc Fossorier, Tom Høholdt, and Alain Poli, editors, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, pages 43-50, Berlin, Heidelberg, 2003. Springer. and Renens et al. (2016)Joost Renes, Craig Costello, and Lejla Batina. Complete addition formulas for prime order elliptic curves. In Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I, pages 403-28, 2016..

Standards for efficient cryptography group (SECG)

The SECG is an international consortium formed by CerticomCerticom Research. Standards for efficient cryptography, SEC 2: Recommended elliptic curve domain parameters, January 2010. Version 2.0.. The recommended elliptic curve parameters are listed in SECG 2. SECG offers elliptic curves over prime fields $\mathbb{F}_{p}$ and over binary fields $\mathbb{F}_{p^{m}}$ as well. For the labeling of curves, SFCG denotes Koblitz. curves by $k$ and verifiably random generated curves by $r$. All curves over prime fields $\mathbb{F}_{p}$ use special form primes, i.e., generalized Mersenne numbers in order to allow efficient implementations and have cofactor $h=1$.

For each security level, SECG provides two different types of curves over the prime fields $\mathbb{F}_{p}$, namely a generalized version of Koblitz curves and curves whose parameters were selected in a verifiably random way. The special class of generalized Koblitz curves possesses an efficiently computable endomorphism (cf. definition :Group_endomorphism ) as described by Gallant et al. (2001)Robert P. Gallant, Robert J. Lambert, and Scott A. Vanstone. Faster point multiplication on elliptic curves with efficient endomorphisms. In Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, CRYPTO '01, pages 190-200, London, UK, 2001. Springer-Verlag., which yields a speed-up of up to $50 \%$. The Certicom SEC 2 standard includes the Koblitz curve secp256k1, the curve that’s used in the Bitcoin protocol.

ECC-Brainpool

Unlike NIST and SECG, ECC-BrainpoolJohannes Merkle and Manfred Lochter. Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and Curve Generation. RFC 5639, March 2010. uses pseudo-random primes $p$. Thus, $p$ must not be of any special form but shall fulfill $p \equiv 3 \quad mod \space 4$, which allows efficient point compression. The Brainpool standard requires that “elliptic curve domain parameters shall be generated in a pseudo-random manner using seeds that are generated in a systematic and comprehensive way.” Furthermore, all curves have cofactor $h=1$ in order to avoid small subgroup attacks (Johannes Merkle et al. (2010)Johannes Merkle and Manfred Lochter. Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and Curve Generation. RFC 5639, March 2010.).