diff options
Diffstat (limited to 'src/math/numbertheory')
-rw-r--r-- | src/math/numbertheory/curve_gfp.h | 96 | ||||
-rw-r--r-- | src/math/numbertheory/info.txt | 3 | ||||
-rw-r--r-- | src/math/numbertheory/numthry.cpp | 100 | ||||
-rw-r--r-- | src/math/numbertheory/numthry.h | 16 | ||||
-rw-r--r-- | src/math/numbertheory/point_gfp.cpp | 423 | ||||
-rw-r--r-- | src/math/numbertheory/point_gfp.h | 201 | ||||
-rw-r--r-- | src/math/numbertheory/reducer.cpp | 19 | ||||
-rw-r--r-- | src/math/numbertheory/reducer.h | 32 |
8 files changed, 806 insertions, 84 deletions
diff --git a/src/math/numbertheory/curve_gfp.h b/src/math/numbertheory/curve_gfp.h new file mode 100644 index 000000000..697065dfe --- /dev/null +++ b/src/math/numbertheory/curve_gfp.h @@ -0,0 +1,96 @@ +/* +* Elliptic curves over GF(p) +* +* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke +* 2010 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_GFP_CURVE_H__ +#define BOTAN_GFP_CURVE_H__ + +#include <botan/numthry.h> +#include <botan/reducer.h> + +namespace Botan { + +/** +* This class represents an elliptic curve over GF(p) +*/ +class BOTAN_DLL CurveGFp + { + public: + + /** + * Construct the elliptic curve E: y^2 = x^3 + ax + b over GF(p) + * @param p prime number of the field + * @param a first coefficient + * @param b second coefficient + */ + CurveGFp(const BigInt& p, const BigInt& a, const BigInt& b) : + p(p), a(a), b(b), reducer_p(p) {} + + // CurveGFp(const CurveGFp& other) = default; + // CurveGFp& operator=(const CurveGFp& other) = default; + + /** + * Get coefficient a + * @result coefficient a + */ + const BigInt& get_a() const { return a; } + + /** + * Get coefficient b + * @result coefficient b + */ + const BigInt& get_b() const { return b; } + + /** + * Get prime modulus of the field of the curve + * @result prime modulus of the field of the curve + */ + const BigInt& get_p() const { return p; } + + const Modular_Reducer& mod_p() const { return reducer_p; } + + /** + * swaps the states of *this and other, does not throw + * @param other The curve to swap values with + */ + void swap(CurveGFp& other) + { + std::swap(a, other.a); + std::swap(b, other.b); + std::swap(p, other.p); + } + + bool operator==(const CurveGFp& other) const + { + return (p == other.p && a == other.a && b == other.b); + } + + private: + BigInt p, a, b; + Modular_Reducer reducer_p; + }; + +inline bool operator!=(const CurveGFp& lhs, const CurveGFp& rhs) + { + return !(lhs == rhs); + } + +} + +namespace std { + +template<> inline +void swap<Botan::CurveGFp>(Botan::CurveGFp& curve1, + Botan::CurveGFp& curve2) + { + curve1.swap(curve2); + } + +} // namespace std + +#endif diff --git a/src/math/numbertheory/info.txt b/src/math/numbertheory/info.txt index 19abfaaa0..58851e055 100644 --- a/src/math/numbertheory/info.txt +++ b/src/math/numbertheory/info.txt @@ -4,7 +4,9 @@ define BIGINT_MATH <header:public> blinding.h +curve_gfp.h numthry.h +point_gfp.h pow_mod.h reducer.h </header:public> @@ -20,6 +22,7 @@ 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/numthry.cpp b/src/math/numbertheory/numthry.cpp index 760250712..f79fdec2b 100644 --- a/src/math/numbertheory/numthry.cpp +++ b/src/math/numbertheory/numthry.cpp @@ -1,11 +1,12 @@ /* * Number Theory Functions -* (C) 1999-2009 Jack Lloyd +* (C) 1999-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ #include <botan/numthry.h> +#include <botan/reducer.h> #include <botan/internal/bit_ops.h> #include <algorithm> @@ -14,6 +15,62 @@ namespace Botan { namespace { /* +* Miller-Rabin Primality Tester +*/ +class MillerRabin_Test + { + public: + bool passes_test(const BigInt& nonce); + MillerRabin_Test(const BigInt& num); + private: + BigInt n, r, n_minus_1; + u32bit s; + Fixed_Exponent_Power_Mod pow_mod; + Modular_Reducer reducer; + }; + +/* +* Miller-Rabin Test +*/ +bool MillerRabin_Test::passes_test(const BigInt& a) + { + if(a < 2 || a >= n_minus_1) + throw Invalid_Argument("Bad size for nonce in Miller-Rabin test"); + + BigInt y = pow_mod(a); + if(y == 1 || y == n_minus_1) + return true; + + for(u32bit i = 1; i != s; ++i) + { + y = reducer.square(y); + + if(y == 1) + return false; + if(y == n_minus_1) + return true; + } + return false; + } + +/* +* Miller-Rabin Constructor +*/ +MillerRabin_Test::MillerRabin_Test(const BigInt& num) + { + if(num.is_even() || num < 3) + throw Invalid_Argument("MillerRabin_Test: Invalid number for testing"); + + n = num; + n_minus_1 = n - 1; + s = low_zero_bits(n_minus_1); + r = n_minus_1 >> s; + + pow_mod = Fixed_Exponent_Power_Mod(r, n); + reducer = Modular_Reducer(n); + } + +/* * Miller-Rabin Iterations */ u32bit miller_rabin_test_iterations(u32bit bits, bool verify) @@ -300,45 +357,4 @@ bool passes_mr_tests(RandomNumberGenerator& rng, return true; } -/* -* Miller-Rabin Test -*/ -bool MillerRabin_Test::passes_test(const BigInt& a) - { - if(a < 2 || a >= n_minus_1) - throw Invalid_Argument("Bad size for nonce in Miller-Rabin test"); - - BigInt y = pow_mod(a); - if(y == 1 || y == n_minus_1) - return true; - - for(u32bit i = 1; i != s; ++i) - { - y = reducer.square(y); - - if(y == 1) - return false; - if(y == n_minus_1) - return true; - } - return false; - } - -/* -* Miller-Rabin Constructor -*/ -MillerRabin_Test::MillerRabin_Test(const BigInt& num) - { - if(num.is_even() || num < 3) - throw Invalid_Argument("MillerRabin_Test: Invalid number for testing"); - - n = num; - n_minus_1 = n - 1; - s = low_zero_bits(n_minus_1); - r = n_minus_1 >> s; - - pow_mod = Fixed_Exponent_Power_Mod(r, n); - reducer = Modular_Reducer(n); - } - } diff --git a/src/math/numbertheory/numthry.h b/src/math/numbertheory/numthry.h index ae2c219fc..080f184a4 100644 --- a/src/math/numbertheory/numthry.h +++ b/src/math/numbertheory/numthry.h @@ -9,7 +9,6 @@ #define BOTAN_NUMBER_THEORY_H__ #include <botan/bigint.h> -#include <botan/reducer.h> #include <botan/pow_mod.h> #include <botan/rng.h> @@ -100,21 +99,6 @@ const u32bit PRIME_PRODUCTS_TABLE_SIZE = 256; extern const u16bit BOTAN_DLL PRIMES[]; extern const u64bit PRIME_PRODUCTS[]; -/* -* Miller-Rabin Primality Tester -*/ -class BOTAN_DLL MillerRabin_Test - { - public: - bool passes_test(const BigInt&); - MillerRabin_Test(const BigInt&); - private: - BigInt n, r, n_minus_1; - u32bit s; - Fixed_Exponent_Power_Mod pow_mod; - Modular_Reducer reducer; - }; - } #endif diff --git a/src/math/numbertheory/point_gfp.cpp b/src/math/numbertheory/point_gfp.cpp new file mode 100644 index 000000000..06c42d18c --- /dev/null +++ b/src/math/numbertheory/point_gfp.cpp @@ -0,0 +1,423 @@ +/* +* Arithmetic for point groups of elliptic curves over GF(p) +* +* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke +* 2008-2010 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include <botan/point_gfp.h> +#include <botan/numthry.h> + +namespace Botan { + +namespace { + +BigInt decompress_point(bool yMod2, + const BigInt& x, + const CurveGFp& curve) + { + BigInt xpow3 = x * x * x; + + BigInt g = curve.get_a() * x; + g += xpow3; + g += curve.get_b(); + g = g % curve.get_p(); + + BigInt z = ressol(g, curve.get_p()); + + if(z < 0) + throw Illegal_Point("error during decompression"); + + if(z.get_bit(0) != yMod2) + z = curve.get_p() - z; + + return z; + } + +} + +// arithmetic operators +PointGFp& PointGFp::operator+=(const PointGFp& rhs) + { + if(rhs.is_zero()) + return *this; + + if(is_zero()) + { + *this = rhs; + return *this; + } + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt rhs_z2 = mod_p.square(rhs.coord_z); + BigInt U1 = mod_p.multiply(coord_x, rhs_z2); + BigInt S1 = mod_p.multiply(coord_y, mod_p.multiply(rhs.coord_z, rhs_z2)); + + BigInt lhs_z2 = mod_p.square(coord_z); + BigInt U2 = mod_p.multiply(rhs.coord_x, lhs_z2); + BigInt S2 = mod_p.multiply(rhs.coord_y, mod_p.multiply(coord_z, lhs_z2)); + + BigInt H = mod_p.reduce(U2 - U1); + BigInt r = mod_p.reduce(S2 - S1); + + if(H.is_zero()) + { + if(r.is_zero()) + { + mult2_in_place(); + return *this; + } + + *this = PointGFp(curve); // setting myself to zero + return *this; + } + + U2 = mod_p.square(H); + + S2 = mod_p.multiply(U2, H); + + U2 = mod_p.multiply(U1, U2); + + BigInt x = mod_p.reduce(mod_p.square(r) - S2 - mod_p.multiply(2, U2)); + BigInt y = mod_p.reduce(mod_p.multiply(r, (U2-x)) - mod_p.multiply(S1, S2)); + BigInt z = mod_p.multiply(mod_p.multiply(coord_z, rhs.coord_z), H); + + coord_x = x; + coord_y = y; + coord_z = z; + + return *this; + } + +PointGFp& PointGFp::operator-=(const PointGFp& rhs) + { + PointGFp minus_rhs = PointGFp(rhs).negate(); + + if(is_zero()) + *this = minus_rhs; + else + *this += minus_rhs; + + return *this; + } + +PointGFp& PointGFp::operator*=(const BigInt& scalar) + { + if(scalar.abs() <= 2) // special cases for small values + { + u32bit value = scalar.abs().to_u32bit(); + + if(value == 0) + *this = PointGFp(curve); // set to zero point + else if(value == 1) + { + if(scalar.is_negative()) + this->negate(); + } + else if(value == 2) + { + this->mult2_in_place(); + if(scalar.is_negative()) + this->negate(); + } + + return *this; + } + + PointGFp H(this->curve); // create as zero + PointGFp P(*this); + + if(scalar.is_negative()) + P.negate(); + + for(int i = scalar.bits() - 1; i >= 0; --i) + { + H.mult2_in_place(); + if(scalar.get_bit(i)) + H += P; + } + + if(!H.is_zero()) // cannot convert if H == O + { + /** + * Convert H to an equivalent point with z == 1, thus x and y + * correspond to their affine coordinates + */ + if(H.coord_z != 1) + { + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt z_inv = inverse_mod(H.coord_z, curve.get_p()); + + BigInt z_inv_2 = mod_p.square(z_inv); + + H.coord_x = mod_p.multiply(H.coord_x, z_inv_2); + H.coord_y = mod_p.multiply(H.coord_y, mod_p.multiply(z_inv, z_inv_2)); + H.coord_z = 1; + } + } + + *this = H; + return *this; + } + +PointGFp& PointGFp::negate() + { + if(!is_zero()) + coord_y = curve.get_p() - coord_y; + + return *this; + } + +// *this *= 2 +void PointGFp::mult2_in_place() + { + if(is_zero()) + return; + else if(coord_y.is_zero()) + { + *this = PointGFp(curve); // setting myself to zero + return; + } + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt y_2 = mod_p.square(coord_y); + + BigInt S = mod_p.multiply(4, mod_p.multiply(coord_x, y_2)); + + BigInt a_z4 = mod_p.multiply(curve.get_a(), + mod_p.square(mod_p.square(coord_z))); + + BigInt M = mod_p.reduce(a_z4 + 3 * mod_p.square(coord_x)); + + BigInt x = mod_p.reduce(mod_p.square(M) - mod_p.multiply(2, S)); + + BigInt y = mod_p.square(y_2); + + BigInt z = mod_p.multiply(2, mod_p.reduce(y + y)); + + BigInt U = mod_p.reduce(z + z); + + y = mod_p.reduce(mod_p.multiply(M, S - x) - U); + + z = mod_p.multiply(2, mod_p.multiply(coord_y, coord_z)); + + coord_x = x; + coord_y = y; + coord_z = z; + } + +BigInt PointGFp::get_affine_x() const + { + if(is_zero()) + throw Illegal_Transformation("cannot convert to affine"); + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt z2 = mod_p.square(coord_z); + return mod_p.multiply(coord_x, inverse_mod(z2, curve.get_p())); + } + +BigInt PointGFp::get_affine_y() const + { + if(is_zero()) + throw Illegal_Transformation("cannot convert to affine"); + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt z3 = mod_p.cube(coord_z); + return mod_p.multiply(coord_y, inverse_mod(z3, curve.get_p())); + } + +// Is this the point at infinity? +bool PointGFp::is_zero() const + { + return(coord_x.is_zero() && coord_z.is_zero()); + } + +void PointGFp::check_invariants() const + { + /* + Is the point still on the curve?? (If everything is correct, the + point is always on its curve; then the function will return + silently. If Oskar managed to corrupt this object's state, then it + will throw an exception.) + */ + + if(is_zero()) + return; + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt y2 = mod_p.square(coord_y); + BigInt x3 = mod_p.cube(coord_x); + + BigInt ax = mod_p.multiply(coord_x, curve.get_a()); + + if(coord_z == 1) + { + if(mod_p.reduce(x3 + ax + curve.get_b()) != y2) + throw Illegal_Point("Invalid ECP point: y^2 != x^3 + a*x + b"); + } + + BigInt z2 = mod_p.square(coord_z); + BigInt z3 = mod_p.multiply(coord_z, z2); + + BigInt ax_z4 = mod_p.multiply(mod_p.multiply(z3, coord_z), ax); + + BigInt b_z6 = mod_p.multiply(curve.get_b(), mod_p.square(z3)); + + if(y2 != mod_p.reduce(x3 + ax_z4 + b_z6)) + throw Illegal_Point("Invalid ECP point: y^2 != x^3 + a*x*z^4 + b*z^6"); + } + +// swaps the states of *this and other, does not throw! +void PointGFp::swap(PointGFp& other) + { + curve.swap(other.curve); + coord_x.swap(other.coord_x); + coord_y.swap(other.coord_y); + coord_z.swap(other.coord_z); + } + +bool PointGFp::operator==(const PointGFp& other) const + { + return (coord_x == other.coord_x && + coord_y == other.coord_y && + coord_z == other.coord_z && + get_curve() == other.get_curve()); + } + +// arithmetic operators +PointGFp operator+(const PointGFp& lhs, PointGFp const& rhs) + { + PointGFp tmp(lhs); + return tmp += rhs; + } + +PointGFp operator-(const PointGFp& lhs, PointGFp const& rhs) + { + PointGFp tmp(lhs); + return tmp -= rhs; + } + +PointGFp operator-(const PointGFp& lhs) + { + return PointGFp(lhs).negate(); + } + +PointGFp operator*(const BigInt& scalar, const PointGFp& point) + { + PointGFp result(point); + return result *= scalar; + } + +PointGFp operator*(const PointGFp& point, const BigInt& scalar) + { + PointGFp result(point); + return result *= scalar; + } + +// encoding and decoding +SecureVector<byte> EC2OSP(const PointGFp& point, byte format) + { + if(point.is_zero()) + return SecureVector<byte>(1); // single 0 byte + + const u32bit p_bytes = point.get_curve().get_p().bytes(); + + BigInt x = point.get_affine_x(); + BigInt y = point.get_affine_y(); + + SecureVector<byte> bX = BigInt::encode_1363(x, p_bytes); + SecureVector<byte> bY = BigInt::encode_1363(y, p_bytes); + + if(format == PointGFp::UNCOMPRESSED) + { + SecureVector<byte> result(2*p_bytes+1); + result[0] = 4; + + result.copy(1, bX.begin(), p_bytes); + result.copy(p_bytes+1, bY.begin(), p_bytes); + return result; + } + else if(format == PointGFp::COMPRESSED) + { + SecureVector<byte> result(p_bytes+1); + result[0] = 2; + + result.copy(1, bX.begin(), bX.size()); + + if(y.get_bit(0)) + result[0] |= 1; + + return result; + } + else if(format == PointGFp::HYBRID) + { + SecureVector<byte> result(2*p_bytes+1); + result[0] = 6; + + result.copy(1, bX.begin(), bX.size()); + result.copy(p_bytes+1, bY.begin(), bY.size()); + + if(y.get_bit(0)) + result[0] |= 1; + + return result; + } + else + throw Invalid_Argument("illegal point encoding format specification"); + } + +PointGFp OS2ECP(const MemoryRegion<byte>& os, const CurveGFp& curve) + { + if(os.size() == 1 && os[0] == 0) + return PointGFp(curve); // return zero + + const byte pc = os[0]; + + BigInt x, y; + + if(pc == 2 || pc == 3) + { + //compressed form + x = BigInt::decode(&os[1], os.size() - 1); + + bool yMod2 = ((pc & 0x01) == 1); + y = decompress_point(yMod2, x, curve); + } + else if(pc == 4) + { + // uncompressed form + u32bit l = (os.size() - 1) / 2; + + x = BigInt::decode(&os[1], l); + y = BigInt::decode(&os[l+1], l); + } + else if(pc == 6 || pc == 7) + { + // hybrid form + u32bit l = (os.size() - 1) / 2; + + x = BigInt::decode(&os[1], l); + y = BigInt::decode(&os[l+1], l); + + bool yMod2 = ((pc & 0x01) == 1); + + if(decompress_point(yMod2, x, curve) != y) + throw Illegal_Point("OS2ECP: Decoding error in hybrid format"); + } + else + throw Invalid_Argument("OS2ECP: Unknown format type"); + + PointGFp result(curve, x, y); + result.check_invariants(); + return result; + } + +} diff --git a/src/math/numbertheory/point_gfp.h b/src/math/numbertheory/point_gfp.h new file mode 100644 index 000000000..0741b5e56 --- /dev/null +++ b/src/math/numbertheory/point_gfp.h @@ -0,0 +1,201 @@ +/* +* Arithmetic for point groups of elliptic curves over GF(p) +* +* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke +* 2008-2010 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_POINT_GFP_H__ +#define BOTAN_POINT_GFP_H__ + +#include <botan/curve_gfp.h> +#include <vector> + +namespace Botan { + +struct BOTAN_DLL Illegal_Transformation : public Exception + { + Illegal_Transformation(const std::string& err = + "Requested transformation is not possible") : + Exception(err) {} + }; + +struct BOTAN_DLL Illegal_Point : public Exception + { + Illegal_Point(const std::string& err = "Malformed ECP point detected") : + Exception(err) {} + }; + +/** +* This class represents one point on a curve of GF(p) +*/ +class BOTAN_DLL PointGFp + { + public: + enum Compression_Type { + UNCOMPRESSED = 0, + COMPRESSED = 1, + HYBRID = 2 + }; + + /** + * Construct the point O + * @param curve The base curve + */ + PointGFp(const CurveGFp& curve) : + curve(curve), coord_x(0), coord_y(1), coord_z(0) {} + + /** + * Construct a point given its affine coordinates + * @param curve the base curve + * @param x affine x coordinate + * @param y affine y coordinate + */ + PointGFp(const CurveGFp& curve, + const BigInt& x, const BigInt& y) : + curve(curve), coord_x(x), coord_y(y), coord_z(1) {} + + /** + * Construct a point given its jacobian projective coordinates + * @param curve the base curve + * @param x jacobian projective x coordinate + * @param y jacobian projective y coordinate + * @param z jacobian projective z coordinate + */ + PointGFp(const CurveGFp& curve, + const BigInt& x, const BigInt& y, const BigInt& z) : + curve(curve), coord_x(x), coord_y(y), coord_z(z) {} + + //PointGFp(const PointGFp& other) = default; + //PointGFp& operator=(const PointGFp& other) = default; + + /** + * += Operator + * @param rhs the PointGFp to add to the local value + * @result resulting PointGFp + */ + PointGFp& operator+=(const PointGFp& rhs); + + /** + * -= Operator + * @param rhs the PointGFp to subtract from the local value + * @result resulting PointGFp + */ + PointGFp& operator-=(const PointGFp& rhs); + + /** + * *= Operator + * This function turns on the the special reduction multiplication + * itself for fast computation, turns it off again when finished. + * @param scalar the PointGFp to multiply with *this + * @result resulting PointGFp + */ + PointGFp& operator*=(const BigInt& scalar); + + /** + * Negate this point + * @return *this + */ + PointGFp& negate(); + + /** + * Return base curve of this point + * @result the curve over GF(p) of this point + */ + const CurveGFp& get_curve() const { return curve; } + + /** + * get affine x coordinate + * @result affine x coordinate + */ + BigInt get_affine_x() const; + + /** + * get affine y coordinate + * @result affine y coordinate + */ + BigInt get_affine_y() const; + + /** + * get the jacobian projective x coordinate + * @result jacobian projective x coordinate + */ + const BigInt& get_jac_proj_x() const { return coord_x; } + + /** + * get the jacobian projective y coordinate + * @result jacobian projective y coordinate + */ + const BigInt& get_jac_proj_y() const { return coord_y; } + + /** + * get the jacobian projective z coordinate + * @result jacobian projective z coordinate + */ + const BigInt& get_jac_proj_z() const { return coord_z; } + + /** + * Is this the point at infinity? + * @result true, if this point is at infinity, false otherwise. + */ + bool is_zero() const; + + /** + * Checks whether the point is to be found on the underlying curve. + * Throws an Invalid_Point exception in case of detecting that the point + * does not satisfy the curve equation. + * To be used to ensure against fault attacks. + */ + void check_invariants() const; + + /** + * swaps the states of *this and other, does not throw! + * @param other the object to swap values with + */ + void swap(PointGFp& other); + + /** + * Equality operator + */ + bool operator==(const PointGFp& other) const; + private: + /** + * Multiply the point by two + */ + void mult2_in_place(); + + CurveGFp curve; + BigInt coord_x, coord_y, coord_z; + }; + +// relational operators +inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs) + { + return !(rhs == lhs); + } + +// arithmetic operators +PointGFp BOTAN_DLL operator+(const PointGFp& lhs, const PointGFp& rhs); +PointGFp BOTAN_DLL operator-(const PointGFp& lhs, const PointGFp& rhs); +PointGFp BOTAN_DLL operator-(const PointGFp& lhs); + +PointGFp BOTAN_DLL operator*(const BigInt& scalar, const PointGFp& point); +PointGFp BOTAN_DLL operator*(const PointGFp& point, const BigInt& scalar); + +// encoding and decoding +SecureVector<byte> BOTAN_DLL EC2OSP(const PointGFp& point, byte format); +PointGFp BOTAN_DLL OS2ECP(const MemoryRegion<byte>& os, const CurveGFp& curve); + +} + +namespace std { + +template<> +inline void swap<Botan::PointGFp>(Botan::PointGFp& x, Botan::PointGFp& y) + { x.swap(y); } + +} + +#endif diff --git a/src/math/numbertheory/reducer.cpp b/src/math/numbertheory/reducer.cpp index aa53f1a0e..257ece56e 100644 --- a/src/math/numbertheory/reducer.cpp +++ b/src/math/numbertheory/reducer.cpp @@ -1,12 +1,11 @@ /* * Modular Reducer -* (C) 1999-2007 Jack Lloyd +* (C) 1999-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ #include <botan/reducer.h> -#include <botan/numthry.h> #include <botan/internal/mp_core.h> namespace Botan { @@ -78,20 +77,4 @@ BigInt Modular_Reducer::reduce(const BigInt& x) const return t1; } -/* -* Multiply, followed by a reduction -*/ -BigInt Modular_Reducer::multiply(const BigInt& x, const BigInt& y) const - { - return reduce(x * y); - } - -/* -* Square, followed by a reduction -*/ -BigInt Modular_Reducer::square(const BigInt& x) const - { - return reduce(Botan::square(x)); - } - } diff --git a/src/math/numbertheory/reducer.h b/src/math/numbertheory/reducer.h index d234e0735..80c0f27e1 100644 --- a/src/math/numbertheory/reducer.h +++ b/src/math/numbertheory/reducer.h @@ -1,14 +1,14 @@ /* * Modular Reducer -* (C) 1999-2007 Jack Lloyd +* (C) 1999-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ -#ifndef BOTAN_MODARITH_H__ -#define BOTAN_MODARITH_H__ +#ifndef BOTAN_MODULAR_REDUCER_H__ +#define BOTAN_MODULAR_REDUCER_H__ -#include <botan/bigint.h> +#include <botan/numthry.h> namespace Botan { @@ -18,14 +18,30 @@ namespace Botan { class BOTAN_DLL Modular_Reducer { public: - BigInt multiply(const BigInt&, const BigInt&) const; - BigInt square(const BigInt&) const; - BigInt reduce(const BigInt&) const; + BigInt reduce(const BigInt& x) const; + + /** + * Multiply mod p + */ + BigInt multiply(const BigInt& x, const BigInt& y) const + { return reduce(x * y); } + + /** + * Square mod p + */ + BigInt square(const BigInt& x) const + { return reduce(Botan::square(x)); } + + /** + * Cube mod p + */ + BigInt cube(const BigInt& x) const + { return multiply(x, this->square(x)); } bool initialized() const { return (mod_words != 0); } Modular_Reducer() { mod_words = 0; } - Modular_Reducer(const BigInt&); + Modular_Reducer(const BigInt& mod); private: BigInt modulus, modulus_2, mu; u32bit mod_words, mod2_words, mu_words; |