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.

3 files changed, 53 insertions, 44 deletions

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;
    }