Why is sc_reduce32 needed?

Question

I recently read a question about sc_reduce32 I stumbled on while investigating on Monero's Mnemonic Seed working. A great tool has been llcoins which states the following when talking about conversions between the Hexadecimal and Mnemonic seed:

The "seeds" created by this method will always be valid scalars as they are sent to sc_reduce32 first.

MRL-0003 defines sc_reduce32 as:

4.1.11 sc_reduce
Takes a 64-byte integer and outputs the lowest 32 bytes modulo the prime q. This is not a CryptoNote-specific function, but comes from the standard ed25519 library.

4.1.12 sc_reduce32
Takes a 32-byte integer and outputs the integer modulo q. Same code as above, except skipping the 64→32 byte step.

My question can be split in two:

1. Why does the first statement imply that without sc_reduce32, the hexadecimal seed would potentially be an invalid scalar?
2. How is sc_reduce and sc_reduce32's prime q chosen? When looking at crypto_ops::generate_keys I have the feeling that it can be a random scalar, not even prime.

Answer 1

The paper is incorrect; it's actually mod l, not q. l is the curve order of ed25519. The primary reason AFAIK is that the code doesn't work correctly with scalars above a certain multiple of l. The random_scalar() function outputs an integer

Answer 2

The order for both ed25519 and curve25519 curves can be found from libgcrypt-1.8.5/cipher/ecc-curves.c in hex is 1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED.

Examine the following that normalizes either an ed25519 or curve25519 private key to their common shared order:

% echo deefd263cbfed62a3711dd133df3ccbd1c4dc4aac21d7405fd667498bf8ebaa1 | sc_reduce32 9ca838c2c31f1fbad7f030b68a3017ed1b4dc4aac21d7405fd667498bf8eba01

Contrast the results above to the following 3 command line steps. Step 1 swaps the endian of the pre-normalized private key. Step 2 normalizes the candidate key to the order of the ed25519 or cv25519 curves using the basic multi-precision calculator (bc) standard to most flavors of UNIX. Step 3 performs an endian swap again.

1% echo DEEFD263CBFED62A3711DD133DF3CCBD1C4DC4AAC21D7405FD667498BF8EBAA1 | rev | dd conv=swab

A1BA8EBF987466FD05741DC2AAC44D1CBDCCF33D13DD11372AD6FECB63D2EFDE

2% echo "obase=16; ibase=16; A1BA8EBF987466FD05741DC2AAC44D1CBDCCF33D13DD11372AD6FECB63D2EFDE % 1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED" | bc

1BA8EBF987466FD05741DC2AAC44D1BED17308AB630F0D7BA1F1FC3C238A89C

3% echo 1BA8EBF987466FD05741DC2AAC44D1BED17308AB630F0D7BA1F1FC3C238A89C | rev | dd conv=swab

9CA838C2C31F1FBAD7F030B68A3017ED1B4DC4AAC21D7405FD667498BF8EBA

Now the real question is what is the purpose of the extra 0x01 tucked on to the end of the results from the sc_reduce32 operation (where 32*8=256) ? Answer - MUST maintain leading hex zero digits when an endian conversion occurs!