aboutsummaryrefslogtreecommitdiffstats
path: root/src/math/numbertheory
diff options
context:
space:
mode:
Diffstat (limited to 'src/math/numbertheory')
-rw-r--r--src/math/numbertheory/point_gfp.cpp32
-rw-r--r--src/math/numbertheory/point_gfp.h2
-rw-r--r--src/math/numbertheory/powm_mnt.cpp63
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;
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-28 05:54:57 +0000