aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib')
-rw-r--r--src/lib/pubkey/ec_group/curve_gfp.cpp7
-rw-r--r--src/lib/pubkey/ec_group/curve_gfp.h7
-rw-r--r--src/lib/pubkey/ec_group/ec_group.cpp2
-rw-r--r--src/lib/pubkey/ec_group/point_gfp.cpp31
-rw-r--r--src/lib/pubkey/ec_group/point_gfp.h26
-rw-r--r--src/lib/pubkey/ec_group/point_mul.cpp50
-rw-r--r--src/lib/pubkey/ec_group/point_mul.h3
7 files changed, 105 insertions, 21 deletions
diff --git a/src/lib/pubkey/ec_group/curve_gfp.cpp b/src/lib/pubkey/ec_group/curve_gfp.cpp
index 9f614ac61..e76636589 100644
--- a/src/lib/pubkey/ec_group/curve_gfp.cpp
+++ b/src/lib/pubkey/ec_group/curve_gfp.cpp
@@ -52,6 +52,8 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr
const BigInt& get_b_rep() const override { return m_b_r; }
+ const BigInt& get_1_rep() const override { return m_r; }
+
bool is_one(const BigInt& x) const override { return x == m_r; }
size_t get_p_words() const override { return m_p_words; }
@@ -197,7 +199,7 @@ class CurveGFp_NIST : public CurveGFp_Repr
{
public:
CurveGFp_NIST(size_t p_bits, const BigInt& a, const BigInt& b) :
- m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS)
+ m_1(1), m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS)
{
// All Solinas prime curves are assumed a == -3
}
@@ -209,6 +211,8 @@ class CurveGFp_NIST : public CurveGFp_Repr
const BigInt& get_b() const override { return m_b; }
+ const BigInt& get_1_rep() const override { return m_1; }
+
size_t get_p_words() const override { return m_p_words; }
size_t get_ws_size() const override { return 2*m_p_words + 4; }
@@ -242,6 +246,7 @@ class CurveGFp_NIST : public CurveGFp_Repr
virtual void redc(BigInt& x, secure_vector<word>& ws) const = 0;
// Curve parameters
+ BigInt m_1;
BigInt m_a, m_b;
size_t m_p_words; // cache of m_p.sig_words()
};
diff --git a/src/lib/pubkey/ec_group/curve_gfp.h b/src/lib/pubkey/ec_group/curve_gfp.h
index 3a17c6678..865bb68f8 100644
--- a/src/lib/pubkey/ec_group/curve_gfp.h
+++ b/src/lib/pubkey/ec_group/curve_gfp.h
@@ -44,6 +44,11 @@ class BOTAN_UNSTABLE_API CurveGFp_Repr
*/
virtual const BigInt& get_b_rep() const = 0;
+ /*
+ * Returns to_curve_rep(1)
+ */
+ virtual const BigInt& get_1_rep() const = 0;
+
virtual BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const = 0;
virtual void to_curve_rep(BigInt& x, secure_vector<word>& ws) const = 0;
@@ -120,6 +125,8 @@ class BOTAN_UNSTABLE_API CurveGFp final
const BigInt& get_b_rep() const { return m_repr->get_b_rep(); }
+ const BigInt& get_1_rep() const { return m_repr->get_1_rep(); }
+
bool a_is_minus_3() const { return m_repr->a_is_minus_3(); }
bool a_is_zero() const { return m_repr->a_is_zero(); }
diff --git a/src/lib/pubkey/ec_group/ec_group.cpp b/src/lib/pubkey/ec_group/ec_group.cpp
index d5a94c90c..fc512b733 100644
--- a/src/lib/pubkey/ec_group/ec_group.cpp
+++ b/src/lib/pubkey/ec_group/ec_group.cpp
@@ -528,7 +528,7 @@ PointGFp EC_Group::blinded_var_point_multiply(const PointGFp& point,
std::vector<BigInt>& ws) const
{
PointGFp_Var_Point_Precompute mul(point);
- mul.randomize_repr(rng);
+ mul.randomize_repr(rng, ws);
return mul.mul(k, rng, get_order(), ws);
}
diff --git a/src/lib/pubkey/ec_group/point_gfp.cpp b/src/lib/pubkey/ec_group/point_gfp.cpp
index 860459252..c65b4ac16 100644
--- a/src/lib/pubkey/ec_group/point_gfp.cpp
+++ b/src/lib/pubkey/ec_group/point_gfp.cpp
@@ -111,8 +111,7 @@ void PointGFp::add_affine(const word x_words[], size_t x_size,
// FIXME avoid the copy here
m_coord_x = BigInt(x_words, x_size);
m_coord_y = BigInt(y_words, y_size);
- m_coord_z = 1;
- m_curve.to_rep(m_coord_z, ws_bn[0].get_word_vector());
+ m_coord_z = m_curve.get_1_rep();
return;
}
@@ -284,6 +283,25 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
m_curve.mul(m_coord_z, T0, T4, ws);
}
+void PointGFp::mult2i(size_t iterations, std::vector<BigInt>& ws_bn)
+ {
+ if(iterations == 0)
+ return;
+
+ if(m_coord_y.is_zero())
+ {
+ *this = PointGFp(m_curve); // setting myself to zero
+ return;
+ }
+
+ /*
+ TODO we can save 2 squarings per iteration by computing
+ a*Z^4 using values cached from previous iteration
+ */
+ for(size_t i = 0; i != iterations; ++i)
+ mult2(ws_bn);
+ }
+
// *this *= 2
void PointGFp::mult2(std::vector<BigInt>& ws_bn)
{
@@ -301,7 +319,7 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
secure_vector<word>& ws = ws_bn[0].get_word_vector();
BigInt& T0 = ws_bn[1];
BigInt& T1 = ws_bn[2];
- BigInt& T2 = ws_bn[6];
+ BigInt& T2 = ws_bn[3];
BigInt& T3 = ws_bn[4];
BigInt& T4 = ws_bn[5];
@@ -459,13 +477,11 @@ void PointGFp::force_all_affine(std::vector<PointGFp>& points,
*/
const CurveGFp& curve = points[0].m_curve;
+ const BigInt& rep_1 = curve.get_1_rep();
if(ws.size() < curve.get_ws_size())
ws.resize(curve.get_ws_size());
- BigInt rep_1 = 1;
- curve.to_rep(rep_1, ws);
-
std::vector<BigInt> c(points.size());
c[0] = points[0].m_coord_z;
@@ -512,8 +528,7 @@ void PointGFp::force_affine()
const BigInt z3_inv = m_curve.mul_to_tmp(z_inv, z2_inv, ws);
m_coord_x = m_curve.mul_to_tmp(m_coord_x, z2_inv, ws);
m_coord_y = m_curve.mul_to_tmp(m_coord_y, z3_inv, ws);
- m_coord_z = 1;
- m_curve.to_rep(m_coord_z, ws);
+ m_coord_z = m_curve.get_1_rep();
}
bool PointGFp::is_affine() const
diff --git a/src/lib/pubkey/ec_group/point_gfp.h b/src/lib/pubkey/ec_group/point_gfp.h
index 2a9948fde..271d7383a 100644
--- a/src/lib/pubkey/ec_group/point_gfp.h
+++ b/src/lib/pubkey/ec_group/point_gfp.h
@@ -152,6 +152,13 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final
const BigInt& get_y() const { return m_coord_y; }
const BigInt& get_z() const { return m_coord_z; }
+ void swap_coords(BigInt& new_x, BigInt& new_y, BigInt& new_z)
+ {
+ m_coord_x.swap(new_x);
+ m_coord_y.swap(new_y);
+ m_coord_z.swap(new_z);
+ }
+
/**
* Force this point to affine coordinates
*/
@@ -236,6 +243,13 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final
void mult2(std::vector<BigInt>& workspace);
/**
+ * Repeated point doubling
+ * @param i number of doublings to perform
+ * @param workspace temp space, at least WORKSPACE_SIZE elements
+ */
+ void mult2i(size_t i, std::vector<BigInt>& workspace);
+
+ /**
* Point addition
* @param other the point to add to *this
* @param workspace temp space, at least WORKSPACE_SIZE elements
@@ -249,6 +263,18 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final
}
/**
+ * Point doubling
+ * @param workspace temp space, at least WORKSPACE_SIZE elements
+ * @return *this doubled
+ */
+ PointGFp double_of(std::vector<BigInt>& workspace) const
+ {
+ PointGFp x = (*this);
+ x.mult2(workspace);
+ return x;
+ }
+
+ /**
* Return the zero (aka infinite) point associated with this curve
*/
PointGFp zero() const { return PointGFp(m_curve); }
diff --git a/src/lib/pubkey/ec_group/point_mul.cpp b/src/lib/pubkey/ec_group/point_mul.cpp
index d052b837c..17087a6ed 100644
--- a/src/lib/pubkey/ec_group/point_mul.cpp
+++ b/src/lib/pubkey/ec_group/point_mul.cpp
@@ -140,22 +140,54 @@ PointGFp_Var_Point_Precompute::PointGFp_Var_Point_Precompute(const PointGFp& poi
{
m_window_bits = 4;
+ std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
+
m_U.resize(1U << m_window_bits);
m_U[0] = point.zero();
m_U[1] = point;
- std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
- for(size_t i = 2; i < m_U.size(); ++i)
+ for(size_t i = 2; i < m_U.size(); i += 2)
{
- m_U[i] = m_U[i-1];
- m_U[i].add(point, ws);
+ m_U[i] = m_U[i/2].double_of(ws);
+ m_U[i+1] = m_U[i].plus(point, ws);
}
}
-void PointGFp_Var_Point_Precompute::randomize_repr(RandomNumberGenerator& rng)
+void PointGFp_Var_Point_Precompute::randomize_repr(RandomNumberGenerator& rng,
+ std::vector<BigInt>& ws_bn)
{
+ if(BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS <= 1)
+ return;
+
+ if(ws_bn.size() < 7)
+ ws_bn.resize(7);
+
+ BigInt& mask = ws_bn[0];
+ BigInt& mask2 = ws_bn[1];
+ BigInt& mask3 = ws_bn[2];
+ BigInt& new_x = ws_bn[3];
+ BigInt& new_y = ws_bn[4];
+ BigInt& new_z = ws_bn[5];
+ secure_vector<word>& ws = ws_bn[6].get_word_vector();
+
+ const CurveGFp& curve = m_U[0].get_curve();
+
+ // Skipping zero point since it can't be randomized
for(size_t i = 1; i != m_U.size(); ++i)
- m_U[i].randomize_repr(rng);
+ {
+ mask.randomize(rng, BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS, false);
+ // Easy way of ensuring mask != 0
+ mask.set_bit(0);
+
+ curve.sqr(mask2, mask, ws);
+ curve.mul(mask3, mask, mask2, ws);
+
+ curve.mul(new_x, m_U[i].get_x(), mask2, ws);
+ curve.mul(new_y, m_U[i].get_y(), mask3, ws);
+ curve.mul(new_z, m_U[i].get_z(), mask, ws);
+
+ m_U[i].swap_coords(new_x, new_y, new_z);
+ }
}
PointGFp PointGFp_Var_Point_Precompute::mul(const BigInt& k,
@@ -193,8 +225,7 @@ PointGFp PointGFp_Var_Point_Precompute::mul(const BigInt& k,
while(windows)
{
- for(size_t i = 0; i != m_window_bits; ++i)
- R.mult2(ws);
+ R.mult2i(m_window_bits, ws);
const uint32_t inner_nibble = scalar.get_substring((windows-1)*m_window_bits, m_window_bits);
// cache side channel here, we are relying on blinding...
@@ -261,8 +292,7 @@ PointGFp PointGFp_Multi_Point_Precompute::multi_exp(const BigInt& z1,
{
if(i > 0)
{
- H.mult2(ws);
- H.mult2(ws);
+ H.mult2i(2, ws);
}
const uint8_t z1_b = z1.get_substring(z_bits - i - 2, 2);
diff --git a/src/lib/pubkey/ec_group/point_mul.h b/src/lib/pubkey/ec_group/point_mul.h
index cfce05d5c..da1d3b744 100644
--- a/src/lib/pubkey/ec_group/point_mul.h
+++ b/src/lib/pubkey/ec_group/point_mul.h
@@ -43,7 +43,8 @@ class PointGFp_Var_Point_Precompute
public:
PointGFp_Var_Point_Precompute(const PointGFp& point);
- void randomize_repr(RandomNumberGenerator& rng);
+ void randomize_repr(RandomNumberGenerator& rng,
+ std::vector<BigInt>& ws);
PointGFp mul(const BigInt& k,
RandomNumberGenerator& rng,
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-02 22:42:47 +0000