sc_reduce32 … is it really supposed to be that complicated?

Question

sc_reduce32 in crypto-ops.c looks super involved, but according to MRL-0003.pdf, its just:

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

Also according to this question(sorry I don't have enough rep to ask as a comment):

import ed25519
import binascii
spendkey_hex = b'77fadbe52830d30438ff68036374c0e3fb755d0d983743bcbfb6a45962f50a09'
sk = binascii.unhexlify(spendkey_hex)

def sc_reduce32(n):
    n = int.from_bytes(n, byteorder='little')
    l = (2**252 + 27742317777372353535851937790883648493)
    reduced = n % l
    newbytes = reduced.to_bytes(32, 'little')
    return newbytes

reduced_sk = sc_reduce32(sk)

which in turn doesn't match MiniNero code:

q = 2**255 - 19
l = 2**252 + 27742317777372353535851937790883648493
def sc_reduce_key(a):
   return intToHex(hexToInt(a) % l)

I realise MiniNero is hugely outdated and ShenNoether's replacement never materialized. His version/profiles have disappeared from GitHub/Reddit(Noblesir), but I noticed that Ryan started work on replicating sc_reduce32 in Python(note he's also the guy who asked Q2290), but it seems incomplete.

I wonder if someone could clarify for me what exactly sc_reduce32 is currently supposed to be doing, so I can continue/complete replicating it in python(unless someone already has? link please?).

Answer 1

There was almost two questions packed into one here (the title and final paragraph), so I'll answer the other. The function sc_reduce32 was written to prevent against data leakage via timing analysis. Division ASM instructions and alternate code branches take a variable number of cycles to complete, and the relative timings could leak data to an observer. So the implementation has to perform a modulus operation over an integer value larger than any built-in C integer type without using division, or a single branch (if, while, etc).

Python has built-in support for big-integers; the % operator in that mininero sample is deceptive because it is calling a much larger C function that is doing similar logic to the sc_reduce32 function. The python implementation looks different because it handles variable byte length integers, signed integers, and was not written to complete in constant number of CPU cycles.

Answer 2

I experimented with this using javacsript biginteger library and it is what it says - just a mod l operation. Endianness and encoding could make some confusion, though.

From your code it looks like the difference is just in the input/output format. One uses a string with base16 encoding, and the other one uses a byte array. They should both represent the same number, though.