aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/lib/pubkey/ec_group/ec_group.cpp3
-rw-r--r--src/lib/pubkey/ec_group/point_gfp.cpp60
-rw-r--r--src/lib/pubkey/ec_group/point_mul.cpp81
-rw-r--r--src/lib/pubkey/ec_group/point_mul.h16
-rw-r--r--src/lib/pubkey/ecdsa/ecdsa.cpp7
5 files changed, 103 insertions, 64 deletions
diff --git a/src/lib/pubkey/ec_group/ec_group.cpp b/src/lib/pubkey/ec_group/ec_group.cpp
index 50a4d85c7..ed1a75b48 100644
--- a/src/lib/pubkey/ec_group/ec_group.cpp
+++ b/src/lib/pubkey/ec_group/ec_group.cpp
@@ -473,7 +473,8 @@ PointGFp EC_Group::point(const BigInt& x, const BigInt& y) const
PointGFp EC_Group::point_multiply(const BigInt& x, const PointGFp& pt, const BigInt& y) const
{
- return multi_exponentiate(get_base_point(), x, pt, y);
+ PointGFp_Multi_Point_Precompute xy_mul(get_base_point(), pt);
+ return xy_mul.multi_exp(x, y);
}
PointGFp EC_Group::blinded_base_point_multiply(const BigInt& k,
diff --git a/src/lib/pubkey/ec_group/point_gfp.cpp b/src/lib/pubkey/ec_group/point_gfp.cpp
index 51cb7d153..48ae91f3c 100644
--- a/src/lib/pubkey/ec_group/point_gfp.cpp
+++ b/src/lib/pubkey/ec_group/point_gfp.cpp
@@ -361,66 +361,6 @@ PointGFp& PointGFp::operator*=(const BigInt& scalar)
return *this;
}
-PointGFp multi_exponentiate(const PointGFp& x, const BigInt& z1,
- const PointGFp& y, const BigInt& z2)
- {
- const size_t z_bits = round_up(std::max(z1.bits(), z2.bits()), 2);
-
- std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
-
- PointGFp x2 = x;
- x2.mult2(ws);
-
- const PointGFp x3(x2.plus(x, ws));
-
- PointGFp y2 = y;
- y2.mult2(ws);
-
- const PointGFp y3(y2.plus(y, ws));
-
- const PointGFp M[16] = {
- x.zero(), // 0000
- x, // 0001
- x2, // 0010
- x3, // 0011
- y, // 0100
- y.plus(x, ws), // 0101
- y.plus(x2, ws), // 0110
- y.plus(x3, ws), // 0111
- y2, // 1000
- y2.plus(x, ws), // 1001
- y2.plus(x2, ws), // 1010
- y2.plus(x3, ws), // 1011
- y3, // 1100
- y3.plus(x, ws), // 1101
- y3.plus(x2, ws), // 1110
- y3.plus(x3, ws), // 1111
- };
-
- PointGFp H = x.zero();
-
- for(size_t i = 0; i != z_bits; i += 2)
- {
- if(i > 0)
- {
- H.mult2(ws);
- H.mult2(ws);
- }
-
- const uint8_t z1_b = z1.get_substring(z_bits - i - 2, 2);
- const uint8_t z2_b = z2.get_substring(z_bits - i - 2, 2);
-
- const uint8_t z12 = (4*z2_b) + z1_b;
-
- H.add(M[z12], ws);
- }
-
- if(z1.is_negative() != z2.is_negative())
- H.negate();
-
- return H;
- }
-
PointGFp operator*(const BigInt& scalar, const PointGFp& point)
{
BOTAN_DEBUG_ASSERT(point.on_the_curve());
diff --git a/src/lib/pubkey/ec_group/point_mul.cpp b/src/lib/pubkey/ec_group/point_mul.cpp
index 7acb60b6a..adddaaa37 100644
--- a/src/lib/pubkey/ec_group/point_mul.cpp
+++ b/src/lib/pubkey/ec_group/point_mul.cpp
@@ -10,6 +10,13 @@
namespace Botan {
+PointGFp multi_exponentiate(const PointGFp& x, const BigInt& z1,
+ const PointGFp& y, const BigInt& z2)
+ {
+ PointGFp_Multi_Point_Precompute xy_mul(x, y);
+ return xy_mul.multi_exp(z1, z2);
+ }
+
Blinded_Point_Multiply::Blinded_Point_Multiply(const PointGFp& base,
const BigInt& order,
size_t h) :
@@ -178,4 +185,78 @@ PointGFp PointGFp_Var_Point_Precompute::mul(const BigInt& k,
return R;
}
+
+PointGFp_Multi_Point_Precompute::PointGFp_Multi_Point_Precompute(const PointGFp& x,
+ const PointGFp& y)
+ {
+ std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
+
+ PointGFp x2 = x;
+ x2.mult2(ws);
+
+ const PointGFp x3(x2.plus(x, ws));
+
+ PointGFp y2 = y;
+ y2.mult2(ws);
+
+ const PointGFp y3(y2.plus(y, ws));
+
+ m_M.reserve(15);
+
+ m_M.push_back(x);
+ m_M.push_back(x2);
+ m_M.push_back(x3);
+
+ m_M.push_back(y);
+ m_M.push_back(y.plus(x, ws));
+ m_M.push_back(y.plus(x2, ws));
+ m_M.push_back(y.plus(x3, ws));
+
+ m_M.push_back(y2);
+ m_M.push_back(y2.plus(x, ws));
+ m_M.push_back(y2.plus(x2, ws));
+ m_M.push_back(y2.plus(x3, ws));
+
+ m_M.push_back(y3);
+ m_M.push_back(y3.plus(x, ws));
+ m_M.push_back(y3.plus(x2, ws));
+ m_M.push_back(y3.plus(x3, ws));
+
+ PointGFp::force_all_affine(m_M, ws[0].get_word_vector());
+ }
+
+PointGFp PointGFp_Multi_Point_Precompute::multi_exp(const BigInt& z1,
+ const BigInt& z2) const
+ {
+ std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
+
+ const size_t z_bits = round_up(std::max(z1.bits(), z2.bits()), 2);
+
+ PointGFp H = m_M[0].zero();
+
+ for(size_t i = 0; i != z_bits; i += 2)
+ {
+ if(i > 0)
+ {
+ H.mult2(ws);
+ H.mult2(ws);
+ }
+
+ const uint8_t z1_b = z1.get_substring(z_bits - i - 2, 2);
+ const uint8_t z2_b = z2.get_substring(z_bits - i - 2, 2);
+
+ const uint8_t z12 = (4*z2_b) + z1_b;
+
+ if(z12)
+ {
+ H.add_affine(m_M[z12-1], ws);
+ }
+ }
+
+ if(z1.is_negative() != z2.is_negative())
+ H.negate();
+
+ return H;
+ }
+
}
diff --git a/src/lib/pubkey/ec_group/point_mul.h b/src/lib/pubkey/ec_group/point_mul.h
index 97fd326a2..9a19f90d4 100644
--- a/src/lib/pubkey/ec_group/point_mul.h
+++ b/src/lib/pubkey/ec_group/point_mul.h
@@ -42,6 +42,22 @@ class PointGFp_Var_Point_Precompute
std::vector<PointGFp> m_U;
};
+class PointGFp_Multi_Point_Precompute
+ {
+ public:
+ PointGFp_Multi_Point_Precompute(const PointGFp& g1,
+ const PointGFp& g2);
+
+ /*
+ * Return (g1*k1 + g2*k2)
+ * Not constant time, intended to use with public inputs
+ */
+ PointGFp multi_exp(const BigInt& k1,
+ const BigInt& k2) const;
+ private:
+ std::vector<PointGFp> m_M;
+ };
+
}
#endif
diff --git a/src/lib/pubkey/ecdsa/ecdsa.cpp b/src/lib/pubkey/ecdsa/ecdsa.cpp
index a2877f7fc..6ff02e8c9 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.cpp
+++ b/src/lib/pubkey/ecdsa/ecdsa.cpp
@@ -10,6 +10,7 @@
#include <botan/ecdsa.h>
#include <botan/internal/pk_ops_impl.h>
+#include <botan/internal/point_mul.h>
#include <botan/keypair.h>
#include <botan/reducer.h>
#include <botan/emsa.h>
@@ -112,7 +113,7 @@ class ECDSA_Verification_Operation final : public PK_Ops::Verification_with_EMSA
const std::string& emsa) :
PK_Ops::Verification_with_EMSA(emsa),
m_group(ecdsa.domain()),
- m_public_point(ecdsa.public_point())
+ m_gy_mul(m_group.get_base_point(), ecdsa.public_point())
{
}
@@ -124,7 +125,7 @@ class ECDSA_Verification_Operation final : public PK_Ops::Verification_with_EMSA
const uint8_t sig[], size_t sig_len) override;
private:
const EC_Group m_group;
- const PointGFp& m_public_point;
+ const PointGFp_Multi_Point_Precompute m_gy_mul;
};
bool ECDSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
@@ -145,7 +146,7 @@ bool ECDSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
const BigInt u1 = m_group.multiply_mod_order(e, w);
const BigInt u2 = m_group.multiply_mod_order(r, w);
- const PointGFp R = m_group.point_multiply(u1, m_public_point, u2);
+ const PointGFp R = m_gy_mul.multi_exp(u1, u2);
if(R.is_zero())
return false;
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-28 16:43:47 +0000