Botan  2.9.0
Crypto and TLS for C++11
Public Types | Public Member Functions | Static Public Member Functions | List of all members
Botan::PointGFp Class Referencefinal

#include <point_gfp.h>

Public Types

enum  { WORKSPACE_SIZE = 8 }
 
enum  Compression_Type { UNCOMPRESSED = 0, COMPRESSED = 1, HYBRID = 2 }
 

Public Member Functions

void add (const PointGFp &other, std::vector< BigInt > &workspace)
 
void add (const word x_words[], size_t x_size, const word y_words[], size_t y_size, const word z_words[], size_t z_size, std::vector< BigInt > &workspace)
 
void add_affine (const PointGFp &other, std::vector< BigInt > &workspace)
 
void add_affine (const word x_words[], size_t x_size, const word y_words[], size_t y_size, std::vector< BigInt > &workspace)
 
PointGFp double_of (std::vector< BigInt > &workspace) const
 
std::vector< uint8_t > encode (PointGFp::Compression_Type format) const
 
void force_affine ()
 
BigInt get_affine_x () const
 
BigInt get_affine_y () const
 
const CurveGFpget_curve () const
 
const BigIntget_x () const
 
const BigIntget_y () const
 
const BigIntget_z () const
 
bool is_affine () const
 
bool is_zero () const
 
void mult2 (std::vector< BigInt > &workspace)
 
void mult2i (size_t i, std::vector< BigInt > &workspace)
 
PointGFpnegate ()
 
bool on_the_curve () const
 
PointGFpoperator*= (const BigInt &scalar)
 
PointGFpoperator+= (const PointGFp &rhs)
 
PointGFpoperator-= (const PointGFp &rhs)
 
PointGFpoperator= (const PointGFp &)=default
 
PointGFpoperator= (PointGFp &&other)
 
bool operator== (const PointGFp &other) const
 
PointGFp plus (const PointGFp &other, std::vector< BigInt > &workspace) const
 
 PointGFp ()=default
 
 PointGFp (const CurveGFp &curve)
 
 PointGFp (const PointGFp &)=default
 
 PointGFp (PointGFp &&other)
 
 PointGFp (const CurveGFp &curve, const BigInt &x, const BigInt &y)
 
void randomize_repr (RandomNumberGenerator &rng)
 
void randomize_repr (RandomNumberGenerator &rng, secure_vector< word > &ws)
 
void swap (PointGFp &other)
 
void swap_coords (BigInt &new_x, BigInt &new_y, BigInt &new_z)
 
PointGFp zero () const
 

Static Public Member Functions

static void force_all_affine (std::vector< PointGFp > &points, secure_vector< word > &ws)
 

Detailed Description

This class represents one point on a curve of GF(p)

Definition at line 47 of file point_gfp.h.

Member Enumeration Documentation

◆ anonymous enum

anonymous enum
Enumerator
WORKSPACE_SIZE 

Definition at line 56 of file point_gfp.h.

◆ Compression_Type

Enumerator
UNCOMPRESSED 
COMPRESSED 
HYBRID 

Definition at line 50 of file point_gfp.h.

Constructor & Destructor Documentation

◆ PointGFp() [1/5]

Botan::PointGFp::PointGFp ( )
default

Construct an uninitialized PointGFp

Referenced by mult2(), mult2i(), and operator-=().

◆ PointGFp() [2/5]

Botan::PointGFp::PointGFp ( const CurveGFp curve)
explicit

Construct the zero point

Parameters
curveThe base curve

Definition at line 18 of file point_gfp.cpp.

18  :
19  m_curve(curve),
20  m_coord_x(0),
21  m_coord_y(curve.get_1_rep()),
22  m_coord_z(0)
23  {
24  // Assumes Montgomery rep of zero is zero
25  }

◆ PointGFp() [3/5]

Botan::PointGFp::PointGFp ( const PointGFp )
default

Copy constructor

◆ PointGFp() [4/5]

Botan::PointGFp::PointGFp ( PointGFp &&  other)
inline

Move Constructor

Definition at line 77 of file point_gfp.h.

78  {
79  this->swap(other);
80  }
void swap(PointGFp &other)
Definition: point_gfp.cpp:573

◆ PointGFp() [5/5]

Botan::PointGFp::PointGFp ( const CurveGFp curve,
const BigInt x,
const BigInt y 
)

Construct a point from its affine coordinates

Parameters
curvethe base curve
xaffine x coordinate
yaffine y coordinate

Definition at line 27 of file point_gfp.cpp.

References Botan::CurveGFp::get_p(), Botan::CurveGFp::get_ws_size(), and Botan::CurveGFp::to_rep().

