aboutsummaryrefslogtreecommitdiffstats
path: root/src/math/numbertheory
diff options
context:
space:
mode:
Diffstat (limited to 'src/math/numbertheory')
-rw-r--r--src/math/numbertheory/curve_gfp.h96
-rw-r--r--src/math/numbertheory/info.txt3
-rw-r--r--src/math/numbertheory/numthry.cpp100
-rw-r--r--src/math/numbertheory/numthry.h16
-rw-r--r--src/math/numbertheory/point_gfp.cpp423
-rw-r--r--src/math/numbertheory/point_gfp.h201
-rw-r--r--src/math/numbertheory/reducer.cpp19
-rw-r--r--src/math/numbertheory/reducer.h32
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;