1

In sc_add (crypto-ops.c) we first load three chars, we mask with 2097151 (loosing information?):

int64_t a0 = 2097151 & load_3(a);

Then continue with something similar, but this time with four chars, starting with one that we already loaded in the last step (?!). And we shift by 5:

int64_t a1 = 2097151 & (load_4(a + 2) >> 5);

Later we shift by other values, like 7:

int64_t a3 = 2097151 & (load_4(a + 7) >> 7);

Why the overlapping? Why the AND'ing / masking? Based on what do we decide how many steps to shift?

Why not just add like 'a' + 'c' = 'd' (and 'z' + 'a' = 'a'), primitively speaking?

It's been ages for me since I last handled bitwise operations, so I'm struggling to see the pattern and logic here. Those shifts for example mostly have me think we're discarding information.

As you can see, I'm pretty much a n00b on this, but maybe someone can lend a hand and get me on the right track?

1

sc_add - scalar add - is taking two big numbers, which are stored as binary in byte (char) arrays and returning the result of adding them together in another byte array, mod the order of the base point.

The function has to use byte arrays because the largest type for native numbers in C/C++ is 64 bits, hence if you want to add two 256 bit numbers you need to 1) store these numbers as byte arrays and 2) use shifting and ANDing to perform the calculation.

int64_t a0 = 2097151 & load_3(a);

Is taking 3 bytes pointed at by a and taking the lower 21 bits.

int64_t a1 = 2097151 & (load_4(a + 2) >> 5);

Is taking 4 bytes pointing at by a + 2 (so not the same bytes as the previous line), shifting the bits down 5 places and then taking 21 bits.

Why not just add like 'a' + 'c' = 'd' (and 'z' + 'a' = 'a')

Ignoring the fact that in C that 'a' + 'c' = 'd' is incorrect, the reason you can't just use operators like +,-,/,% is because the numbers we are operating on are too big (as I outlined at the beginning). This, and many other of the crypto functions, are highly optimized math operations on large numbers for 32/64 bit systems.

  • This clears it up a bit. (My 'z' + 'a' = 'a' concept was based on the false presumption that we would just happily overflow - as in "0 comes after 255". On second thought not very intelligent in a cryptographic context :) – hokkjoy Dec 12 '18 at 18:27
  • One of my other confusions is: If a is a pointer to the first element of the array. So a+1 (or a[1]) is a pointer to the second and so forth. If we load_3, I understand that we are loading a + 0, a + 1 and a + 2. Then, in load_4, we load a + 2, a + 3, a + 4, a + 5. Thus we're loading a+2 two times. Why not just load_3 again, starting at a+3 up to a+5? – hokkjoy Dec 12 '18 at 18:27
  • The loading of a+2 happens twice because some bits may have been discarded from the first call. Recall that only 21 bits are assigned to each of these aN variables, so 3 bytes is 24 bits, thus the next read needs to grab 3 bits from previous loaded bytes. – jtgrassie Dec 12 '18 at 20:04
  • To understand the magic numbers, see comments in this file: github.com/str4d/ed25519-java/blob/v0.3.0/src/net/i2p/crypto/… – knaccc Dec 13 '18 at 5:33

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.