10 #include <botan/point_gfp.h>
11 #include <botan/numthry.h>
12 #include <botan/reducer.h>
13 #include <botan/internal/mp_core.h>
18 curve(curve), ws(2 * (curve.get_p_words() + 2))
21 coord_y = monty_mult(1, curve.
get_r2());
26 curve(curve), ws(2 * (curve.get_p_words() + 2))
28 coord_x = monty_mult(x, curve.
get_r2());
29 coord_y = monty_mult(y, curve.
get_r2());
30 coord_z = monty_mult(1, curve.
get_r2());
44 const BigInt& p = curve.
get_p();
48 SecureVector<word>& z_reg = z.
get_reg();
55 p.data(), p_size, p_dash,
60 void PointGFp::monty_sqr(BigInt& z,
const BigInt& x)
const
70 const BigInt& p = curve.
get_p();
74 SecureVector<word>& z_reg = z.get_reg();
75 z_reg.resize(2*p_size+1);
79 x.data(), x.size(), x.sig_words(),
80 p.data(), p_size, p_dash,
85 void PointGFp::add(
const PointGFp& rhs, std::vector<BigInt>& ws_bn)
89 coord_x = rhs.coord_x;
90 coord_y = rhs.coord_y;
91 coord_z = rhs.coord_z;
94 else if(rhs.is_zero())
97 const BigInt& p = curve.
get_p();
99 BigInt& rhs_z2 = ws_bn[0];
100 BigInt& U1 = ws_bn[1];
101 BigInt& S1 = ws_bn[2];
103 BigInt& lhs_z2 = ws_bn[3];
104 BigInt& U2 = ws_bn[4];
105 BigInt& S2 = ws_bn[5];
107 BigInt& H = ws_bn[6];
108 BigInt&
r = ws_bn[7];
110 monty_sqr(rhs_z2, rhs.coord_z);
111 monty_mult(U1, coord_x, rhs_z2);
112 monty_mult(S1, coord_y, monty_mult(rhs.coord_z, rhs_z2));
114 monty_sqr(lhs_z2, coord_z);
115 monty_mult(U2, rhs.coord_x, lhs_z2);
116 monty_mult(S2, rhs.coord_y, monty_mult(coord_z, lhs_z2));
142 monty_mult(S2, U2, H);
144 U2 = monty_mult(U1, U2);
146 monty_sqr(coord_x, r);
148 coord_x -= (U2 << 1);
156 monty_mult(coord_y, r, U2);
157 coord_y -= monty_mult(S1, S2);
161 monty_mult(coord_z, monty_mult(coord_z, rhs.coord_z), H);
165 void PointGFp::mult2(std::vector<BigInt>& ws_bn)
175 const BigInt& p = curve.
get_p();
177 BigInt& y_2 = ws_bn[0];
178 BigInt& S = ws_bn[1];
179 BigInt& z4 = ws_bn[2];
180 BigInt& a_z4 = ws_bn[3];
181 BigInt& M = ws_bn[4];
182 BigInt& U = ws_bn[5];
183 BigInt& x = ws_bn[6];
184 BigInt& y = ws_bn[7];
185 BigInt& z = ws_bn[8];
187 monty_sqr(y_2, coord_y);
189 monty_mult(S, coord_x, y_2);
194 monty_sqr(z4, monty_sqr(coord_z));
195 monty_mult(a_z4, curve.
get_a_r(), z4);
197 M = 3 * monty_sqr(coord_x);
204 while(x.is_negative())
213 while(S.is_negative())
221 monty_mult(z, coord_y, coord_z);
234 std::vector<BigInt> ws(9);
253 *
this = scalar * *
this;
263 size_t bits_left = std::max(z1.
bits(), z2.
bits());
265 std::vector<BigInt> ws(9);
271 const bool z1_b = z1.
get_bit(bits_left - 1);
272 const bool z2_b = z2.
get_bit(bits_left - 1);
274 if(z1_b ==
true && z2_b ==
true)
297 std::vector<BigInt> ws(9);
299 if(scalar.
abs() <= 2)
314 const size_t scalar_bits = scalar.
bits();
321 size_t bits_left = scalar_bits;
326 const bool bit_set = scalar.
get_bit(bits_left - 1);
348 const size_t window_size = 4;
350 std::vector<PointGFp> Ps(1 << window_size);
354 for(
size_t i = 2; i != Ps.size(); ++i)
357 Ps[i].add(point, ws);
361 size_t bits_left = scalar_bits;
363 while(bits_left >= window_size)
365 for(
size_t i = 0; i != window_size; ++i)
371 H.add(Ps[nibble], ws);
373 bits_left -= window_size;
379 if(scalar.
get_bit(bits_left-1))
399 BigInt z2 = monty_sqr(coord_z);
402 z2 = monty_mult(z2, r2);
403 return monty_mult(coord_x, z2);
413 BigInt z3 = monty_mult(coord_z, monty_sqr(coord_z));
415 z3 = monty_mult(z3, r2);
416 return monty_mult(coord_y, z3);
431 BigInt y2 = monty_mult(monty_sqr(coord_y), 1);
432 BigInt x3 = monty_mult(coord_x, monty_sqr(coord_x));
438 BigInt z2 = monty_sqr(coord_z);
442 if(y2 != monty_mult(x3 + ax + b_r, 1))
446 BigInt z3 = monty_mult(coord_z, z2);
448 BigInt ax_z4 = monty_mult(ax, monty_sqr(z2));
450 BigInt b_z6 = monty_mult(b_r, monty_sqr(z3));
452 if(y2 != monty_mult(x3 + ax_z4 + b_z6, 1))
461 curve.
swap(other.curve);
462 coord_x.
swap(other.coord_x);
463 coord_y.
swap(other.coord_y);
464 coord_z.
swap(other.coord_z);
530 BigInt decompress_point(
bool yMod2,
532 const CurveGFp& curve)
534 BigInt xpow3 = x * x * x;
536 BigInt g = curve.get_a() * x;
539 g = g % curve.get_p();
541 BigInt z =
ressol(g, curve.get_p());
544 throw Illegal_Point(
"error during decompression");
546 if(z.get_bit(0) != yMod2)
547 z = curve.get_p() - z;
560 const byte pc = data[0];
564 if(pc == 2 || pc == 3)
569 const bool y_mod_2 = ((pc & 0x01) == 1);
570 y = decompress_point(y_mod_2, x, curve);
574 const size_t l = (data_len - 1) / 2;
580 else if(pc == 6 || pc == 7)
582 const size_t l = (data_len - 1) / 2;
588 const bool y_mod_2 = ((pc & 0x01) == 1);
590 if(decompress_point(y_mod_2, x, curve) != y)
591 throw Illegal_Point(
"OS2ECP: Decoding error in hybrid format");
599 throw Illegal_Point(
"OS2ECP: Decoded point was not on the curve");
BigInt get_affine_y() const
PointGFp & operator*=(const BigInt &scalar)
PointGFp OS2ECP(const byte data[], size_t data_len, const CurveGFp &curve)
byte byte_at(size_t n) const
SecureVector< word > & get_reg()
const BigInt & get_b_r() const
bool operator==(const PointGFp &other) const
BigInt BOTAN_DLL ressol(const BigInt &x, const BigInt &p)
std::invalid_argument Invalid_Argument
size_t get_p_words() const
void bigint_monty_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word p[], size_t p_size, word p_dash, word workspace[])
const CurveGFp & get_curve() const
const BigInt & get_r2() const
SecureVector< byte > EC2OSP(const PointGFp &point, byte format)
BigInt get_affine_x() const
u32bit get_substring(size_t offset, size_t length) const
void swap(PointGFp &other)
const BigInt & get_a_r() const
const word * data() const
BigInt operator*(const BigInt &x, const BigInt &y)
void swap(CurveGFp &other)
void bigint_monty_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, const word p[], size_t p_size, word p_dash, word workspace[])
void swap(MemoryRegion< T > &other)
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
const BigInt & get_p() const
static BigInt decode(const byte buf[], size_t length, Base base=Binary)
bool on_the_curve() const
bool get_bit(size_t n) const
PointGFp & operator+=(const PointGFp &rhs)
PointGFp & operator-=(const PointGFp &rhs)
void zeroise(MemoryRegion< T > &vec)
static SecureVector< byte > encode_1363(const BigInt &n, size_t bytes)
PointGFp multi_exponentiate(const PointGFp &p1, const BigInt &z1, const PointGFp &p2, const BigInt &z2)