Page MenuHome GnuPG

gcry_mpi_invm producing wrong result
Open, HighPublic

Description

https://lists.gnupg.org/pipermail/gcrypt-devel/2022-April/005303.html - 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");
end:

    return 0;
}

Revisions and Commits

Related Objects

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.