3
$\begingroup$

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[0], mysecret[1], ..., mysecret[31].

Then do

mysecret[0] &= 248;
mysecret[31] &= 127;
mysecret[31] |= 64;

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ "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) $\endgroup$ – poncho Mar 16 '18 at 20:16
  • $\begingroup$ @poncho UGH! Bureaucratic standardsese AND fenceposts with probability near $2^{-256}$! $\endgroup$ – Squeamish Ossifrage Mar 16 '18 at 20:35
  • $\begingroup$ 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 $\endgroup$ – Maarten Bodewes Mar 17 '18 at 15:49
  • $\begingroup$ @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! $\endgroup$ – Squeamish Ossifrage Mar 17 '18 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.