10 #include <botan/point_gfp.h> 11 #include <botan/numthry.h> 12 #include <botan/rng.h> 13 #include <botan/internal/rounding.h> 14 #include <botan/internal/ct_utils.h> 21 m_coord_y(curve.get_1_rep()),
31 m_coord_z(m_curve.get_1_rep())
33 if(x < 0 || x >= curve.
get_p())
35 if(y < 0 || y >= curve.
get_p())
39 m_curve.
to_rep(m_coord_x, monty_ws);
40 m_curve.
to_rep(m_coord_y, monty_ws);
63 m_coord_x = m_curve.
mul_to_tmp(m_coord_x, mask2, ws);
64 m_coord_y = m_curve.
mul_to_tmp(m_coord_y, mask3, ws);
65 m_coord_z = m_curve.
mul_to_tmp(m_coord_z, mask, ws);
70 inline void resize_ws(std::vector<BigInt>& ws_bn,
size_t cap_size)
73 "Expected size for PointGFp workspace");
75 for(
size_t i = 0; i != ws_bn.size(); ++i)
76 if(ws_bn[i].size() < cap_size)
77 ws_bn[i].get_word_vector().resize(cap_size);
80 inline word all_zeros(
const word x[],
size_t len)
83 for(
size_t i = 0; i != len; ++i)
91 const word y_words[],
size_t y_size,
92 std::vector<BigInt>& ws_bn)
94 if(all_zeros(x_words, x_size) & all_zeros(y_words, y_size))
125 m_curve.
sqr(T3, m_coord_z, ws);
126 m_curve.
mul(T4, x_words, x_size, T3, ws);
128 m_curve.
mul(T2, m_coord_z, T3, ws);
129 m_curve.
mul(T0, y_words, y_size, T2, ws);
131 T4.
mod_sub(m_coord_x, p, sub_ws);
133 T0.
mod_sub(m_coord_y, p, sub_ws);
150 m_curve.
sqr(T2, T4, ws);
152 m_curve.
mul(T3, m_coord_x, T2, ws);
154 m_curve.
mul(T1, T2, T4, ws);
156 m_curve.
sqr(m_coord_x, T0, ws);
157 m_coord_x.
mod_sub(T1, p, sub_ws);
159 m_coord_x.
mod_sub(T3, p, sub_ws);
160 m_coord_x.
mod_sub(T3, p, sub_ws);
162 T3.
mod_sub(m_coord_x, p, sub_ws);
164 m_curve.
mul(T2, T0, T3, ws);
165 m_curve.
mul(T0, m_coord_y, T1, ws);
169 m_curve.
mul(T0, m_coord_z, T4, ws);
174 const word y_words[],
size_t y_size,
175 const word z_words[],
size_t z_size,
176 std::vector<BigInt>& ws_bn)
178 if(all_zeros(x_words, x_size) & all_zeros(z_words, z_size))
207 m_curve.
sqr(T0, z_words, z_size, ws);
208 m_curve.
mul(T1, m_coord_x, T0, ws);
209 m_curve.
mul(T3, z_words, z_size, T0, ws);
210 m_curve.
mul(T2, m_coord_y, T3, ws);
212 m_curve.
sqr(T3, m_coord_z, ws);
213 m_curve.
mul(T4, x_words, x_size, T3, ws);
215 m_curve.
mul(T5, m_coord_z, T3, ws);
216 m_curve.
mul(T0, y_words, y_size, T5, ws);
237 m_curve.
sqr(T5, T4, ws);
239 m_curve.
mul(T3, T1, T5, ws);
241 m_curve.
mul(T1, T5, T4, ws);
243 m_curve.
sqr(m_coord_x, T0, ws);
244 m_coord_x.
mod_sub(T1, p, sub_ws);
245 m_coord_x.
mod_sub(T3, p, sub_ws);
246 m_coord_x.
mod_sub(T3, p, sub_ws);
248 T3.
mod_sub(m_coord_x, p, sub_ws);
250 m_curve.
mul(m_coord_y, T0, T3, ws);
251 m_curve.
mul(T3, T2, T1, ws);
253 m_coord_y.
mod_sub(T3, p, sub_ws);
255 m_curve.
mul(T3, z_words, z_size, m_coord_z, ws);
256 m_curve.
mul(m_coord_z, T3, T4, ws);
274 for(
size_t i = 0; i != iterations; ++i)
306 m_curve.
sqr(T0, m_coord_y, ws);
308 m_curve.
mul(T1, m_coord_x, T0, ws);
314 m_curve.
sqr(T4, m_coord_x, ws);
323 m_curve.
sqr(T3, m_coord_z, ws);
330 T3.
mod_add(m_coord_x, p, sub_ws);
332 m_curve.
mul(T4, T2, T3, ws);
338 m_curve.
sqr(T3, m_coord_z, ws);
339 m_curve.
sqr(T4, T3, ws);
342 m_curve.
sqr(T4, m_coord_x, ws);
347 m_curve.
sqr(T2, T4, ws);
351 m_curve.
sqr(T3, T0, ws);
356 m_curve.
mul(T0, T4, T1, ws);
361 m_curve.
mul(T2, m_coord_y, m_coord_z, ws);
390 *
this = scalar * *
this;
398 const size_t scalar_bits = scalar.
bits();
404 for(
size_t i = scalar_bits; i > 0; i--)
406 const size_t b = scalar.
get_bit(i - 1);
407 R[b ^ 1].
add(R[b], ws);
423 if(points.size() <= 1)
425 for(
size_t i = 0; i != points.size(); ++i)
430 for(
size_t i = 0; i != points.size(); ++i)
433 throw Invalid_State(
"Cannot convert zero ECC point to affine");
445 const CurveGFp& curve = points[0].m_curve;
451 std::vector<BigInt> c(points.size());
452 c[0] = points[0].m_coord_z;
454 for(
size_t i = 1; i != points.size(); ++i)
456 curve.
mul(c[i], c[i-1], points[i].m_coord_z, ws);
461 BigInt z_inv, z2_inv, z3_inv;
463 for(
size_t i = points.size() - 1; i != 0; i--)
467 curve.
mul(z_inv, s_inv, c[i-1], ws);
469 s_inv = curve.
mul_to_tmp(s_inv, point.m_coord_z, ws);
471 curve.
sqr(z2_inv, z_inv, ws);
472 curve.
mul(z3_inv, z2_inv, z_inv, ws);
473 point.m_coord_x = curve.
mul_to_tmp(point.m_coord_x, z2_inv, ws);
474 point.m_coord_y = curve.
mul_to_tmp(point.m_coord_y, z3_inv, ws);
475 point.m_coord_z = rep_1;
478 curve.
sqr(z2_inv, s_inv, ws);
479 curve.
mul(z3_inv, z2_inv, s_inv, ws);
480 points[0].m_coord_x = curve.
mul_to_tmp(points[0].m_coord_x, z2_inv, ws);
481 points[0].m_coord_y = curve.
mul_to_tmp(points[0].m_coord_y, z3_inv, ws);
482 points[0].m_coord_z = rep_1;
488 throw Invalid_State(
"Cannot convert zero ECC point to affine");
495 m_coord_x = m_curve.
mul_to_tmp(m_coord_x, z2_inv, ws);
496 m_coord_y = m_curve.
mul_to_tmp(m_coord_y, z3_inv, ws);
502 return m_curve.
is_one(m_coord_z);
519 m_curve.
mul(r, m_coord_x, z2, monty_ws);
539 m_curve.
mul(r, m_coord_y, z3_inv, monty_ws);
581 m_curve.
swap(other.m_curve);
582 m_coord_x.
swap(other.m_coord_x);
583 m_coord_y.
swap(other.m_coord_y);
584 m_coord_z.
swap(other.m_coord_z);
589 if(m_curve != other.m_curve)
604 return std::vector<uint8_t>(1);
606 const size_t p_bytes = m_curve.
get_p().
bytes();
611 std::vector<uint8_t> result;
615 result.resize(1 + 2*p_bytes);
622 result.resize(1 + p_bytes);
623 result[0] = 0x02 |
static_cast<uint8_t
>(y.
get_bit(0));
628 result.resize(1 + 2*p_bytes);
629 result[0] = 0x06 |
static_cast<uint8_t
>(y.
get_bit(0));
641 BigInt decompress_point(
bool yMod2,
676 PointGFp point(curve, xy.first, xy.second);
678 if(!point.on_the_curve())
679 throw Illegal_Point(
"OS2ECP: Decoded point was not on the curve");
684 std::pair<BigInt, BigInt>
OS2ECP(
const uint8_t data[],
size_t data_len,
692 const uint8_t pc = data[0];
696 if(pc == 2 || pc == 3)
701 const bool y_mod_2 = ((pc & 0x01) == 1);
702 y = decompress_point(y_mod_2, x, curve_p, curve_a, curve_b);
706 const size_t l = (data_len - 1) / 2;
712 else if(pc == 6 || pc == 7)
714 const size_t l = (data_len - 1) / 2;
720 const bool y_mod_2 = ((pc & 0x01) == 1);
722 if(decompress_point(y_mod_2, x, curve_p, curve_a, curve_b) != y)
723 throw Illegal_Point(
"OS2ECP: Decoding error in hybrid format");
728 return std::make_pair(x, y);
bool get_bit(size_t n) const
bool a_is_minus_3() const
const BigInt & get_a_rep() const
void to_rep(BigInt &x, secure_vector< word > &ws) const
PointGFp & operator*=(const BigInt &scalar)
const BigInt & get_b_rep() const
std::vector< uint8_t > encode(PointGFp::Compression_Type format) const
secure_vector< word > & get_word_vector()
BigInt & mod_sub(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
BigInt ressol(const BigInt &x, const BigInt &p)
std::string to_string(const BER_Object &obj)
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
size_t get_ws_size() const
void add(const PointGFp &other, std::vector< BigInt > &workspace)
void from_rep(BigInt &x, secure_vector< word > &ws) const
BigInt from_rep_to_tmp(const BigInt &x, secure_vector< word > &ws) const
BigInt get_affine_x() const
BigInt get_affine_y() const
#define BOTAN_ASSERT(expr, assertion_made)
const BigInt & get_1_rep() const
void swap(PointGFp &other)
BigInt invert_element(const BigInt &x, secure_vector< word > &ws) const
#define BOTAN_DEBUG_ASSERT(expr)
void randomize_repr(RandomNumberGenerator &rng)
void mult2i(size_t i, std::vector< BigInt > &workspace)
BigInt & mod_add(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
bool is_one(const BigInt &x) const
BigInt sqr_to_tmp(const BigInt &x, secure_vector< word > &ws) const
void set_words(const word w[], size_t len)
void swap(CurveGFp &other)
BigInt mul_to_tmp(const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
void mult2(std::vector< BigInt > &workspace)
const BigInt & get_b() const
BigInt & mod_mul(uint8_t y, const BigInt &mod, secure_vector< word > &ws)
bool on_the_curve() const
void add_affine(const PointGFp &other, std::vector< BigInt > &workspace)
const BigInt & get_a() const
BigInt operator*(const BigInt &x, const BigInt &y)
static BigInt decode(const uint8_t buf[], size_t length)
static void force_all_affine(std::vector< PointGFp > &points, secure_vector< word > &ws)
bool operator==(const PointGFp &other) const
static secure_vector< uint8_t > encode_1363(const BigInt &n, size_t bytes)
std::vector< T, secure_allocator< T > > secure_vector
PointGFp & operator+=(const PointGFp &rhs)
const BigInt & get_p() const
static Mask< T > is_zero(T x)
PointGFp & operator-=(const PointGFp &rhs)
void sqr(BigInt &z, const BigInt &x, secure_vector< word > &ws) const
PointGFp OS2ECP(const uint8_t data[], size_t data_len, const CurveGFp &curve)