aboutsummaryrefslogtreecommitdiffstats
path: root/src/math
diff options
context:
space:
mode:
Diffstat (limited to 'src/math')
-rw-r--r--src/math/bigint/bigint.cpp54
-rw-r--r--src/math/bigint/bigint.h7
-rw-r--r--src/math/ec_gfp/curve_gfp.h (renamed from src/math/numbertheory/curve_gfp.h)57
-rw-r--r--src/math/ec_gfp/info.txt16
-rw-r--r--src/math/ec_gfp/point_gfp.cpp (renamed from src/math/numbertheory/point_gfp.cpp)267
-rw-r--r--src/math/ec_gfp/point_gfp.h (renamed from src/math/numbertheory/point_gfp.h)54
-rw-r--r--src/math/mp/info.txt6
-rw-r--r--src/math/mp/monty_generic/info.txt5
-rw-r--r--src/math/mp/monty_generic/mp_monty.cpp72
-rw-r--r--src/math/mp/mp_asm.cpp3
-rw-r--r--src/math/mp/mp_asm64/info.txt3
-rw-r--r--src/math/mp/mp_core.h36
-rw-r--r--src/math/mp/mp_generic/mp_asm.h2
-rw-r--r--src/math/mp/mp_monty.cpp99
-rw-r--r--src/math/mp/mp_msvc64/info.txt2
-rw-r--r--src/math/mp/mp_mulop.cpp (renamed from src/math/mp/mulop_generic/mp_mulop.cpp)0
-rw-r--r--src/math/mp/mp_x86_32/info.txt (renamed from src/math/mp/mp_ia32/info.txt)2
-rw-r--r--src/math/mp/mp_x86_32/mp_asm.h (renamed from src/math/mp/mp_ia32/mp_asm.h)2
-rw-r--r--src/math/mp/mp_x86_32/mp_asmi.h (renamed from src/math/mp/mp_ia32/mp_asmi.h)0
-rw-r--r--src/math/mp/mp_x86_32_msvc/info.txt (renamed from src/math/mp/mp_ia32_msvc/info.txt)2
-rw-r--r--src/math/mp/mp_x86_32_msvc/mp_asmi.h (renamed from src/math/mp/mp_ia32_msvc/mp_asmi.h)0
-rw-r--r--src/math/mp/mp_x86_64/info.txt (renamed from src/math/mp/mp_amd64/info.txt)2
-rw-r--r--src/math/mp/mp_x86_64/mp_asm.h (renamed from src/math/mp/mp_amd64/mp_asm.h)4
-rw-r--r--src/math/mp/mp_x86_64/mp_asmi.h (renamed from src/math/mp/mp_amd64/mp_asmi.h)2
-rw-r--r--src/math/mp/mulop_generic/info.txt5
-rw-r--r--src/math/numbertheory/info.txt7
-rw-r--r--src/math/numbertheory/pow_mod.cpp7
-rw-r--r--src/math/numbertheory/powm_mnt.cpp58
-rw-r--r--src/math/numbertheory/reducer.cpp64
-rw-r--r--src/math/numbertheory/reducer.h4
30 files changed, 463 insertions, 379 deletions
diff --git a/src/math/bigint/bigint.cpp b/src/math/bigint/bigint.cpp
index a49335e75..ae536813f 100644
--- a/src/math/bigint/bigint.cpp
+++ b/src/math/bigint/bigint.cpp
@@ -1,6 +1,6 @@
/*
* BigInt Base
-* (C) 1999-2008 Jack Lloyd
+* (C) 1999-2011 Jack Lloyd
*
* Distributed under the terms of the Botan license
*/
@@ -26,8 +26,8 @@ BigInt::BigInt(u64bit n)
const size_t limbs_needed = sizeof(u64bit) / sizeof(word);
reg.resize(4*limbs_needed);
- for(size_t j = 0; j != limbs_needed; ++j)
- reg[j] = ((n >> (j*MP_WORD_BITS)) & MP_WORD_MASK);
+ for(size_t i = 0; i != limbs_needed; ++i)
+ reg[i] = ((n >> (i*MP_WORD_BITS)) & MP_WORD_MASK);
}
/*
@@ -190,16 +190,35 @@ u32bit BigInt::get_substring(size_t offset, size_t length) const
throw Invalid_Argument("BigInt::get_substring: Substring size too big");
u64bit piece = 0;
- for(size_t j = 0; j != 8; ++j)
- piece = (piece << 8) | byte_at((offset / 8) + (7-j));
+ for(size_t i = 0; i != 8; ++i)
+ {
+ const byte part = byte_at((offset / 8) + (7-i));
+ piece = (piece << 8) | part;
+ }
- u64bit mask = (1 << length) - 1;
- size_t shift = (offset % 8);
+ const u64bit mask = (static_cast<u64bit>(1) << length) - 1;
+ const size_t shift = (offset % 8);
return static_cast<u32bit>((piece >> shift) & mask);
}
/*
+* Convert this number to a u32bit, if possible
+*/
+u32bit BigInt::to_u32bit() const
+ {
+ if(is_negative())
+ throw Encoding_Error("BigInt::to_u32bit: Number is negative");
+ if(bits() >= 32)
+ throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
+
+ u32bit out = 0;
+ for(u32bit j = 0; j != 4; ++j)
+ out = (out << 8) | byte_at(3-j);
+ return out;
+ }
+
+/*
* Set bit number n
*/
void BigInt::set_bit(size_t n)
@@ -233,8 +252,8 @@ void BigInt::mask_bits(size_t n)
const word mask = (static_cast<word>(1) << (n % MP_WORD_BITS)) - 1;
if(top_word < size())
- for(size_t j = top_word + 1; j != size(); ++j)
- reg[j] = 0;
+ for(size_t i = top_word + 1; i != size(); ++i)
+ reg[i] = 0;
reg[top_word] &= mask;
}
@@ -340,8 +359,8 @@ BigInt BigInt::abs() const
void BigInt::binary_encode(byte output[]) const
{
const size_t sig_bytes = bytes();
- for(size_t j = 0; j != sig_bytes; ++j)
- output[sig_bytes-j-1] = byte_at(j);
+ for(size_t i = 0; i != sig_bytes; ++i)
+ output[sig_bytes-i-1] = byte_at(i);
}
/*
@@ -354,14 +373,15 @@ void BigInt::binary_decode(const byte buf[], size_t length)
clear();
reg.resize(round_up<size_t>((length / WORD_BYTES) + 1, 8));
- for(size_t j = 0; j != length / WORD_BYTES; ++j)
+ for(size_t i = 0; i != length / WORD_BYTES; ++i)
{
- size_t top = length - WORD_BYTES*j;
- for(size_t k = WORD_BYTES; k > 0; --k)
- reg[j] = (reg[j] << 8) | buf[top - k];
+ const size_t top = length - WORD_BYTES*i;
+ for(size_t j = WORD_BYTES; j > 0; --j)
+ reg[i] = (reg[i] << 8) | buf[top - j];
}
- for(size_t j = 0; j != length % WORD_BYTES; ++j)
- reg[length / WORD_BYTES] = (reg[length / WORD_BYTES] << 8) | buf[j];
+
+ for(size_t i = 0; i != length % WORD_BYTES; ++i)
+ reg[length / WORD_BYTES] = (reg[length / WORD_BYTES] << 8) | buf[i];
}
/*
diff --git a/src/math/bigint/bigint.h b/src/math/bigint/bigint.h
index 5b3dcc2dd..06e3ecd2f 100644
--- a/src/math/bigint/bigint.h
+++ b/src/math/bigint/bigint.h
@@ -218,6 +218,13 @@ class BOTAN_DLL BigInt
u32bit get_substring(size_t offset, size_t length) const;
/**
+ * Convert this value into a u32bit, if it is in the range
+ * [0 ... 2**32-1], or otherwise throw an exception.
+ * @result the value as a u32bit if conversion is possible
+ */
+ u32bit to_u32bit() const;
+
+ /**
* @param n the offset to get a byte from
* @result byte at offset n
*/
diff --git a/src/math/numbertheory/curve_gfp.h b/src/math/ec_gfp/curve_gfp.h
index 1ab803ec9..9867f82fe 100644
--- a/src/math/numbertheory/curve_gfp.h
+++ b/src/math/ec_gfp/curve_gfp.h
@@ -2,7 +2,7 @@
* Elliptic curves over GF(p)
*
* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke
-* 2010 Jack Lloyd
+* 2010-2011 Jack Lloyd
*
* Distributed under the terms of the Botan license
*/
@@ -11,7 +11,6 @@
#define BOTAN_GFP_CURVE_H__
#include <botan/numthry.h>
-#include <botan/reducer.h>
namespace Botan {
@@ -34,18 +33,15 @@ class BOTAN_DLL CurveGFp
* @param b second coefficient
*/
CurveGFp(const BigInt& p, const BigInt& a, const BigInt& b) :
- p(p), a(a), b(b), reducer_p(p)
+ p(p), a(a), b(b), p_words(p.sig_words())
{
- r = 1;
- r <<= p.sig_words() * BOTAN_MP_WORD_BITS;
+ BigInt r(BigInt::Power2, p_words * BOTAN_MP_WORD_BITS);
- r_inv = inverse_mod(r, p);
+ p_dash = (((r * inverse_mod(r, p)) - 1) / p).word_at(0);
- p_dash = (((r * r_inv) - 1) / p).word_at(0);
-
- a_r = reducer_p.multiply(a, r);
-
- p_words = p.sig_words();
+ r2 = (r * r) % p;
+ a_r = (a * r) % p;
+ b_r = (b * r) % p;
}
// CurveGFp(const CurveGFp& other) = default;
@@ -68,19 +64,19 @@ class BOTAN_DLL CurveGFp
const BigInt& get_p() const { return p; }
/**
- * @return Montgomery parameter r
+ * @return Montgomery parameter r^2 % p
*/
- const BigInt& get_r() const { return r; }
+ const BigInt& get_r2() const { return r2; }
/**
- * @return Montgomery parameter r^-1
+ * @return a * r mod p
*/
- const BigInt& get_r_inv() const { return r_inv; }
+ const BigInt& get_a_r() const { return a_r; }
/**
- * @return a * r mod p
+ * @return b * r mod p
*/
- const BigInt& get_a_r() const { return a_r; }
+ const BigInt& get_b_r() const { return b_r; }
/**
* @return Montgomery parameter p-dash
@@ -93,23 +89,22 @@ class BOTAN_DLL CurveGFp
size_t get_p_words() const { return p_words; }
/**
- * @return modular reducer for p
- */
- const Modular_Reducer& mod_p() const { return reducer_p; }
-
- /**
* swaps the states of *this and other, does not throw
* @param other curve to swap values with
*/
void swap(CurveGFp& other)
{
+ std::swap(p, other.p);
+
std::swap(a, other.a);
std::swap(b, other.b);
- std::swap(p, other.p);
- std::swap(reducer_p, other.reducer_p);
- std::swap(r, other.r);
- std::swap(r_inv, other.r_inv);
+ std::swap(a_r, other.a_r);
+ std::swap(b_r, other.b_r);
+
+ std::swap(p_words, other.p_words);
+
+ std::swap(r2, other.r2);
std::swap(p_dash, other.p_dash);
}
@@ -120,7 +115,11 @@ class BOTAN_DLL CurveGFp
*/
bool operator==(const CurveGFp& other) const
{
- return (p == other.p && a == other.a && b == other.b);
+ /*
+ Relies on choice of R, but that is fixed by constructor based
+ on size of p
+ */
+ return (p == other.p && a_r == other.a_r && b_r == other.b_r);
}
private:
@@ -130,10 +129,8 @@ class BOTAN_DLL CurveGFp
size_t p_words; // cache of p.sig_words()
// Montgomery parameters
- BigInt r, r_inv, a_r;
+ BigInt r2, a_r, b_r;
word p_dash;
-
- Modular_Reducer reducer_p;
};
/**
diff --git a/src/math/ec_gfp/info.txt b/src/math/ec_gfp/info.txt
new file mode 100644
index 000000000..e6ee1d6bf
--- /dev/null
+++ b/src/math/ec_gfp/info.txt
@@ -0,0 +1,16 @@
+define EC_CURVE_GFP
+
+load_on auto
+
+<header:public>
+curve_gfp.h
+point_gfp.h
+</header:public>
+
+<source>
+point_gfp.cpp
+</source>
+
+<requires>
+numbertheory
+</requires>
diff --git a/src/math/numbertheory/point_gfp.cpp b/src/math/ec_gfp/point_gfp.cpp
index fab731d29..7ac6b4141 100644
--- a/src/math/numbertheory/point_gfp.cpp
+++ b/src/math/ec_gfp/point_gfp.cpp
@@ -1,40 +1,37 @@
/*
-* Arithmetic for point groups of elliptic curves over GF(p)
+* Point arithmetic on elliptic curves over GF(p)
*
* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke
-* 2008-2010 Jack Lloyd
+* 2008-2011 Jack Lloyd
*
* Distributed under the terms of the Botan license
*/
#include <botan/point_gfp.h>
#include <botan/numthry.h>
+#include <botan/reducer.h>
#include <botan/internal/mp_core.h>
namespace Botan {
PointGFp::PointGFp(const CurveGFp& curve) :
- curve(curve),
- coord_x(0),
- coord_y(curve.get_r()),
- coord_z(0)
+ curve(curve), ws(2 * (curve.get_p_words() + 2))
{
+ coord_x = 0;
+ coord_y = monty_mult(1, curve.get_r2());
+ coord_z = 0;
}
PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) :
- curve(curve)
+ curve(curve), ws(2 * (curve.get_p_words() + 2))
{
- const Modular_Reducer& mod_p = curve.mod_p();
-
- coord_x = mod_p.multiply(curve.get_r(), x);
- coord_y = mod_p.multiply(curve.get_r(), y);
- coord_z = mod_p.reduce(curve.get_r());
+ coord_x = monty_mult(x, curve.get_r2());
+ coord_y = monty_mult(y, curve.get_r2());
+ coord_z = monty_mult(1, curve.get_r2());
}
// Montgomery multiplication
-void PointGFp::monty_mult(BigInt& z,
- const BigInt& x, const BigInt& y,
- MemoryRegion<word>& workspace) const
+void PointGFp::monty_mult(BigInt& z, const BigInt& x, const BigInt& y) const
{
//assert(&z != &x && &z != &y);
@@ -52,19 +49,15 @@ void PointGFp::monty_mult(BigInt& z,
z_reg.resize(2*p_size+1);
zeroise(z_reg);
- 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(&z[0], z.size(),
- &workspace[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
-void PointGFp::monty_sqr(BigInt& z, const BigInt& x,
- MemoryRegion<word>& workspace) const
+void PointGFp::monty_sqr(BigInt& z, const BigInt& x) const
{
//assert(&z != &x);
@@ -82,17 +75,14 @@ void PointGFp::monty_sqr(BigInt& z, const BigInt& x,
z_reg.resize(2*p_size+1);
zeroise(z_reg);
- bigint_sqr(&z[0], z.size(),
- &workspace[0],
- x.data(), x.size(), x.sig_words());
-
- bigint_monty_redc(&z[0], z.size(),
- &workspace[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
-void PointGFp::add(const PointGFp& rhs, Workspace& workspace)
+void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
{
if(is_zero())
{
@@ -106,9 +96,6 @@ void PointGFp::add(const PointGFp& rhs, Workspace& workspace)
const BigInt& p = curve.get_p();
- MemoryRegion<word>& ws = workspace.ws_monty;
- std::vector<BigInt>& ws_bn = workspace.ws_bn;
-
BigInt& rhs_z2 = ws_bn[0];
BigInt& U1 = ws_bn[1];
BigInt& S1 = ws_bn[2];
@@ -120,17 +107,13 @@ void PointGFp::add(const PointGFp& rhs, Workspace& workspace)
BigInt& H = ws_bn[6];
BigInt& r = ws_bn[7];
- BigInt& x = ws_bn[8];
- BigInt& y = ws_bn[9];
- BigInt& z = ws_bn[10];
+ monty_sqr(rhs_z2, rhs.coord_z);
+ monty_mult(U1, coord_x, rhs_z2);
+ monty_mult(S1, coord_y, monty_mult(rhs.coord_z, rhs_z2));
- monty_sqr(rhs_z2, rhs.coord_z, ws);
- monty_mult(U1, coord_x, rhs_z2, ws);
- monty_mult(S1, coord_y, monty_mult(rhs.coord_z, rhs_z2, ws), ws);
-
- monty_sqr(lhs_z2, coord_z, ws);
- monty_mult(U2, rhs.coord_x, lhs_z2, ws);
- monty_mult(S2, rhs.coord_y, monty_mult(coord_z, lhs_z2, ws), ws);
+ monty_sqr(lhs_z2, coord_z);
+ monty_mult(U2, rhs.coord_x, lhs_z2);
+ monty_mult(S2, rhs.coord_y, monty_mult(coord_z, lhs_z2));
H = U2;
H -= U1;
@@ -146,7 +129,7 @@ void PointGFp::add(const PointGFp& rhs, Workspace& workspace)
{
if(r.is_zero())
{
- mult2(workspace);
+ mult2(ws_bn);
return;
}
@@ -154,36 +137,32 @@ void PointGFp::add(const PointGFp& rhs, Workspace& workspace)
return;
}
- monty_sqr(U2, H, ws);
+ monty_sqr(U2, H);
- monty_mult(S2, U2, H, ws);
+ monty_mult(S2, U2, H);
- U2 = monty_mult(U1, U2, ws);
+ U2 = monty_mult(U1, U2);
- monty_sqr(x, r, ws);
- x -= S2;
- x -= (U2 << 1);
- while(x.is_negative())
- x += p;
+ monty_sqr(coord_x, r);
+ coord_x -= S2;
+ coord_x -= (U2 << 1);
+ while(coord_x.is_negative())
+ coord_x += p;
- U2 -= x;
+ U2 -= coord_x;
if(U2.is_negative())
U2 += p;
- monty_mult(y, r, U2, ws);
- y -= monty_mult(S1, S2, ws);
- if(y.is_negative())
- y += p;
-
- monty_mult(z, monty_mult(coord_z, rhs.coord_z, ws), H, ws);
+ monty_mult(coord_y, r, U2);
+ coord_y -= monty_mult(S1, S2);
+ if(coord_y.is_negative())
+ coord_y += p;
- coord_x = x;
- coord_y = y;
- coord_z = z;
+ monty_mult(coord_z, monty_mult(coord_z, rhs.coord_z), H);
}
// *this *= 2
-void PointGFp::mult2(Workspace& workspace)
+void PointGFp::mult2(std::vector<BigInt>& ws_bn)
{
if(is_zero())
return;
@@ -195,9 +174,6 @@ void PointGFp::mult2(Workspace& workspace)
const BigInt& p = curve.get_p();
- MemoryRegion<word>& ws = workspace.ws_monty;
- std::vector<BigInt>& ws_bn = workspace.ws_bn;
-
BigInt& y_2 = ws_bn[0];
BigInt& S = ws_bn[1];
BigInt& z4 = ws_bn[2];
@@ -208,27 +184,27 @@ void PointGFp::mult2(Workspace& workspace)
BigInt& y = ws_bn[7];
BigInt& z = ws_bn[8];
- monty_sqr(y_2, coord_y, ws);
+ monty_sqr(y_2, coord_y);
- monty_mult(S, coord_x, y_2, ws);
+ monty_mult(S, coord_x, y_2);
S <<= 2; // * 4
while(S >= p)
S -= p;
- monty_sqr(z4, monty_sqr(coord_z, ws), ws);
- monty_mult(a_z4, curve.get_a_r(), z4, ws);
+ monty_sqr(z4, monty_sqr(coord_z));
+ monty_mult(a_z4, curve.get_a_r(), z4);
- M = 3 * monty_sqr(coord_x, ws);
+ M = 3 * monty_sqr(coord_x);
M += a_z4;
while(M >= p)
M -= p;
- monty_sqr(x, M, ws);
+ monty_sqr(x, M);
x -= (S << 1);
while(x.is_negative())
x += p;
- monty_sqr(U, y_2, ws);
+ monty_sqr(U, y_2);
U <<= 3;
while(U >= p)
U -= p;
@@ -237,12 +213,12 @@ void PointGFp::mult2(Workspace& workspace)
while(S.is_negative())
S += p;
- monty_mult(y, M, S, ws);
+ monty_mult(y, M, S);
y -= U;
if(y.is_negative())
y += p;
- monty_mult(z, coord_y, coord_z, ws);
+ monty_mult(z, coord_y, coord_z);
z <<= 1;
if(z >= p)
z -= p;
@@ -255,7 +231,7 @@ void PointGFp::mult2(Workspace& workspace)
// arithmetic operators
PointGFp& PointGFp::operator+=(const PointGFp& rhs)
{
- Workspace ws(curve.get_p_words());
+ std::vector<BigInt> ws(9);
add(rhs, ws);
return *this;
}
@@ -278,6 +254,39 @@ PointGFp& PointGFp::operator*=(const BigInt& scalar)
return *this;
}
+PointGFp multi_exponentiate(const PointGFp& p1, const BigInt& z1,
+ const PointGFp& p2, const BigInt& z2)
+ {
+ const PointGFp p3 = p1 + p2;
+
+ PointGFp H(p1.curve); // create as zero
+ size_t bits_left = std::max(z1.bits(), z2.bits());
+
+ std::vector<BigInt> ws(9);
+
+ while(bits_left)
+ {
+ H.mult2(ws);
+
+ const bool z1_b = z1.get_bit(bits_left - 1);
+ const bool z2_b = z2.get_bit(bits_left - 1);
+
+ if(z1_b == true && z2_b == true)
+ H.add(p3, ws);
+ else if(z1_b)
+ H.add(p1, ws);
+ else if(z2_b)
+ H.add(p2, ws);
+
+ --bits_left;
+ }
+
+ if(z1.is_negative() != z2.is_negative())
+ H.negate();
+
+ return H;
+ }
+
PointGFp operator*(const BigInt& scalar, const PointGFp& point)
{
const CurveGFp& curve = point.get_curve();
@@ -285,7 +294,7 @@ PointGFp operator*(const BigInt& scalar, const PointGFp& point)
if(scalar.is_zero())
return PointGFp(curve); // zero point
- PointGFp::Workspace ws(curve.get_p_words());
+ std::vector<BigInt> ws(9);
if(scalar.abs() <= 2) // special cases for small values
{
@@ -304,6 +313,38 @@ PointGFp operator*(const BigInt& scalar, const PointGFp& point)
const size_t scalar_bits = scalar.bits();
+#if 0
+
+ PointGFp x1 = PointGFp(curve);
+ PointGFp x2 = point;
+
+ size_t bits_left = scalar_bits;
+
+ // Montgomery Ladder
+ while(bits_left)
+ {
+ const bool bit_set = scalar.get_bit(bits_left - 1);
+
+ if(bit_set)
+ {
+ x1.add(x2, ws);
+ x2.mult2(ws);
+ }
+ else
+ {
+ x2.add(x1, ws);
+ x1.mult2(ws);
+ }
+
+ --bits_left;
+ }
+
+ if(scalar.is_negative())
+ x1.negate();
+
+ return x1;
+
+#else
const size_t window_size = 4;
std::vector<PointGFp> Ps(1 << window_size);
@@ -345,6 +386,7 @@ PointGFp operator*(const BigInt& scalar, const PointGFp& point)
H.negate();
return H;
+#endif
}
BigInt PointGFp::get_affine_x() const
@@ -352,23 +394,13 @@ BigInt PointGFp::get_affine_x() const
if(is_zero())
throw Illegal_Transformation("Cannot convert zero point to affine");
- const Modular_Reducer& mod_p = curve.mod_p();
-
-#if 1
- BigInt x = mod_p.multiply(curve.get_r_inv(), coord_x);
- BigInt z = mod_p.multiply(curve.get_r_inv(), coord_z);
-
- BigInt z2 = mod_p.square(z);
- return mod_p.multiply(x, inverse_mod(z2, curve.get_p()));
-#else
-
- SecureVector<word> ws(2 * (curve.get_p_words() + 2));
+ const BigInt& r2 = curve.get_r2();
- BigInt z2 = monty_sqr(coord_z, ws);
+ BigInt z2 = monty_sqr(coord_z);
z2 = inverse_mod(z2, curve.get_p());
- z2 = mod_p.multiply(z2, curve.get_r());
- return monty_mult(coord_x, z2, ws);
-#endif
+
+ z2 = monty_mult(z2, r2);
+ return monty_mult(coord_x, z2);
}
BigInt PointGFp::get_affine_y() const
@@ -376,23 +408,12 @@ BigInt PointGFp::get_affine_y() const
if(is_zero())
throw Illegal_Transformation("Cannot convert zero point to affine");
- const Modular_Reducer& mod_p = curve.mod_p();
+ const BigInt& r2 = curve.get_r2();
-#if 1
- BigInt y = mod_p.multiply(curve.get_r_inv(), coord_y);
- BigInt z = mod_p.multiply(curve.get_r_inv(), coord_z);
-
- BigInt z3 = mod_p.cube(z);
- return mod_p.multiply(y, inverse_mod(z3, curve.get_p()));
-#else
-
- SecureVector<word> ws(2 * (curve.get_p_words() + 2));
-
- BigInt z3 = monty_mult(coord_z, monty_sqr(coord_z, ws), ws);
+ BigInt z3 = monty_mult(coord_z, monty_sqr(coord_z));
z3 = inverse_mod(z3, curve.get_p());
- z3 = mod_p.multiply(z3, curve.get_r());
- return monty_mult(coord_y, z3, ws);
-#endif
+ z3 = monty_mult(z3, r2);
+ return monty_mult(coord_y, z3);
}
bool PointGFp::on_the_curve() const
@@ -407,31 +428,28 @@ bool PointGFp::on_the_curve() const
if(is_zero())
return true;
- const Modular_Reducer& mod_p = curve.mod_p();
+ BigInt y2 = monty_mult(monty_sqr(coord_y), 1);
+ BigInt x3 = monty_mult(coord_x, monty_sqr(coord_x));
- BigInt x = mod_p.multiply(curve.get_r_inv(), coord_x);
- BigInt y = mod_p.multiply(curve.get_r_inv(), coord_y);
- BigInt z = mod_p.multiply(curve.get_r_inv(), coord_z);
+ BigInt ax = monty_mult(coord_x, curve.get_a_r());
- BigInt y2 = mod_p.square(y);
- BigInt x3 = mod_p.cube(x);
+ const BigInt& b_r = curve.get_b_r();
- BigInt ax = mod_p.multiply(x, curve.get_a());
+ BigInt z2 = monty_sqr(coord_z);
- if(z == 1)
+ if(coord_z == z2) // Is z equal to 1 (in Montgomery form)?
{
- if(mod_p.reduce(x3 + ax + curve.get_b()) != y2)
+ if(y2 != monty_mult(x3 + ax + b_r, 1))
return false;
}
- BigInt z2 = mod_p.square(z);
- BigInt z3 = mod_p.multiply(z, z2);
+ BigInt z3 = monty_mult(coord_z, z2);
- BigInt ax_z4 = mod_p.multiply(mod_p.multiply(z3, z), ax);
+ BigInt ax_z4 = monty_mult(ax, monty_sqr(z2));
- BigInt b_z6 = mod_p.multiply(curve.get_b(), mod_p.square(z3));
+ BigInt b_z6 = monty_mult(b_r, monty_sqr(z3));
- if(y2 != mod_p.reduce(x3 + ax_z4 + b_z6))
+ if(y2 != monty_mult(x3 + ax_z4 + b_z6, 1))
return false;
return true;
@@ -444,6 +462,7 @@ void PointGFp::swap(PointGFp& other)
coord_x.swap(other.coord_x);
coord_y.swap(other.coord_y);
coord_z.swap(other.coord_z);
+ ws.swap(other.ws);
}
bool PointGFp::operator==(const PointGFp& other) const
diff --git a/src/math/numbertheory/point_gfp.h b/src/math/ec_gfp/point_gfp.h
index 35ec6d503..b2b6fe2f0 100644
--- a/src/math/numbertheory/point_gfp.h
+++ b/src/math/ec_gfp/point_gfp.h
@@ -1,8 +1,8 @@
/*
-* Arithmetic for point groups of elliptic curves over GF(p)
+* Point arithmetic on elliptic curves over GF(p)
*
* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke
-* 2008-2010 Jack Lloyd
+* 2008-2011 Jack Lloyd
*
* Distributed under the terms of the Botan license
*/
@@ -99,6 +99,18 @@ class BOTAN_DLL PointGFp
friend BOTAN_DLL PointGFp operator*(const BigInt& scalar, const PointGFp& point);
/**
+ * Multiexponentiation
+ * @param p1 a point
+ * @param z1 a scalar
+ * @param p2 a point
+ * @param z2 a scalar
+ * @result (p1 * z1 + p2 * z2)
+ */
+ friend BOTAN_DLL PointGFp multi_exponentiate(
+ const PointGFp& p1, const BigInt& z1,
+ const PointGFp& p2, const BigInt& z2);
+
+ /**
* Negate this point
* @return *this
*/
@@ -153,27 +165,16 @@ class BOTAN_DLL PointGFp
bool operator==(const PointGFp& other) const;
private:
- class Workspace
- {
- public:
- Workspace(size_t p_words) :
- ws_monty(2*(p_words+2)), ws_bn(12) {}
-
- SecureVector<word> ws_monty;
- std::vector<BigInt> ws_bn;
- };
-
/**
* Montgomery multiplication/reduction
* @param x first multiplicand
* @param y second multiplicand
* @param workspace temp space
*/
- BigInt monty_mult(const BigInt& x, const BigInt& y,
- MemoryRegion<word>& workspace) const
+ BigInt monty_mult(const BigInt& x, const BigInt& y) const
{
BigInt result;
- monty_mult(result, x, y, workspace);
+ monty_mult(result, x, y);
return result;
}
@@ -183,22 +184,17 @@ class BOTAN_DLL PointGFp
* @param z output
* @param x first multiplicand
* @param y second multiplicand
- * @param workspace temp space
*/
- void monty_mult(BigInt& z,
- const BigInt& x, const BigInt& y,
- MemoryRegion<word>& workspace) const;
+ void monty_mult(BigInt& z, const BigInt& x, const BigInt& y) const;
/**
* Montgomery squaring/reduction
* @param x multiplicand
- * @param workspace temp space
*/
- BigInt monty_sqr(const BigInt& x,
- MemoryRegion<word>& workspace) const
+ BigInt monty_sqr(const BigInt& x) const
{
BigInt result;
- monty_sqr(result, x, workspace);
+ monty_sqr(result, x);
return result;
}
@@ -207,24 +203,24 @@ class BOTAN_DLL PointGFp
* @warning z cannot alias x
* @param z output
* @param x multiplicand
- * @param workspace temp space
*/
- void monty_sqr(BigInt& z, const BigInt& x,
- MemoryRegion<word>& workspace) const;
+ void monty_sqr(BigInt& z, const BigInt& x) const;
/**
* Point addition
+ * @param workspace temp space, at least 11 elements
*/
- void add(const PointGFp& other, Workspace& workspace);
+ void add(const PointGFp& other, std::vector<BigInt>& workspace);
/**
* Point doubling
- * @param workspace temp space
+ * @param workspace temp space, at least 9 elements
*/
- void mult2(Workspace& workspace);
+ void mult2(std::vector<BigInt>& workspace);
CurveGFp curve;
BigInt coord_x, coord_y, coord_z;
+ mutable SecureVector<word> ws; // workspace for Montgomery
};
// relational operators
diff --git a/src/math/mp/info.txt b/src/math/mp/info.txt
index a3c994d8b..bf7f40d3c 100644
--- a/src/math/mp/info.txt
+++ b/src/math/mp/info.txt
@@ -4,6 +4,8 @@ define BIGINT_MP
mp_asm.cpp
mp_comba.cpp
mp_karat.cpp
+mp_monty.cpp
+mp_mulop.cpp
mp_misc.cpp
mp_shift.cpp
</source>
@@ -17,7 +19,5 @@ mp_core.h
</header:internal>
<requires>
-mp_amd64|mp_msvc64|mp_asm64|mp_ia32|mp_ia32_msvc|mp_generic
-monty_generic
-mulop_generic
+mp_x86_64|mp_msvc64|mp_asm64|mp_x86_32|mp_x86_32_msvc|mp_generic
</requires>
diff --git a/src/math/mp/monty_generic/info.txt b/src/math/mp/monty_generic/info.txt
deleted file mode 100644
index cd05ccdc0..000000000
--- a/src/math/mp/monty_generic/info.txt
+++ /dev/null
@@ -1,5 +0,0 @@
-load_on dep
-
-<source>
-mp_monty.cpp
-</source>
diff --git a/src/math/mp/monty_generic/mp_monty.cpp b/src/math/mp/monty_generic/mp_monty.cpp
deleted file mode 100644
index d7f7e0306..000000000
--- a/src/math/mp/monty_generic/mp_monty.cpp
+++ /dev/null
@@ -1,72 +0,0 @@
-/*
-* Montgomery Reduction
-* (C) 1999-2010 Jack Lloyd
-* 2006 Luca Piccarreta
-*
-* Distributed under the terms of the Botan license
-*/
-
-#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 {
-
-extern "C" {
-
-/*
-* Montgomery Reduction Algorithm
-*/
-void bigint_monty_redc(word z[], size_t z_size,
- word ws[],
- const word x[], size_t x_size,
- word u)
- {
- const size_t blocks_of_8 = x_size - (x_size % 8);
-
- for(size_t i = 0; i != x_size; ++i)
- {
- word* z_i = z + i;
-
- 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(size_t j = 0; j != blocks_of_8; j += 8)
- carry = word8_madd3(z_i + j, x + j, y, carry);
-
- for(size_t j = blocks_of_8; j != x_size; ++j)
- z_i[j] = word_madd3(x[j], y, z_i[j], &carry);
-
- word z_sum = z_i[x_size] + carry;
- carry = (z_sum < z_i[x_size]);
- z_i[x_size] = z_sum;
-
- // Note: not constant time
- for(size_t j = x_size + 1; carry && j != z_size - i; ++j)
- {
- ++z_i[j];
- carry = !z_i[j];
- }
- }
-
- word borrow = 0;
- for(size_t i = 0; i != x_size; ++i)
- ws[i] = word_sub(z[x_size + i], x[i], &borrow);
-
- ws[x_size] = word_sub(z[x_size+x_size], 0, &borrow);
-
- copy_mem(ws + x_size + 1, z + x_size, x_size + 1);
-
- copy_mem(z, ws + borrow*(x_size+1), x_size + 1);
- clear_mem(z + x_size + 1, z_size - x_size - 1);
- }
-
-}
-
-}
diff --git a/src/math/mp/mp_asm.cpp b/src/math/mp/mp_asm.cpp
index d164c1d33..3ba52c4b1 100644
--- a/src/math/mp/mp_asm.cpp
+++ b/src/math/mp/mp_asm.cpp
@@ -67,7 +67,8 @@ word bigint_add3_nc(word z[], const word x[], size_t x_size,
*/
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
{
- x[x_size] += bigint_add2_nc(x, x_size, y, y_size);
+ if(bigint_add2_nc(x, x_size, y, y_size))
+ x[x_size] += 1;
}
/*
diff --git a/src/math/mp/mp_asm64/info.txt b/src/math/mp/mp_asm64/info.txt
index fd0242a7a..9af7c4ae7 100644
--- a/src/math/mp/mp_asm64/info.txt
+++ b/src/math/mp/mp_asm64/info.txt
@@ -8,7 +8,6 @@ mp_generic:mp_asmi.h
</header:internal>
<arch>
-#amd64
alpha
ia64
mips64
@@ -21,5 +20,5 @@ sparc64
# win, so it's probably worth using elsewhere.
<cc>
gcc
-sunwspro
+sunstudio
</cc>
diff --git a/src/math/mp/mp_core.h b/src/math/mp/mp_core.h
index e1692006e..40327b02b 100644
--- a/src/math/mp/mp_core.h
+++ b/src/math/mp/mp_core.h
@@ -77,19 +77,35 @@ 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)
-* @param workspace array of at least 2*(x_size+1) words
-* @param x modulus
-* @param x_size size of x
-* @param u Montgomery value
+* @param z integer to reduce (also output in first p_size+1 words)
+* @param z_size size of z (should be >= 2*p_size+1)
+* @param p modulus
+* @param p_size size of p
+* @param p_dash Montgomery value
+* @param workspace array of at least 2*(p_size+1) words
*/
void bigint_monty_redc(word z[], size_t z_size,
- word workspace[],
- const word x[], size_t x_size,
- word u);
+ const word p[], size_t p_size, word p_dash,
+ word workspace[]);
+
+/*
+* 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
diff --git a/src/math/mp/mp_generic/mp_asm.h b/src/math/mp/mp_generic/mp_asm.h
index ee46e1aa9..7c18343ef 100644
--- a/src/math/mp/mp_generic/mp_asm.h
+++ b/src/math/mp/mp_generic/mp_asm.h
@@ -14,7 +14,7 @@
#if (BOTAN_MP_WORD_BITS == 8)
typedef Botan::u16bit dword;
#elif (BOTAN_MP_WORD_BITS == 16)
- typedef Botan::size_t dword;
+ typedef Botan::u32bit dword;
#elif (BOTAN_MP_WORD_BITS == 32)
typedef Botan::u64bit dword;
#elif (BOTAN_MP_WORD_BITS == 64)
diff --git a/src/math/mp/mp_monty.cpp b/src/math/mp/mp_monty.cpp
new file mode 100644
index 000000000..d37fb5844
--- /dev/null
+++ b/src/math/mp/mp_monty.cpp
@@ -0,0 +1,99 @@
+/*
+* Montgomery Reduction
+* (C) 1999-2011 Jack Lloyd
+* 2006 Luca Piccarreta
+*
+* Distributed under the terms of the Botan license
+*/
+
+#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 {
+
+extern "C" {
+
+/*
+* Montgomery Reduction Algorithm
+*/
+void bigint_monty_redc(word z[], size_t z_size,
+ const word p[], size_t p_size,
+ word p_dash, word ws[])
+ {
+ const size_t blocks_of_8 = p_size - (p_size % 8);
+
+ for(size_t i = 0; i != p_size; ++i)
+ {
+ word* z_i = z + i;
+
+ const word y = z_i[0] * p_dash;
+
+ /*
+ bigint_linmul3(ws, p, p_size, y);
+ bigint_add2(z_i, z_size - i, ws, p_size+1);
+ */
+
+ word carry = 0;
+
+ for(size_t j = 0; j != blocks_of_8; j += 8)
+ carry = word8_madd3(z_i + j, p + j, y, carry);
+
+ for(size_t j = blocks_of_8; j != p_size; ++j)
+ z_i[j] = word_madd3(p[j], y, z_i[j], &carry);
+
+ word z_sum = z_i[p_size] + carry;
+ carry = (z_sum < z_i[p_size]);
+ z_i[p_size] = z_sum;
+
+ for(size_t j = p_size + 1; carry && j != z_size - i; ++j)
+ {
+ ++z_i[j];
+ carry = !z_i[j];
+ }
+ }
+
+ word borrow = 0;
+ for(size_t i = 0; i != p_size; ++i)
+ ws[i] = word_sub(z[p_size + i], p[i], &borrow);
+
+ ws[p_size] = word_sub(z[p_size+p_size], 0, &borrow);
+
+ copy_mem(ws + p_size + 1, z + p_size, p_size + 1);
+
+ copy_mem(z, ws + borrow*(p_size+1), p_size + 1);
+ clear_mem(z + p_size + 1, z_size - p_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 ws[])
+ {
+ bigint_mul(&z[0], z_size, &ws[0],
+ &x[0], x_size, x_sw,
+ &y[0], y_size, y_sw);
+
+ bigint_monty_redc(&z[0], z_size,
+ &p[0], p_size, p_dash,
+ &ws[0]);
+ }
+
+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 ws[])
+ {
+ bigint_sqr(&z[0], z_size, &ws[0],
+ &x[0], x_size, x_sw);
+
+ bigint_monty_redc(&z[0], z_size,
+ &p[0], p_size, p_dash,
+ &ws[0]);
+ }
+
+}
+
+}
diff --git a/src/math/mp/mp_msvc64/info.txt b/src/math/mp/mp_msvc64/info.txt
index 56ae05927..fa7d90fed 100644
--- a/src/math/mp/mp_msvc64/info.txt
+++ b/src/math/mp/mp_msvc64/info.txt
@@ -8,7 +8,7 @@ mp_generic:mp_asmi.h
</header:internal>
<arch>
-amd64
+x86_64
ia64
</arch>
diff --git a/src/math/mp/mulop_generic/mp_mulop.cpp b/src/math/mp/mp_mulop.cpp
index e6a8ba891..e6a8ba891 100644
--- a/src/math/mp/mulop_generic/mp_mulop.cpp
+++ b/src/math/mp/mp_mulop.cpp
diff --git a/src/math/mp/mp_ia32/info.txt b/src/math/mp/mp_x86_32/info.txt
index 1659f74cf..432f909f8 100644
--- a/src/math/mp/mp_ia32/info.txt
+++ b/src/math/mp/mp_x86_32/info.txt
@@ -8,7 +8,7 @@ mp_asmi.h
</header:internal>
<arch>
-ia32
+x86_32
</arch>
<cc>
diff --git a/src/math/mp/mp_ia32/mp_asm.h b/src/math/mp/mp_x86_32/mp_asm.h
index 4d3afc992..9be5680f8 100644
--- a/src/math/mp/mp_ia32/mp_asm.h
+++ b/src/math/mp/mp_x86_32/mp_asm.h
@@ -12,7 +12,7 @@
#include <botan/mp_types.h>
#if (BOTAN_MP_WORD_BITS != 32)
- #error The mp_ia32 module requires that BOTAN_MP_WORD_BITS == 32
+ #error The mp_x86_32 module requires that BOTAN_MP_WORD_BITS == 32
#endif
namespace Botan {
diff --git a/src/math/mp/mp_ia32/mp_asmi.h b/src/math/mp/mp_x86_32/mp_asmi.h
index c7b679e80..c7b679e80 100644
--- a/src/math/mp/mp_ia32/mp_asmi.h
+++ b/src/math/mp/mp_x86_32/mp_asmi.h
diff --git a/src/math/mp/mp_ia32_msvc/info.txt b/src/math/mp/mp_x86_32_msvc/info.txt
index 55a42c310..8d35c02e7 100644
--- a/src/math/mp/mp_ia32_msvc/info.txt
+++ b/src/math/mp/mp_x86_32_msvc/info.txt
@@ -8,7 +8,7 @@ mp_asmi.h
</header:internal>
<arch>
-ia32
+x86_32
</arch>
<cc>
diff --git a/src/math/mp/mp_ia32_msvc/mp_asmi.h b/src/math/mp/mp_x86_32_msvc/mp_asmi.h
index aee457d65..aee457d65 100644
--- a/src/math/mp/mp_ia32_msvc/mp_asmi.h
+++ b/src/math/mp/mp_x86_32_msvc/mp_asmi.h
diff --git a/src/math/mp/mp_amd64/info.txt b/src/math/mp/mp_x86_64/info.txt
index 11cc380e2..fdcc05dd6 100644
--- a/src/math/mp/mp_amd64/info.txt
+++ b/src/math/mp/mp_x86_64/info.txt
@@ -8,7 +8,7 @@ mp_asmi.h
</header:internal>
<arch>
-amd64
+x86_64
</arch>
<cc>
diff --git a/src/math/mp/mp_amd64/mp_asm.h b/src/math/mp/mp_x86_64/mp_asm.h
index fa66d04f3..edfaf6352 100644
--- a/src/math/mp/mp_amd64/mp_asm.h
+++ b/src/math/mp/mp_x86_64/mp_asm.h
@@ -12,7 +12,7 @@
#include <botan/mp_types.h>
#if (BOTAN_MP_WORD_BITS != 64)
- #error The mp_amd64 module requires that BOTAN_MP_WORD_BITS == 64
+ #error The mp_x86_64 module requires that BOTAN_MP_WORD_BITS == 64
#endif
namespace Botan {
@@ -20,7 +20,7 @@ namespace Botan {
extern "C" {
/*
-* Helper Macros for amd64 Assembly
+* Helper Macros for x86-64 Assembly
*/
#define ASM(x) x "\n\t"
diff --git a/src/math/mp/mp_amd64/mp_asmi.h b/src/math/mp/mp_x86_64/mp_asmi.h
index adf7774ef..f14df0e89 100644
--- a/src/math/mp/mp_amd64/mp_asmi.h
+++ b/src/math/mp/mp_x86_64/mp_asmi.h
@@ -16,7 +16,7 @@ namespace Botan {
extern "C" {
/*
-* Helper Macros for amd64 Assembly
+* Helper Macros for x86-64 Assembly
*/
#ifndef ASM
#define ASM(x) x "\n\t"
diff --git a/src/math/mp/mulop_generic/info.txt b/src/math/mp/mulop_generic/info.txt
deleted file mode 100644
index 548d0f44b..000000000
--- a/src/math/mp/mulop_generic/info.txt
+++ /dev/null
@@ -1,5 +0,0 @@
-load_on dep
-
-<source>
-mp_mulop.cpp
-</source>
diff --git a/src/math/numbertheory/info.txt b/src/math/numbertheory/info.txt
index 18349ef78..0c6a9aefc 100644
--- a/src/math/numbertheory/info.txt
+++ b/src/math/numbertheory/info.txt
@@ -1,11 +1,9 @@
-load_on auto
-
define BIGINT_MATH
+load_on auto
+
<header:public>
-curve_gfp.h
numthry.h
-point_gfp.h
pow_mod.h
reducer.h
</header:public>
@@ -20,7 +18,6 @@ jacobi.cpp
make_prm.cpp
mp_numth.cpp
numthry.cpp
-point_gfp.cpp
pow_mod.cpp
powm_fw.cpp
powm_mnt.cpp
diff --git a/src/math/numbertheory/pow_mod.cpp b/src/math/numbertheory/pow_mod.cpp
index a66a1f7df..bf6b29275 100644
--- a/src/math/numbertheory/pow_mod.cpp
+++ b/src/math/numbertheory/pow_mod.cpp
@@ -118,7 +118,12 @@ size_t Power_Mod::window_bits(size_t exp_bits, size_t,
Power_Mod::Usage_Hints hints)
{
static const size_t wsize[][2] = {
- { 2048, 7 }, { 1024, 6 }, { 256, 5 }, { 128, 4 }, { 64, 3 }, { 0, 0 }
+ { 1434, 7 },
+ { 539, 6 },
+ { 197, 4 },
+ { 70, 3 },
+ { 25, 2 },
+ { 0, 0 }
};
size_t window_bits = 1;
diff --git a/src/math/numbertheory/powm_mnt.cpp b/src/math/numbertheory/powm_mnt.cpp
index 421470364..8993f4ba9 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);
}
@@ -110,8 +104,8 @@ BigInt Montgomery_Exponentiator::execute() const
x.get_reg().resize(2*mod_words+1);
bigint_monty_redc(&x[0], x.size(),
- &workspace[0],
- modulus.data(), mod_words, mod_prime);
+ modulus.data(), mod_words, mod_prime,
+ &workspace[0]);
x.get_reg().resize(mod_words+1);
@@ -134,14 +128,12 @@ Montgomery_Exponentiator::Montgomery_Exponentiator(const BigInt& mod,
mod_words = modulus.sig_words();
- BigInt mod_prime_bn(BigInt::Power2, MP_WORD_BITS);
- mod_prime = (mod_prime_bn - inverse_mod(modulus, mod_prime_bn)).word_at(0);
+ BigInt r(BigInt::Power2, mod_words * BOTAN_MP_WORD_BITS);
+ mod_prime = (((r * inverse_mod(r, mod)) - 1) / mod).word_at(0);
- R_mod = BigInt(BigInt::Power2, MP_WORD_BITS * mod_words);
- R_mod %= modulus;
+ R_mod = r % modulus;
- R2 = BigInt(BigInt::Power2, 2 * MP_WORD_BITS * mod_words);
- R2 %= modulus;
+ R2 = (R_mod * R_mod) % modulus;
}
}
diff --git a/src/math/numbertheory/reducer.cpp b/src/math/numbertheory/reducer.cpp
index 257ece56e..466996e99 100644
--- a/src/math/numbertheory/reducer.cpp
+++ b/src/math/numbertheory/reducer.cpp
@@ -1,6 +1,6 @@
/*
* Modular Reducer
-* (C) 1999-2010 Jack Lloyd
+* (C) 1999-2011 Jack Lloyd
*
* Distributed under the terms of the Botan license
*/
@@ -22,10 +22,8 @@ Modular_Reducer::Modular_Reducer(const BigInt& mod)
mod_words = modulus.sig_words();
modulus_2 = Botan::square(modulus);
- mod2_words = modulus_2.sig_words();
mu = BigInt(BigInt::Power2, 2 * MP_WORD_BITS * mod_words) / modulus;
- mu_words = mu.sig_words();
}
/*
@@ -36,45 +34,49 @@ BigInt Modular_Reducer::reduce(const BigInt& x) const
if(mod_words == 0)
throw Invalid_State("Modular_Reducer: Never initalized");
- BigInt t1 = x;
- t1.set_sign(BigInt::Positive);
-
- if(t1 < modulus)
+ if(x.cmp(modulus, false) < 0)
{
- if(x.is_negative() && t1.is_nonzero())
- return modulus - t1;
+ if(x.is_negative())
+ return x + modulus; // make positive
return x;
}
+ else if(x.cmp(modulus_2, false) < 0)
+ {
+ BigInt t1 = x;
+ t1.set_sign(BigInt::Positive);
+ t1 >>= (MP_WORD_BITS * (mod_words - 1));
+ t1 *= mu;
- if(t1 >= modulus_2)
- return (x % modulus);
+ t1 >>= (MP_WORD_BITS * (mod_words + 1));
+ t1 *= modulus;
- t1 >>= (MP_WORD_BITS * (mod_words - 1));
- t1 *= mu;
- t1 >>= (MP_WORD_BITS * (mod_words + 1));
+ t1.mask_bits(MP_WORD_BITS * (mod_words + 1));
- t1 *= modulus;
- t1.mask_bits(MP_WORD_BITS * (mod_words+1));
+ BigInt t2 = x;
+ t2.set_sign(BigInt::Positive);
+ t2.mask_bits(MP_WORD_BITS * (mod_words + 1));
- BigInt t2 = x;
- t2.set_sign(BigInt::Positive);
- t2.mask_bits(MP_WORD_BITS * (mod_words+1));
+ t2 -= t1;
- t1 = t2 - t1;
+ if(t2.is_negative())
+ {
+ BigInt b_to_k1(BigInt::Power2, MP_WORD_BITS * (mod_words + 1));
+ t2 += b_to_k1;
+ }
- if(t1.is_negative())
+ while(t2 >= modulus)
+ t2 -= modulus;
+
+ if(x.is_positive())
+ return t2;
+ else
+ return (modulus - t2);
+ }
+ else
{
- BigInt b_to_k1(BigInt::Power2, MP_WORD_BITS * (mod_words+1));
- t1 += b_to_k1;
+ // too big, fall back to normal division
+ return (x % modulus);
}
-
- while(t1 >= modulus)
- t1 -= modulus;
-
- if(x.is_negative() && t1.is_nonzero())
- t1 = modulus - t1;
-
- return t1;
}
}
diff --git a/src/math/numbertheory/reducer.h b/src/math/numbertheory/reducer.h
index 05c12a440..76712074c 100644
--- a/src/math/numbertheory/reducer.h
+++ b/src/math/numbertheory/reducer.h
@@ -13,7 +13,7 @@
namespace Botan {
/**
-* Modular Reducer
+* Modular Reducer (using Barrett's technique)
*/
class BOTAN_DLL Modular_Reducer
{
@@ -53,7 +53,7 @@ class BOTAN_DLL Modular_Reducer
Modular_Reducer(const BigInt& mod);
private:
BigInt modulus, modulus_2, mu;
- size_t mod_words, mod2_words, mu_words;
+ size_t mod_words;
};
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-22 09:21:39 +0000