cleanup mod_inv.
authorNIIBE Yutaka <gniibe@fsij.org>
Tue, 8 Apr 2014 01:57:46 +0000 (10:57 +0900)
committerNIIBE Yutaka <gniibe@fsij.org>
Tue, 8 Apr 2014 01:57:46 +0000 (10:57 +0900)
ChangeLog
src/jpc.c
src/jpc_p256k1.c
src/jpc_p256r1.c
src/mod.c
src/mod.h
src/modp256k1.c
src/modp256k1.h
src/modp256r1.c
src/modp256r1.h

index 04b1e1e..87ecd19 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+2014-04-08  Niibe Yutaka  <gniibe@fsij.org>
+
+       * src/mod.c (mod_inv): Use MAX_GCD_STEPS_BN256.
+       Return failure or success.
+       * src/jpc.c (jpc_to_ac): Use mod_inv.
+       * src/modp256k1.c (modp256k1_inv): Remove.
+       * src/modp256r1.c (modp256r1_inv): Remove.
+
 2014-04-07  Niibe Yutaka  <gniibe@fsij.org>
 
        * src/openpgp-do.c (algorithm_attr_ed25519): It's OID only.
index c4cf879..1d8fadd 100644 (file)
--- a/src/jpc.c
+++ b/src/jpc.c
@@ -185,7 +185,7 @@ FUNC(jpc_to_ac) (ac *X, const jpc *A)
 {
   bn256 z_inv[1], z_inv_sqr[1];
 
-  if (MFNC(inv) (z_inv, A->z) < 0)
+  if (mod_inv (z_inv, A->z, CONST_P256) < 0)
     return -1;
 
   MFNC(sqr) (z_inv_sqr, z_inv);
index dd6b30d..a903b12 100644 (file)
@@ -24,6 +24,7 @@
 #include <stdint.h>
 #include <string.h>
 #include "bn.h"
+#include "mod.h"
 #include "modp256k1.h"
 #include "affine.h"
 #include "jpc-ac_p256k1.h"
index 63b52d7..1196945 100644 (file)
@@ -24,6 +24,7 @@
 #include <stdint.h>
 #include <string.h>
 #include "bn.h"
+#include "mod.h"
 #include "modp256r1.h"
 #include "affine.h"
 #include "jpc-ac_p256r1.h"
index 2cbe8e4..05e3bef 100644 (file)
--- a/src/mod.c
+++ b/src/mod.c
@@ -134,20 +134,31 @@ mod_reduce (bn256 *X, const bn512 *A, const bn256 *B, const bn256 *MU_lower)
 #undef borrow
 }
 
+/*
+ * Reference:
+ * Donald E. Knuth, The Art of Computer Programming, Vol. 2:
+ * Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1998
+ *
+ * Max loop: X=0x8000...0000 and N=0xffff...ffff
+ */
+#define MAX_GCD_STEPS_BN256 (3*256-2)
+
 /**
  * @brief C = X^(-1) mod N
  * 
+ * Assume X and N are co-prime (or N is prime).
  */
-#define MAX_N_BITS 256
-
-void
+int
 mod_inv (bn256 *C, const bn256 *X, const bn256 *N)
 {
   bn256 u[1], v[1], tmp[1];
   bn256 A[1] = { { { 1, 0, 0, 0, 0, 0, 0, 0 } } };
   uint32_t carry;
 #define borrow carry
-  int n = MAX_N_BITS * 3;
+  int n = MAX_GCD_STEPS_BN256;
+
+  if (bn256_is_zero (X))
+    return -1;
 
   memset (C, 0, sizeof (bn256));
   memcpy (u, X, sizeof (bn256));
@@ -341,4 +352,6 @@ mod_inv (bn256 *C, const bn256 *X, const bn256 *N)
        }
     }
 #undef borrow
+
+  return 0;
 }
index 117bcc7..c28dacf 100644 (file)
--- a/src/mod.h
+++ b/src/mod.h
@@ -1,3 +1,3 @@
 void mod_reduce (bn256 *X, const bn512 *A, const bn256 *B,
                 const bn256 *MU_lower);
-void mod_inv (bn256 *X, const bn256 *A, const bn256 *N);
+int mod_inv (bn256 *X, const bn256 *A, const bn256 *N);
index e22f826..d0ca6cc 100644 (file)
@@ -284,187 +284,6 @@ modp256k1_sqr (bn256 *X, const bn256 *A)
   modp256k1_reduce (X, AA);
 }
 
