i'm back! uwu~

so there's this reimplementation of part of nacl that was done in a way it could be fit into 100 tweets. it's called tweetnacl.

the whole idea was to make it easily auditable, but i think it's also just cute in its own right. so i wanted to showcase how it handles eddsa signatures.

to start, here's the source. it's uncommented, which makes this fun :3


/// the signing algorithm ///

here's the signing operation, which I've added comments to!! you can follow along using the wikipedia description of eddsa. heads up that to save chars, a lot of the keywords are typedef'd (i.e. i64 for long long int) and there's some wacky macros. i'll note anything non-obvious as we go :)

1// twetnacl.c:711-741, reformatted to add comments

2

3int crypto_sign(

4    u8 *sm,       // signed message

5    u64 *smlen,   // signed message length

6    const u8 *m,  // message to sign

7    u64 n,        // message length

8    const u8 *sk  // secret key

9)

10{

11  // initialize everything

12  u8 d[64],h[64],r[64];

13  i64 i,j,x[64];

14  gf p[4];  // gf is typedef for i64[16]

^ to start, crypto_sign takes a u8 * for where the signed message is to be stored and a u64 * for where its length will go, as well as the message, its length, and the secret key to use (a random 256-bit string).

14  // compute d = SHA-512(sk)

15  crypto_hash(d, sk, 32);

^ next, we calculate SHA-512 of the first half secret key. in particular this gives us d[:32], the multiple of the basepoint of our curve we use for the public key.

16  // "clamp" d[:32]

17  d[0] &= 248;

18  d[31] &= 127;

19  d[31] |= 64;

^ we then "clamp" that multiple. since "every" machine is little-endian, this

  1. clears d[:32]'s 3 lowest bits
  2. unsets d[:32]'s top bit
  3. sets the bit below that.

the motiviation for this is because we'll multiply the base point of our curve by d[:32] to obtain part of our signature:

(1) is done because the group for curve25519 is order 8 * L, where L is a large prime. by clearing the low bits of d[:32], we make d[:32] a multiple of 8, so it lies in the subgroup of order L. this stops small subgroup attacks.

(2) is done because 8 * L is 255 bits, so we don't need to consider any multiples of our base point larger than that.

(3) is done because we want a montgomery ladder using this value to run in constant time, and some implementations of montgomery ladders vary in runtime based on where the most significant bit is (ew).

if you're super bored, a couple great "why clamping" posts are here and here :P

20  // set smlen to n + 64 (m + signature)

21  *smlen = n+64;

^ well, our signature is always gonna be 64 words, so we can set the length of the signed message right now :)

22  // load m into sm[64:]

23  FOR(i,n) sm[64 + i] = m[i];  // FOR(i, n) loops i = 0..n-1

24

25  // load d[32:64] into sm[32:64]

26  FOR(i,32) sm[32 + i] = d[32 + i];

27

28  // compute r = SHA-512(d[32:64] || m) mod L

29  crypto_hash(r, sm+32, n+32);

30  reduce(r);

^ now we concatenate the unused half of our secret key hash d and our message m, hash them together, then reduce mod L to get r.

31  // compute r * <basepoint> and pack into sm[:32]

32  scalarbase(p,r);

33  pack(sm,p);

^ r is what we multiply our basepoint by to get the first half of our signature (!!), which we stuff in the first 32 words of sm.

34  // load sk[32:64] into sm[32:64]

35  FOR(i,32) sm[i+32] = sk[i+32];

36

37  // compute h = SHA-512(sm) mod L

38  crypto_hash(h,sm,n + 64);

39  reduce(h);

^ now, we stick the half of sk we didn't use after our half-sig but before the message m. then, we hash the three of them together into h.

on wiki, the middle part is actually the eddsa public key instead of sk[32:64]. good news is that this is the part of sk reserved for generating the pubkey, so we're still committing to the same thing by just putting sk[32:64] in there :3

40  // clear x[:64] and load x[:32] = r

41  FOR(i,64) x[i] = 0;

42  FOR(i,32) x[i] = (u64) r[i];

43

44  // compute (multiword) x += h * d

45  FOR(i,32) FOR(j,32) x[i+j] += h[i] * (u64) d[j];

46

47  // compute x mod L and store into sm[n + 32:]

48  modL(sm + 32,x);

^ last, we calculate r + h * d mod L and stick it into the second half of the signature before the message. the signature is complete!

49  // no error

50  return 0;

51}

^ level clear!


/// conclusion ///

whew! we just went through a whole eddsa signing! go hydrate and then exercise for the reader: try pulling apart some of the functions in tweetnacl.c that this one relies on!

or check out the salsa20 implementation (i swear it's cute).

uhhh if you liked this lmk and i'll do more like this!

lol. cya!

-- foxmoder