Commit af3bc61ea20d46a55224bcd26b0576235e551b87

Steffen Jaeckel 2018-09-22T17:14:50

Merge pull request #119 from libtom/pr/possible-fix-118 bn_fast_mp_invmod fix related to #118

diff --git a/bn_fast_mp_invmod.c b/bn_fast_mp_invmod.c
index 91b5bf6..be1a810 100644
--- a/bn_fast_mp_invmod.c
+++ b/bn_fast_mp_invmod.c
@@ -138,6 +138,14 @@ top:
          goto LBL_ERR;
       }
    }
+
+   /* too big */
+   while (mp_cmp_mag(&D, b) != MP_LT) {
+      if ((res = mp_sub(&D, b, &D)) != MP_OKAY) {
+         goto LBL_ERR;
+      }
+   }
+
    mp_exch(&D, c);
    c->sign = neg;
    res = MP_OKAY;
diff --git a/demo/demo.c b/demo/demo.c
index ff67fcc..b5af727 100644
--- a/demo/demo.c
+++ b/demo/demo.c
@@ -382,6 +382,37 @@ int main(void)
       }
    }
 
+   // mp_invmod corner-case of https://github.com/libtom/libtommath/issues/118
+   printf("\n\nTesting: mp_invmod");
+   {
+      const char *a_ = "47182BB8DF0FFE9F61B1F269BACC066B48BA145D35137D426328DC3F88A5EA44";
+      const char *b_ = "FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF";
+      const char *should_ = "0521A82E10376F8E4FDEF9A32A427AC2A0FFF686E00290D39E3E4B5522409596";
+
+      if (mp_read_radix(&a, a_, 16) != MP_OKAY) {
+         printf("\nmp_read_radix(a) failed!");
+         return EXIT_FAILURE;
+      }
+      if (mp_read_radix(&b, b_, 16) != MP_OKAY) {
+         printf("\nmp_read_radix(b) failed!");
+         return EXIT_FAILURE;
+      }
+      if (mp_read_radix(&c, should_, 16) != MP_OKAY) {
+         printf("\nmp_read_radix(should) failed!");
+         return EXIT_FAILURE;
+      }
+
+      if (mp_invmod(&a, &b, &d) != MP_OKAY) {
+         printf("\nmp_invmod() failed!");
+         return EXIT_FAILURE;
+      }
+
+      if (mp_cmp(&c, &d) != MP_EQ) {
+         printf("\nmp_invmod() bad result!");
+         return EXIT_FAILURE;
+      }
+   }
+
    // test mp_get_int
    printf("\n\nTesting: mp_get_int");
    for (i = 0; i < 1000; ++i) {