27  :
28  m_curve(curve),
29  m_coord_x(x),
30  m_coord_y(y),
31  m_coord_z(m_curve.get_1_rep())
32  {
33  if(x <= 0 || x >= curve.get_p())
34  throw Invalid_Argument("Invalid PointGFp affine x");
35  if(y <= 0 || y >= curve.get_p())
36  throw Invalid_Argument("Invalid PointGFp affine y");
37 
38  secure_vector<word> monty_ws(m_curve.get_ws_size());
39  m_curve.to_rep(m_coord_x, monty_ws);
40  m_curve.to_rep(m_coord_y, monty_ws);
41  }
void to_rep(BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:153
size_t get_ws_size() const
Definition: curve_gfp.h:135
const BigInt & get_1_rep() const
Definition: curve_gfp.h:141

Member Function Documentation

◆ add() [1/2]

void Botan::PointGFp::add ( const PointGFp other,
std::vector< BigInt > &  workspace 
)
inline

Point addition

Parameters
otherthe point to add to *this
workspacetemp space, at least WORKSPACE_SIZE elements

Definition at line 220 of file point_gfp.h.

References BOTAN_ASSERT_NOMSG, Botan::BigInt::data(), and Botan::BigInt::size().

Referenced by Botan::operator*(), operator+=(), and plus().

221  {
222  BOTAN_ASSERT_NOMSG(m_curve == other.m_curve);
223 
224  const size_t p_words = m_curve.get_p_words();
225 
226  add(other.m_coord_x.data(), std::min(p_words, other.m_coord_x.size()),
227  other.m_coord_y.data(), std::min(p_words, other.m_coord_y.size()),
228  other.m_coord_z.data(), std::min(p_words, other.m_coord_z.size()),
229  workspace);
230  }
size_t get_p_words() const
Definition: curve_gfp.h:133
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68
void add(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:220

◆ add() [2/2]

void Botan::PointGFp::add ( const word  x_words[],
size_t  x_size,
const word  y_words[],
size_t  y_size,
const word  z_words[],
size_t  z_size,
std::vector< BigInt > &  workspace 
)

Point addition. Array version.

Parameters
x_wordsthe words of the x coordinate of the other point
x_sizesize of x_words
y_wordsthe words of the y coordinate of the other point
y_sizesize of y_words
z_wordsthe words of the z coordinate of the other point
z_sizesize of z_words
workspacetemp space, at least WORKSPACE_SIZE elements

Definition at line 173 of file point_gfp.cpp.

References Botan::BigInt::clear(), Botan::CurveGFp::get_1_rep(), Botan::CurveGFp::get_p(), Botan::CurveGFp::get_ws_size(), is_zero(), Botan::BigInt::is_zero(), Botan::BigInt::mod_sub(), Botan::CurveGFp::mul(), mult2(), Botan::BigInt::set_words(), and Botan::CurveGFp::sqr().

177  {
178  if(all_zeros(x_words, x_size) & all_zeros(z_words, z_size))
179  return;
180 
181  if(is_zero())
182  {
183  m_coord_x.set_words(x_words, x_size);
184  m_coord_y.set_words(y_words, y_size);
185  m_coord_z.set_words(z_words, z_size);
186  return;
187  }
188 
189  resize_ws(ws_bn, m_curve.get_ws_size());
190 
191  secure_vector<word>& ws = ws_bn[0].get_word_vector();
192  secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();
193 
194  BigInt& T0 = ws_bn[2];
195  BigInt& T1 = ws_bn[3];
196  BigInt& T2 = ws_bn[4];
197  BigInt& T3 = ws_bn[5];
198  BigInt& T4 = ws_bn[6];
199  BigInt& T5 = ws_bn[7];
200 
201  /*
202  https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
203  */
204 
205  const BigInt& p = m_curve.get_p();
206 
207  m_curve.sqr(T0, z_words, z_size, ws); // z2^2
208  m_curve.mul(T1, m_coord_x, T0, ws); // x1*z2^2
209  m_curve.mul(T3, z_words, z_size, T0, ws); // z2^3
210  m_curve.mul(T2, m_coord_y, T3, ws); // y1*z2^3
211 
212  m_curve.sqr(T3, m_coord_z, ws); // z1^2
213  m_curve.mul(T4, x_words, x_size, T3, ws); // x2*z1^2
214 
215  m_curve.mul(T5, m_coord_z, T3, ws); // z1^3
216  m_curve.mul(T0, y_words, y_size, T5, ws); // y2*z1^3
217 
218  T4.mod_sub(T1, p, sub_ws); // x2*z1^2 - x1*z2^2
219 
220  T0.mod_sub(T2, p, sub_ws);
221 
222  if(T4.is_zero())
223  {
224  if(T0.is_zero())
225  {
226  mult2(ws_bn);
227  return;
228  }
229 
230  // setting to zero:
231  m_coord_x.clear();
232  m_coord_y = m_curve.get_1_rep();
233  m_coord_z.clear();
234  return;
235  }
236 
237  m_curve.sqr(T5, T4, ws);
238 
239  m_curve.mul(T3, T1, T5, ws);
240 
241  m_curve.mul(T1, T5, T4, ws);
242 
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);
247 
248  T3.mod_sub(m_coord_x, p, sub_ws);
249 
250  m_curve.mul(m_coord_y, T0, T3, ws);
251  m_curve.mul(T3, T2, T1, ws);
252 
253  m_coord_y.mod_sub(T3, p, sub_ws);
254 
255  m_curve.mul(T3, z_words, z_size, m_coord_z, ws);
256  m_curve.mul(m_coord_z, T3, T4, ws);
257  }
BigInt & mod_sub(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:93
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:172
size_t get_ws_size() const
Definition: curve_gfp.h:135
const BigInt & get_1_rep() const
Definition: curve_gfp.h:141
void set_words(const word w[], size_t len)
Definition: bigint.h:521
void mult2(std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:279
void clear()
Definition: bigint.h:365
bool is_zero() const
Definition: point_gfp.h:183
const BigInt & get_p() const
Definition: curve_gfp.h:131
void sqr(BigInt &z, const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:183

◆ add_affine() [1/2]

void Botan::PointGFp::add_affine ( const PointGFp other,
std::vector< BigInt > &  workspace 
)
inline

Point addition - mixed J+A

Parameters
otheraffine point to add - assumed to be affine!
workspacetemp space, at least WORKSPACE_SIZE elements

Definition at line 253 of file point_gfp.h.

References BOTAN_ASSERT_NOMSG, BOTAN_DEBUG_ASSERT, Botan::BigInt::data(), is_affine(), and Botan::BigInt::size().

Referenced by Botan::PointGFp_Base_Point_Precompute::mul(), and Botan::PointGFp_Multi_Point_Precompute::multi_exp().

254  {
255  BOTAN_ASSERT_NOMSG(m_curve == other.m_curve);
256  BOTAN_DEBUG_ASSERT(other.is_affine());
257 
258  const size_t p_words = m_curve.get_p_words();
259  add_affine(other.m_coord_x.data(), std::min(p_words, other.m_coord_x.size()),
260  other.m_coord_y.data(), std::min(p_words, other.m_coord_y.size()),
261  workspace);
262  }
size_t get_p_words() const
Definition: curve_gfp.h:133
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
void add_affine(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:253

◆ add_affine() [2/2]

void Botan::PointGFp::add_affine ( const word  x_words[],
size_t  x_size,
const word  y_words[],
size_t  y_size,
std::vector< BigInt > &  workspace 
)

Point addition - mixed J+A. Array version.

Parameters
x_wordsthe words of the x coordinate of the other point
x_sizesize of x_words
y_wordsthe words of the y coordinate of the other point
y_sizesize of y_words
workspacetemp space, at least WORKSPACE_SIZE elements

Definition at line 90 of file point_gfp.cpp.

References Botan::BigInt::clear(), Botan::CurveGFp::get_1_rep(), Botan::CurveGFp::get_p(), Botan::BigInt::get_word_vector(), Botan::CurveGFp::get_ws_size(), is_zero(), Botan::BigInt::is_zero(), Botan::BigInt::mod_sub(), Botan::CurveGFp::mul(), mult2(), Botan::BigInt::set_words(), Botan::CurveGFp::sqr(), and Botan::BigInt::swap().

93  {
94  if(all_zeros(x_words, x_size) & all_zeros(y_words, y_size))
95  {
96  return;
97  }
98 
99  if(is_zero())
100  {
101  m_coord_x.set_words(x_words, x_size);
102  m_coord_y.set_words(y_words, y_size);
103  m_coord_z = m_curve.get_1_rep();
104  return;
105  }
106 
107  resize_ws(ws_bn, m_curve.get_ws_size());
108 
109  secure_vector<word>& ws = ws_bn[0].get_word_vector();
110  secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();
111 
112  BigInt& T0 = ws_bn[2];
113  BigInt& T1 = ws_bn[3];
114  BigInt& T2 = ws_bn[4];
115  BigInt& T3 = ws_bn[5];
116  BigInt& T4 = ws_bn[6];
117 
118  /*
119  https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
120  simplified with Z2 = 1
121  */
122 
123  const BigInt& p = m_curve.get_p();
124 
125  m_curve.sqr(T3, m_coord_z, ws); // z1^2
126  m_curve.mul(T4, x_words, x_size, T3, ws); // x2*z1^2
127 
128  m_curve.mul(T2, m_coord_z, T3, ws); // z1^3
129  m_curve.mul(T0, y_words, y_size, T2, ws); // y2*z1^3
130 
131  T4.mod_sub(m_coord_x, p, sub_ws); // x2*z1^2 - x1*z2^2
132 
133  T0.mod_sub(m_coord_y, p, sub_ws);
134 
135  if(T4.is_zero())
136  {
137  if(T0.is_zero())
138  {
139  mult2(ws_bn);
140  return;
141  }
142 
143  // setting to zero:
144  m_coord_x.clear();
145  m_coord_y = m_curve.get_1_rep();
146  m_coord_z.clear();
147  return;
148  }
149 
150  m_curve.sqr(T2, T4, ws);
151 
152  m_curve.mul(T3, m_coord_x, T2, ws);
153 
154  m_curve.mul(T1, T2, T4, ws);
155 
156  m_curve.sqr(m_coord_x, T0, ws);
157  m_coord_x.mod_sub(T1, p, sub_ws);
158 
159  m_coord_x.mod_sub(T3, p, sub_ws);
160  m_coord_x.mod_sub(T3, p, sub_ws);
161 
162  T3.mod_sub(m_coord_x, p, sub_ws);
163 
164  m_curve.mul(T2, T0, T3, ws);
165  m_curve.mul(T0, m_coord_y, T1, ws);
166  T2.mod_sub(T0, p, sub_ws);
167  m_coord_y.swap(T2);
168 
169  m_curve.mul(T0, m_coord_z, T4, ws);
170  m_coord_z.swap(T0);
171  }
secure_vector< word > & get_word_vector()
Definition: bigint.h:628
BigInt & mod_sub(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:93
void swap(BigInt &other)
Definition: bigint.h:160
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:172
size_t get_ws_size() const
Definition: curve_gfp.h:135
const BigInt & get_1_rep() const
Definition: curve_gfp.h:141
void set_words(const word w[], size_t len)
Definition: bigint.h:521
void mult2(std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:279
void clear()
Definition: bigint.h:365
bool is_zero() const
Definition: point_gfp.h:183
const BigInt & get_p() const
Definition: curve_gfp.h:131
void sqr(BigInt &z, const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:183

◆ double_of()

PointGFp Botan::PointGFp::double_of ( std::vector< BigInt > &  workspace) const
inline

Point doubling

Parameters
workspacetemp space, at least WORKSPACE_SIZE elements
Returns
*this doubled

Definition at line 308 of file point_gfp.h.

References mult2().

309  {
310  PointGFp x = (*this);
311  x.mult2(workspace);
312  return x;
313  }
PointGFp()=default

◆ encode()

std::vector< uint8_t > Botan::PointGFp::encode ( PointGFp::Compression_Type  format) const

EC2OSP - elliptic curve to octet string primitive

Parameters
formatwhich format to encode using

Definition at line 595 of file point_gfp.cpp.

References Botan::BigInt::bytes(), COMPRESSED, Botan::BigInt::encode_1363(), get_affine_x(), get_affine_y(), Botan::BigInt::get_bit(), Botan::CurveGFp::get_p(), HYBRID, is_zero(), and UNCOMPRESSED.

Referenced by Botan::ECIES_Encryptor::ECIES_Encryptor(), Botan::EC_PrivateKey::private_key_bits(), and Botan::EC_PublicKey::public_key_bits().

596  {
597  if(is_zero())
598  return std::vector<uint8_t>(1); // single 0 byte
599 
600  const size_t p_bytes = m_curve.get_p().bytes();
601 
602  const BigInt x = get_affine_x();
603  const BigInt y = get_affine_y();
604 
605  std::vector<uint8_t> result;
606 
607  if(format == PointGFp::UNCOMPRESSED)
608  {
609  result.resize(1 + 2*p_bytes);
610  result[0] = 0x04;
611  BigInt::encode_1363(&result[1], p_bytes, x);
612  BigInt::encode_1363(&result[1+p_bytes], p_bytes, y);
613  }
614  else if(format == PointGFp::COMPRESSED)
615  {
616  result.resize(1 + p_bytes);
617  result[0] = 0x02 | static_cast<uint8_t>(y.get_bit(0));
618  BigInt::encode_1363(&result[1], p_bytes, x);
619  }
620  else if(format == PointGFp::HYBRID)
621  {
622  result.resize(1 + 2*p_bytes);
623  result[0] = 0x06 | static_cast<uint8_t>(y.get_bit(0));
624  BigInt::encode_1363(&result[1], p_bytes, x);
625  BigInt::encode_1363(&result[1+p_bytes], p_bytes, y);
626  }
627  else
628  throw Invalid_Argument("EC2OSP illegal point encoding");
629 
630  return result;
631  }
BigInt get_affine_x() const
Definition: point_gfp.cpp:499
BigInt get_affine_y() const
Definition: point_gfp.cpp:518
size_t bytes() const
Definition: bigint.cpp:266
bool is_zero() const
Definition: point_gfp.h:183
static secure_vector< uint8_t > encode_1363(const BigInt &n, size_t bytes)
Definition: big_code.cpp:123
const BigInt & get_p() const
Definition: curve_gfp.h:131

◆ force_affine()

void Botan::PointGFp::force_affine ( )

Force this point to affine coordinates

Definition at line 479 of file point_gfp.cpp.

References Botan::CurveGFp::get_1_rep(), Botan::CurveGFp::invert_element(), is_zero(), Botan::CurveGFp::mul_to_tmp(), and Botan::CurveGFp::sqr_to_tmp().

Referenced by force_all_affine().

480  {
481  if(is_zero())
482  throw Invalid_State("Cannot convert zero ECC point to affine");
483 
484  secure_vector<word> ws;
485 
486  const BigInt z_inv = m_curve.invert_element(m_coord_z, ws);
487  const BigInt z2_inv = m_curve.sqr_to_tmp(z_inv, ws);
488  const BigInt z3_inv = m_curve.mul_to_tmp(z_inv, z2_inv, ws);
489  m_coord_x = m_curve.mul_to_tmp(m_coord_x, z2_inv, ws);
490  m_coord_y = m_curve.mul_to_tmp(m_coord_y, z3_inv, ws);
491  m_coord_z = m_curve.get_1_rep();
492  }
const BigInt & get_1_rep() const
Definition: curve_gfp.h:141
BigInt invert_element(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:148
BigInt sqr_to_tmp(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:210
BigInt mul_to_tmp(const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:203
bool is_zero() const
Definition: point_gfp.h:183

◆ force_all_affine()

void Botan::PointGFp::force_all_affine ( std::vector< PointGFp > &  points,
secure_vector< word > &  ws 
)
static

Force all points on the list to affine coordinates

Definition at line 420 of file point_gfp.cpp.

References force_affine(), Botan::CurveGFp::get_1_rep(), Botan::CurveGFp::get_ws_size(), Botan::CurveGFp::invert_element(), Botan::CurveGFp::mul(), Botan::CurveGFp::mul_to_tmp(), Botan::BigInt::resize(), and Botan::CurveGFp::sqr().

Referenced by Botan::PointGFp_Multi_Point_Precompute::PointGFp_Multi_Point_Precompute().

422  {
423  if(points.size() <= 1)
424  {
425  for(size_t i = 0; i != points.size(); ++i)
426  points[i].force_affine();
427  return;
428  }
429 
430  /*
431  For >= 2 points use Montgomery's trick
432 
433  See Algorithm 2.26 in "Guide to Elliptic Curve Cryptography"
434  (Hankerson, Menezes, Vanstone)
435 
436  TODO is it really necessary to save all k points in c?
437  */
438 
439  const CurveGFp& curve = points[0].m_curve;
440  const BigInt& rep_1 = curve.get_1_rep();
441 
442  if(ws.size() < curve.get_ws_size())
443  ws.resize(curve.get_ws_size());
444 
445  std::vector<BigInt> c(points.size());
446  c[0] = points[0].m_coord_z;
447 
448  for(size_t i = 1; i != points.size(); ++i)
449  {
450  curve.mul(c[i], c[i-1], points[i].m_coord_z, ws);
451  }
452 
453  BigInt s_inv = curve.invert_element(c[c.size()-1], ws);
454 
455  BigInt z_inv, z2_inv, z3_inv;
456 
457  for(size_t i = points.size() - 1; i != 0; i--)
458  {
459  PointGFp& point = points[i];
460 
461  curve.mul(z_inv, s_inv, c[i-1], ws);
462 
463  s_inv = curve.mul_to_tmp(s_inv, point.m_coord_z, ws);
464 
465  curve.sqr(z2_inv, z_inv, ws);
466  curve.mul(z3_inv, z2_inv, z_inv, ws);
467  point.m_coord_x = curve.mul_to_tmp(point.m_coord_x, z2_inv, ws);
468  point.m_coord_y = curve.mul_to_tmp(point.m_coord_y, z3_inv, ws);
469  point.m_coord_z = rep_1;
470  }
471 
472  curve.sqr(z2_inv, s_inv, ws);
473  curve.mul(z3_inv, z2_inv, s_inv, ws);
474  points[0].m_coord_x = curve.mul_to_tmp(points[0].m_coord_x, z2_inv, ws);
475  points[0].m_coord_y = curve.mul_to_tmp(points[0].m_coord_y, z3_inv, ws);
476  points[0].m_coord_z = rep_1;
477  }
void force_affine()
Definition: point_gfp.cpp:479
PointGFp()=default

◆ get_affine_x()

BigInt Botan::PointGFp::get_affine_x ( ) const

get affine x coordinate

Returns
affine x coordinate

Definition at line 499 of file point_gfp.cpp.

References Botan::CurveGFp::from_rep(), Botan::CurveGFp::invert_element(), is_affine(), is_zero(), Botan::CurveGFp::mul(), and Botan::CurveGFp::sqr_to_tmp().

Referenced by Botan::EC_Group::blinded_base_point_multiply_x(), encode(), operator==(), Botan::GOST_3410_PublicKey::public_key_bits(), and Botan::sm2_compute_za().

500  {
501  if(is_zero())
502  throw Illegal_Transformation("Cannot convert zero point to affine");
503 
504  secure_vector<word> monty_ws;
505 
506  if(is_affine())
507  return m_curve.from_rep(m_coord_x, monty_ws);
508 
509  BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
510  z2 = m_curve.invert_element(z2, monty_ws);
511 
512  BigInt r;
513  m_curve.mul(r, m_coord_x, z2, monty_ws);
514  m_curve.from_rep(r, monty_ws);
515  return r;
516  }
bool is_affine() const
Definition: point_gfp.cpp:494
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:172
void from_rep(BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:158
BigInt invert_element(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:148
BigInt sqr_to_tmp(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:210
bool is_zero() const
Definition: point_gfp.h:183

◆ get_affine_y()

BigInt Botan::PointGFp::get_affine_y ( ) const

get affine y coordinate

Returns
affine y coordinate

Definition at line 518 of file point_gfp.cpp.

References Botan::CurveGFp::from_rep(), Botan::CurveGFp::invert_element(), is_affine(), is_zero(), Botan::CurveGFp::mul(), Botan::CurveGFp::mul_to_tmp(), and Botan::CurveGFp::sqr_to_tmp().

Referenced by encode(), operator==(), Botan::GOST_3410_PublicKey::public_key_bits(), and Botan::sm2_compute_za().

519  {
520  if(is_zero())
521  throw Illegal_Transformation("Cannot convert zero point to affine");
522 
523  secure_vector<word> monty_ws;
524 
525  if(is_affine())
526  return m_curve.from_rep(m_coord_y, monty_ws);
527 
528  const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
529  const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws);
530  const BigInt z3_inv = m_curve.invert_element(z3, monty_ws);
531 
532  BigInt r;
533  m_curve.mul(r, m_coord_y, z3_inv, monty_ws);
534  m_curve.from_rep(r, monty_ws);
535  return r;
536  }
bool is_affine() const
Definition: point_gfp.cpp:494
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:172
void from_rep(BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:158
BigInt invert_element(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:148
BigInt sqr_to_tmp(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:210
BigInt mul_to_tmp(const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:203
bool is_zero() const
Definition: point_gfp.h:183

◆ get_curve()

const CurveGFp& Botan::PointGFp::get_curve ( ) const
inline

Return base curve of this point

Returns
the curve over GF(p) of this point

You should not need to use this

Definition at line 326 of file point_gfp.h.

Referenced by Botan::EC_PublicKey::EC_PublicKey().

326 { return m_curve; }

◆ get_x()

const BigInt& Botan::PointGFp::get_x ( ) const
inline

Definition at line 155 of file point_gfp.h.

155 { return m_coord_x; }

◆ get_y()

const BigInt& Botan::PointGFp::get_y ( ) const
inline

Definition at line 156 of file point_gfp.h.

156 { return m_coord_y; }

◆ get_z()

const BigInt& Botan::PointGFp::get_z ( ) const
inline

Definition at line 157 of file point_gfp.h.

157 { return m_coord_z; }

◆ is_affine()

bool Botan::PointGFp::is_affine ( ) const

Definition at line 494 of file point_gfp.cpp.

References Botan::CurveGFp::is_one().

Referenced by add_affine(), get_affine_x(), and get_affine_y().

495  {
496  return m_curve.is_one(m_coord_z);
497  }
bool is_one(const BigInt &x) const
Definition: curve_gfp.h:146

◆ is_zero()

bool Botan::PointGFp::is_zero ( ) const
inline

Is this the point at infinity?

Returns
true, if this point is at infinity, false otherwise.

Definition at line 183 of file point_gfp.h.

Referenced by add(), add_affine(), Botan::EC_Group::blinded_base_point_multiply_x(), Botan::ECIES_KA_Operation::derive_secret(), encode(), force_affine(), get_affine_x(), get_affine_y(), mult2(), on_the_curve(), operator-=(), operator==(), and Botan::EC_Group::verify_public_element().

183 { return m_coord_z.is_zero(); }
bool is_zero() const
Definition: bigint.h:420

◆ mult2()

void Botan::PointGFp::mult2 ( std::vector< BigInt > &  workspace)

Point doubling

Parameters
workspacetemp space, at least WORKSPACE_SIZE elements

Definition at line 279 of file point_gfp.cpp.

References Botan::CurveGFp::a_is_minus_3(), Botan::CurveGFp::a_is_zero(), Botan::CurveGFp::get_a_rep(), Botan::CurveGFp::get_p(), Botan::CurveGFp::get_ws_size(), is_zero(), Botan::BigInt::is_zero(), Botan::BigInt::mod_add(), Botan::BigInt::mod_mul(), Botan::BigInt::mod_sub(), Botan::CurveGFp::mul(), PointGFp(), Botan::CurveGFp::sqr(), and Botan::BigInt::swap().

Referenced by add(), add_affine(), double_of(), mult2i(), Botan::operator*(), and Botan::PointGFp_Multi_Point_Precompute::PointGFp_Multi_Point_Precompute().

280  {
281  if(is_zero())
282  return;
283 
284  if(m_coord_y.is_zero())
285  {
286  *this = PointGFp(m_curve); // setting myself to zero
287  return;
288  }
289 
290  resize_ws(ws_bn, m_curve.get_ws_size());
291 
292  secure_vector<word>& ws = ws_bn[0].get_word_vector();
293  secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();
294 
295  BigInt& T0 = ws_bn[2];
296  BigInt& T1 = ws_bn[3];
297  BigInt& T2 = ws_bn[4];
298  BigInt& T3 = ws_bn[5];
299  BigInt& T4 = ws_bn[6];
300 
301  /*
302  https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-1986-cc
303  */
304  const BigInt& p = m_curve.get_p();
305 
306  m_curve.sqr(T0, m_coord_y, ws);
307 
308  m_curve.mul(T1, m_coord_x, T0, ws);
309  T1.mod_mul(4, p, sub_ws);
310 
311  if(m_curve.a_is_zero())
312  {
313  // if a == 0 then 3*x^2 + a*z^4 is just 3*x^2
314  m_curve.sqr(T4, m_coord_x, ws); // x^2
315  T4.mod_mul(3, p, sub_ws); // 3*x^2
316  }
317  else if(m_curve.a_is_minus_3())
318  {
319  /*
320  if a == -3 then
321  3*x^2 + a*z^4 == 3*x^2 - 3*z^4 == 3*(x^2-z^4) == 3*(x-z^2)*(x+z^2)
322  */
323  m_curve.sqr(T3, m_coord_z, ws); // z^2
324 
325  // (x-z^2)
326  T2 = m_coord_x;
327  T2.mod_sub(T3, p, sub_ws);
328 
329  // (x+z^2)
330  T3.mod_add(m_coord_x, p, sub_ws);
331 
332  m_curve.mul(T4, T2, T3, ws); // (x-z^2)*(x+z^2)
333 
334  T4.mod_mul(3, p, sub_ws); // 3*(x-z^2)*(x+z^2)
335  }
336  else
337  {
338  m_curve.sqr(T3, m_coord_z, ws); // z^2
339  m_curve.sqr(T4, T3, ws); // z^4
340  m_curve.mul(T3, m_curve.get_a_rep(), T4, ws); // a*z^4
341 
342  m_curve.sqr(T4, m_coord_x, ws); // x^2
343  T4.mod_mul(3, p, sub_ws);
344  T4.mod_add(T3, p, sub_ws); // 3*x^2 + a*z^4
345  }
346 
347  m_curve.sqr(T2, T4, ws);
348  T2.mod_sub(T1, p, sub_ws);
349  T2.mod_sub(T1, p, sub_ws);
350 
351  m_curve.sqr(T3, T0, ws);
352  T3.mod_mul(8, p, sub_ws);
353 
354  T1.mod_sub(T2, p, sub_ws);
355 
356  m_curve.mul(T0, T4, T1, ws);
357  T0.mod_sub(T3, p, sub_ws);
358 
359  m_coord_x.swap(T2);
360 
361  m_curve.mul(T2, m_coord_y, m_coord_z, ws);
362  T2.mod_mul(2, p, sub_ws);
363 
364  m_coord_y.swap(T0);
365  m_coord_z.swap(T2);
366  }
bool a_is_minus_3() const
Definition: curve_gfp.h:143
const BigInt & get_a_rep() const
Definition: curve_gfp.h:137
BigInt & mod_sub(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:93
bool is_zero() const
Definition: bigint.h:420
void swap(BigInt &other)
Definition: bigint.h:160
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:172
size_t get_ws_size() const
Definition: curve_gfp.h:135
PointGFp()=default
BigInt & mod_add(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:50
bool a_is_zero() const
Definition: curve_gfp.h:144
bool is_zero() const
Definition: point_gfp.h:183
const BigInt & get_p() const
Definition: curve_gfp.h:131
void sqr(BigInt &z, const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:183

◆ mult2i()

void Botan::PointGFp::mult2i ( size_t  i,
std::vector< BigInt > &  workspace 
)

Repeated point doubling

Parameters
inumber of doublings to perform
workspacetemp space, at least WORKSPACE_SIZE elements

Definition at line 259 of file point_gfp.cpp.

References Botan::BigInt::is_zero(), mult2(), and PointGFp().

Referenced by Botan::PointGFp_Multi_Point_Precompute::multi_exp().

260  {
261  if(iterations == 0)
262  return;
263 
264  if(m_coord_y.is_zero())
265  {
266  *this = PointGFp(m_curve); // setting myself to zero
267  return;
268  }
269 
270  /*
271  TODO we can save 2 squarings per iteration by computing
272  a*Z^4 using values cached from previous iteration
273  */
274  for(size_t i = 0; i != iterations; ++i)
275  mult2(ws_bn);
276  }
bool is_zero() const
Definition: bigint.h:420
PointGFp()=default
void mult2(std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:279

◆ negate()

PointGFp& Botan::PointGFp::negate ( )
inline

Negate this point

Returns
*this

Definition at line 136 of file point_gfp.h.

Referenced by Botan::PointGFp_Multi_Point_Precompute::multi_exp(), and Botan::operator-().

137  {
138  if(!is_zero())
139  m_coord_y = m_curve.get_p() - m_coord_y;
140  return *this;
141  }
bool is_zero() const
Definition: point_gfp.h:183
const BigInt & get_p() const
Definition: curve_gfp.h:131

◆ on_the_curve()

bool Botan::PointGFp::on_the_curve ( ) const

Checks whether the point is to be found on the underlying curve; used to prevent fault attacks.

Returns
if the point is on the curve

Definition at line 538 of file point_gfp.cpp.

References Botan::CurveGFp::from_rep(), Botan::CurveGFp::get_a_rep(), Botan::CurveGFp::get_b_rep(), is_zero(), Botan::CurveGFp::mul_to_tmp(), and Botan::CurveGFp::sqr_to_tmp().

Referenced by Botan::EC_PrivateKey::EC_PrivateKey(), Botan::GOST_3410_PublicKey::GOST_3410_PublicKey(), Botan::PointGFp_Base_Point_Precompute::mul(), Botan::operator*(), Botan::EC_Group::verify_group(), and Botan::EC_Group::verify_public_element().

539  {
540  /*
541  Is the point still on the curve?? (If everything is correct, the
542  point is always on its curve; then the function will return true.
543  If somehow the state is corrupted, which suggests a fault attack
544  (or internal computational error), then return false.
545  */
546  if(is_zero())
547  return true;
548 
549  secure_vector<word> monty_ws;
550 
551  const BigInt y2 = m_curve.from_rep(m_curve.sqr_to_tmp(m_coord_y, monty_ws), monty_ws);
552  const BigInt x3 = m_curve.mul_to_tmp(m_coord_x, m_curve.sqr_to_tmp(m_coord_x, monty_ws), monty_ws);
553  const BigInt ax = m_curve.mul_to_tmp(m_coord_x, m_curve.get_a_rep(), monty_ws);
554  const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
555 
556  if(m_coord_z == z2) // Is z equal to 1 (in Montgomery form)?
557  {
558  if(y2 != m_curve.from_rep(x3 + ax + m_curve.get_b_rep(), monty_ws))
559  return false;
560  }
561 
562  const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws);
563  const BigInt ax_z4 = m_curve.mul_to_tmp(ax, m_curve.sqr_to_tmp(z2, monty_ws), monty_ws);
564  const BigInt b_z6 = m_curve.mul_to_tmp(m_curve.get_b_rep(), m_curve.sqr_to_tmp(z3, monty_ws), monty_ws);
565 
566  if(y2 != m_curve.from_rep(x3 + ax_z4 + b_z6, monty_ws))
567  return false;
568 
569  return true;
570  }
const BigInt & get_a_rep() const
Definition: curve_gfp.h:137
const BigInt & get_b_rep() const
Definition: curve_gfp.h:139
void from_rep(BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:158
BigInt sqr_to_tmp(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:210
BigInt mul_to_tmp(const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:203
bool is_zero() const
Definition: point_gfp.h:183

◆ operator*=()

PointGFp & Botan::PointGFp::operator*= ( const BigInt scalar)

*= Operator

Parameters
scalarthe PointGFp to multiply with *this
Returns
resulting PointGFp

Definition at line 388 of file point_gfp.cpp.

389  {
390  *this = scalar * *this;
391  return *this;
392  }

◆ operator+=()

PointGFp & Botan::PointGFp::operator+= ( const PointGFp rhs)

+= Operator

Parameters
rhsthe PointGFp to add to the local value
Returns
resulting PointGFp

Definition at line 369 of file point_gfp.cpp.

References add(), and WORKSPACE_SIZE.

370  {
371  std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
372  add(rhs, ws);
373  return *this;
374  }
void add(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.h:220

◆ operator-=()

PointGFp & Botan::PointGFp::operator-= ( const PointGFp rhs)

-= Operator

Parameters
rhsthe PointGFp to subtract from the local value
Returns
resulting PointGFp

Definition at line 376 of file point_gfp.cpp.

References is_zero(), and PointGFp().

377  {
378  PointGFp minus_rhs = PointGFp(rhs).negate();
379 
380  if(is_zero())
381  *this = minus_rhs;
382  else
383  *this += minus_rhs;
384 
385  return *this;
386  }
PointGFp()=default
bool is_zero() const
Definition: point_gfp.h:183

◆ operator=() [1/2]

PointGFp& Botan::PointGFp::operator= ( const PointGFp )
default

Standard Assignment

◆ operator=() [2/2]

PointGFp& Botan::PointGFp::operator= ( PointGFp &&  other)
inline

Move Assignment

Definition at line 90 of file point_gfp.h.

91  {
92  if(this != &other)
93  this->swap(other);
94  return (*this);
95  }
void swap(PointGFp &other)
Definition: point_gfp.cpp:573

◆ operator==()

bool Botan::PointGFp::operator== ( const PointGFp other) const

Equality operator

Definition at line 581 of file point_gfp.cpp.

References get_affine_x(), get_affine_y(), and is_zero().

582  {
583  if(m_curve != other.m_curve)
584  return false;
585 
586  // If this is zero, only equal if other is also zero
587  if(is_zero())
588  return other.is_zero();
589 
590  return (get_affine_x() == other.get_affine_x() &&
591  get_affine_y() == other.get_affine_y());
592  }
BigInt get_affine_x() const
Definition: point_gfp.cpp:499
BigInt get_affine_y() const
Definition: point_gfp.cpp:518
bool is_zero() const
Definition: point_gfp.h:183

◆ plus()

PointGFp Botan::PointGFp::plus ( const PointGFp other,
std::vector< BigInt > &  workspace 
) const
inline

Point addition

Parameters
otherthe point to add to *this
workspacetemp space, at least WORKSPACE_SIZE elements
Returns
other plus *this

Definition at line 296 of file point_gfp.h.

References add().

Referenced by Botan::PointGFp_Multi_Point_Precompute::PointGFp_Multi_Point_Precompute().

297  {
298  PointGFp x = (*this);
299  x.add(other, workspace);
300  return x;
301  }
PointGFp()=default

◆ randomize_repr() [1/2]

void Botan::PointGFp::randomize_repr ( RandomNumberGenerator rng)

Randomize the point representation The actual value (get_affine_x, get_affine_y) does not change

Definition at line 43 of file point_gfp.cpp.

References Botan::CurveGFp::get_ws_size().

Referenced by Botan::PointGFp_Base_Point_Precompute::mul().

44  {
45  secure_vector<word> ws(m_curve.get_ws_size());
46  randomize_repr(rng, ws);
47  }
size_t get_ws_size() const
Definition: curve_gfp.h:135
void randomize_repr(RandomNumberGenerator &rng)
Definition: point_gfp.cpp:43

◆ randomize_repr() [2/2]

void Botan::PointGFp::randomize_repr ( RandomNumberGenerator rng,
secure_vector< word > &  ws 
)

Randomize the point representation The actual value (get_affine_x, get_affine_y) does not change

Definition at line 49 of file point_gfp.cpp.

References Botan::CurveGFp::get_p(), Botan::CurveGFp::mul_to_tmp(), Botan::BigInt::random_integer(), and Botan::CurveGFp::sqr_to_tmp().

50  {
51  const BigInt mask = BigInt::random_integer(rng, 2, m_curve.get_p());
52 
53  /*
54  * No reason to convert this to Montgomery representation first,
55  * just pretend the random mask was chosen as Redc(mask) and the
56  * random mask we generated above is in the Montgomery
57  * representation.
58  * //m_curve.to_rep(mask, ws);
59  */
60  const BigInt mask2 = m_curve.sqr_to_tmp(mask, ws);
61  const BigInt mask3 = m_curve.mul_to_tmp(mask2, mask, ws);
62 
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);
66  }
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
Definition: big_rand.cpp:45
BigInt sqr_to_tmp(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:210
BigInt mul_to_tmp(const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:203
const BigInt & get_p() const
Definition: curve_gfp.h:131

◆ swap()

void Botan::PointGFp::swap ( PointGFp other)

swaps the states of *this and other, does not throw!

Parameters
otherthe object to swap values with

Definition at line 573 of file point_gfp.cpp.

References Botan::BigInt::swap(), and Botan::CurveGFp::swap().

574  {
575  m_curve.swap(other.m_curve);
576  m_coord_x.swap(other.m_coord_x);
577  m_coord_y.swap(other.m_coord_y);
578  m_coord_z.swap(other.m_coord_z);
579  }
void swap(BigInt &other)
Definition: bigint.h:160
void swap(CurveGFp &other)
Definition: curve_gfp.h:217

◆ swap_coords()

void Botan::PointGFp::swap_coords ( BigInt new_x,
BigInt new_y,
BigInt new_z 
)
inline

Definition at line 159 of file point_gfp.h.

160  {
161  m_coord_x.swap(new_x);
162  m_coord_y.swap(new_y);
163  m_coord_z.swap(new_z);
164  }
void swap(BigInt &other)
Definition: bigint.h:160

◆ zero()

PointGFp Botan::PointGFp::zero ( ) const
inline

Return the zero (aka infinite) point associated with this curve

Definition at line 318 of file point_gfp.h.

Referenced by Botan::PointGFp_Base_Point_Precompute::mul(), and Botan::operator*().

318 { return PointGFp(m_curve); }
PointGFp()=default

The documentation for this class was generated from the following files: