Add monty sqr and multiply routines (they just call karatsuba and then

redc, currently)

4 files changed, 77 insertions, 43 deletions

diff --git a/src/math/ec_gfp/point_gfp.cpp b/src/math/ec_gfp/point_gfp.cpp
index a6b35b18d..7ac6b4141 100644
--- a/src/math/ec_gfp/point_gfp.cpp
+++ b/src/math/ec_gfp/point_gfp.cpp
@@ -49,14 +49,11 @@ void PointGFp::monty_mult(BigInt& z, const BigInt& x, const BigInt& y) const
    z_reg.resize(2*p_size+1);
    zeroise(z_reg);
 
-   bigint_mul(&z_reg[0], z_reg.size(),
-              &ws[0],
-              x.data(), x.size(), x.sig_words(),
-              y.data(), y.size(), y.sig_words());
-
-   bigint_monty_redc(&z[0], z.size(),
-                     &ws[0],
-                     p.data(), p_size, p_dash);
+   bigint_monty_mul(&z_reg[0], z_reg.size(),
+                    x.data(), x.size(), x.sig_words(),
+                    y.data(), y.size(), y.sig_words(),
+                    p.data(), p_size, p_dash,
+                    &ws[0]);
    }
 
 // Montgomery squaring
@@ -78,13 +75,10 @@ void PointGFp::monty_sqr(BigInt& z, const BigInt& x) const
    z_reg.resize(2*p_size+1);
    zeroise(z_reg);
 
-   bigint_sqr(&z[0], z.size(),
-              &ws[0],
-              x.data(), x.size(), x.sig_words());
-
-   bigint_monty_redc(&z[0], z.size(),
-                     &ws[0],
-                     p.data(), p_size, p_dash);
+   bigint_monty_sqr(&z_reg[0], z_reg.size(),
+                    x.data(), x.size(), x.sig_words(),
+                    p.data(), p_size, p_dash,
+                    &ws[0]);
    }
 
 // Point addition
diff --git a/src/math/mp/mp_core.h b/src/math/mp/mp_core.h
index e1692006e..96f43d713 100644
--- a/src/math/mp/mp_core.h
+++ b/src/math/mp/mp_core.h
@@ -77,7 +77,7 @@ void bigint_simple_sqr(word z[], const word x[], size_t x_size);
 void bigint_linmul2(word x[], size_t x_size, word y);
 void bigint_linmul3(word z[], const word x[], size_t x_size, word y);
 
-/*
+/**
 * Montgomery Reduction
 * @param z integer to reduce (also output in first x_size+1 words)
 * @param z_size size of z (should be >= 2*x_size+1)
@@ -92,6 +92,23 @@ void bigint_monty_redc(word z[], size_t z_size,
                        word u);
 
 /*
+* Montgomery Multiplication
+*/
+void bigint_monty_mul(word z[], size_t z_size,
+                      const word x[], size_t x_size, size_t x_sw,
+                      const word y[], size_t y_size, size_t y_sw,
+                      const word p[], size_t p_size, word p_dash,
+                      word workspace[]);
+
+/*
+* Montgomery Squaring
+*/
+void bigint_monty_sqr(word z[], size_t z_size,
+                      const word x[], size_t x_size, size_t x_sw,
+                      const word p[], size_t p_size, word p_dash,
+                      word workspace[]);
+
+/*
 * Division operation
 */
 size_t bigint_divcore(word q, word y2, word y1,
diff --git a/src/math/mp/mp_monty.cpp b/src/math/mp/mp_monty.cpp
index d7f7e0306..cdb31f951 100644
--- a/src/math/mp/mp_monty.cpp
+++ b/src/math/mp/mp_monty.cpp
@@ -31,10 +31,10 @@ void bigint_monty_redc(word z[], size_t z_size,
 
       const word y = z_i[0] * u;
 
-      /*
+#if 1
       bigint_linmul3(ws, x, x_size, y);
       bigint_add2(z_i, z_size - i, ws, x_size+1);
-      */
+#else
       word carry = 0;
 
       for(size_t j = 0; j != blocks_of_8; j += 8)
@@ -53,6 +53,7 @@ void bigint_monty_redc(word z[], size_t z_size,
          ++z_i[j];
          carry = !z_i[j];
          }
+#endif
       }
 
    word borrow = 0;
@@ -67,6 +68,34 @@ void bigint_monty_redc(word z[], size_t z_size,
    clear_mem(z + x_size + 1, z_size - x_size - 1);
    }
 
+void bigint_monty_mul(word z[], size_t z_size,
+                      const word x[], size_t x_size, size_t x_sw,
+                      const word y[], size_t y_size, size_t y_sw,
+                      const word p[], size_t p_size, word p_dash,
+                      word workspace[])
+   {
+   bigint_mul(&z[0], z_size, &workspace[0],
+              &x[0], x_size, x_sw,
+              &y[0], y_size, y_sw);
+
+   bigint_monty_redc(&z[0], z_size,
+                     &workspace[0],
+                     &p[0], p_size, p_dash);
+
+   }
+
+void bigint_monty_sqr(word z[], size_t z_size,
+                      const word x[], size_t x_size, size_t x_sw,
+                      const word p[], size_t p_size, word p_dash,
+                      word workspace[])
+   {
+   bigint_sqr(&z[0], z_size, &workspace[0],
+              &x[0], x_size, x_sw);
+
+   bigint_monty_redc(&z[0], z_size, &workspace[0],
+                     &p[0], p_size, p_dash);
+   }
+
 }
 
 }
