1
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – knaccc
    Jan 27, 2022 at 16:28
  • $\begingroup$ This is for simplicity only - not for "constant timeness" in its traditional / security sense. $\endgroup$ Jan 27, 2022 at 16:58
  • $\begingroup$ 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. $\endgroup$
    – knaccc
    Jan 27, 2022 at 17:05

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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