-/**
- * @brief  C = (1 / a)  mod p256k1
- *
- * Return -1 on error.
- * Return 0 on success.
- */
-#define MAX_N_BITS 256
-
-int
-modp256k1_inv (bn256 *C, const bn256 *a)
-{
-  bn256 u[1], v[1], tmp[1];
-  bn256 A[1] = { { { 1, 0, 0, 0, 0, 0, 0, 0 } } };
-  uint32_t carry;
-  int n = MAX_N_BITS * 3;
-
-  if (bn256_is_zero (a))
-    return -1;
-
-  memset (C, 0, sizeof (bn256));
-  memcpy (u, a, sizeof (bn256));
-  memcpy (v, P256K1, sizeof (bn256));
-
-  while (n--)
-    {
-      int c = (bn256_is_even (u) << 1) + bn256_is_even (v);
-
-      switch (c)
-       {
-       case 3:
-         bn256_shift (u, u, -1);
-         if (bn256_is_even (A))
-           {
-             bn256_add (tmp, A, P256K1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (A, A, P256K1);
-
-         bn256_shift (A, A, -1);
-         A->word[7] |= carry * 0x80000000;
-
-         bn256_shift (v, v, -1);
-         if (bn256_is_even (C))
-           {
-             bn256_add (tmp, C, P256K1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (C, C, P256K1);
-
-         bn256_shift (C, C, -1);
-         C->word[7] |= carry * 0x80000000;
-
-         if (bn256_is_ge (tmp, tmp))
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256k1_sub (tmp, tmp, tmp);
-           }
-         else
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256k1_sub (tmp, tmp, A);
-           }
-         break;
-
-       case 1:
-         bn256_shift (tmp, tmp, -1);
-         if (bn256_is_even (tmp))
-           {
-             bn256_add (tmp, tmp, P256K1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (tmp, tmp, P256K1);
-
-         bn256_shift (tmp, tmp, -1);
-         tmp->word[7] |= carry * 0x80000000;
-
-         bn256_shift (v, v, -1);
-         if (bn256_is_even (C))
-           {
-             bn256_add (tmp, C, P256K1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (C, C, P256K1);
-
-         bn256_shift (C, C, -1);
-         C->word[7] |= carry * 0x80000000;
-
-         if (bn256_is_ge (tmp, tmp))
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256k1_sub (tmp, tmp, tmp);
-           }
-         else
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256k1_sub (tmp, tmp, A);
-           }
-         break;
-
-       case 2:
-         bn256_shift (u, u, -1);
-         if (bn256_is_even (A))
-           {
-             bn256_add (tmp, A, P256K1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (A, A, P256K1);
-
-         bn256_shift (A, A, -1);
-         A->word[7] |= carry * 0x80000000;
-
-         bn256_shift (tmp, tmp, -1);
-         if (bn256_is_even (tmp))
-           {
-             bn256_add (tmp, tmp, P256K1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (tmp, tmp, P256K1);
-
-         bn256_shift (tmp, tmp, -1);
-         tmp->word[7] |= carry * 0x80000000;
-
-         if (bn256_is_ge (tmp, tmp))
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256k1_sub (tmp, tmp, tmp);
-           }
-         else
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256k1_sub (tmp, tmp, A);
-           }
-         break;
-
-       case 0:
-         bn256_shift (tmp, tmp, -1);
-         if (bn256_is_even (tmp))
-           {
-             bn256_add (tmp, tmp, P256K1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (tmp, tmp, P256K1);
-
-         bn256_shift (tmp, tmp, -1);
-         tmp->word[7] |= carry * 0x80000000;
-
-         bn256_shift (tmp, tmp, -1);
-         if (bn256_is_even (tmp))
-           {
-             bn256_add (tmp, tmp, P256K1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (tmp, tmp, P256K1);
-
-         bn256_shift (tmp, tmp, -1);
-         tmp->word[7] |= carry * 0x80000000;
-
-         if (bn256_is_ge (u, v))
-           {
-             bn256_sub (u, u, v);
-             modp256k1_sub (A, A, C);
-           }
-         else
-           {
-             bn256_sub (v, v, u);
-             modp256k1_sub (C, C, A);
-           }
-         break;
-       }
-    }
-
-  return 0;
-}
 
 /**
  * @brief  X = (A << shift) mod p256k1
index 5f9e4f6..3e20ab5 100644 (file)
@@ -7,4 +7,3 @@ void modp256k1_reduce (bn256 *X, const bn512 *A);
 void modp256k1_mul (bn256 *X, const bn256 *A, const bn256 *B);
 void modp256k1_sqr (bn256 *X, const bn256 *A);
 void modp256k1_shift (bn256 *X, const bn256 *A, int shift);
-int modp256k1_inv (bn256 *C, const bn256 *a);
index dc52a73..32c1aa7 100644 (file)
@@ -240,187 +240,6 @@ modp256r1_sqr (bn256 *X, const bn256 *A)
   modp256r1_reduce (X, AA);
 }
 
-/**
- * @brief  C = (1 / a)  mod p256r1
- *
- * Return -1 on error.
- * Return 0 on success.
- */
-#define MAX_N_BITS 256
-
-int
-modp256r1_inv (bn256 *C, const bn256 *a)
-{
-  bn256 u[1], v[1], tmp[1];
-  bn256 A[1] = { { { 1, 0, 0, 0, 0, 0, 0, 0 } } };
-  uint32_t carry;
-  int n = MAX_N_BITS * 3;
-
-  if (bn256_is_zero (a))
-    return -1;
-
-  memset (C, 0, sizeof (bn256));
-  memcpy (u, a, sizeof (bn256));
-  memcpy (v, P256R1, sizeof (bn256));
-
-  while (n--)
-    {
-      int c = (bn256_is_even (u) << 1) + bn256_is_even (v);
-
-      switch (c)
-       {
-       case 3:
-         bn256_shift (u, u, -1);
-         if (bn256_is_even (A))
-           {
-             bn256_add (tmp, A, P256R1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (A, A, P256R1);
-
-         bn256_shift (A, A, -1);
-         A->word[7] |= carry * 0x80000000;
-
-         bn256_shift (v, v, -1);
-         if (bn256_is_even (C))
-           {
-             bn256_add (tmp, C, P256R1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (C, C, P256R1);
-
-         bn256_shift (C, C, -1);
-         C->word[7] |= carry * 0x80000000;
-
-         if (bn256_is_ge (tmp, tmp))
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256r1_sub (tmp, tmp, tmp);
-           }
-         else
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256r1_sub (tmp, tmp, A);
-           }
-         break;
-
-       case 1:
-         bn256_shift (tmp, tmp, -1);
-         if (bn256_is_even (tmp))
-           {
-             bn256_add (tmp, tmp, P256R1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (tmp, tmp, P256R1);
-
-         bn256_shift (tmp, tmp, -1);
-         tmp->word[7] |= carry * 0x80000000;
-
-         bn256_shift (v, v, -1);
-         if (bn256_is_even (C))
-           {
-             bn256_add (tmp, C, P256R1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (C, C, P256R1);
-
-         bn256_shift (C, C, -1);
-         C->word[7] |= carry * 0x80000000;
-
-         if (bn256_is_ge (tmp, tmp))
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256r1_sub (tmp, tmp, tmp);
-           }
-         else
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256r1_sub (tmp, tmp, A);
-           }
-         break;
-
-       case 2:
-         bn256_shift (u, u, -1);
-         if (bn256_is_even (A))
-           {
-             bn256_add (tmp, A, P256R1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (A, A, P256R1);
-
-         bn256_shift (A, A, -1);
-         A->word[7] |= carry * 0x80000000;
-
-         bn256_shift (tmp, tmp, -1);
-         if (bn256_is_even (tmp))
-           {
-             bn256_add (tmp, tmp, P256R1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (tmp, tmp, P256R1);
-
-         bn256_shift (tmp, tmp, -1);
-         tmp->word[7] |= carry * 0x80000000;
-
-         if (bn256_is_ge (tmp, tmp))
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256r1_sub (tmp, tmp, tmp);
-           }
-         else
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256r1_sub (tmp, tmp, A);
-           }
-         break;
-
-       case 0:
-         bn256_shift (tmp, tmp, -1);
-         if (bn256_is_even (tmp))
-           {
-             bn256_add (tmp, tmp, P256R1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (tmp, tmp, P256R1);
-
-         bn256_shift (tmp, tmp, -1);
-         tmp->word[7] |= carry * 0x80000000;
-
-         bn256_shift (tmp, tmp, -1);
-         if (bn256_is_even (tmp))
-           {
-             bn256_add (tmp, tmp, P256R1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (tmp, tmp, P256R1);
-
-         bn256_shift (tmp, tmp, -1);
-         tmp->word[7] |= carry * 0x80000000;
-
-         if (bn256_is_ge (u, v))
-           {
-             bn256_sub (u, u, v);
-             modp256r1_sub (A, A, C);
-           }
-         else
-           {
-             bn256_sub (v, v, u);
-             modp256r1_sub (C, C, A);
-           }
-         break;
-       }
-    }
-
-  return 0;
-}
 
 /**
  * @brief  X = (A << shift) mod p256r1
index af49954..f7dcf94 100644 (file)
@@ -7,4 +7,3 @@ void modp256r1_reduce (bn256 *X, const bn512 *A);
 void modp256r1_mul (bn256 *X, const bn256 *A, const bn256 *B);
 void modp256r1_sqr (bn256 *X, const bn256 *A);
 void modp256r1_shift (bn256 *X, const bn256 *A, int shift);
-int modp256r1_inv (bn256 *C, const bn256 *a);