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.h9
-rw-r--r--src/math/numbertheory/point_gfp.cpp82
-rw-r--r--src/math/numbertheory/point_gfp.h4
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
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-14 15:20:23 +0000