Page MenuHome GnuPG

gcry_mpi_invm producing wrong result
Closed, ResolvedPublic

Description - Guido Vranken wrote:

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");

    return 0;

Revisions and Commits

Event Timeline

gniibe triaged this task as High priority.
gniibe added a project: backport.
gniibe added a subscriber: gniibe.

Thanks for creating this ticket. I'll reply.

Pushed the change. Also, it's backported to 1.10 branch.

I confirmed that 1.8 branch has no issue for this.

werner changed the task status from Open to Testing.Sep 22 2022, 10:56 AM
werner removed a project: Restricted Project.