diff --git a/src/math/numbertheory/powm_mnt.cpp b/src/math/numbertheory/powm_mnt.cpp
index 421470364..0f674ba03 100644
--- a/src/math/numbertheory/powm_mnt.cpp
+++ b/src/math/numbertheory/powm_mnt.cpp
@@ -33,13 +33,12 @@ void Montgomery_Exponentiator::set_base(const BigInt& base)
    SecureVector<word> workspace(z.size());
 
    g[0] = (base >= modulus) ? (base % modulus) : base;
-   bigint_mul(&z[0], z.size(), &workspace[0],
-              g[0].data(), g[0].size(), g[0].sig_words(),
-              R2.data(), R2.size(), R2.sig_words());
 
-   bigint_monty_redc(&z[0], z.size(),
-                     &workspace[0],
-                     modulus.data(), mod_words, mod_prime);
+   bigint_monty_mul(&z[0], z.size(),
+                    g[0].data(), g[0].size(), g[0].sig_words(),
+                    R2.data(), R2.size(), R2.sig_words(),
+                    modulus.data(), mod_words, mod_prime,
+                    &workspace[0]);
 
    g[0].assign(&z[0], mod_words + 1);
 
@@ -52,13 +51,11 @@ void Montgomery_Exponentiator::set_base(const BigInt& base)
       const size_t y_sig = y.sig_words();
 
       zeroise(z);
-      bigint_mul(&z[0], z.size(), &workspace[0],
-                 x.data(), x.size(), x_sig,
-                 y.data(), y.size(), y_sig);
-
-      bigint_monty_redc(&z[0], z.size(),
-                        &workspace[0],
-                        modulus.data(), mod_words, mod_prime);
+      bigint_monty_mul(&z[0], z.size(),
+                       x.data(), x.size(), x_sig,
+                       y.data(), y.size(), y_sig,
+                       modulus.data(), mod_words, mod_prime,
+                       &workspace[0]);
 
       g[i].assign(&z[0], mod_words + 1);
       }
@@ -80,12 +77,11 @@ BigInt Montgomery_Exponentiator::execute() const
       for(size_t k = 0; k != window_bits; ++k)
          {
          zeroise(z);
-         bigint_sqr(&z[0], z.size(), &workspace[0],
-                    x.data(), x.size(), x.sig_words());
 
-         bigint_monty_redc(&z[0], z.size(),
-                           &workspace[0],
-                           modulus.data(), mod_words, mod_prime);
+         bigint_monty_sqr(&z[0], z.size(),
+                          x.data(), x.size(), x.sig_words(),
+                          modulus.data(), mod_words, mod_prime,
+                          &workspace[0]);
 
          x.assign(&z[0], mod_words + 1);
          }
@@ -95,13 +91,11 @@ BigInt Montgomery_Exponentiator::execute() const
          const BigInt& y = g[nibble-1];
 
          zeroise(z);
-         bigint_mul(&z[0], z.size(), &workspace[0],
-                    x.data(), x.size(), x.sig_words(),
-                    y.data(), y.size(), y.sig_words());
-
-         bigint_monty_redc(&z[0], z.size(),
-                           &workspace[0],
-                           modulus.data(), mod_words, mod_prime);
+         bigint_monty_mul(&z[0], z.size(),
+                          x.data(), x.size(), x.sig_words(),
+                          y.data(), y.size(), y.sig_words(),
+                          modulus.data(), mod_words, mod_prime,
+                          &workspace[0]);
 
          x.assign(&z[0], mod_words + 1);
          }