# Generating a NIST P-256 private key

From the Curve25519 spec I learned that it possible to take a random 32 bytes and with a few operations make it on the curve:

To generate a 32-byte Curve25519 secret key, start by generating 32 secret random bytes from a cryptographically safe source:

mysecret, mysecret, ..., mysecret.


Then do

mysecret &= 248;
mysecret &= 127;
mysecret |= 64;


Is there a similar way to take random bytes and use it for a p-256 private key?

## 1 Answer

A NIST P-256 secret key (for ECDH or ECDSA) represents any scalar modulo $\ell$ for $$\ell = 2^{256} - 432420386565659656852420866394968145599,$$ whereas an X25519 secret key represents an integer multiple of 8 between $2^{254}$ and $2^{255}$, interpreted as a scalar modulo $8 p_1$ for $$p_1 = 2^{252} + 27742317777372353535851937790883648493.$$ In both cases, the secret key should be chosen uniformly at random from all possibilities, so that every possibility has equal probability. Here $\ell$ and $p_1$, both large primes, are the orders of the standard base points on the respective curves.

The NIST recommends, in FIPS 186-4 Appendix B.4 pp. 61–64, that you either generate 320 bits uniformly at random, reduce modulo $\ell - 1$, and add $1$; or do rejection sampling, drawing 256-bit $n$ and starting over unless $0 < n < \ell$. These methods keep the modulo bias respectively either small or nonexistent, and avoid $n = 0$. The benefit of this negligible, so I would just accept the modulo bias of picking 256 bits uniformly at random and performing a single conditional subtraction, losing less than a single bit of theoretical security. But if you're using NIST P-256, you're probably slave to compliance with government bureaucracy standards, so you should probably follow the letter of the standard.

Technical details, or, why is it different for (say) ECDH over NIST P-256 and X25519?

The curve group NIST P-256 has prime order $\ell$, and the standard base point generates the entire group, so even if you reveal $[n]P$ for attacker-controlled points $P$ where $n$ is your secret scalar, there are no active small-subgroup attacks possible on NIST P-256; and although the quadratic twist of NIST P-256 does not have prime order, it happens to have the modest cofactor $34905 = 3 \cdot 5 \cdot 13 \cdot 179$ which confers a degree of twist security. Caveat: If you foolishly handle uncompressed $(x, y)$ inputs, twist security is not enough; you must still validate them to thwart invalid-curve attacks.

In contrast, the curve group Curve25519 has composite order $8 p_1$, and its twist has composite order $4 p_2$ for another large prime $p_2$, while the standard base point has order $p_1$. So to thwart small-subgroup and twist attacks without requiring point validation, the secret scalar $n$ is always chosen to be congruent to zero modulo the cofactor 8 and the twist cofactor 4, and public keys are transmitted as $x$ coordinates only so the only possible invalid curve is the quadratic twist.

• "NIST recommends ... either generate 320 bits uniformly at random and reduce modulo $\ell$", actually, their recommendation actually is "reduce it modulo $\ell-1$, and then add 1 (obviously to reduce the probability of generating 0 from negligible to impossible) – poncho Mar 16 '18 at 20:16
• @poncho UGH! Bureaucratic standardsese AND fenceposts with probability near $2^{-256}$! – Squeamish Ossifrage Mar 16 '18 at 20:35
• Yeah, you might as well amend it with an additional check that the answer isn't 1 or N-1 as something is clearly wrong if it ever reaches either of those values :P – Maarten Bodewes Mar 17 '18 at 15:49
• @MaartenBodewes Holy key generation, Bodewesman! What if it turns out to be 21397745653766824805525653055986092741404767722902725289987975828237449574345, which is the concatenation of the last handful of serial numbers I saw on boxes and parcels while going through the recycling? Better check for that number too—especially now that it's posted on the internet where Google can find it! – Squeamish Ossifrage Mar 17 '18 at 16:46
• Why is it OK for Curve25519 to choose a random number $2^{254} \le x < 2^{255}$ (divisible by 8), while P-256 needs a random number $0 < x < \ell$? In other words, why can Curve25519 ignore the numbers between $0$ and $2^{254}$ and between $2^{255}$ and $\ell$? – Conrado Jan 16 '20 at 18:36