Score:1

Trimming uniformly random input for elliptic curve private keys

ru flag

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?

knaccc avatar
es flag
Why is it important for the entire process to be constant-time? It's important to test each random number for being in range in constant time, but I can't see a reason that it would be a problem to have to loop an indeterminate number of times.
ru flag
This is for simplicity only - not for "constant timeness" in its traditional / security sense.
knaccc avatar
es flag
Note that for the technique I've described in my answer, if you always loop 29 times, that will only fail to be enough iterations $1$ in every $2^{128}$ attempts. That would qualify as constant-time but I assume would not qualify as "simple" as per your requirement. I can't see any other way to have a truly unbiased scalar.
Score:1
es flag

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%.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.