10 #include <botan/point_gfp.h>
11 #include <botan/numthry.h>
12 #include <botan/loadstor.h>
13 #include <botan/internal/rounding.h>
24 m_curve.
to_rep(m_coord_x, m_monty_ws);
25 m_curve.
to_rep(m_coord_y, m_monty_ws);
26 m_curve.
to_rep(m_coord_z, m_monty_ws);
35 if(x <= 0 || x >= curve.
get_p())
37 if(y <= 0 || y >= curve.
get_p())
40 m_curve.
to_rep(m_coord_x, m_monty_ws);
41 m_curve.
to_rep(m_coord_y, m_monty_ws);
42 m_curve.
to_rep(m_coord_z, m_monty_ws);
47 if(BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS > 1)
51 mask.
randomize(rng, BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS,
false);
53 m_curve.
to_rep(mask, m_monty_ws);
54 const BigInt mask2 = curve_mult(mask, mask);
55 const BigInt mask3 = curve_mult(mask2, mask);
57 m_coord_x = curve_mult(m_coord_x, mask2);
58 m_coord_y = curve_mult(m_coord_y, mask3);
59 m_coord_z = curve_mult(m_coord_z, mask);
64 void PointGFp::add(
const PointGFp& rhs, std::vector<BigInt>& ws_bn)
68 m_coord_x = rhs.m_coord_x;
69 m_coord_y = rhs.m_coord_y;
70 m_coord_z = rhs.m_coord_z;
76 const BigInt& p = m_curve.
get_p();
78 BigInt& rhs_z2 = ws_bn[0];
79 BigInt& U1 = ws_bn[1];
80 BigInt& S1 = ws_bn[2];
82 BigInt& lhs_z2 = ws_bn[3];
83 BigInt& U2 = ws_bn[4];
84 BigInt& S2 = ws_bn[5];
93 curve_sqr(rhs_z2, rhs.m_coord_z);
94 curve_mult(U1, m_coord_x, rhs_z2);
95 curve_mult(S1, m_coord_y, curve_mult(rhs.m_coord_z, rhs_z2));
97 curve_sqr(lhs_z2, m_coord_z);
98 curve_mult(U2, rhs.m_coord_x, lhs_z2);
99 curve_mult(S2, rhs.m_coord_y, curve_mult(m_coord_z, lhs_z2));
128 curve_mult(S2, U2, H);
130 U2 = curve_mult(U1, U2);
132 curve_sqr(m_coord_x, r);
134 m_coord_x -= (U2 << 1);
142 curve_mult(m_coord_y, r, U2);
143 m_coord_y -= curve_mult(S1, S2);
147 curve_mult(m_coord_z, curve_mult(m_coord_z, rhs.m_coord_z), H);
151 void PointGFp::mult2(std::vector<BigInt>& ws_bn)
165 const BigInt& p = m_curve.
get_p();
167 BigInt& y_2 = ws_bn[0];
168 BigInt& S = ws_bn[1];
169 BigInt& z4 = ws_bn[2];
170 BigInt& a_z4 = ws_bn[3];
171 BigInt& M = ws_bn[4];
172 BigInt& U = ws_bn[5];
173 BigInt& x = ws_bn[6];
174 BigInt& y = ws_bn[7];
175 BigInt& z = ws_bn[8];
177 curve_sqr(y_2, m_coord_y);
179 curve_mult(S, m_coord_x, y_2);
184 curve_sqr(z4, curve_sqr(m_coord_z));
185 curve_mult(a_z4, m_curve.
get_a_rep(), z4);
187 M = curve_sqr(m_coord_x);
195 while(x.is_negative())
204 while(S.is_negative())
212 curve_mult(z, m_coord_y, m_coord_z);
225 std::vector<BigInt> ws(9);
244 *
this = scalar * *
this;
256 std::vector<BigInt> ws(9);
262 const bool z1_b = z1.
get_bit(bits_left - 1);
263 const bool z2_b = z2.
get_bit(bits_left - 1);
265 if(z1_b ==
true && z2_b ==
true)
287 const size_t scalar_bits = scalar.
bits();
289 std::vector<BigInt> ws(9);
293 for(
size_t i = scalar_bits; i > 0; i--)
295 const size_t b = scalar.
get_bit(i - 1);
296 R[b ^ 1].add(R[b], ws);
309 m_h(h > 0 ? h : 4),
m_order(order), m_ws(9)
312 if(m_h < 1 || m_h > 8)
319 m_U.resize(6*m_h + 3);
325 for(
size_t i = 1; i <= 3 * m_h + 1; ++i)
327 m_U[3*m_h+1+i] = m_U[3*m_h+i];
328 m_U[3*m_h+1+i].add(base, m_ws);
330 m_U[3*m_h+1-i] = m_U[3*m_h+2-i];
331 m_U[3*m_h+1-i].add(inv, m_ws);
341 #if BOTAN_POINTGFP_USE_SCALAR_BLINDING
343 const BigInt mask(rng, (m_order.
bits()+1)/2,
false);
344 const BigInt scalar = scalar_in + m_order * mask;
346 const BigInt& scalar = scalar_in;
349 const size_t scalar_bits = scalar.
bits();
352 for(
size_t i = 0; i != m_U.size(); ++i)
353 m_U[i].randomize_repr(rng);
368 for(
size_t i = scalar_bits; i > 0; i--)
370 const int32_t ki = scalar.
get_bit(i);
373 const int32_t gamma =
static_cast<int32_t
>((rng.
next_byte() % (2*m_h))) - m_h;
374 const int32_t l = gamma - 2*alpha + ki - (ki ^ 1);
377 R.add(m_U.at(3*m_h + 1 + l), m_ws);
381 const int32_t k0 = scalar.
get_bit(0);
382 R.add(m_U[3*m_h + 1 - alpha - (k0 ^ 1)], m_ws);
395 BigInt z2 = curve_sqr(m_coord_z);
399 return curve_mult(z2, m_coord_x);
407 BigInt z3 = curve_mult(m_coord_z, curve_sqr(m_coord_z));
409 m_curve.
to_rep(z3, m_monty_ws);
411 return curve_mult(z3, m_coord_y);
425 const BigInt y2 = m_curve.
from_rep(curve_sqr(m_coord_y), m_monty_ws);
426 const BigInt x3 = curve_mult(m_coord_x, curve_sqr(m_coord_x));
428 const BigInt z2 = curve_sqr(m_coord_z);
436 const BigInt z3 = curve_mult(m_coord_z, z2);
437 const BigInt ax_z4 = curve_mult(ax, curve_sqr(z2));
440 if(y2 != m_curve.
from_rep(x3 + ax_z4 + b_z6, m_monty_ws))
449 m_curve.
swap(other.m_curve);
450 m_coord_x.
swap(other.m_coord_x);
451 m_coord_y.
swap(other.m_coord_y);
452 m_coord_z.
swap(other.m_coord_z);
453 m_monty_ws.swap(other.m_monty_ws);
486 result.push_back(0x04);
496 result.push_back(0x02 | static_cast<uint8_t>(y.
get_bit(0)));
505 result.push_back(0x06 | static_cast<uint8_t>(y.
get_bit(0)));
518 BigInt decompress_point(
bool yMod2,
520 const CurveGFp& curve)
522 BigInt xpow3 = x * x * x;
524 const BigInt& p = curve.get_p();
526 BigInt g = curve.get_a() * x;
534 throw Illegal_Point(
"error during EC point decompression");
536 if(z.get_bit(0) != yMod2)
550 const uint8_t pc = data[0];
554 if(pc == 2 || pc == 3)
559 const bool y_mod_2 = ((pc & 0x01) == 1);
560 y = decompress_point(y_mod_2, x, curve);
564 const size_t l = (data_len - 1) / 2;
570 else if(pc == 6 || pc == 7)
572 const size_t l = (data_len - 1) / 2;
578 const bool y_mod_2 = ((pc & 0x01) == 1);
580 if(decompress_point(y_mod_2, x, curve) != y)
581 throw Illegal_Point(
"OS2ECP: Decoding error in hybrid format");
589 throw Illegal_Point(
"OS2ECP: Decoded point was not on the curve");
BigInt get_affine_y() const
static PointGFp zero_of(const CurveGFp &curve)
PointGFp & operator*=(const BigInt &scalar)
secure_vector< uint8_t > EC2OSP(const PointGFp &point, uint8_t format)
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
bool operator==(const PointGFp &other) const
BigInt BOTAN_DLL ressol(const BigInt &x, const BigInt &p)
const BigInt & get_a_rep() const
std::string to_string(const BER_Object &obj)
const CurveGFp & get_curve() const
BigInt get_affine_x() const
void swap(PointGFp &other)
std::vector< T, secure_allocator< T >> secure_vector
void to_rep(BigInt &x, secure_vector< word > &ws) const
void randomize_repr(RandomNumberGenerator &rng)
PointGFp OS2ECP(const uint8_t data[], size_t data_len, const CurveGFp &curve)
void from_rep(BigInt &x, secure_vector< word > &ws) const
PointGFp blinded_multiply(const BigInt &scalar, RandomNumberGenerator &rng)
BigInt operator*(const BigInt &x, const BigInt &y)
const BigInt & get_b_rep() const
void swap(CurveGFp &other)
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
const BigInt & get_p() const
bool on_the_curve() const
static secure_vector< uint8_t > encode_1363(const BigInt &n, size_t bytes)
bool get_bit(size_t n) const
PointGFp & operator+=(const PointGFp &rhs)
Blinded_Point_Multiply(const PointGFp &base, const BigInt &order, size_t h=0)
PointGFp & operator-=(const PointGFp &rhs)
PointGFp multi_exponentiate(const PointGFp &p1, const BigInt &z1, const PointGFp &p2, const BigInt &z2)
static BigInt decode(const uint8_t buf[], size_t length, Base base=Binary)