5

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

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

|improve this answer|||||
1

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!

|improve this answer|||||
  • Interesting question. I verified your calculation, and the 0x01 shouldn't be there. – koe Jan 22 at 1:10
  • Interesting to note that xmr.llcoins.net/addresstests.html generates the same 0x01 suffix. Wondering if there are masking bits that will be implicitly applied? – skaht Jan 22 at 2:16
  • tools.ietf.org/html/rfc8032#section-5.1 mentions the encoding for ed25519 is inherently little endian. tools.ietf.org/html/rfc7748#section-5 mentions the most significant bit of X25519 MUST be masked. – skaht Jan 22 at 2:33
  • Ah it must be related to the range, since the order is 252 bits but sc_reduce is 256 bits – koe Jan 22 at 3:29
  • Also, section 5 is talking about elliptic field elements in the finite field q, while sc_reduce32 is creating elements of the field l with order equal to the curve's order. Also I can't believe this garbage site makes lower case L look like upper case i. – koe Jan 22 at 3:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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