mp_exptmod incorrect result since version 0.32

[guidovranken]

The following prints 0 but should print 25204017012210281742336 (on Linux x64):

#include <tommath.h>
#include <stdlib.h>

#define CHECK(x) if ( (x) != MP_OKAY ) abort();

int main(void)
{
    mp_int base, exp, mod, res;
    char str[1024];
    CHECK(mp_init(&base));
    CHECK(mp_init(&exp));
    CHECK(mp_init(&mod));
    CHECK(mp_init(&res));
    CHECK(mp_read_radix(&base, "24", 10));
    CHECK(mp_read_radix(&exp, "9223372036854775808", 10));
    CHECK(mp_read_radix(&mod, "75556710804409716572160", 10));
    CHECK(mp_exptmod(&base, &exp, &mod, &res));
    CHECK(mp_to_radix(&res, str, 1024, NULL, 10));
    printf("%s\n", str);
    return 0;
}

If libtommath was compiled with -DMP_32BIT, the following prints 1 but should print 1073741825:

#include <tommath.h>
#include <stdlib.h>

#define CHECK(x) if ( (x) != MP_OKAY ) abort();

int main(void)
{
    mp_int base, exp, mod, res;
    char str[1024];
    CHECK(mp_init(&base));
    CHECK(mp_init(&exp));
    CHECK(mp_init(&mod));
    CHECK(mp_init(&res));
    CHECK(mp_read_radix(&base, "67927325822352824469517479013", 10));
    CHECK(mp_read_radix(&exp, "2147483648", 10));
    CHECK(mp_read_radix(&mod, "1879048192", 10));
    CHECK(mp_exptmod(&base, &exp, &mod, &res));
    CHECK(mp_to_radix(&res, str, 1024, NULL, 10));
    printf("%s\n", str);
    return 0;
}

Bug introduced in e549ccf according to git bisect (Github lists the date as 2010 but it's actually 2004).

Found during audit of Nimbus funded by Ethereum.

[czurnieden]

It goes a bit deeper.

small base = 24, large base = 67927325822352824469517479013

Version 0.31:

size	small	large
MP_32BIT	25204017012210281742336	1
MP_64BIT	25204017012210281742336	1

Version 0.32:

size	small	large
MP_32BIT	0	1073741825
MP_64BIT	0	1073741825

This might take a while.

But nevertheless: thank you very much for the bug report!

[czurnieden]

The algorithm as implemented does not work if the least significant digit is zero. Added check for a non-empty LSD in #564 .

[guidovranken]

Thanks, confirmed fixed.