aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/build-data/buildh.in6
-rw-r--r--src/cli/speed.cpp23
-rw-r--r--src/fuzzer/ecc_helper.h40
-rw-r--r--src/lib/pubkey/ec_group/curve_gfp.cpp42
-rw-r--r--src/lib/pubkey/ec_group/curve_gfp.h11
-rw-r--r--src/lib/pubkey/ec_group/ec_group.cpp24
-rw-r--r--src/lib/pubkey/ec_group/ec_group.h13
-rw-r--r--src/lib/pubkey/ec_group/info.txt10
-rw-r--r--src/lib/pubkey/ec_group/point_gfp.cpp160
-rw-r--r--src/lib/pubkey/ec_group/point_gfp.h77
-rw-r--r--src/lib/pubkey/ec_group/point_mul.cpp131
-rw-r--r--src/lib/pubkey/ec_group/point_mul.h47
-rw-r--r--src/lib/pubkey/ecdh/ecdh.cpp5
-rw-r--r--src/lib/pubkey/ecies/ecies.cpp5
-rw-r--r--src/lib/pubkey/sm2/sm2_enc.cpp14
-rw-r--r--src/tests/unit_ecc.cpp26
16 files changed, 460 insertions, 174 deletions
diff --git a/src/build-data/buildh.in b/src/build-data/buildh.in
index 06ae5b598..fcdd8e6d6 100644
--- a/src/build-data/buildh.in
+++ b/src/build-data/buildh.in
@@ -124,12 +124,6 @@
#define BOTAN_USE_VOLATILE_MEMSET_FOR_ZERO 1
/*
-* If enabled the ECC implementation will use scalar blinding with order.bits()/2
-* bit long masks.
-*/
-#define BOTAN_POINTGFP_USE_SCALAR_BLINDING 1
-
-/*
* Set number of bits used to generate mask for blinding the
* representation of an ECC point. Set to zero to disable this
* side-channel countermeasure.
diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index 209e8d68a..42cb10ca6 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -1258,28 +1258,35 @@ class Speed final : public Command
{
const Botan::EC_Group group(group_name);
- std::unique_ptr<Timer> mult_timer = make_timer(group_name + " scalar mult");
- std::unique_ptr<Timer> blinded_mult_timer = make_timer(group_name + " blinded scalar mult");
+ std::unique_ptr<Timer> mult_timer = make_timer(group_name + " Montgomery ladder");
+ std::unique_ptr<Timer> blinded_mult_timer = make_timer(group_name + " blinded comb");
+ std::unique_ptr<Timer> blinded_var_mult_timer = make_timer(group_name + " blinded window");
- const Botan::BigInt scalar(rng(), group.get_p_bits());
const Botan::PointGFp& base_point = group.get_base_point();
- const Botan::PointGFp_Blinded_Multiplier scalar_mult(base_point);
-
std::vector<Botan::BigInt> ws;
- while(blinded_mult_timer->under(runtime))
+ while(mult_timer->under(runtime) &&
+ blinded_mult_timer->under(runtime) &&
+ blinded_var_mult_timer->under(runtime))
{
+ const Botan::BigInt scalar(rng(), group.get_p_bits());
+
const Botan::PointGFp r1 = mult_timer->run([&]() { return base_point * scalar; });
const Botan::PointGFp r2 = blinded_mult_timer->run(
- [&]() { return scalar_mult.mul(scalar, group.get_order(), rng(), ws); });
+ [&]() { return group.blinded_base_point_multiply(scalar, rng(), ws); });
+
+ const Botan::PointGFp r3 = blinded_var_mult_timer->run(
+ [&]() { return group.blinded_var_point_multiply(base_point, scalar, rng(), ws); });
- BOTAN_ASSERT_EQUAL(r1, r2, "Same point computed by both methods");
+ BOTAN_ASSERT_EQUAL(r1, r2, "Same point computed by Montgomery and comb");
+ BOTAN_ASSERT_EQUAL(r1, r3, "Same point computed by Montgomery and window");
}
record_result(mult_timer);
record_result(blinded_mult_timer);
+ record_result(blinded_var_mult_timer);
}
}
diff --git a/src/fuzzer/ecc_helper.h b/src/fuzzer/ecc_helper.h
index cd0ef0ac9..ce0f56988 100644
--- a/src/fuzzer/ecc_helper.h
+++ b/src/fuzzer/ecc_helper.h
@@ -24,35 +24,45 @@ void check_ecc_math(const Botan::EC_Group& group,
{
// These depend only on the group, which is also static
static const Botan::PointGFp base_point = group.get_base_point();
- static Botan::PointGFp_Blinded_Multiplier blind(base_point);
// This is shared across runs to reduce overhead
- static std::vector<Botan::BigInt> ws(10);
+ static std::vector<Botan::BigInt> ws(Botan::PointGFp::WORKSPACE_SIZE);
const size_t hlen = len / 2;
const Botan::BigInt a = Botan::BigInt::decode(in, hlen);
const Botan::BigInt b = Botan::BigInt::decode(in + hlen, len - hlen);
-
const Botan::BigInt c = a + b;
- const Botan::PointGFp P = base_point * a;
- const Botan::PointGFp Q = base_point * b;
- const Botan::PointGFp R = base_point * c;
+ const Botan::PointGFp P1 = base_point * a;
+ const Botan::PointGFp Q1 = base_point * b;
+ const Botan::PointGFp R1 = base_point * c;
- const Botan::PointGFp A1 = P + Q;
- const Botan::PointGFp A2 = Q + P;
+ const Botan::PointGFp S1 = P1 + Q1;
+ const Botan::PointGFp T1 = Q1 + P1;
- FUZZER_ASSERT_EQUAL(A1, A2);
+ FUZZER_ASSERT_EQUAL(S1, R1);
+ FUZZER_ASSERT_EQUAL(T1, R1);
- const Botan::PointGFp P1 = blind.mul(a, group.get_order(), fuzzer_rng(), ws);
- const Botan::PointGFp Q1 = blind.mul(b, group.get_order(), fuzzer_rng(), ws);
- const Botan::PointGFp R1 = blind.mul(c, group.get_order(), fuzzer_rng(), ws);
+ const Botan::PointGFp P2 = group.blinded_base_point_multiply(a, fuzzer_rng(), ws);
+ const Botan::PointGFp Q2 = group.blinded_base_point_multiply(b, fuzzer_rng(), ws);
+ const Botan::PointGFp R2 = group.blinded_base_point_multiply(c, fuzzer_rng(), ws);
+ const Botan::PointGFp S2 = P2 + Q2;
+ const Botan::PointGFp T2 = Q2 + P2;
- const Botan::PointGFp S1 = P1 + Q1;
- const Botan::PointGFp S2 = Q1 + P1;
+ FUZZER_ASSERT_EQUAL(S2, R2);
+ FUZZER_ASSERT_EQUAL(T2, R2);
+
+ const Botan::PointGFp P3 = group.blinded_var_point_multiply(base_point, a, fuzzer_rng(), ws);
+ const Botan::PointGFp Q3 = group.blinded_var_point_multiply(base_point, b, fuzzer_rng(), ws);
+ const Botan::PointGFp R3 = group.blinded_var_point_multiply(base_point, c, fuzzer_rng(), ws);
+ const Botan::PointGFp S3 = P3 + Q3;
+ const Botan::PointGFp T3 = Q3 + P3;
+
+ FUZZER_ASSERT_EQUAL(S3, R3);
+ FUZZER_ASSERT_EQUAL(T3, R3);
FUZZER_ASSERT_EQUAL(S1, S2);
- FUZZER_ASSERT_EQUAL(S1, A1);
+ FUZZER_ASSERT_EQUAL(S1, S3);
}
}
diff --git a/src/lib/pubkey/ec_group/curve_gfp.cpp b/src/lib/pubkey/ec_group/curve_gfp.cpp
index 216f2a894..e17812ca4 100644
--- a/src/lib/pubkey/ec_group/curve_gfp.cpp
+++ b/src/lib/pubkey/ec_group/curve_gfp.cpp
@@ -25,13 +25,15 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr
m_p_words(m_p.sig_words()),
m_p_dash(monty_inverse(m_p.word_at(0)))
{
- const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
-
Modular_Reducer mod_p(m_p);
- m_r2 = mod_p.square(r);
- m_a_r = mod_p.multiply(r, m_a);
- m_b_r = mod_p.multiply(r, m_b);
+ m_r.set_bit(m_p_words * BOTAN_MP_WORD_BITS);
+ m_r = mod_p.reduce(m_r);
+
+ m_r2 = mod_p.square(m_r);
+ m_r3 = mod_p.multiply(m_r, m_r2);
+ m_a_r = mod_p.multiply(m_r, m_a);
+ m_b_r = mod_p.multiply(m_r, m_b);
}
const BigInt& get_a() const override { return m_a; }
@@ -44,8 +46,12 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr
const BigInt& get_b_rep() const override { return m_b_r; }
+ bool is_one(const BigInt& x) const override { return x == m_r; }
+
size_t get_p_words() const override { return m_p_words; }
+ BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
+
void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override;
void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override;
@@ -56,14 +62,25 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr
void curve_sqr(BigInt& z, const BigInt& x,
secure_vector<word>& ws) const override;
private:
- BigInt m_p, m_a, m_b;
+ BigInt m_p;
+ BigInt m_a, m_b;
+ BigInt m_a_r, m_b_r;
size_t m_p_words; // cache of m_p.sig_words()
// Montgomery parameters
- BigInt m_r2, m_a_r, m_b_r;
+ BigInt m_r, m_r2, m_r3;
word m_p_dash;
};
+BigInt CurveGFp_Montgomery::invert_element(const BigInt& x, secure_vector<word>& ws) const
+ {
+ // Should we use Montgomery inverse instead?
+ const BigInt inv = inverse_mod(x, m_p);
+ BigInt res;
+ curve_mul(res, inv, m_r3, ws);
+ return res;
+ }
+
void CurveGFp_Montgomery::to_curve_rep(BigInt& x, secure_vector<word>& ws) const
{
const BigInt tx = x;
@@ -149,12 +166,16 @@ class CurveGFp_NIST : public CurveGFp_Repr
const BigInt& get_b_rep() const override { return m_b; }
+ bool is_one(const BigInt& x) const override { return x == 1; }
+
void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override
{ redc(x, ws); }
void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override
{ redc(x, ws); }
+ BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
+
void curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
secure_vector<word>& ws) const override;
@@ -168,6 +189,13 @@ class CurveGFp_NIST : public CurveGFp_Repr
size_t m_p_words; // cache of m_p.sig_words()
};
+
+BigInt CurveGFp_NIST::invert_element(const BigInt& x, secure_vector<word>& ws) const
+ {
+ BOTAN_UNUSED(ws);
+ return inverse_mod(x, get_p());
+ }
+
void CurveGFp_NIST::curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
secure_vector<word>& ws) const
{
diff --git a/src/lib/pubkey/ec_group/curve_gfp.h b/src/lib/pubkey/ec_group/curve_gfp.h
index 60e1a485d..d9649474b 100644
--- a/src/lib/pubkey/ec_group/curve_gfp.h
+++ b/src/lib/pubkey/ec_group/curve_gfp.h
@@ -26,6 +26,8 @@ class BOTAN_UNSTABLE_API CurveGFp_Repr
virtual size_t get_p_words() const = 0;
+ virtual bool is_one(const BigInt& x) const = 0;
+
/*
* Returns to_curve_rep(get_a())
*/
@@ -36,6 +38,8 @@ class BOTAN_UNSTABLE_API CurveGFp_Repr
*/
virtual const BigInt& get_b_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;
virtual void from_curve_rep(BigInt& x, secure_vector<word>& ws) const = 0;
@@ -96,6 +100,13 @@ class BOTAN_UNSTABLE_API CurveGFp final
const BigInt& get_b_rep() const { return m_repr->get_b_rep(); }
+ bool is_one(const BigInt& x) const { return m_repr->is_one(x); }
+
+ BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const
+ {
+ return m_repr->invert_element(x, ws);
+ }
+
void to_rep(BigInt& x, secure_vector<word>& ws) const
{
m_repr->to_curve_rep(x, ws);
diff --git a/src/lib/pubkey/ec_group/ec_group.cpp b/src/lib/pubkey/ec_group/ec_group.cpp
index 9da1cd81f..723a4148e 100644
--- a/src/lib/pubkey/ec_group/ec_group.cpp
+++ b/src/lib/pubkey/ec_group/ec_group.cpp
@@ -9,6 +9,7 @@
*/
#include <botan/ec_group.h>
+#include <botan/internal/point_mul.h>
#include <botan/ber_dec.h>
#include <botan/der_enc.h>
#include <botan/oids.h>
@@ -17,10 +18,6 @@
#include <botan/mutex.h>
#include <vector>
-#if defined(BOTAN_HAS_SYSTEM_RNG)
- #include <botan/system_rng.h>
-#endif
-
namespace Botan {
class EC_Group_Data final
@@ -42,15 +39,12 @@ class EC_Group_Data final
m_order(order),
m_cofactor(cofactor),
m_mod_order(order),
- m_base_mult(m_base_point, 5),
+ m_base_mult(m_base_point),
m_oid(oid),
m_p_bits(p.bits()),
m_order_bits(order.bits()),
m_a_is_minus_3(a == p - 3)
{
-#if defined(BOTAN_HAS_SYSTEM_RNG)
- m_base_mult.randomize(system_rng());
-#endif
}
bool match(const BigInt& p, const BigInt& a, const BigInt& b,
@@ -97,7 +91,7 @@ class EC_Group_Data final
RandomNumberGenerator& rng,
std::vector<BigInt>& ws) const
{
- return m_base_mult.mul(k, m_order, rng, ws);
+ return m_base_mult.mul(k, rng, m_order, ws);
}
private:
@@ -109,7 +103,7 @@ class EC_Group_Data final
BigInt m_order;
BigInt m_cofactor;
Modular_Reducer m_mod_order;
- PointGFp_Blinded_Multiplier m_base_mult;
+ PointGFp_Base_Point_Precompute m_base_mult;
OID m_oid;
size_t m_p_bits;
size_t m_order_bits;
@@ -489,6 +483,16 @@ PointGFp EC_Group::blinded_base_point_multiply(const BigInt& k,
return data().blinded_base_point_multiply(k, rng, ws);
}
+PointGFp EC_Group::blinded_var_point_multiply(const PointGFp& point,
+ const BigInt& k,
+ RandomNumberGenerator& rng,
+ std::vector<BigInt>& ws) const
+ {
+ PointGFp_Var_Point_Precompute mul(point);
+ mul.randomize_repr(rng);
+ return mul.mul(k, rng, get_order(), ws);
+ }
+
PointGFp EC_Group::zero_point() const
{
return PointGFp(data().curve());
diff --git a/src/lib/pubkey/ec_group/ec_group.h b/src/lib/pubkey/ec_group/ec_group.h
index 938059fc4..8238c2902 100644
--- a/src/lib/pubkey/ec_group/ec_group.h
+++ b/src/lib/pubkey/ec_group/ec_group.h
@@ -247,6 +247,19 @@ class BOTAN_PUBLIC_API(2,0) EC_Group final
std::vector<BigInt>& ws) const;
/**
+ * Blinded point multiplication, attempts resistance to side channels
+ * @param point input point
+ * @param k the scalar
+ * @param rng a random number generator
+ * @param ws a temp workspace
+ * @return point*k
+ */
+ PointGFp blinded_var_point_multiply(const PointGFp& point,
+ const BigInt& k,
+ RandomNumberGenerator& rng,
+ std::vector<BigInt>& ws) const;
+
+ /**
* Return the zero (or infinite) point on this curve
*/
PointGFp zero_point() const;
diff --git a/src/lib/pubkey/ec_group/info.txt b/src/lib/pubkey/ec_group/info.txt
index a0d025379..e382e25a5 100644
--- a/src/lib/pubkey/ec_group/info.txt
+++ b/src/lib/pubkey/ec_group/info.txt
@@ -8,3 +8,13 @@ asn1
numbertheory
pem
</requires>
+
+<header:internal>
+point_mul.h
+</header:internal>
+
+<header:public>
+curve_gfp.h
+ec_group.h
+point_gfp.h
+</header:public>
diff --git a/src/lib/pubkey/ec_group/point_gfp.cpp b/src/lib/pubkey/ec_group/point_gfp.cpp
index da8b292f4..7968d2dcd 100644
--- a/src/lib/pubkey/ec_group/point_gfp.cpp
+++ b/src/lib/pubkey/ec_group/point_gfp.cpp
@@ -63,9 +63,113 @@ void PointGFp::randomize_repr(RandomNumberGenerator& rng)
}
}
+void PointGFp::add_affine(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
+ {
+ if(rhs.is_zero())
+ return;
+
+ if(is_zero())
+ {
+ m_coord_x = rhs.m_coord_x;
+ m_coord_y = rhs.m_coord_y;
+ m_coord_z = rhs.m_coord_z;
+ return;
+ }
+
+ BOTAN_ASSERT(rhs.is_affine(), "PointGFp::add_affine requires arg be affine point");
+
+ /*
+ https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
+ simplified with Z2 = 1
+ */
+
+ const BigInt& p = m_curve.get_p();
+
+ const size_t cap_size = 2*m_curve.get_p_words() + 2;
+
+ BOTAN_ASSERT(ws_bn.size() >= WORKSPACE_SIZE, "Expected size for PointGFp::add workspace");
+
+ for(size_t i = 0; i != ws_bn.size(); ++i)
+ ws_bn[i].ensure_capacity(cap_size);
+
+ secure_vector<word>& ws = ws_bn[0].get_word_vector();
+
+ BigInt& T0 = ws_bn[1];
+ BigInt& T1 = ws_bn[2];
+ BigInt& T2 = ws_bn[3];
+ BigInt& T3 = ws_bn[4];
+ BigInt& T4 = ws_bn[5];
+
+ /*
+ https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
+ */
+
+ m_curve.sqr(T3, m_coord_z, ws); // z1^2
+ m_curve.mul(T4, rhs.m_coord_x, T3, ws); // x2*z1^2
+
+ m_curve.mul(T2, m_coord_z, T3, ws); // z1^3
+ m_curve.mul(T0, rhs.m_coord_y, T2, ws); // y2*z1^3
+
+ T4 -= m_coord_x; // x2*z1^2 - x1*z2^2
+ if(T4.is_negative())
+ T4 += p;
+
+ T0 -= m_coord_y;
+ if(T0.is_negative())
+ T0 += p;
+
+ if(T4.is_zero())
+ {
+ if(T0.is_zero())
+ {
+ mult2(ws_bn);
+ return;
+ }
+
+ // setting to zero:
+ m_coord_x = 0;
+ m_coord_y = 1;
+ m_coord_z = 0;
+ return;
+ }
+
+ m_curve.sqr(T2, T4, ws);
+
+ m_curve.mul(T3, m_coord_x, T2, ws);
+
+ m_curve.mul(T1, T2, T4, ws);
+
+ m_curve.sqr(m_coord_x, T0, ws);
+ m_coord_x -= T1;
+ m_coord_x -= T3;
+ m_coord_x -= T3;
+ while(m_coord_x.is_negative())
+ m_coord_x += p;
+
+ T3 -= m_coord_x;
+ if(T3.is_negative())
+ T3 += p;
+
+ T2 = m_coord_y;
+ m_curve.mul(m_coord_y, T0, T3, ws);
+ m_curve.mul(T3, T2, T1, ws);
+ m_coord_y -= T3;
+ if(m_coord_y.is_negative())
+ m_coord_y += p;
+
+ T3 = m_coord_z;
+ m_curve.mul(m_coord_z, T3, T4, ws);
+ }
+
// Point addition
void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
{
+ if(rhs.is_zero())
+ return;
+
+ if(rhs.is_affine())
+ return this->add_affine(rhs, ws_bn);
+
if(is_zero())
{
m_coord_x = rhs.m_coord_x;
@@ -73,8 +177,6 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
m_coord_z = rhs.m_coord_z;
return;
}
- else if(rhs.is_zero())
- return;
const BigInt& p = m_curve.get_p();
@@ -345,17 +447,48 @@ PointGFp operator*(const BigInt& scalar, const PointGFp& point)
return R[0];
}
+void PointGFp::force_affine()
+ {
+ if(is_zero())
+ throw Invalid_State("Cannot convert zero ECC point to affine");
+
+ secure_vector<word> ws;
+ BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, ws);
+ BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, ws);
+
+ const BigInt z5 = m_curve.mul_to_tmp(z2, z3, ws);
+ const BigInt z5_inv = m_curve.invert_element(z5, ws);
+ const BigInt z2_inv = m_curve.mul_to_tmp(z5_inv, z3, ws);
+ const BigInt z3_inv = m_curve.mul_to_tmp(z5_inv, z2, 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);
+ }
+
+bool PointGFp::is_affine() const
+ {
+ return m_curve.is_one(m_coord_z);
+ }
+
BigInt PointGFp::get_affine_x() const
{
if(is_zero())
throw Illegal_Transformation("Cannot convert zero point to affine");
secure_vector<word> monty_ws;
- BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
- m_curve.from_rep(z2, monty_ws);
- z2 = inverse_mod(z2, m_curve.get_p());
- return m_curve.mul_to_tmp(z2, m_coord_x, monty_ws);
+ if(is_affine())
+ return m_curve.from_rep(m_coord_x, monty_ws);
+
+ const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
+ const BigInt z2_inv = m_curve.invert_element(z2, monty_ws);
+
+ BigInt r;
+ m_curve.mul(r, m_coord_x, z2_inv, monty_ws);
+ m_curve.from_rep(r, monty_ws);
+ return r;
}
BigInt PointGFp::get_affine_y() const
@@ -364,11 +497,18 @@ BigInt PointGFp::get_affine_y() const
throw Illegal_Transformation("Cannot convert zero point to affine");
secure_vector<word> monty_ws;
- BigInt z3 = m_curve.mul_to_tmp(m_coord_z, m_curve.sqr_to_tmp(m_coord_z, monty_ws), monty_ws);
- z3 = inverse_mod(z3, m_curve.get_p());
- m_curve.to_rep(z3, monty_ws);
- return m_curve.mul_to_tmp(z3, m_coord_y, monty_ws);
+ if(is_affine())
+ return m_curve.from_rep(m_coord_y, monty_ws);
+
+ const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
+ const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws);
+ const BigInt z3_inv = m_curve.invert_element(z3, monty_ws);
+
+ BigInt r;
+ m_curve.mul(r, m_coord_y, z3_inv, monty_ws);
+ m_curve.from_rep(r, monty_ws);
+ return r;
}
bool PointGFp::on_the_curve() const
diff --git a/src/lib/pubkey/ec_group/point_gfp.h b/src/lib/pubkey/ec_group/point_gfp.h
index abcc9656e..71701d587 100644
--- a/src/lib/pubkey/ec_group/point_gfp.h
+++ b/src/lib/pubkey/ec_group/point_gfp.h
@@ -149,6 +149,13 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final
BigInt get_affine_y() const;
/**
+ * Force this point to affine coordinates
+ */
+ void force_affine();
+
+ bool is_affine() const;
+
+ /**
* Is this the point at infinity?
* @result true, if this point is at infinity, false otherwise.
*/
@@ -186,6 +193,13 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final
void add(const PointGFp& other, std::vector<BigInt>& workspace);
/**
+ * Point addition - mixed J+A
+ * @param other affine point to add
+ * @param workspace temp space, at least WORKSPACE_SIZE elements
+ */
+ void add_affine(const PointGFp& other, std::vector<BigInt>& workspace);
+
+ /**
* Point doubling
* @param workspace temp space, at least WORKSPACE_SIZE elements
*/
@@ -284,69 +298,22 @@ template<typename Alloc>
PointGFp OS2ECP(const std::vector<uint8_t, Alloc>& data, const CurveGFp& curve)
{ return OS2ECP(data.data(), data.size(), curve); }
+class PointGFp_Var_Point_Precompute;
+
/**
-* Blinded ECC point multiplication
+* Deprecated API for point multiplication
+* Use EC_Group::blinded_base_point_multiply or EC_Group::blinded_var_point_multiply
*/
-class BOTAN_PUBLIC_API(2,5) PointGFp_Blinded_Multiplier final
- {
- public:
- /**
- * @param base_point the point that will be multiplied (eg, the base point of the curve)
- * @param w the window bits (leave as zero to take a default value)
- */
- PointGFp_Blinded_Multiplier(const PointGFp& base_point,
- size_t w = 0);
-
- /**
- * @param base_point the point that will be multiplied (eg, the base point of the curve)
- * @param ws a temporary workspace
- * @param w the window bits (leave as zero to take a default value)
- */
- PointGFp_Blinded_Multiplier(const PointGFp& base_point,
- std::vector<BigInt>& ws,
- size_t w = 0);
-
- /**
- * Randomize the internal state. Changing the values may provide
- * some protection against side channel attacks.
- * @param rng a random number generator
- */
- void randomize(RandomNumberGenerator& rng);
-
- /**
- * Perform blinded point multiplication
- * @param k the scalar
- * @param group_order the order of the group
- * @param rng a random number generator
- * @param ws a temporary workspace
- * @return base_point*k
- */
- PointGFp mul(const BigInt& k,
- const BigInt& group_order,
- RandomNumberGenerator& rng,
- std::vector<BigInt>& ws) const;
- private:
- void init(const PointGFp& base_point, size_t w, std::vector<BigInt>& ws);
-
- std::vector<PointGFp> m_U;
- size_t m_h;
- };
-
-class BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use PointGFp_Blinded_Multiplier") Blinded_Point_Multiply final
+class BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("See comments") Blinded_Point_Multiply final
{
public:
- Blinded_Point_Multiply(const PointGFp& base, const BigInt& order, size_t h = 0) :
- m_ws(PointGFp::WORKSPACE_SIZE), m_order(order), m_point_mul(base, m_ws, h) {}
+ Blinded_Point_Multiply(const PointGFp& base, const BigInt& order, size_t h = 0);
- PointGFp blinded_multiply(const BigInt& scalar, RandomNumberGenerator& rng)
- {
- m_point_mul.randomize(rng);
- return m_point_mul.mul(scalar, m_order, rng, m_ws);
- }
+ PointGFp blinded_multiply(const BigInt& scalar, RandomNumberGenerator& rng);
private:
std::vector<BigInt> m_ws;
const BigInt& m_order;
- PointGFp_Blinded_Multiplier m_point_mul;
+ std::unique_ptr<PointGFp_Var_Point_Precompute> m_point_mul;
};
}
diff --git a/src/lib/pubkey/ec_group/point_mul.cpp b/src/lib/pubkey/ec_group/point_mul.cpp
index 314807166..556a05eb0 100644
--- a/src/lib/pubkey/ec_group/point_mul.cpp
+++ b/src/lib/pubkey/ec_group/point_mul.cpp
@@ -4,86 +4,137 @@
* Botan is released under the Simplified BSD License (see license.txt)
*/
-#include <botan/point_gfp.h>
+#include <botan/internal/point_mul.h>
#include <botan/rng.h>
#include <botan/internal/rounding.h>
namespace Botan {
-PointGFp_Blinded_Multiplier::PointGFp_Blinded_Multiplier(const PointGFp& base,
- std::vector<BigInt>& ws,
- size_t w)
+Blinded_Point_Multiply::Blinded_Point_Multiply(const PointGFp& base,
+ const BigInt& order,
+ size_t h) :
+ m_ws(PointGFp::WORKSPACE_SIZE),
+ m_order(order)
{
- init(base, w, ws);
+ BOTAN_UNUSED(h);
+ m_point_mul.reset(new PointGFp_Var_Point_Precompute(base));
}
-PointGFp_Blinded_Multiplier::PointGFp_Blinded_Multiplier(const PointGFp& base,
- size_t w)
+PointGFp Blinded_Point_Multiply::blinded_multiply(const BigInt& scalar,
+ RandomNumberGenerator& rng)
+ {
+ return m_point_mul->mul(scalar, rng, m_order, m_ws);
+ }
+
+
+PointGFp_Base_Point_Precompute::PointGFp_Base_Point_Precompute(const PointGFp& base)
{
std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
- init(base, w, ws);
+
+ const size_t p_bits = base.get_curve().get_p().bits();
+
+ /*
+ * Some of the curves (eg secp160k1) have an order slightly larger than
+ * the size of the prime modulus. In all cases they are at most 1 bit
+ * longer. The +1 compensates for this.
+ */
+ const size_t T_bits = p_bits + PointGFp_SCALAR_BLINDING_BITS + 1;
+
+ m_T.push_back(base);
+
+ for(size_t i = 1; i != T_bits; ++i)
+ {
+ m_T.push_back(m_T[i-1]);
+ m_T[i].mult2(ws);
+ }
+
+ for(size_t i = 0; i != m_T.size(); ++i)
+ m_T[i].force_affine();
}
-void PointGFp_Blinded_Multiplier::init(const PointGFp& base,
- size_t w,
- std::vector<BigInt>& ws)
+PointGFp PointGFp_Base_Point_Precompute::mul(const BigInt& k,
+ RandomNumberGenerator& rng,
+ const BigInt& group_order,
+ std::vector<BigInt>& ws) const
{
- m_h = (w == 0 ? 5 : w);
+ if(k.is_negative())
+ throw Invalid_Argument("PointGFp_Base_Point_Precompute scalar must be positive");
+
+ // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
+ const BigInt mask(rng, PointGFp_SCALAR_BLINDING_BITS, false);
+ const BigInt scalar = k + group_order * mask;
+
+ const size_t scalar_bits = scalar.bits();
+
+ BOTAN_ASSERT(scalar_bits <= m_T.size(),
+ "Precomputed sufficient values for scalar mult");
+
+ PointGFp R = m_T[0].zero();
if(ws.size() < PointGFp::WORKSPACE_SIZE)
ws.resize(PointGFp::WORKSPACE_SIZE);
- // Upper bound is a sanity check rather than hard limit
- if(m_h < 1 || m_h > 8)
- throw Invalid_Argument("PointGFp_Blinded_Multiplier invalid w param");
+ for(size_t i = 0; i != scalar_bits; ++i)
+ {
+ //if(i % 4 == 3)
+ if(i == 4)
+ {
+ R.randomize_repr(rng);
+ }
+
+ if(scalar.get_bit(i))
+ R.add(m_T[i], ws);
+ }
+
+ return R;
+ }
+
+PointGFp_Var_Point_Precompute::PointGFp_Var_Point_Precompute(const PointGFp& point)
+ {
+ m_window_bits = 4;
- m_U.resize(1 << m_h);
- m_U[0] = base.zero();
- m_U[1] = base;
+ 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)
{
m_U[i] = m_U[i-1];
- m_U[i].add(base, ws);
+ m_U[i].add(point, ws);
}
}
-void PointGFp_Blinded_Multiplier::randomize(RandomNumberGenerator& rng)
+void PointGFp_Var_Point_Precompute::randomize_repr(RandomNumberGenerator& rng)
{
- // Randomize each point representation (Coron's 3rd countermeasure)
- for(size_t i = 0; i != m_U.size(); ++i)
+ for(size_t i = 1; i != m_U.size(); ++i)
m_U[i].randomize_repr(rng);
}
-PointGFp PointGFp_Blinded_Multiplier::mul(const BigInt& k,
- const BigInt& group_order,
- RandomNumberGenerator& rng,
- std::vector<BigInt>& ws) const
+PointGFp PointGFp_Var_Point_Precompute::mul(const BigInt& k,
+ RandomNumberGenerator& rng,
+ const BigInt& group_order,
+ std::vector<BigInt>& ws) const
{
if(k.is_negative())
- throw Invalid_Argument("PointGFp_Blinded_Multiplier scalar must be positive");
+ throw Invalid_Argument("PointGFp_Base_Point_Precompute scalar must be positive");
+ if(ws.size() < PointGFp::WORKSPACE_SIZE)
+ ws.resize(PointGFp::WORKSPACE_SIZE);
-#if BOTAN_POINTGFP_USE_SCALAR_BLINDING
// Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
- const BigInt mask(rng, group_order.bits() / 4, false);
+ const BigInt mask(rng, PointGFp_SCALAR_BLINDING_BITS, false);
const BigInt scalar = k + group_order * mask;
-#else
- const BigInt& scalar = k;
-#endif
-
- if(ws.size() < PointGFp::WORKSPACE_SIZE)
- ws.resize(PointGFp::WORKSPACE_SIZE);
const size_t scalar_bits = scalar.bits();
- size_t windows = round_up(scalar_bits, m_h) / m_h;
+ size_t windows = round_up(scalar_bits, m_window_bits) / m_window_bits;
PointGFp R = m_U[0];
if(windows > 0)
{
windows--;
- const uint32_t nibble = scalar.get_substring(windows*m_h, m_h);
+ const uint32_t nibble = scalar.get_substring(windows*m_window_bits, m_window_bits);
R.add(m_U[nibble], ws);
/*
@@ -95,18 +146,16 @@ PointGFp PointGFp_Blinded_Multiplier::mul(const BigInt& k,
while(windows)
{
- for(size_t i = 0; i != m_h; ++i)
+ for(size_t i = 0; i != m_window_bits; ++i)
R.mult2(ws);
- const uint32_t inner_nibble = scalar.get_substring((windows-1)*m_h, m_h);
+ 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...
R.add(m_U[inner_nibble], ws);
windows--;
}
}
- //BOTAN_ASSERT(R.on_the_curve(), "Output is on the curve");
-
return R;
}
diff --git a/src/lib/pubkey/ec_group/point_mul.h b/src/lib/pubkey/ec_group/point_mul.h
new file mode 100644
index 000000000..97fd326a2
--- /dev/null
+++ b/src/lib/pubkey/ec_group/point_mul.h
@@ -0,0 +1,47 @@
+/*
+* (C) 2018 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_POINT_MUL_H_
+#define BOTAN_POINT_MUL_H_
+
+#include <botan/point_gfp.h>
+
+namespace Botan {
+
+static const size_t PointGFp_SCALAR_BLINDING_BITS = 80;
+
+class PointGFp_Base_Point_Precompute
+ {
+ public:
+ PointGFp_Base_Point_Precompute(const PointGFp& base_point);
+
+ PointGFp mul(const BigInt& k,
+ RandomNumberGenerator& rng,
+ const BigInt& group_order,
+ std::vector<BigInt>& ws) const;
+ private:
+ std::vector<PointGFp> m_T;
+ };
+
+class PointGFp_Var_Point_Precompute
+ {
+ public:
+ PointGFp_Var_Point_Precompute(const PointGFp& point);
+
+ void randomize_repr(RandomNumberGenerator& rng);
+
+ PointGFp mul(const BigInt& k,
+ RandomNumberGenerator& rng,
+ const BigInt& group_order,
+ std::vector<BigInt>& ws) const;
+ private:
+ size_t m_window_bits;
+ std::vector<PointGFp> m_U;
+ };
+
+}
+
+#endif
diff --git a/src/lib/pubkey/ecdh/ecdh.cpp b/src/lib/pubkey/ecdh/ecdh.cpp
index 4989fa0a5..adadb2703 100644
--- a/src/lib/pubkey/ecdh/ecdh.cpp
+++ b/src/lib/pubkey/ecdh/ecdh.cpp
@@ -39,9 +39,8 @@ class ECDH_KA_Operation final : public PK_Ops::Key_Agreement_with_KDF
PointGFp input_point = m_group.get_cofactor() * m_group.OS2ECP(w, w_len);
input_point.randomize_repr(m_rng);
- PointGFp_Blinded_Multiplier blinder(input_point, m_ws);
-
- const PointGFp S = blinder.mul(m_l_times_priv, m_group.get_order(), m_rng, m_ws);
+ const PointGFp S = m_group.blinded_var_point_multiply(
+ input_point, m_l_times_priv, m_rng, m_ws);
if(S.on_the_curve() == false)
throw Internal_Error("ECDH agreed value was not on the curve");
diff --git a/src/lib/pubkey/ecies/ecies.cpp b/src/lib/pubkey/ecies/ecies.cpp
index 1120a850a..06d5cfeee 100644
--- a/src/lib/pubkey/ecies/ecies.cpp
+++ b/src/lib/pubkey/ecies/ecies.cpp
@@ -71,9 +71,8 @@ class ECIES_ECDH_KA_Operation final : public PK_Ops::Key_Agreement_with_KDF
PointGFp input_point = group.OS2ECP(w, w_len);
input_point.randomize_repr(m_rng);
- PointGFp_Blinded_Multiplier blinder(input_point, m_ws);
-
- const PointGFp S = blinder.mul(m_key.private_value(), group.get_order(), m_rng, m_ws);
+ const PointGFp S = group.blinded_var_point_multiply(
+ input_point, m_key.private_value(), m_rng, m_ws);
if(S.on_the_curve() == false)
throw Internal_Error("ECDH agreed value was not on the curve");
diff --git a/src/lib/pubkey/sm2/sm2_enc.cpp b/src/lib/pubkey/sm2/sm2_enc.cpp
index b0d773635..4a6aa2b6e 100644
--- a/src/lib/pubkey/sm2/sm2_enc.cpp
+++ b/src/lib/pubkey/sm2/sm2_enc.cpp
@@ -6,6 +6,7 @@
*/
#include <botan/sm2_enc.h>
+#include <botan/internal/point_mul.h>
#include <botan/pk_ops.h>
#include <botan/keypair.h>
#include <botan/der_enc.h>
@@ -76,7 +77,7 @@ class SM2_Encryption_Operation final : public PK_Ops::Encryption
BigInt::encode_1363(x1_bytes.data(), x1_bytes.size(), x1);
BigInt::encode_1363(y1_bytes.data(), y1_bytes.size(), y1);
- const PointGFp kPB = m_mul_public_point.mul(k, m_group.get_order(), rng, m_ws);
+ const PointGFp kPB = m_mul_public_point.mul(k, rng, m_group.get_order(), m_ws);
const BigInt x2 = kPB.get_affine_x();
const BigInt y2 = kPB.get_affine_y();
@@ -113,7 +114,7 @@ class SM2_Encryption_Operation final : public PK_Ops::Encryption
private:
const EC_Group m_group;
- PointGFp_Blinded_Multiplier m_mul_public_point;
+ PointGFp_Var_Point_Precompute m_mul_public_point;
const std::string m_kdf_hash;
std::vector<BigInt> m_ws;
};
@@ -161,6 +162,8 @@ class SM2_Decryption_Operation final : public PK_Ops::Decryption
.verify_end();
PointGFp C1 = group.point(x1, y1);
+ C1.randomize_repr(m_rng);
+
if(!C1.on_the_curve())
return secure_vector<uint8_t>();
@@ -169,11 +172,8 @@ class SM2_Decryption_Operation final : public PK_Ops::Decryption
return secure_vector<uint8_t>();
}
- C1.randomize_repr(m_rng);
-
- PointGFp_Blinded_Multiplier C1_mul(C1);
-
- const PointGFp dbC1 = C1_mul.mul(m_key.private_value(), group.get_order(), m_rng, m_ws);
+ const PointGFp dbC1 = group.blinded_var_point_multiply(
+ C1, m_key.private_value(), m_rng, m_ws);
const BigInt x2 = dbC1.get_affine_x();
const BigInt y2 = dbC1.get_affine_y();
diff --git a/src/tests/unit_ecc.cpp b/src/tests/unit_ecc.cpp
index 6f0d1a243..cbff3ff4f 100644
--- a/src/tests/unit_ecc.cpp
+++ b/src/tests/unit_ecc.cpp
@@ -136,10 +136,6 @@ std::vector<Test::Result> ECC_Randomized_Tests::run()
const size_t trials = (Test::run_long_tests() ? 10 : 3);
for(size_t i = 0; i < trials; ++i)
{
- const size_t w = 1 + (Test::rng().next_byte() % 8);
-
- Botan::PointGFp_Blinded_Multiplier blinded(base_point, w);
-
const Botan::BigInt a = Botan::BigInt::random_integer(Test::rng(), 2, group_order);
const Botan::BigInt b = Botan::BigInt::random_integer(Test::rng(), 2, group_order);
const Botan::BigInt c = a + b;
@@ -148,13 +144,18 @@ std::vector<Test::Result> ECC_Randomized_Tests::run()
const Botan::PointGFp Q = base_point * b;
const Botan::PointGFp R = base_point * c;
- const Botan::PointGFp P1 = blinded.mul(a, group_order, Test::rng(), blind_ws);
- const Botan::PointGFp Q1 = blinded.mul(b, group_order, Test::rng(), blind_ws);
- const Botan::PointGFp R1 = blinded.mul(c, group_order, Test::rng(), blind_ws);
+ Botan::PointGFp P1 = group.blinded_base_point_multiply(a, Test::rng(), blind_ws);
+ Botan::PointGFp Q1 = group.blinded_base_point_multiply(b, Test::rng(), blind_ws);
+ Botan::PointGFp R1 = group.blinded_base_point_multiply(c, Test::rng(), blind_ws);
+
+ Botan::PointGFp A1 = P + Q;
+ Botan::PointGFp A2 = Q + P;
- const Botan::PointGFp A1 = P + Q;
- const Botan::PointGFp A2 = Q + P;
+ result.test_eq("p + q", A1, R);
+ result.test_eq("q + p", A2, R);
+ A1.force_affine();
+ A2.force_affine();
result.test_eq("p + q", A1, R);
result.test_eq("q + p", A2, R);
@@ -165,6 +166,13 @@ std::vector<Test::Result> ECC_Randomized_Tests::run()
result.test_eq("P1", P1, P);
result.test_eq("Q1", Q1, Q);
result.test_eq("R1", R1, R);
+
+ P1.force_affine();
+ Q1.force_affine();
+ R1.force_affine();
+ result.test_eq("P1", P1, P);
+ result.test_eq("Q1", Q1, Q);
+ result.test_eq("R1", R1, R);
}
}
catch(std::exception& e)
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-28 02:56:48 +0000