In the Zero to Monero book, I am reading about Schnorr signatures. Section 2.3.4 references the random32_unbiased() function from src/crypto/crypto.cpp of the codebase. My understsanding is that this function generates a random integer between 1 and l-1 (both inclusive), where l is a large integer.
That function is:
void random32_unbiased(unsigned char *bytes)
{
// l = 2^252 + 27742317777372353535851937790883648493.
// l fits 15 times in 32 bytes (iow, 15 l is the highest multiple of l that fits in 32 bytes)
static const unsigned char limit[32] = { 0xe3, 0x6a, 0x67, 0x72, 0x8b, 0xce, 0x13, 0x29, 0x8f, 0x30, 0x82, 0x8c, 0x0b, 0xa4, 0x10, 0x39, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xf0 };
while(1)
{
generate_random_bytes_thread_safe(32, bytes);
if (!less32(bytes, limit))
continue;
sc_reduce32(bytes);
if (sc_isnonzero(bytes))
break;
}
}
What purpose does the line with static const unsigned char limit[32] have?
My main question is the above one, but in general, I do not deeply understand how function works, so an explanation would be appreciated too.
Monero uses edwards25519 as the underlying elliptic curve which it uses to produce EdDSA (Edwards digital signatures), to create transactions on the Monero blockchain.
edwards25519 is a curve which is of composite order, that is, it's not a prime order curve like secp256k1, which is used by Bitcoin.
Owing to this fact, in cryptographic contexts we must work in a prime order subgroup of the curve, so our group is prime, for security reasons.
That subgroup for Monero is ~8-times smaller than the order of the actual curve! Thus the subgroup size is l, i.e. 2^252 + 27742317777372353535851937790883648493
So, there can only be 2^252 + 27742317777372353535851937790883648493 valid public keys for Monero, or anything else using edwards25519
As James K. Polk points out, we want to ensure we stay inside the cyclic subgroup, but not introduce bias in the key material.
Interestingly, I stuck l into sagemath, multiplied it by 15, and indeed it does fit in 256-bits.
255.906890595609 to be exact, 16 times would require 256.000000000000000000000000000000000000005 bits. Math yo.