Trimming uniformly random input for elliptic curve private keys

Question

Imagine there is 256-bit uniform input from CSPRNG. Suppose there is a curve like secp256r1 whose curve order is slightly less than 256 bits.

We cannot just mod(input, curve_order) because it will introduce modulo bias. What if we trim 256 bits to 255 bits which is less than curve order? Then all values within 255 bits will have an equal chance of appearance.

ed25519 seems to do exactly that, with their ~252-bit curve order - they adjust 3 bits.

Rejection sampling from NIST SP 800-56A rev 3, section 5.6.1.2.2 is not constant-time, so looking for something simpler.

Additional question: What if we also adjust last 1 bit so that keys 0 and 1 will never appear by using |= 2 that will force them to always be 1 (the same way we always force beginning to be 0?

Answer 1

This is how the Monero codebase generates random scalars for use with ed25519:

For the ed25519 curve, the order $\ell$ of the group of the base point is $2^{252}+27742317777372353535851937790883648493$.

In order to generate an unbiased random number less than $\ell$, we first determine that the maximum multiple of $\ell$ that can fit into 32 bytes is $15$.

To generate the unbiased random number, we repeatedly generate a random 32-byte sequence and test if it is less than $15\ell$. Once we find such a number, we can then reduce this number $mod\ \ell$ without introducing modulo bias. The probability of finding a suitable random number on the first iteration is approx. 94%.

The same technique applies to secp256r1, where you would use $3 \ell$ instead of $15\ell$ due to the order of the group of the base point for secp256r1 being larger (see 2.4.2 Recommended Parameters secp256r1). The probability of finding a suitable random number on the first iteration is approx. 95%.