Modify bigint_monty_redc to take an additional workspace argument.

Modify it to avoid a timing condition during the compare at the end;
this is done by always doing the subtraction, and then copying to the
output either the pre-subtraction or post-subtraction value depending
on if the final borrow was set or not.

5 files changed, 83 insertions, 71 deletions

diff --git a/src/math/bigint/monty_generic/mp_monty.cpp b/src/math/bigint/monty_generic/mp_monty.cpp
index ba1071e21..d8c88a7e7 100644
--- a/src/math/bigint/monty_generic/mp_monty.cpp
+++ b/src/math/bigint/monty_generic/mp_monty.cpp
@@ -1,6 +1,6 @@
 /*
 * Montgomery Reduction
-* (C) 1999-2008 Jack Lloyd
+* (C) 1999-2010 Jack Lloyd
 *     2006 Luca Piccarreta
 *
 * Distributed under the terms of the Botan license
@@ -9,6 +9,7 @@
 #include <botan/internal/mp_core.h>
 #include <botan/internal/mp_asm.h>
 #include <botan/internal/mp_asmi.h>
+#include <botan/mem_ops.h>
 
 namespace Botan {
 
@@ -18,7 +19,9 @@ extern "C" {
 * Montgomery Reduction Algorithm
 */
 void bigint_monty_redc(word z[], u32bit z_size,
-                       const word x[], u32bit x_size, word u)
+                       word ws[],
+                       const word x[], u32bit x_size,
+                       word u)
    {
    const u32bit blocks_of_8 = x_size - (x_size % 8);
 
@@ -28,6 +31,10 @@ void bigint_monty_redc(word z[], u32bit z_size,
 
       const word y = z_i[0] * u;
 
+      /*
+      bigint_linmul3(ws, x, x_size, y);
+      bigint_add2(z_i, z_size - i, ws, x_size+1);
+      */
       word carry = 0;
 
       for(u32bit j = 0; j != blocks_of_8; j += 8)
@@ -40,6 +47,7 @@ void bigint_monty_redc(word z[], u32bit z_size,
       carry = (z_sum < z_i[x_size]);
       z_i[x_size] = z_sum;
 
+      // Note: not constant time
       for(u32bit j = x_size + 1; carry && j != z_size - i; ++j)
          {
          ++z_i[j];
@@ -47,30 +55,17 @@ void bigint_monty_redc(word z[], u32bit z_size,
          }
       }
 
-   // Check if z[x_size...x_size+1] >= x[0...x_size] using bigint_cmp (inlined)
-   if(!z[x_size + x_size])
-      {
-      for(u32bit i = x_size; i > 0; --i)
-         {
-         if(z[x_size + i - 1] > x[i-1])
-            break;
-
-         if(z[x_size + i - 1] < x[i-1])
-            return;
-         }
-      }
+   word borrow = 0;
+   for(u32bit i = 0; i != x_size; ++i)
+      ws[i] = word_sub(z[x_size + i], x[i], &borrow);
 
-   // If the compare above is true, subtract using bigint_sub2 (inlined)
-   word carry = 0;
+   ws[x_size] = word_sub(z[x_size+x_size], 0, &borrow);
 
-   for(u32bit i = 0; i != blocks_of_8; i += 8)
-      carry = word8_sub2(z + x_size + i, x + i, carry);
+   copy_mem(ws + x_size + 1, z + x_size, x_size + 1);
 
-   for(u32bit i = blocks_of_8; i != x_size; ++i)
-      z[x_size + i] = word_sub(z[x_size + i], x[i], &carry);
+   clear_mem(z, z_size);
 
-   if(carry)
-      --z[x_size+x_size];
+   copy_mem(z, ws + borrow*(x_size+1), x_size + 1);
    }
 
 }
diff --git a/src/math/bigint/mp_core.h b/src/math/bigint/mp_core.h
index 4bc04ed52..63082795f 100644
--- a/src/math/bigint/mp_core.h
+++ b/src/math/bigint/mp_core.h
@@ -1,6 +1,6 @@
 /*
 * MPI Algorithms
-* (C) 1999-2007 Jack Lloyd
+* (C) 1999-2010 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
@@ -35,7 +35,7 @@ word bigint_add3_nc(word z[],
                     const word x[], u32bit x_size,
                     const word y[], u32bit y_size);
 
-void bigint_sub2(word x[], u32bit x_size,
+word bigint_sub2(word x[], u32bit x_size,
                  const word y[], u32bit y_size);
 
 /**
@@ -43,7 +43,7 @@ void bigint_sub2(word x[], u32bit x_size,
 */
 void bigint_sub2_rev(word x[], const word y[], u32bit y_size);
 
-void bigint_sub3(word z[],
+word bigint_sub3(word z[],
                  const word x[], u32bit x_size,
                  const word y[], u32bit y_size);
 
@@ -79,12 +79,20 @@ void bigint_linmul3(word z[], const word x[], u32bit 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)
+* @param workspace array of at least 2*(x_size+1) words
+* @param x modulus
+* @param x_size size of x
+* @param u Montgomery value
 */
 void bigint_monty_redc(word z[], u32bit z_size,
-                       const word x[], u32bit x_size, word u);
+                       word workspace[],
+                       const word x[], u32bit x_size,
+                       word u);
 
 /*
-* Misc Utility Operations
+* Division operation
 */
 u32bit bigint_divcore(word q, word y2, word y1,
                       word x3, word x2, word x1);
diff --git a/src/math/numbertheory/point_gfp.cpp b/src/math/numbertheory/point_gfp.cpp
index b593443f7..1f6c1ddf6 100644
--- a/src/math/numbertheory/point_gfp.cpp
+++ b/src/math/numbertheory/point_gfp.cpp
@@ -36,6 +36,8 @@ void PointGFp::monty_mult(BigInt& z,
                           const BigInt& x, const BigInt& y,
                           MemoryRegion<word>& workspace) const
    {
+   //assert(&z != &x && &z != &y);
+
    if(x.is_zero() || y.is_zero())
       {
       z = 0;
@@ -46,23 +48,26 @@ void PointGFp::monty_mult(BigInt& z,
    const u32bit p_size = curve.get_p_words();
    const word p_dash = curve.get_p_dash();
 
-   zeroise(workspace);
+   SecureVector<word>& z_reg = z.get_reg();
+   z_reg.resize(2*p_size+1);
+   zeroise(z_reg);
 
-   bigint_mul(workspace, workspace.size(), 0,
+   bigint_mul(&z_reg[0], z_reg.size(),
+              &workspace[0],
               x.data(), x.size(), x.sig_words(),
               y.data(), y.size(), y.sig_words());
 
-   bigint_monty_redc(workspace, workspace.size(),
+   bigint_monty_redc(&z[0], z.size(),
+                     &workspace[0],
                      p.data(), p_size, p_dash);
-
-   z.get_reg().resize(p_size);
-   copy_mem(&z.get_reg()[0], &workspace[p_size], p_size);
    }
 
 // Montgomery squaring
 void PointGFp::monty_sqr(BigInt& z, const BigInt& x,
                          MemoryRegion<word>& workspace) const
    {
+   //assert(&z != &x);
+
    if(x.is_zero())
       {
       z = 0;
@@ -73,16 +78,17 @@ void PointGFp::monty_sqr(BigInt& z, const BigInt& x,
    const u32bit p_size = curve.get_p_words();
    const word p_dash = curve.get_p_dash();
 
-   zeroise(workspace);
+   SecureVector<word>& z_reg = z.get_reg();
+   z_reg.resize(2*p_size+1);
+   zeroise(z_reg);
 
-   bigint_sqr(workspace, workspace.size(), 0,
+   bigint_sqr(&z[0], z.size(),
+              &workspace[0],
               x.data(), x.size(), x.sig_words());
 
-   bigint_monty_redc(workspace, workspace.size(),
+   bigint_monty_redc(&z[0], z.size(),
+                     &workspace[0],
                      p.data(), p_size, p_dash);
-
-   z.get_reg().resize(p_size);
-   copy_mem(&z.get_reg()[0], &workspace[p_size], p_size);
    }
 
 // Point addition
@@ -152,7 +158,7 @@ void PointGFp::add(const PointGFp& rhs, Workspace& workspace)
 
    monty_mult(S2, U2, H, ws);
 
-   monty_mult(U2, U1, U2, ws);
+   U2 = monty_mult(U1, U2, ws);
 
    monty_sqr(x, r, ws);
    x -= S2;
diff --git a/src/math/numbertheory/point_gfp.h b/src/math/numbertheory/point_gfp.h
index 5b3e32c7d..42baa7d2c 100644
--- a/src/math/numbertheory/point_gfp.h
+++ b/src/math/numbertheory/point_gfp.h
@@ -179,6 +179,7 @@ class BOTAN_DLL PointGFp
 
       /**
       * Montgomery multiplication/reduction
+      * @warning z cannot alias x or y
       * @param z output
       * @param x first multiplicand
       * @param y second multiplicand
@@ -203,6 +204,7 @@ class BOTAN_DLL PointGFp
 
       /**
       * Montgomery squaring/reduction
+      * @warning z cannot alias x
       * @param z output
       * @param x multiplicand
       * @param workspace temp space
diff --git a/src/math/numbertheory/powm_mnt.cpp b/src/math/numbertheory/powm_mnt.cpp
index 7e6b2c811..8b915390c 100644
--- a/src/math/numbertheory/powm_mnt.cpp
+++ b/src/math/numbertheory/powm_mnt.cpp
@@ -1,6 +1,6 @@
 /*
 * Montgomery Exponentiation
-* (C) 1999-2007 Jack Lloyd
+* (C) 1999-2010 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
@@ -11,25 +11,6 @@
 
 namespace Botan {
 
-namespace {
-
-/*
-* Montgomery Reduction
-*/
-inline void montgomery_reduce(BigInt& out, MemoryRegion<word>& z_buf,
-                              const BigInt& x_bn, u32bit x_size, word u)
-   {
-   const word* x = x_bn.data();
-   word* z = &z_buf[0];
-   u32bit z_size = z_buf.size();
-
-   bigint_monty_redc(z, z_size, x, x_size, u);
-
-   out.get_reg().set(z + x_size, x_size + 1);
-   }
-
-}
-
 /*
 * Set the exponent
 */
@@ -56,14 +37,18 @@ void Montgomery_Exponentiator::set_base(const BigInt& base)
               g[0].data(), g[0].size(), g[0].sig_words(),
               R2.data(), R2.size(), R2.sig_words());
 
-   montgomery_reduce(g[0], z, modulus, mod_words, mod_prime);
+   bigint_monty_redc(&z[0], z.size(),
+                     &workspace[0],
+                     modulus.data(), mod_words, mod_prime);
+
+   g[0].get_reg().set(&z[0], mod_words + 1);
 
    const BigInt& x = g[0];
    const u32bit x_sig = x.sig_words();
 
-   for(u32bit j = 1; j != g.size(); ++j)
+   for(u32bit i = 1; i != g.size(); ++i)
       {
-      const BigInt& y = g[j-1];
+      const BigInt& y = g[i-1];
       const u32bit y_sig = y.sig_words();
 
       zeroise(z);
@@ -71,7 +56,11 @@ void Montgomery_Exponentiator::set_base(const BigInt& base)
                  x.data(), x.size(), x_sig,
                  y.data(), y.size(), y_sig);
 
-      montgomery_reduce(g[j], z, modulus, mod_words, mod_prime);
+      bigint_monty_redc(&z[0], z.size(),
+                        &workspace[0],
+                        modulus.data(), mod_words, mod_prime);
+
+      g[i].get_reg().set(&z[0], mod_words + 1);
       }
    }
 
@@ -86,7 +75,7 @@ BigInt Montgomery_Exponentiator::execute() const
    SecureVector<word> z(2 * (mod_words + 1));
    SecureVector<word> workspace(2 * (mod_words + 1));
 
-   for(u32bit j = exp_nibbles; j > 0; --j)
+   for(u32bit i = exp_nibbles; i > 0; --i)
       {
       for(u32bit k = 0; k != window_bits; ++k)
          {
@@ -94,10 +83,14 @@ BigInt Montgomery_Exponentiator::execute() const
          bigint_sqr(&z[0], z.size(), &workspace[0],
                     x.data(), x.size(), x.sig_words());
 
-         montgomery_reduce(x, z, modulus, mod_words, mod_prime);
+         bigint_monty_redc(&z[0], z.size(),
+                           &workspace[0],
+                           modulus.data(), mod_words, mod_prime);
+
+         x.get_reg().set(&z[0], mod_words + 1);
          }
 
-      u32bit nibble = exp.get_substring(window_bits*(j-1), window_bits);
+      u32bit nibble = exp.get_substring(window_bits*(i-1), window_bits);
       if(nibble)
          {
          const BigInt& y = g[nibble-1];
@@ -107,14 +100,22 @@ BigInt Montgomery_Exponentiator::execute() const
                     x.data(), x.size(), x.sig_words(),
                     y.data(), y.size(), y.sig_words());
 
-         montgomery_reduce(x, z, modulus, mod_words, mod_prime);
+         bigint_monty_redc(&z[0], z.size(),
+                           &workspace[0],
+                           modulus.data(), mod_words, mod_prime);
+
+         x.get_reg().set(&z[0], mod_words + 1);
          }
       }
 
-   zeroise(z);
-   z.copy(x.data(), x.size());
+   x.get_reg().resize(2*mod_words+1);
+
+   bigint_monty_redc(&x[0], x.size(),
+                     &workspace[0],
+                     modulus.data(), mod_words, mod_prime);
+
+   x.get_reg().resize(mod_words+1);
 
-   montgomery_reduce(x, z, modulus, mod_words, mod_prime);
    return x;
    }