aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math/ec_gfp/point_gfp.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/math/ec_gfp/point_gfp.cpp')
-rw-r--r--src/lib/math/ec_gfp/point_gfp.cpp328
1 files changed, 211 insertions, 117 deletions
diff --git a/src/lib/math/ec_gfp/point_gfp.cpp b/src/lib/math/ec_gfp/point_gfp.cpp
index 2505e4d54..a319d8657 100644
--- a/src/lib/math/ec_gfp/point_gfp.cpp
+++ b/src/lib/math/ec_gfp/point_gfp.cpp
@@ -2,36 +2,55 @@
* Point arithmetic on elliptic curves over GF(p)
*
* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke
-* 2008-2011,2012,2014 Jack Lloyd
+* 2008-2011,2012,2014,2015 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/
#include <botan/point_gfp.h>
#include <botan/numthry.h>
+#include <botan/loadstor.h>
namespace Botan {
+const size_t BOTAN_POINTGFP_MONTGOMERY_BLINDING_BITS = 20;
+const size_t BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS = 48;
+
+#define BOTAN_POINTGFP_BLINDED_MULTIPLY_USE_MONTGOMERY_LADDER 1
+
PointGFp::PointGFp(const CurveGFp& curve) :
- curve(curve),
- coord_x(0),
- coord_y(1),
- coord_z(0)
+ m_curve(curve),
+ m_coord_x(0),
+ m_coord_y(1),
+ m_coord_z(0)
{
- curve.to_rep(coord_x, ws);
- curve.to_rep(coord_y, ws);
- curve.to_rep(coord_z, ws);
+ m_curve.to_rep(m_coord_x, m_monty_ws);
+ m_curve.to_rep(m_coord_y, m_monty_ws);
+ m_curve.to_rep(m_coord_z, m_monty_ws);
}
PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) :
- curve(curve),
- coord_x(x),
- coord_y(y),
- coord_z(1)
+ m_curve(curve),
+ m_coord_x(x),
+ m_coord_y(y),
+ m_coord_z(1)
+ {
+ m_curve.to_rep(m_coord_x, m_monty_ws);
+ m_curve.to_rep(m_coord_y, m_monty_ws);
+ m_curve.to_rep(m_coord_z, m_monty_ws);
+ }
+
+void PointGFp::randomize_repr(RandomNumberGenerator& rng)
{
- curve.to_rep(coord_x, ws);
- curve.to_rep(coord_y, ws);
- curve.to_rep(coord_z, ws);
+ BigInt mask(rng, BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS, false);
+
+ m_curve.to_rep(mask, m_monty_ws);
+ const BigInt mask2 = curve_mult(mask, mask);
+ const BigInt mask3 = curve_mult(mask2, mask);
+
+ m_coord_x = curve_mult(m_coord_x, mask2);
+ m_coord_y = curve_mult(m_coord_y, mask3);
+ m_coord_z = curve_mult(m_coord_z, mask);
}
// Point addition
@@ -39,15 +58,15 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
{
if(is_zero())
{
- coord_x = rhs.coord_x;
- coord_y = rhs.coord_y;
- coord_z = rhs.coord_z;
+ m_coord_x = rhs.m_coord_x;
+ m_coord_y = rhs.m_coord_y;
+ m_coord_z = rhs.m_coord_z;
return;
}
else if(rhs.is_zero())
return;
- const BigInt& p = curve.get_p();
+ const BigInt& p = m_curve.get_p();
BigInt& rhs_z2 = ws_bn[0];
BigInt& U1 = ws_bn[1];
@@ -64,13 +83,13 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
*/
- curve_sqr(rhs_z2, rhs.coord_z);
- curve_mult(U1, coord_x, rhs_z2);
- curve_mult(S1, coord_y, curve_mult(rhs.coord_z, rhs_z2));
+ curve_sqr(rhs_z2, rhs.m_coord_z);
+ curve_mult(U1, m_coord_x, rhs_z2);
+ curve_mult(S1, m_coord_y, curve_mult(rhs.m_coord_z, rhs_z2));
- curve_sqr(lhs_z2, coord_z);
- curve_mult(U2, rhs.coord_x, lhs_z2);
- curve_mult(S2, rhs.coord_y, curve_mult(coord_z, lhs_z2));
+ curve_sqr(lhs_z2, m_coord_z);
+ curve_mult(U2, rhs.m_coord_x, lhs_z2);
+ curve_mult(S2, rhs.m_coord_y, curve_mult(m_coord_z, lhs_z2));
H = U2;
H -= U1;
@@ -90,7 +109,10 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
return;
}
- *this = PointGFp(curve); // setting myself to zero
+ // setting to zero:
+ m_coord_x = 0;
+ m_coord_y = 1;
+ m_coord_z = 0;
return;
}
@@ -100,22 +122,22 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
U2 = curve_mult(U1, U2);
- curve_sqr(coord_x, r);
- coord_x -= S2;
- coord_x -= (U2 << 1);
- while(coord_x.is_negative())
- coord_x += p;
+ curve_sqr(m_coord_x, r);
+ m_coord_x -= S2;
+ m_coord_x -= (U2 << 1);
+ while(m_coord_x.is_negative())
+ m_coord_x += p;
- U2 -= coord_x;
+ U2 -= m_coord_x;
if(U2.is_negative())
U2 += p;
- curve_mult(coord_y, r, U2);
- coord_y -= curve_mult(S1, S2);
- if(coord_y.is_negative())
- coord_y += p;
+ curve_mult(m_coord_y, r, U2);
+ m_coord_y -= curve_mult(S1, S2);
+ if(m_coord_y.is_negative())
+ m_coord_y += p;
- curve_mult(coord_z, curve_mult(coord_z, rhs.coord_z), H);
+ curve_mult(m_coord_z, curve_mult(m_coord_z, rhs.m_coord_z), H);
}
// *this *= 2
@@ -123,9 +145,9 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
{
if(is_zero())
return;
- else if(coord_y.is_zero())
+ else if(m_coord_y.is_zero())
{
- *this = PointGFp(curve); // setting myself to zero
+ *this = PointGFp(m_curve); // setting myself to zero
return;
}
@@ -133,7 +155,7 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-1986-cc
*/
- const BigInt& p = curve.get_p();
+ const BigInt& p = m_curve.get_p();
BigInt& y_2 = ws_bn[0];
BigInt& S = ws_bn[1];
@@ -145,17 +167,17 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
BigInt& y = ws_bn[7];
BigInt& z = ws_bn[8];
- curve_sqr(y_2, coord_y);
+ curve_sqr(y_2, m_coord_y);
- curve_mult(S, coord_x, y_2);
+ curve_mult(S, m_coord_x, y_2);
S <<= 2; // * 4
while(S >= p)
S -= p;
- curve_sqr(z4, curve_sqr(coord_z));
- curve_mult(a_z4, curve.get_a_rep(), z4);
+ curve_sqr(z4, curve_sqr(m_coord_z));
+ curve_mult(a_z4, m_curve.get_a_rep(), z4);
- M = curve_sqr(coord_x);
+ M = curve_sqr(m_coord_x);
M *= 3;
M += a_z4;
while(M >= p)
@@ -180,14 +202,14 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
if(y.is_negative())
y += p;
- curve_mult(z, coord_y, coord_z);
+ curve_mult(z, m_coord_y, m_coord_z);
z <<= 1;
if(z >= p)
z -= p;
- coord_x = x;
- coord_y = y;
- coord_z = z;
+ m_coord_x = x;
+ m_coord_y = y;
+ m_coord_z = z;
}
// arithmetic operators
@@ -221,7 +243,7 @@ PointGFp multi_exponentiate(const PointGFp& p1, const BigInt& z1,
{
const PointGFp p3 = p1 + p2;
- PointGFp H(p1.curve); // create as zero
+ PointGFp H(p1.get_curve()); // create as zero
size_t bits_left = std::max(z1.bits(), z2.bits());
std::vector<BigInt> ws(9);
@@ -251,22 +273,24 @@ PointGFp multi_exponentiate(const PointGFp& p1, const BigInt& z1,
PointGFp operator*(const BigInt& scalar, const PointGFp& point)
{
- //BOTAN_ASSERT(point.on_the_curve(), "Input is valid");
+ //BOTAN_ASSERT(point.on_the_curve(), "Input is on the curve");
const CurveGFp& curve = point.get_curve();
- if(scalar.is_zero())
- return PointGFp(curve); // zero point
+ const size_t scalar_bits = scalar.bits();
std::vector<BigInt> ws(9);
- if(scalar.abs() <= 2) // special cases for small values
+ if(scalar_bits <= 2)
{
- byte value = scalar.abs().byte_at(0);
+ const byte abs_val = scalar.byte_at(0);
+
+ if(abs_val == 0)
+ return PointGFp::zero_of(curve);
PointGFp result = point;
- if(value == 2)
+ if(abs_val == 2)
result.mult2(ws);
if(scalar.is_negative())
@@ -275,94 +299,164 @@ PointGFp operator*(const BigInt& scalar, const PointGFp& point)
return result;
}
- const size_t scalar_bits = scalar.bits();
+ PointGFp R[2] = { PointGFp(curve), point };
- PointGFp x1(curve); // zero
+ for(size_t i = scalar_bits; i > 0; i--)
+ {
+ const size_t b = scalar.get_bit(i - 1);
+ R[b ^ 1].add(R[b], ws);
+ R[b].mult2(ws);
+ }
- size_t bits_left = scalar_bits;
+ if(scalar.is_negative())
+ R[0].negate();
-#if BOTAN_CURVE_GFP_USE_MONTGOMERY_LADDER
+ //BOTAN_ASSERT(R[0].on_the_curve(), "Output is on the curve");
- PointGFp x2 = point;
- while(bits_left)
+ return R[0];
+ }
+
+Blinded_Point_Multiply::Blinded_Point_Multiply(const PointGFp& base, const BigInt& order, size_t h) :
+ m_order(order), m_h(h ? h : 4), m_ws(9)
+ {
+ // Upper bound is a sanity check rather than hard limit
+ if(m_h < 1 || m_h > 8)
+ throw std::invalid_argument("Blinded_Point_Multiply invalid h param");
+
+ const CurveGFp& curve = base.get_curve();
+
+#if BOTAN_POINTGFP_BLINDED_MULTIPLY_USE_MONTGOMERY_LADDER
+
+ const PointGFp inv = -base;
+
+ m_U.resize(6*m_h + 3);
+
+ m_U[3*m_h+0] = inv;
+ m_U[3*m_h+1] = PointGFp::zero_of(curve);
+ m_U[3*m_h+2] = base;
+
+ for(size_t i = 1; i <= 3 * m_h + 1; ++i)
{
- if(scalar.get_bit(bits_left - 1))
- {
- x1.add(x2, ws);
- x2.mult2(ws);
- }
- else
- {
- x2.add(x1, ws);
- x1.mult2(ws);
- }
+ m_U[3*m_h+1+i] = m_U[3*m_h+i];
+ m_U[3*m_h+1+i].add(base, m_ws);
- --bits_left;
+ m_U[3*m_h+1-i] = m_U[3*m_h+2-i];
+ m_U[3*m_h+1-i].add(inv, m_ws);
}
-
#else
- const size_t window_bits = 4;
+ m_U.resize(1 << m_h);
+ m_U[0] = PointGFp::zero_of(curve);
+ m_U[1] = base;
+
+ for(size_t i = 2; i < m_U.size(); ++i)
+ {
+ m_U[i] = m_U[i-1];
+ m_U[i].add(base, m_ws);
+ }
+#endif
+ }
- std::vector<PointGFp> Ps(1 << window_bits);
- Ps[0] = x1;
- Ps[1] = point;
+PointGFp Blinded_Point_Multiply::blinded_multiply(const BigInt& scalar_in,
+ RandomNumberGenerator& rng)
+ {
+ if(scalar_in.is_negative())
+ throw std::invalid_argument("Blinded_Point_Multiply scalar must be positive");
+
+ // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
+ const u64bit mask = rng.gen_mask(BOTAN_POINTGFP_MONTGOMERY_BLINDING_BITS);
+ const BigInt scalar = scalar_in + m_order * mask;
+ const size_t scalar_bits = scalar.bits();
+
+ // Randomize each point representation (Coron's 3rd countermeasure)
+ for(size_t i = 0; i != m_U.size(); ++i)
+ m_U[i].randomize_repr(rng);
+
+#if BOTAN_POINTGFP_BLINDED_MULTIPLY_USE_MONTGOMERY_LADDER
+ PointGFp R = m_U.at(3*m_h + 2); // base point
+ int32_t alpha = 0;
+
+ R.randomize_repr(rng);
+
+ /*
+ Algorithm 7 from "Randomizing the Montgomery Powering Ladder"
+ Duc-Phong Le, Chik How Tan and Michael Tunstall
+ http://eprint.iacr.org/2015/657
- for(size_t i = 2; i < Ps.size(); ++i)
+ It takes a random walk through (a subset of) the set of addition
+ chains that end in k.
+ */
+ for(size_t i = scalar_bits; i > 0; i--)
{
- Ps[i] = Ps[i-1];
- Ps[i].add(point, ws);
+ const int32_t ki = scalar.get_bit(i);
+
+ // choose gamma from -h,...,h
+ const int32_t gamma = static_cast<int32_t>((rng.next_byte() % (2*m_h))) - m_h;
+ const int32_t l = gamma - 2*alpha + ki - (ki ^ 1);
+
+ R.mult2(m_ws);
+ R.add(m_U.at(3*m_h + 1 + l), m_ws);
+ alpha = gamma;
}
- while(bits_left >= window_bits)
+ const int32_t k0 = scalar.get_bit(0);
+ R.add(m_U[3*m_h + 1 - alpha - (k0 ^ 1)], m_ws);
+
+#else
+
+ size_t bits_left = scalar_bits;
+
+ PointGFp R = m_U[0];
+
+ while(bits_left >= m_h)
{
- for(size_t i = 0; i != window_bits; ++i)
- x1.mult2(ws);
+ for(size_t i = 0; i != m_h; ++i)
+ R.mult2(m_ws);
- const u32bit nibble = scalar.get_substring(bits_left - window_bits, window_bits);
- x1.add(Ps[nibble], ws);
- bits_left -= window_bits;
+ const u32bit nibble = scalar.get_substring(bits_left - m_h, m_h);
+ R.add(m_U[nibble], m_ws);
+ bits_left -= m_h;
}
while(bits_left)
{
- x1.mult2(ws);
+ R.mult2(m_ws);
if(scalar.get_bit(bits_left-1))
- x1.add(point, ws);
+ R.add(m_U[1], m_ws);
--bits_left;
}
-
#endif
- if(scalar.is_negative())
- x1.negate();
+ //BOTAN_ASSERT(R.on_the_curve(), "Output is on the curve");
- //BOTAN_ASSERT(x1.on_the_curve(), "Output is on the curve");
-
- return x1;
+ return R;
}
BigInt PointGFp::get_affine_x() const
{
if(is_zero())
+ abort();
+ if(is_zero())
throw Illegal_Transformation("Cannot convert zero point to affine");
- BigInt z2 = curve_sqr(coord_z);
- curve.from_rep(z2, ws);
- z2 = inverse_mod(z2, curve.get_p());
+ BigInt z2 = curve_sqr(m_coord_z);
+ m_curve.from_rep(z2, m_monty_ws);
+ z2 = inverse_mod(z2, m_curve.get_p());
- return curve_mult(z2, coord_x);
+ return curve_mult(z2, m_coord_x);
}
BigInt PointGFp::get_affine_y() const
{
if(is_zero())
+ abort();
+ if(is_zero())
throw Illegal_Transformation("Cannot convert zero point to affine");
- BigInt z3 = curve_mult(coord_z, curve_sqr(coord_z));
- z3 = inverse_mod(z3, curve.get_p());
- curve.to_rep(z3, ws);
+ BigInt z3 = curve_mult(m_coord_z, curve_sqr(m_coord_z));
+ z3 = inverse_mod(z3, m_curve.get_p());
+ m_curve.to_rep(z3, m_monty_ws);
- return curve_mult(z3, coord_y);
+ return curve_mult(z3, m_coord_y);
}
bool PointGFp::on_the_curve() const
@@ -376,22 +470,22 @@ bool PointGFp::on_the_curve() const
if(is_zero())
return true;
- const BigInt y2 = curve.from_rep(curve_sqr(coord_y), ws);
- const BigInt x3 = curve_mult(coord_x, curve_sqr(coord_x));
- const BigInt ax = curve_mult(coord_x, curve.get_a_rep());
- const BigInt z2 = curve_sqr(coord_z);
+ const BigInt y2 = m_curve.from_rep(curve_sqr(m_coord_y), m_monty_ws);
+ const BigInt x3 = curve_mult(m_coord_x, curve_sqr(m_coord_x));
+ const BigInt ax = curve_mult(m_coord_x, m_curve.get_a_rep());
+ const BigInt z2 = curve_sqr(m_coord_z);
- if(coord_z == z2) // Is z equal to 1 (in Montgomery form)?
+ if(m_coord_z == z2) // Is z equal to 1 (in Montgomery form)?
{
- if(y2 != curve.from_rep(x3 + ax + curve.get_b_rep(), ws))
+ if(y2 != m_curve.from_rep(x3 + ax + m_curve.get_b_rep(), m_monty_ws))
return false;
}
- const BigInt z3 = curve_mult(coord_z, z2);
+ const BigInt z3 = curve_mult(m_coord_z, z2);
const BigInt ax_z4 = curve_mult(ax, curve_sqr(z2));
- const BigInt b_z6 = curve_mult(curve.get_b_rep(), curve_sqr(z3));
+ const BigInt b_z6 = curve_mult(m_curve.get_b_rep(), curve_sqr(z3));
- if(y2 != curve.from_rep(x3 + ax_z4 + b_z6, ws))
+ if(y2 != m_curve.from_rep(x3 + ax_z4 + b_z6, m_monty_ws))
return false;
return true;
@@ -400,11 +494,11 @@ bool PointGFp::on_the_curve() const
// swaps the states of *this and other, does not throw!
void PointGFp::swap(PointGFp& other)
{
- curve.swap(other.curve);
- coord_x.swap(other.coord_x);
- coord_y.swap(other.coord_y);
- coord_z.swap(other.coord_z);
- ws.swap(other.ws);
+ m_curve.swap(other.m_curve);
+ m_coord_x.swap(other.m_coord_x);
+ m_coord_y.swap(other.m_coord_y);
+ m_coord_z.swap(other.m_coord_z);
+ m_monty_ws.swap(other.m_monty_ws);
}
bool PointGFp::operator==(const PointGFp& other) const
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-18 20:36:54 +0000