diff options
| -rw-r--r-- | src/math/bigint/monty_generic/mp_monty.cpp | 39 | ||||
| -rw-r--r-- | src/math/bigint/mp_core.h | 18 | ||||
| -rw-r--r-- | src/math/numbertheory/point_gfp.cpp | 32 | ||||
| -rw-r--r-- | src/math/numbertheory/point_gfp.h | 2 | ||||
| -rw-r--r-- | src/math/numbertheory/powm_mnt.cpp | 63 |
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; } |