Old bug in gcry_mpi_invm producing wrong result

[Guido Vranken]

It says that InvMod(18446744073709551615,
340282366762482138434845932244680310781) is
170141183381241069226646338154899963903 but that's not true, because
170141183381241069226646338154899963903 * 18446744073709551615 %
340282366762482138434845932244680310781 is 4294967297, not 1.

It looks like this bug has been present at least since libgcrypt-1.2.0 from
2004.

#include <gcrypt.h>

#define CF_CHECK_EQ(expr, res) if ( (expr) != (res) ) { goto end; }

int main(void)
{
    gcry_mpi_t A;
    gcry_mpi_t B;
    gcry_mpi_t C;
    gcry_error_t err;

    CF_CHECK_EQ(err = gcry_mpi_scan(&A, GCRYMPI_FMT_HEX,
"ffffffffffffffff", 0, NULL), 0);
    CF_CHECK_EQ(err = gcry_mpi_scan(&B, GCRYMPI_FMT_HEX,
"fffffffdfffffffffffffffffffffffd", 0, NULL), 0);
    CF_CHECK_EQ(err = gcry_mpi_scan(&C, GCRYMPI_FMT_HEX, "1", 0, NULL), 0);
    CF_CHECK_EQ(gcry_mpi_invm(C, A, B), 1);
    printf("Inverse exists\n");
end:

    return 0;
}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.gnupg.org/pipermail/gcrypt-devel/attachments/20220423/3dd6d942/attachment-0001.html>