# sc_reduce32 ... is it really supposed to be that complicated?

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
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?).

• You should be aware that the Ed25519 implementation uses a highly advanced representation of field points to reduce the amount of computation needed, for example by having bigger than necessary limbs and not modulo reducing after every operation. You should read section 3 of the Ed25519 paper.
– orlp
Commented Feb 8, 2017 at 2:48
• @orlp ah, so you're referring to `void sc_reduce32(unsigned char *s)` in crypto-ops.c (wonder if @JollyMort missed my reference?) ... and that all those bit shifts(sorry I'm a noob) are in fact speeding up what `modulo l` does ? I take it that'd be the `Radix-2^51` representation ? Commented Feb 8, 2017 at 12:25
• @kumarz they have to calculate the modulo manually because the number is too large to fit in a "standard" type like an int1_64. Commented Feb 9, 2017 at 9:32
• ah cool, thanks! So if I am doing this in Python, no need to bother with all of that then: Yay :D Commented Feb 11, 2017 at 17:36

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