incosistent MP_32BIT vs. MP_31BIT in tommath.h

[karel-m]

In tommath.h we have:

...
#if !(defined(MP_32BIT) || defined(MP_16BIT) || defined(MP_8BIT))
...

and couple of lines after that:

...
#ifdef MP_31BIT
...

IMO both MP_31BIT and MP_32BIT should be consistent

[karel-m]

After investigating other files I think MP_32BIT is correct

[sjaeckel]

well MP_31BIT is an extension to MP_32BIT where ltm uses internally 31 bit to store a limb instead of 28 bit in the normal configuration. (i.e. you have to define MP_31BIT in addition to MP_32BIT) Why? to be size-wise more efficient I guess, but I don't know why the standard configuration only uses 28 bit... probably @czurnieden or @tomstdenis can give some details on that choice

[karel-m]

But in that case MP_32BIT is equivalent to MP_28BIT which is also used in tommath.h

[hikari-no-yume]

Ideally you'd just have MP_28BIT, MP_31BIT etc., then add the 32/64 aliases with #define.

[karel-m]

If you look through the *.h and *.c files you will find

• MP_64BIT ... DIGIT_BIT = 60
• MP_32BIT ... DIGIT_BIT = 28 ?????
• MP_31BIT ... DIGIT_BIT = 31
• MP_28BIT ... DIGIT_BIT = 28 ?????
• MP_16BIT ... DIGIT_BIT = 15
• MP_8BIT ... DIGIT_BIT = 7

So MP_28BIT or MP_32BIT is IMO redundant

[sjaeckel]

You are absolutely right, but that's already stated near the define of the MP_28BIT macro https://github.com/libtom/libtommath/blob/develop/tommath.h#L93

[karel-m]

OK, so what about to replace MP_32BIT with MP_28BIT (it is just in demo.c + testme.sh and once in tommath.h)?

[czurnieden]

The reason for the 28 bits? It's in the Comba algorithm and relates to the maximum size of the smaller input. With 28 bit it can be at most 256 limbs large but with 32 bits only a poor and lonely single limb is allowed. There are also three places (bn_mp_add_d.c lines 67, 73 and in bn_mp_montgomery_reduce.c line 90) which would need one bit less than a word size (e.g.: 31 bits instead of 32 bits) hence the 15 bits for MP_16 and 7 bits for MP_8. The latter could be repaired quite easily if necessary, but the 28-bit (60-bit) restriction is hard to get rid off. The Comba multiplication is too useful for small numbers, especially in the range of cryptographic keys. (Ignoring timing attacks, but I just assume that people using libtommath for cryptographic purposes know what they are doing)

For more details see the documentation: chapter 5 in the section titled "Column Weight" (page 76 in my version).

So, @karel-m , no chance to get rid of the whole mess, only parts of it, sorry.

[tomstdenis]

Yes, 28 or 60 bits is "on purpose" for exactly that reason. 15/31 and others are provided for academic purposes (re: nobody should use it really) same with MP_8BIT and what not.

Personally, I'm ok with the exotic bit sizes being disabled since they're not always practical. They're good for teaching purposes but that's about it.