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;
}
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;
}