aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/lib/math/bigint/big_ops2.cpp38
-rw-r--r--src/lib/math/bigint/bigint.cpp2
-rw-r--r--src/lib/math/bigint/bigint.h14
-rw-r--r--src/lib/math/mp/mp_core.h41
-rw-r--r--src/lib/math/numbertheory/monty.cpp22
-rw-r--r--src/lib/math/numbertheory/nistp_redc.cpp6
-rw-r--r--src/lib/pubkey/ec_group/curve_gfp.cpp9
-rw-r--r--src/lib/pubkey/ec_group/curve_gfp.h7
-rw-r--r--src/lib/pubkey/ec_group/point_gfp.cpp21
9 files changed, 104 insertions, 56 deletions
diff --git a/src/lib/math/bigint/big_ops2.cpp b/src/lib/math/bigint/big_ops2.cpp
index 6ce14f8f1..5e4ee949c 100644
--- a/src/lib/math/bigint/big_ops2.cpp
+++ b/src/lib/math/bigint/big_ops2.cpp
@@ -126,19 +126,39 @@ BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>&
swap_reg(ws);
}
#else
- // is t < s or not?
- const auto is_lt = bigint_ct_is_lt(data(), mod_sw, s.data(), mod_sw);
+ if(mod_sw == 4)
+ bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data());
+ else
+ bigint_mod_sub(mutable_data(), s.data(), mod.data(), mod_sw, ws.data());
+#endif
+
+ return (*this);
+ }
- // ws = p - s
- const word borrow = bigint_sub3(ws.data(), mod.data(), mod_sw, s.data(), mod_sw);
+BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws)
+ {
+ BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive");
+ BOTAN_ARG_CHECK(y < 16, "y too large");
- // Compute either (t - s) or (t + (p - s)) depending on mask
- const word carry = bigint_cnd_addsub(is_lt, mutable_data(), ws.data(), s.data(), mod_sw);
+ BOTAN_DEBUG_ASSERT(*this < mod);
- BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0);
- BOTAN_UNUSED(carry, borrow);
-#endif
+ switch(y)
+ {
+ case 2:
+ *this <<= 1;
+ break;
+ case 4:
+ *this <<= 2;
+ break;
+ case 8:
+ *this <<= 3;
+ break;
+ default:
+ *this *= static_cast<word>(y);
+ break;
+ }
+ this->reduce_below(mod, ws);
return (*this);
}
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index 667035686..d64082476 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -335,8 +335,6 @@ void BigInt::reduce_below(const BigInt& p, secure_vector<word>& ws)
for(;;)
{
word borrow = bigint_sub3(ws.data(), data(), p_words + 1, p.data(), p_words);
-
- //CT::unpoison(borrow); // fixme
if(borrow)
break;
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 58c45dd67..9b385348e 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -328,7 +328,17 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
BigInt& mod_sub(const BigInt& y, const BigInt& mod, secure_vector<word>& ws);
/**
- * Return *this below mod
+ * Set *this to (*this * y) % mod
+ * This function assumes *this is >= 0 && < mod
+ * y should be small, less than 16
+ * @param y the small integer to multiply by
+ * @param mod the positive modulus
+ * @param ws a temp workspace
+ */
+ BigInt& mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws);
+
+ /**
+ * Return *this % mod
*
* Assumes that *this is (if anything) only slightly larger than
* mod and performs repeated subtractions. It should not be used if
@@ -933,7 +943,7 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
if(n > size())
{
if(n <= m_reg.capacity())
- m_reg.resize(m_reg.capacity());
+ m_reg.resize(n);
else
m_reg.resize(n + (8 - (n % 8)));
}
diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h
index 6e2fba049..2824a3456 100644
--- a/src/lib/math/mp/mp_core.h
+++ b/src/lib/math/mp/mp_core.h
@@ -685,6 +685,47 @@ bigint_sub_abs(word z[],
}
/**
+* Set t to t-s modulo mod
+*
+* @param t first integer
+* @param s second integer
+* @param mod the modulus
+* @param mod_sw size of t, s, and mod
+* @param ws workspace of size mod_sw
+*/
+inline void
+bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[])
+ {
+ // is t < s or not?
+ const auto is_lt = bigint_ct_is_lt(t, mod_sw, s, mod_sw);
+
+ // ws = p - s
+ const word borrow = bigint_sub3(ws, mod, mod_sw, s, mod_sw);
+
+ // Compute either (t - s) or (t + (p - s)) depending on mask
+ const word carry = bigint_cnd_addsub(is_lt, t, ws, s, mod_sw);
+
+ BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0);
+ BOTAN_UNUSED(carry, borrow);
+ }
+
+template<size_t N>
+inline void bigint_mod_sub_n(word t[], const word s[], const word mod[], word ws[])
+ {
+ // is t < s or not?
+ const auto is_lt = bigint_ct_is_lt(t, N, s, N);
+
+ // ws = p - s
+ const word borrow = bigint_sub3(ws, mod, N, s, N);
+
+ // Compute either (t - s) or (t + (p - s)) depending on mask
+ const word carry = bigint_cnd_addsub(is_lt, t, ws, s, N);
+
+ BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0);
+ BOTAN_UNUSED(carry, borrow);
+ }
+
+/**
* Compute ((n1<<bits) + n0) / d
*/
inline word bigint_divop(word n1, word n0, word d)
diff --git a/src/lib/math/numbertheory/monty.cpp b/src/lib/math/numbertheory/monty.cpp
index 61a10eae5..f3d85e44c 100644
--- a/src/lib/math/numbertheory/monty.cpp
+++ b/src/lib/math/numbertheory/monty.cpp
@@ -312,17 +312,17 @@ BigInt Montgomery_Int::value() const
Montgomery_Int Montgomery_Int::operator+(const Montgomery_Int& other) const
{
- BigInt z = m_v + other.m_v;
secure_vector<word> ws;
- z.reduce_below(m_params->p(), ws);
+ BigInt z = m_v;
+ z.mod_add(other.m_v, m_params->p(), ws);
return Montgomery_Int(m_params, z, false);
}
Montgomery_Int Montgomery_Int::operator-(const Montgomery_Int& other) const
{
- BigInt z = m_v - other.m_v;
- if(z.is_negative())
- z += m_params->p();
+ secure_vector<word> ws;
+ BigInt z = m_v;
+ z.mod_sub(other.m_v, m_params->p(), ws);
return Montgomery_Int(m_params, z, false);
}
@@ -420,29 +420,25 @@ Montgomery_Int Montgomery_Int::additive_inverse() const
Montgomery_Int& Montgomery_Int::mul_by_2(secure_vector<word>& ws)
{
- m_v <<= 1;
- m_v.reduce_below(m_params->p(), ws);
+ m_v.mod_mul(2, m_params->p(), ws);
return (*this);
}
Montgomery_Int& Montgomery_Int::mul_by_3(secure_vector<word>& ws)
{
- m_v *= 3;
- m_v.reduce_below(m_params->p(), ws);
+ m_v.mod_mul(3, m_params->p(), ws);
return (*this);
}
Montgomery_Int& Montgomery_Int::mul_by_4(secure_vector<word>& ws)
{
- m_v <<= 2;
- m_v.reduce_below(m_params->p(), ws);
+ m_v.mod_mul(4, m_params->p(), ws);
return (*this);
}
Montgomery_Int& Montgomery_Int::mul_by_8(secure_vector<word>& ws)
{
- m_v <<= 3;
- m_v.reduce_below(m_params->p(), ws);
+ m_v.mod_mul(8, m_params->p(), ws);
return (*this);
}
diff --git a/src/lib/math/numbertheory/nistp_redc.cpp b/src/lib/math/numbertheory/nistp_redc.cpp
index a74c4de9f..d5935584d 100644
--- a/src/lib/math/numbertheory/nistp_redc.cpp
+++ b/src/lib/math/numbertheory/nistp_redc.cpp
@@ -48,13 +48,14 @@ void redc_p521(BigInt& x, secure_vector<word>& ws)
if(bit_522_set)
{
#if (BOTAN_MP_WORD_BITS == 64)
- static const word p521_words[9] = {
+ static const word p521_words[p_words] = {
0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
0x1FF };
- bigint_sub2(x.mutable_data(), p_words, p521_words, 9);
+ bigint_sub2(x.mutable_data(), p_words, p521_words, p_words);
#else
+ // FIXME use bigint_sub2
x -= prime_p521();
#endif
}
@@ -576,5 +577,4 @@ void redc_p384(BigInt& x, secure_vector<word>& ws)
#endif
-
}
diff --git a/src/lib/pubkey/ec_group/curve_gfp.cpp b/src/lib/pubkey/ec_group/curve_gfp.cpp
index bd68a3ed7..f2f5607e1 100644
--- a/src/lib/pubkey/ec_group/curve_gfp.cpp
+++ b/src/lib/pubkey/ec_group/curve_gfp.cpp
@@ -60,8 +60,6 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr
size_t get_ws_size() const override { return 2*m_p_words + 4; }
- void redc_mod_p(BigInt& z, secure_vector<word>& ws) const override;
-
BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override;
@@ -93,11 +91,6 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr
bool m_a_is_minus_3;
};
-void CurveGFp_Montgomery::redc_mod_p(BigInt& z, secure_vector<word>& ws) const
- {
- z.reduce_below(m_p, ws);
- }
-
BigInt CurveGFp_Montgomery::invert_element(const BigInt& x, secure_vector<word>& ws) const
{
// Should we use Montgomery inverse instead?
@@ -207,6 +200,8 @@ class CurveGFp_NIST : public CurveGFp_Repr
void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override
{ redc_mod_p(x, ws); }
+ virtual void redc_mod_p(BigInt& z, secure_vector<word>& ws) const = 0;
+
BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
void curve_mul_words(BigInt& z,
diff --git a/src/lib/pubkey/ec_group/curve_gfp.h b/src/lib/pubkey/ec_group/curve_gfp.h
index d03247244..fe7a0a54d 100644
--- a/src/lib/pubkey/ec_group/curve_gfp.h
+++ b/src/lib/pubkey/ec_group/curve_gfp.h
@@ -49,8 +49,6 @@ class BOTAN_UNSTABLE_API CurveGFp_Repr
*/
virtual const BigInt& get_1_rep() const = 0;
- virtual void redc_mod_p(BigInt& z, secure_vector<word>& ws) 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;
@@ -171,11 +169,6 @@ class BOTAN_UNSTABLE_API CurveGFp final
// TODO: from_rep taking && ref
- void redc_mod_p(BigInt& z, secure_vector<word>& ws) const
- {
- m_repr->redc_mod_p(z, ws);
- }
-
void mul(BigInt& z, const BigInt& x, const BigInt& y, secure_vector<word>& ws) const
{
m_repr->curve_mul(z, x, y, ws);
diff --git a/src/lib/pubkey/ec_group/point_gfp.cpp b/src/lib/pubkey/ec_group/point_gfp.cpp
index 7bc6c4975..b4b3871cb 100644
--- a/src/lib/pubkey/ec_group/point_gfp.cpp
+++ b/src/lib/pubkey/ec_group/point_gfp.cpp
@@ -2,7 +2,7 @@
* Point arithmetic on elliptic curves over GF(p)
*
* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke
-* 2008-2011,2012,2014,2015 Jack Lloyd
+* 2008-2011,2012,2014,2015,2018 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/
@@ -152,6 +152,7 @@ void PointGFp::add_affine(const word x_words[], size_t x_size,
m_curve.sqr(m_coord_x, T0, ws);
m_coord_x.mod_sub(T1, p, sub_ws);
+
m_coord_x.mod_sub(T3, p, sub_ws);
m_coord_x.mod_sub(T3, p, sub_ws);
@@ -303,15 +304,13 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
m_curve.sqr(T0, m_coord_y, ws);
m_curve.mul(T1, m_coord_x, T0, ws);
- T1 <<= 2; // * 4
- m_curve.redc_mod_p(T1, sub_ws);
+ T1.mod_mul(4, p, sub_ws);
if(m_curve.a_is_zero())
{
// if a == 0 then 3*x^2 + a*z^4 is just 3*x^2
m_curve.sqr(T4, m_coord_x, ws); // x^2
- T4 *= 3; // 3*x^2
- m_curve.redc_mod_p(T4, sub_ws);
+ T4.mod_mul(3, p, sub_ws); // 3*x^2
}
else if(m_curve.a_is_minus_3())
{
@@ -330,8 +329,7 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
m_curve.mul(T4, T2, T3, ws); // (x-z^2)*(x+z^2)
- T4 *= 3; // 3*(x-z^2)*(x+z^2)
- m_curve.redc_mod_p(T4, sub_ws);
+ T4.mod_mul(3, p, sub_ws); // 3*(x-z^2)*(x+z^2)
}
else
{
@@ -340,8 +338,7 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
m_curve.mul(T3, m_curve.get_a_rep(), T4, ws); // a*z^4
m_curve.sqr(T4, m_coord_x, ws); // x^2
- T4 *= 3; // 3*x^2
- T4.reduce_below(p, sub_ws);
+ T4.mod_mul(3, p, sub_ws);
T4.mod_add(T3, p, sub_ws); // 3*x^2 + a*z^4
}
@@ -350,8 +347,7 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
T2.mod_sub(T1, p, sub_ws);
m_curve.sqr(T3, T0, ws);
- T3 <<= 3;
- m_curve.redc_mod_p(T3, sub_ws);
+ T3.mod_mul(8, p, sub_ws);
T1.mod_sub(T2, p, sub_ws);
@@ -361,8 +357,7 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
m_coord_x = T2;
m_curve.mul(T2, m_coord_y, m_coord_z, ws);
- T2 <<= 1;
- m_curve.redc_mod_p(T2, sub_ws);
+ T2.mod_mul(2, p, sub_ws);
m_coord_y = T0;
m_coord_z = T2;
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-20 09:37:05 +0000