NUMS

In 2014, Black, Bos, Costello, Longa, and Naehrig proposed three Weierstrass curves and three twisted Edwards curves, one of each for three different security levels (256, 384, and 512-bit prime fields) as an Internet draft Elliptic Curve Cryptography (ECC) Nothing Up My Sleeve (NUMS) Curves and Curve Generation [1]. These curves have been chosen to support constant-time, exception-free scalar multiplications and were generated deterministically based on algorithms from the document without any hidden parameters. The six NUMS curves were firstly proposed in [2] by Bos, Costello, Longa, and Naehrig, in which the authors select 12 Weierstrass curves and 12 twisted Edwards curves in order to contribute toward new elliptic curves recommendation. The prime generation, as well as elliptic curve generation, are further explained here, including an analysis of scalar multiplication algorithms and software implementation.

Primes

The Internet draft specifies prime generation for base fields of elliptic curves. For three bit-lengths $s \in \{256,384,512\}$ a pseudo-Mersenne prime $p=2^s-c$ is selected where $c$ is the smallest positive integer such that $p$ is prime satisfying $p=3 \pmod 4$ (Algorithm 1).

The original paper [2] proposes two types of primes: pseudo-Mersenne and Montgomery-friendly primes. The pseudo-Mersenne primes are generated in the same way as in the Internet draft. The Montgomery-friendly primes of the form $p=2^\alpha(2^\beta-\gamma)-1$ are generated by putting $\alpha=8\delta$, $\beta \in \{2s-\alpha,2s-2-\alpha\}$ and choosing $\gamma$ and $\delta$ as the smallest positive integers such that $p$ is prime with bit length $2s$ (resp. $2s-2$). More specifically the authors incremented $\delta$ (starting with $\delta=1$), and for each such $\delta$ incremented $\gamma$ (starting with $\gamma=1$).

Curve generation

To select Weierstrass curves $y^2=x^3+ax+b$, the authors of the Internet draft consider only curves with $a=-3$. The parameter $b$ is selected as the element of $\mathbb{F}_p$, different from $\pm 2$ (nonzero discriminant), with the smallest absolute value when represented as an integer in the interval $[-(p-1)/2,(p-1)/2]$ such that the curve satisfies the first two conditions from the security requirements below (Algorithm 2). However, in order to fulfill the last two security conditions, the authors only comment that "care must be taken to ensure the MOV degree and CM discriminant requirements." Truly careful care must be taken as, for example, checking these conditions in line 2 of the Algorithm 2 would be, of course, a mistake as in line 3, the algorithm might switch to the quadratic twist (which doesn't preserve the lower bound on embedding degree). Regarding the twisted Edwards curves $ax^2+y^2=1+dx^2y^2$, authors consider only curves with $a=-1$. The parameter $d$ is selected as the element of $\mathbb{F}_p$, different from $-1,0$ (nonzero discriminant), with the smallest value when represented as an integer such that first two conditions of the mentioned security requirements are satisfied. A similar comment as for the Weierstrass curves is given concerning the other two conditions. The generators for both types of curves were generated as the affine points with the smallest nonzero $x$-coordinate when represented as an integer. The second coordinate is chosen as the smallest of the two roots.

In the original paper [2] the method of generation of the Weierstrass curves is the same as in the Internet draft, claiming to leave no room for manipulation. The twisted Edwards curves require more attention. The proposed curves, including the six of them in the Internet draft, were generated using a different method than is presented in the draft. However, the authors prove that both methods are equivalent. More specifically, in the Internet draft, they used the twisted Edwards form $-x^2+y^2=1+dx^2y^2$ and iterated through $d$ starting from $d=1$, thus finding minimal $d$ such that the curve is secure enough. In this original paper, they consider a Montgomery form $y^2=x^3+Ax^2+x$, and they minimalize the absolute value of $A$. Even though every Montgomery curve is birationally equivalent to a twisted Edwards curve [3], this equivalence doesn't preserve the minimality of the parameters (i.e. minimal $A$ for which the Montgomery form is secure doesn't correspond to a minimal $d$ for which the Edwards form is secure). The authors, therefore, consider another twisted Edwards curve which is isogenous to the original one and therefore has the same number of points. In short, the parameters $A$ and $d$ are minimal ones such that the curve is secure. However, they do not define birationally equivalent curves, only isogenous ones.

Security

• The curve order as well as the order of its twist shall be primes.
• The trace $t$ of the curve can't be 0 or 1. This condition is further extended by requiring $t>1$ for easier implementation.
• The embedding degree shall be greater than $(n-1)/100$ following the Brainpool standard.
• The CM discriminant shall be greater than $2^{100}$ following the SafeCurves recommendations [4].

Recommended curves

Table 1 and Table 2 present the Weierstrass curves (denoted with the letter w) and the twisted Edwards curves (denoted with ed) as proposed in [2]. The rest of the name of the curve indicates the bit length of the underlying prime field and the type of the prime: mers for pseudo-Mersenne primes, which were then used for the Internet draft and mont for the Montgomery-friendly primes. The $\rho$ complexity is an estimate of the actual security of the ECDLP against Pollard's $\rho$ method (more specifically, it is the $\log_2(\sqrt{\pi/4}\cdot \sqrt{r})$ rounded to an integer). For each security level, one curve has half a bit of ECDLP security sacrificed in favor of potential efficiency.