diff options
author | lloyd <[email protected]> | 2010-03-15 17:51:40 +0000 |
---|---|---|
committer | lloyd <[email protected]> | 2010-03-15 17:51:40 +0000 |
commit | ddf2d1af53b96da47ceee166f5527eaaa16f8928 (patch) | |
tree | bd8c166ab2f41abd10fda4dfe01429d4312f9533 /src/math/numbertheory | |
parent | 65e5a8826f4240fd0b21ad99ab9daa9da862fc29 (diff) |
Cache p.sig_words() in curve object
Avoid using Barett reduction in core operations; seems to help perf.
Diffstat (limited to 'src/math/numbertheory')
-rw-r--r-- | src/math/numbertheory/curve_gfp.h | 9 | ||||
-rw-r--r-- | src/math/numbertheory/point_gfp.cpp | 82 | ||||
-rw-r--r-- | src/math/numbertheory/point_gfp.h | 4 |
3 files changed, 68 insertions, 27 deletions
diff --git a/src/math/numbertheory/curve_gfp.h b/src/math/numbertheory/curve_gfp.h index a7be8987c..0a91fc52d 100644 --- a/src/math/numbertheory/curve_gfp.h +++ b/src/math/numbertheory/curve_gfp.h @@ -44,6 +44,8 @@ class BOTAN_DLL CurveGFp p_dash = (((r * r_inv) - 1) / p).word_at(0); a_r = reducer_p.multiply(a, r); + + p_words = p.sig_words(); } // CurveGFp(const CurveGFp& other) = default; @@ -87,6 +89,11 @@ class BOTAN_DLL CurveGFp */ word get_p_dash() const { return p_dash; } + /** + * @return p.sig_words() + */ + u32bit get_p_words() const { return p_words; } + const Modular_Reducer& mod_p() const { return reducer_p; } /** @@ -114,6 +121,8 @@ class BOTAN_DLL CurveGFp // Curve parameters BigInt p, a, b; + u32bit p_words; // cache of p.sig_words() + // Montgomery parameters BigInt r, r_inv, a_r; word p_dash; diff --git a/src/math/numbertheory/point_gfp.cpp b/src/math/numbertheory/point_gfp.cpp index 2e4f99796..0148d9b3e 100644 --- a/src/math/numbertheory/point_gfp.cpp +++ b/src/math/numbertheory/point_gfp.cpp @@ -32,14 +32,13 @@ PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) : } BigInt PointGFp::monty_mult(const BigInt& a, const BigInt& b, - MemoryRegion<word>& workspace) + MemoryRegion<word>& workspace) const { if(a.is_zero() || b.is_zero()) return 0; const BigInt& p = curve.get_p(); - const u32bit p_size = p.sig_words(); - + const u32bit p_size = curve.get_p_words(); const word p_dash = curve.get_p_dash(); workspace.clear(); @@ -59,14 +58,13 @@ BigInt PointGFp::monty_mult(const BigInt& a, const BigInt& b, } BigInt PointGFp::monty_sqr(const BigInt& x, - MemoryRegion<word>& workspace) + MemoryRegion<word>& workspace) const { if(x.is_zero()) return 0; const BigInt& p = curve.get_p(); - const u32bit p_size = p.sig_words(); - + const u32bit p_size = curve.get_p_words(); const word p_dash = curve.get_p_dash(); workspace.clear(); @@ -97,11 +95,11 @@ void PointGFp::add(const PointGFp& rhs, else if(rhs.is_zero()) return; + const BigInt& p = curve.get_p(); + MemoryRegion<word>& ws = workspace.ws_monty; std::vector<BigInt>& ws_bn = workspace.ws_bn; - const Modular_Reducer& mod_p = curve.mod_p(); - BigInt& rhs_z2 = ws_bn[0]; BigInt& U1 = ws_bn[1]; BigInt& S1 = ws_bn[2]; @@ -125,9 +123,13 @@ void PointGFp::add(const PointGFp& rhs, U2 = monty_mult(rhs.coord_x, lhs_z2, ws); S2 = monty_mult(rhs.coord_y, monty_mult(coord_z, lhs_z2, ws), ws); - H = mod_p.reduce(U2 - U1); + H = U2 - U1; + if(H.is_negative()) + H += p; - r = mod_p.reduce(S2 - S1); + r = S2 - S1; + if(r.is_negative()) + r += p; if(H.is_zero()) { @@ -147,15 +149,17 @@ void PointGFp::add(const PointGFp& rhs, U2 = monty_mult(U1, U2, ws); - x = mod_p.reduce(monty_sqr(r, ws) - S2 - U2*2); + x = monty_sqr(r, ws) - S2 - U2*2; + while(x.is_negative()) + x += p; U2 -= x; if(U2.is_negative()) - U2 += curve.get_p(); + U2 += p; y = monty_mult(r, U2, ws) - monty_mult(S1, S2, ws); if(y.is_negative()) - y += curve.get_p(); + y += p; z = monty_mult(monty_mult(coord_z, rhs.coord_z, ws), H, ws); @@ -167,7 +171,7 @@ void PointGFp::add(const PointGFp& rhs, // arithmetic operators PointGFp& PointGFp::operator+=(const PointGFp& rhs) { - Workspace ws(curve.get_p().sig_words()); + Workspace ws(curve.get_p_words()); add(rhs, ws); return *this; } @@ -186,7 +190,7 @@ PointGFp& PointGFp::operator-=(const PointGFp& rhs) PointGFp& PointGFp::operator*=(const BigInt& scalar) { - Workspace ws(curve.get_p().sig_words()); + Workspace ws(curve.get_p_words()); if(scalar.abs() <= 2) // special cases for small values { @@ -257,11 +261,11 @@ void PointGFp::mult2(Workspace& workspace) return; } + const BigInt& p = curve.get_p(); + MemoryRegion<word>& ws = workspace.ws_monty; std::vector<BigInt>& ws_bn = workspace.ws_bn; - const Modular_Reducer& mod_p = curve.mod_p(); - BigInt& y_2 = ws_bn[0]; BigInt& S = ws_bn[1]; BigInt& z4 = ws_bn[2]; @@ -274,29 +278,37 @@ void PointGFp::mult2(Workspace& workspace) y_2 = monty_sqr(coord_y, ws); - S = mod_p.reduce(4 * monty_mult(coord_x, y_2, ws)); + S = 4 * monty_mult(coord_x, y_2, ws); + while(S >= p) + S -= p; z4 = monty_sqr(monty_sqr(coord_z, ws), ws); a_z4 = monty_mult(curve.get_a_r(), z4, ws); - M = mod_p.reduce(a_z4 + 3 * monty_sqr(coord_x, ws)); + M = 3 * monty_sqr(coord_x, ws) + a_z4; + while(M >= p) + M -= p; - x = mod_p.reduce(monty_sqr(M, ws) - 2*S); + x = monty_sqr(M, ws) - 2*S; + while(x.is_negative()) + x += p; - U = mod_p.reduce(monty_sqr(y_2, ws) << 3); + U = 8 * monty_sqr(y_2, ws); + while(U >= p) + U -= p; S -= x; while(S.is_negative()) - S += curve.get_p(); + S += p; y = monty_mult(M, S, ws) - U; if(y.is_negative()) - y += curve.get_p(); + y += p; z = 2 * monty_mult(coord_y, coord_z, ws); - if(z >= curve.get_p()) - z -= curve.get_p(); + if(z >= p) + z -= p; coord_x = x; coord_y = y; @@ -310,11 +322,21 @@ BigInt PointGFp::get_affine_x() const 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)); + + BigInt z2 = monty_sqr(coord_z, ws); + z2 = inverse_mod(z2, curve.get_p()); + z2 = mod_p.multiply(z2, curve.get_r()); + return monty_mult(coord_x, z2, ws); +#endif } BigInt PointGFp::get_affine_y() const @@ -324,11 +346,21 @@ BigInt PointGFp::get_affine_y() const const Modular_Reducer& mod_p = curve.mod_p(); +#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); + z3 = inverse_mod(z3, curve.get_p()); + z3 = mod_p.multiply(z3, curve.get_r()); + return monty_mult(coord_y, z3, ws); +#endif } void PointGFp::check_invariants() const diff --git a/src/math/numbertheory/point_gfp.h b/src/math/numbertheory/point_gfp.h index c7da6995c..f5cb11157 100644 --- a/src/math/numbertheory/point_gfp.h +++ b/src/math/numbertheory/point_gfp.h @@ -158,7 +158,7 @@ class BOTAN_DLL PointGFp * @param workspace temp space */ BigInt monty_mult(const BigInt& x, const BigInt& y, - MemoryRegion<word>& workspace); + MemoryRegion<word>& workspace) const; /** * Montgomery squaring/reduction @@ -166,7 +166,7 @@ class BOTAN_DLL PointGFp * @param workspace temp space */ BigInt monty_sqr(const BigInt& x, - MemoryRegion<word>& workspace); + MemoryRegion<word>& workspace) const; /** * Point addition |