5

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

  • 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 Feb 8 '17 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 ? – kumarz Feb 8 '17 at 12:25
  • 1
    @kumarz they have to calculate the modulo manually because the number is too large to fit in a "standard" type like an int1_64. – assylias Feb 9 '17 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 – kumarz Feb 11 '17 at 17:36
6

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.

  • understood: many thanks for clarifying Lee ! – kumarz Feb 11 '17 at 17:38
6

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.

  • ok many thanks: Yes, I forgot to mention that according to my testing (vs) Luigi's addresscheck the simpler version does actually work. – kumarz Feb 7 '17 at 23:34

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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