Botan  2.6.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 = 7 }
 
enum  Compression_Type { UNCOMPRESSED = 0, COMPRESSED = 1, HYBRID = 2 }
 

Public Member Functions

void add (const PointGFp &other, 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)
 
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)
 
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)
 
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 43 of file point_gfp.h.

Member Enumeration Documentation

◆ anonymous enum

anonymous enum
Enumerator
WORKSPACE_SIZE 

Definition at line 52 of file point_gfp.h.

◆ Compression_Type

Enumerator
UNCOMPRESSED 
COMPRESSED 
HYBRID 

Definition at line 46 of file point_gfp.h.

Constructor & Destructor Documentation

◆ PointGFp() [1/5]

Botan::PointGFp::PointGFp ( )
default

Construct an uninitialized PointGFp

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

◆ PointGFp() [2/5]

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

Construct the zero point

Parameters
curveThe base curve

Definition at line 17 of file point_gfp.cpp.

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

17  :
18  m_curve(curve),
19  m_coord_x(0),
20  m_coord_y(1),
21  m_coord_z(0)
22  {
23  secure_vector<word> monty_ws(m_curve.get_ws_size());
24  m_curve.to_rep(m_coord_x, monty_ws);
25  m_curve.to_rep(m_coord_y, monty_ws);
26  m_curve.to_rep(m_coord_z, monty_ws);
27  }
void to_rep(BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:126
size_t get_ws_size() const
Definition: curve_gfp.h:113

◆ 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 73 of file point_gfp.h.

74  {
75  this->swap(other);
76  }
void swap(PointGFp &other)
Definition: point_gfp.cpp:565

◆ 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 29 of file point_gfp.cpp.

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

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

Member Function Documentation

◆ add()

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

Point addition

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

Definition at line 195 of file point_gfp.cpp.

References Botan::CurveGFp::get_p(), Botan::BigInt::get_word_vector(), Botan::CurveGFp::get_ws_size(), Botan::BigInt::is_negative(), is_zero(), Botan::BigInt::is_zero(), Botan::CurveGFp::mul(), mult2(), and Botan::CurveGFp::sqr().

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

196  {
197  if(rhs.is_zero())
198  return;
199 
200  if(is_zero())
201  {
202  m_coord_x = rhs.m_coord_x;
203  m_coord_y = rhs.m_coord_y;
204  m_coord_z = rhs.m_coord_z;
205  return;
206  }
207 
208  resize_ws(ws_bn, m_curve.get_ws_size());
209 
210  secure_vector<word>& ws = ws_bn[0].get_word_vector();
211 
212  BigInt& T0 = ws_bn[1];
213  BigInt& T1 = ws_bn[2];
214  BigInt& T2 = ws_bn[3];
215  BigInt& T3 = ws_bn[4];
216  BigInt& T4 = ws_bn[5];
217  BigInt& T5 = ws_bn[6];
218 
219  /*
220  https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
221  */
222 
223  const BigInt& p = m_curve.get_p();
224 
225  m_curve.sqr(T0, rhs.m_coord_z, ws); // z2^2
226  m_curve.mul(T1, m_coord_x, T0, ws); // x1*z2^2
227  m_curve.mul(T3, rhs.m_coord_z, T0, ws); // z2^3
228  m_curve.mul(T2, m_coord_y, T3, ws); // y1*z2^3
229 
230  m_curve.sqr(T3, m_coord_z, ws); // z1^2
231  m_curve.mul(T4, rhs.m_coord_x, T3, ws); // x2*z1^2
232 
233  m_curve.mul(T5, m_coord_z, T3, ws); // z1^3
234  m_curve.mul(T0, rhs.m_coord_y, T5, ws); // y2*z1^3
235 
236  T4 -= T1; // x2*z1^2 - x1*z2^2
237  if(T4.is_negative())
238  T4 += p;
239 
240  T3 = T0;
241  T3 -= T2;
242  if(T3.is_negative())
243  T3 += p;
244 
245  if(T4.is_zero())
246  {
247  if(T3.is_zero())
248  {
249  mult2(ws_bn);
250  return;
251  }
252 
253  // setting to zero:
254  m_coord_x = 0;
255  m_coord_y = 1;
256  m_coord_z = 0;
257  return;
258  }
259 
260  m_curve.sqr(T5, T4, ws);
261 
262  m_curve.mul(T0, T1, T5, ws);
263 
264  m_curve.mul(T1, T5, T4, ws);
265 
266  m_curve.sqr(m_coord_x, T3, ws);
267  m_coord_x -= T1;
268  m_coord_x -= T0;
269  m_coord_x -= T0;
270  while(m_coord_x.is_negative())
271  m_coord_x += p;
272 
273  T0 -= m_coord_x;
274  if(T0.is_negative())
275  T0 += p;
276 
277  m_curve.mul(m_coord_y, T3, T0, ws);
278  m_curve.mul(T0, T2, T1, ws);
279  m_coord_y -= T0;
280  if(m_coord_y.is_negative())
281  m_coord_y += p;
282 
283  m_curve.mul(T0, m_coord_z, rhs.m_coord_z, ws);
284  m_curve.mul(m_coord_z, T0, T4, ws);
285  }
bool is_negative() const
Definition: bigint.h:413
secure_vector< word > & get_word_vector()
Definition: bigint.h:506
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:145
size_t get_ws_size() const
Definition: curve_gfp.h:113
void mult2(std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:288
bool is_zero() const
Definition: point_gfp.h:172
const BigInt & get_p() const
Definition: curve_gfp.h:109
void sqr(BigInt &z, const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:156

◆ add_affine() [1/2]

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

Point addition - mixed J+A

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

Definition at line 92 of file point_gfp.cpp.

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

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

93  {
94  BOTAN_DEBUG_ASSERT(rhs.is_affine());
95 
96  const size_t p_words = m_curve.get_p_words();
97  add_affine(rhs.m_coord_x.data(), std::min(p_words, rhs.m_coord_x.size()),
98  rhs.m_coord_y.data(), std::min(p_words, rhs.m_coord_y.size()),
99  workspace);
100  }
size_t get_p_words() const
Definition: curve_gfp.h:111
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:98
void add_affine(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:92

◆ 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 102 of file point_gfp.cpp.

References Botan::CurveGFp::get_p(), Botan::CurveGFp::get_ws_size(), Botan::BigInt::is_negative(), is_zero(), Botan::BigInt::is_zero(), Botan::CurveGFp::mul(), mult2(), Botan::CurveGFp::sqr(), and Botan::CurveGFp::to_rep().

105  {
106  if(all_zeros(x_words, x_size) && all_zeros(y_words, y_size))
107  return;
108 
109  if(is_zero())
110  {
111  // FIXME avoid the copy here
112  m_coord_x = BigInt(x_words, x_size);
113  m_coord_y = BigInt(y_words, y_size);
114  m_coord_z = 1;
115  m_curve.to_rep(m_coord_z, ws_bn[0].get_word_vector());
116  return;
117  }
118 
119  resize_ws(ws_bn, m_curve.get_ws_size());
120 
121  secure_vector<word>& ws = ws_bn[0].get_word_vector();
122 
123  BigInt& T0 = ws_bn[1];
124  BigInt& T1 = ws_bn[2];
125  BigInt& T2 = ws_bn[3];
126  BigInt& T3 = ws_bn[4];
127  BigInt& T4 = ws_bn[5];
128 
129  /*
130  https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
131  simplified with Z2 = 1
132  */
133 
134  const BigInt& p = m_curve.get_p();
135 
136  m_curve.sqr(T3, m_coord_z, ws); // z1^2
137  m_curve.mul(T4, x_words, x_size, T3, ws); // x2*z1^2
138 
139  m_curve.mul(T2, m_coord_z, T3, ws); // z1^3
140  m_curve.mul(T0, y_words, y_size, T2, ws); // y2*z1^3
141 
142  T4 -= m_coord_x; // x2*z1^2 - x1*z2^2
143  if(T4.is_negative())
144  T4 += p;
145 
146  T0 -= m_coord_y;
147  if(T0.is_negative())
148  T0 += p;
149 
150  if(T4.is_zero())
151  {
152  if(T0.is_zero())
153  {
154  mult2(ws_bn);
155  return;
156  }
157 
158  // setting to zero:
159  m_coord_x = 0;
160  m_coord_y = 1;
161  m_coord_z = 0;
162  return;
163  }
164 
165  m_curve.sqr(T2, T4, ws);
166 
167  m_curve.mul(T3, m_coord_x, T2, ws);
168 
169  m_curve.mul(T1, T2, T4, ws);
170 
171  m_curve.sqr(m_coord_x, T0, ws);
172  m_coord_x -= T1;
173  m_coord_x -= T3;
174  m_coord_x -= T3;
175  while(m_coord_x.is_negative())
176  m_coord_x += p;
177 
178  T3 -= m_coord_x;
179  if(T3.is_negative())
180  T3 += p;
181 
182  T2 = m_coord_y;
183  m_curve.mul(T2, T0, T3, ws);
184  m_curve.mul(T3, m_coord_y, T1, ws);
185  T2 -= T3;
186  if(T2.is_negative())
187  T2 += p;
188  m_coord_y = T2;
189 
190  m_curve.mul(T3, m_coord_z, T4, ws);
191  m_coord_z = T3;
192  }
bool is_negative() const
Definition: bigint.h:413
void to_rep(BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:126
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:145
size_t get_ws_size() const
Definition: curve_gfp.h:113
void mult2(std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:288
bool is_zero() const
Definition: point_gfp.h:172
const BigInt & get_p() const
Definition: curve_gfp.h:109
void sqr(BigInt &z, const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:156

◆ 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 587 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(), and Botan::EC_PublicKey::public_key_bits().

588  {
589  if(is_zero())
590  return std::vector<uint8_t>(1); // single 0 byte
591 
592  const size_t p_bytes = m_curve.get_p().bytes();
593 
594  const BigInt x = get_affine_x();
595  const BigInt y = get_affine_y();
596 
597  std::vector<uint8_t> result;
598 
599  if(format == PointGFp::UNCOMPRESSED)
600  {
601  result.resize(1 + 2*p_bytes);
602  result[0] = 0x04;
603  BigInt::encode_1363(&result[1], p_bytes, x);
604  BigInt::encode_1363(&result[1+p_bytes], p_bytes, y);
605  }
606  else if(format == PointGFp::COMPRESSED)
607  {
608  result.resize(1 + p_bytes);
609  result[0] = 0x02 | static_cast<uint8_t>(y.get_bit(0));
610  BigInt::encode_1363(&result[1], p_bytes, x);
611  }
612  else if(format == PointGFp::HYBRID)
613  {
614  result.resize(1 + 2*p_bytes);
615  result[0] = 0x06 | static_cast<uint8_t>(y.get_bit(0));
616  BigInt::encode_1363(&result[1], p_bytes, x);
617  BigInt::encode_1363(&result[1+p_bytes], p_bytes, y);
618  }
619  else
620  throw Invalid_Argument("EC2OSP illegal point encoding");
621 
622  return result;
623  }
BigInt get_affine_x() const
Definition: point_gfp.cpp:491
BigInt get_affine_y() const
Definition: point_gfp.cpp:510
size_t bytes() const
Definition: bigint.cpp:208
bool is_zero() const
Definition: point_gfp.h:172
static secure_vector< uint8_t > encode_1363(const BigInt &n, size_t bytes)
Definition: big_code.cpp:82
const BigInt & get_p() const
Definition: curve_gfp.h:109

◆ force_affine()

void Botan::PointGFp::force_affine ( )

Force this point to affine coordinates

Definition at line 470 of file point_gfp.cpp.

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

Referenced by force_all_affine().

471  {
472  if(is_zero())
473  throw Invalid_State("Cannot convert zero ECC point to affine");
474 
475  secure_vector<word> ws;
476 
477  const BigInt z_inv = m_curve.invert_element(m_coord_z, ws);
478  const BigInt z2_inv = m_curve.sqr_to_tmp(z_inv, ws);
479  const BigInt z3_inv = m_curve.mul_to_tmp(z_inv, z2_inv, ws);
480  m_coord_x = m_curve.mul_to_tmp(m_coord_x, z2_inv, ws);
481  m_coord_y = m_curve.mul_to_tmp(m_coord_y, z3_inv, ws);
482  m_coord_z = 1;
483  m_curve.to_rep(m_coord_z, ws);
484  }
void to_rep(BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:126
BigInt invert_element(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:121
BigInt sqr_to_tmp(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:178
BigInt mul_to_tmp(const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:171
bool is_zero() const
Definition: point_gfp.h:172

◆ 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 409 of file point_gfp.cpp.

References force_affine(), Botan::CurveGFp::get_ws_size(), Botan::CurveGFp::invert_element(), Botan::CurveGFp::mul(), Botan::CurveGFp::mul_to_tmp(), Botan::CurveGFp::sqr(), and Botan::CurveGFp::to_rep().

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

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

◆ get_affine_x()

BigInt Botan::PointGFp::get_affine_x ( ) const

get affine x coordinate

Returns
affine x coordinate

Definition at line 491 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().

492  {
493  if(is_zero())
494  throw Illegal_Transformation("Cannot convert zero point to affine");
495 
496  secure_vector<word> monty_ws;
497 
498  if(is_affine())
499  return m_curve.from_rep(m_coord_x, monty_ws);
500 
501  BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
502  z2 = m_curve.invert_element(z2, monty_ws);
503 
504  BigInt r;
505  m_curve.mul(r, m_coord_x, z2, monty_ws);
506  m_curve.from_rep(r, monty_ws);
507  return r;
508  }
bool is_affine() const
Definition: point_gfp.cpp:486
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:145
void from_rep(BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:131
BigInt invert_element(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:121
BigInt sqr_to_tmp(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:178
bool is_zero() const
Definition: point_gfp.h:172

◆ get_affine_y()

BigInt Botan::PointGFp::get_affine_y ( ) const

get affine y coordinate

Returns
affine y coordinate

Definition at line 510 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().

511  {
512  if(is_zero())
513  throw Illegal_Transformation("Cannot convert zero point to affine");
514 
515  secure_vector<word> monty_ws;
516 
517  if(is_affine())
518  return m_curve.from_rep(m_coord_y, monty_ws);
519 
520  const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
521  const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws);
522  const BigInt z3_inv = m_curve.invert_element(z3, monty_ws);
523 
524  BigInt r;
525  m_curve.mul(r, m_coord_y, z3_inv, monty_ws);
526  m_curve.from_rep(r, monty_ws);
527  return r;
528  }
bool is_affine() const
Definition: point_gfp.cpp:486
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:145
void from_rep(BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:131
BigInt invert_element(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:121
BigInt sqr_to_tmp(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:178
BigInt mul_to_tmp(const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:171
bool is_zero() const
Definition: point_gfp.h:172

◆ 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 262 of file point_gfp.h.

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

262 { return m_curve; }

◆ get_x()

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

Definition at line 151 of file point_gfp.h.

151 { return m_coord_x; }

◆ get_y()

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

Definition at line 152 of file point_gfp.h.

152 { return m_coord_y; }

◆ get_z()

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

Definition at line 153 of file point_gfp.h.

153 { return m_coord_z; }

◆ is_affine()

bool Botan::PointGFp::is_affine ( ) const

Definition at line 486 of file point_gfp.cpp.

References Botan::CurveGFp::is_one().

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

487  {
488  return m_curve.is_one(m_coord_z);
489  }
bool is_one(const BigInt &x) const
Definition: curve_gfp.h:119

◆ 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 172 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().

173  { return (m_coord_x.is_zero() && m_coord_z.is_zero()); }
bool is_zero() const
Definition: bigint.h:314

◆ mult2()

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

Point doubling

Parameters
workspacetemp space, at least WORKSPACE_SIZE elements

Definition at line 288 of file point_gfp.cpp.

References Botan::CurveGFp::get_a_rep(), Botan::CurveGFp::get_p(), Botan::BigInt::get_word_vector(), Botan::CurveGFp::get_ws_size(), Botan::BigInt::is_negative(), is_zero(), Botan::BigInt::is_zero(), Botan::CurveGFp::mul(), PointGFp(), Botan::BigInt::reduce_below(), and Botan::CurveGFp::sqr().

Referenced by add(), add_affine(), Botan::PointGFp_Var_Point_Precompute::mul(), Botan::PointGFp_Multi_Point_Precompute::multi_exp(), Botan::operator*(), and Botan::PointGFp_Multi_Point_Precompute::PointGFp_Multi_Point_Precompute().

289  {
290  if(is_zero())
291  return;
292 
293  if(m_coord_y.is_zero())
294  {
295  *this = PointGFp(m_curve); // setting myself to zero
296  return;
297  }
298 
299  resize_ws(ws_bn, m_curve.get_ws_size());
300 
301  secure_vector<word>& ws = ws_bn[0].get_word_vector();
302  BigInt& T0 = ws_bn[1];
303  BigInt& T1 = ws_bn[2];
304  BigInt& T2 = ws_bn[6];
305  BigInt& T3 = ws_bn[4];
306  BigInt& T4 = ws_bn[5];
307 
308  /*
309  https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-1986-cc
310  */
311  const BigInt& p = m_curve.get_p();
312 
313  m_curve.sqr(T0, m_coord_y, ws);
314 
315  m_curve.mul(T1, m_coord_x, T0, ws);
316  T1 <<= 2; // * 4
317  T1.reduce_below(p, T3.get_word_vector());
318 
319  m_curve.sqr(T3, m_coord_z, ws); // z^2
320  m_curve.sqr(T4, T3, ws); // z^4
321  m_curve.mul(T3, m_curve.get_a_rep(), T4, ws);
322 
323  m_curve.sqr(T4, m_coord_x, ws);
324  T4 *= 3;
325  T4 += T3;
326  T4.reduce_below(p, T3.get_word_vector());
327 
328  m_curve.sqr(T2, T4, ws);
329  T2 -= T1;
330  T2 -= T1;
331  while(T2.is_negative())
332  T2 += p;
333 
334  m_curve.sqr(T3, T0, ws);
335  T3 <<= 3;
336  T3.reduce_below(p, T0.get_word_vector());
337 
338  T1 -= T2;
339  while(T1.is_negative())
340  T1 += p;
341 
342  m_curve.mul(T0, T4, T1, ws);
343  T0 -= T3;
344  if(T0.is_negative())
345  T0 += p;
346 
347  m_coord_x = T2;
348 
349  m_curve.mul(T2, m_coord_y, m_coord_z, ws);
350  T2 <<= 1;
351  T2.reduce_below(p, T3.get_word_vector());
352 
353  m_coord_y = T0;
354  m_coord_z = T2;
355  }
const BigInt & get_a_rep() const
Definition: curve_gfp.h:115
bool is_zero() const
Definition: bigint.h:314
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:145
size_t get_ws_size() const
Definition: curve_gfp.h:113
PointGFp()=default
bool is_zero() const
Definition: point_gfp.h:172
const BigInt & get_p() const
Definition: curve_gfp.h:109
void sqr(BigInt &z, const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:156

◆ negate()

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

Negate this point

Returns
*this

Definition at line 132 of file point_gfp.h.

References Botan::CT::is_zero().

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

133  {
134  if(!is_zero())
135  m_coord_y = m_curve.get_p() - m_coord_y;
136  return *this;
137  }
bool is_zero() const
Definition: point_gfp.h:172
const BigInt & get_p() const
Definition: curve_gfp.h:109

◆ 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 530 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::PointGFp_Var_Point_Precompute::mul(), Botan::operator*(), Botan::EC_Group::verify_group(), and Botan::EC_Group::verify_public_element().

531  {
532  /*
533  Is the point still on the curve?? (If everything is correct, the
534  point is always on its curve; then the function will return true.
535  If somehow the state is corrupted, which suggests a fault attack
536  (or internal computational error), then return false.
537  */
538  if(is_zero())
539  return true;
540 
541  secure_vector<word> monty_ws;
542 
543  const BigInt y2 = m_curve.from_rep(m_curve.sqr_to_tmp(m_coord_y, monty_ws), monty_ws);
544  const BigInt x3 = m_curve.mul_to_tmp(m_coord_x, m_curve.sqr_to_tmp(m_coord_x, monty_ws), monty_ws);
545  const BigInt ax = m_curve.mul_to_tmp(m_coord_x, m_curve.get_a_rep(), monty_ws);
546  const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
547 
548  if(m_coord_z == z2) // Is z equal to 1 (in Montgomery form)?
549  {
550  if(y2 != m_curve.from_rep(x3 + ax + m_curve.get_b_rep(), monty_ws))
551  return false;
552  }
553 
554  const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws);
555  const BigInt ax_z4 = m_curve.mul_to_tmp(ax, m_curve.sqr_to_tmp(z2, monty_ws), monty_ws);
556  const BigInt b_z6 = m_curve.mul_to_tmp(m_curve.get_b_rep(), m_curve.sqr_to_tmp(z3, monty_ws), monty_ws);
557 
558  if(y2 != m_curve.from_rep(x3 + ax_z4 + b_z6, monty_ws))
559  return false;
560 
561  return true;
562  }
const BigInt & get_a_rep() const
Definition: curve_gfp.h:115
const BigInt & get_b_rep() const
Definition: curve_gfp.h:117
void from_rep(BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:131
BigInt sqr_to_tmp(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:178
BigInt mul_to_tmp(const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:171
bool is_zero() const
Definition: point_gfp.h:172

◆ operator*=()

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

*= Operator

Parameters
scalarthe PointGFp to multiply with *this
Returns
resulting PointGFp

Definition at line 377 of file point_gfp.cpp.

378  {
379  *this = scalar * *this;
380  return *this;
381  }

◆ operator+=()

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

+= Operator

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

Definition at line 358 of file point_gfp.cpp.

References add(), and WORKSPACE_SIZE.

359  {
360  std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
361  add(rhs, ws);
362  return *this;
363  }
void add(const PointGFp &other, std::vector< BigInt > &workspace)
Definition: point_gfp.cpp:195

◆ operator-=()

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

-= Operator

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

Definition at line 365 of file point_gfp.cpp.

References is_zero(), and PointGFp().

366  {
367  PointGFp minus_rhs = PointGFp(rhs).negate();
368 
369  if(is_zero())
370  *this = minus_rhs;
371  else
372  *this += minus_rhs;
373 
374  return *this;
375  }
PointGFp()=default
bool is_zero() const
Definition: point_gfp.h:172

◆ 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 86 of file point_gfp.h.

87  {
88  if(this != &other)
89  this->swap(other);
90  return (*this);
91  }
void swap(PointGFp &other)
Definition: point_gfp.cpp:565

◆ operator==()

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

Equality operator

Definition at line 573 of file point_gfp.cpp.

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

574  {
575  if(m_curve != other.m_curve)
576  return false;
577 
578  // If this is zero, only equal if other is also zero
579  if(is_zero())
580  return other.is_zero();
581 
582  return (get_affine_x() == other.get_affine_x() &&
583  get_affine_y() == other.get_affine_y());
584  }
BigInt get_affine_x() const
Definition: point_gfp.cpp:491
BigInt get_affine_y() const
Definition: point_gfp.cpp:510
bool is_zero() const
Definition: point_gfp.h:172

◆ 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 244 of file point_gfp.h.

References add().

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

245  {
246  PointGFp x = (*this);
247  x.add(other, workspace);
248  return x;
249  }
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 46 of file point_gfp.cpp.

References Botan::CurveGFp::get_ws_size().

Referenced by Botan::PointGFp_Base_Point_Precompute::mul(), and Botan::PointGFp_Var_Point_Precompute::mul().

47  {
48  secure_vector<word> ws(m_curve.get_ws_size());
49  randomize_repr(rng, ws);
50  }
size_t get_ws_size() const
Definition: curve_gfp.h:113
void randomize_repr(RandomNumberGenerator &rng)
Definition: point_gfp.cpp:46

◆ 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 52 of file point_gfp.cpp.

References Botan::BigInt::is_zero(), Botan::CurveGFp::mul_to_tmp(), Botan::BigInt::randomize(), and Botan::CurveGFp::sqr_to_tmp().

53  {
54  if(BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS > 1)
55  {
56  BigInt mask;
57  while(mask.is_zero())
58  mask.randomize(rng, BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS, false);
59 
60  //m_curve.to_rep(mask, ws);
61  const BigInt mask2 = m_curve.sqr_to_tmp(mask, ws);
62  const BigInt mask3 = m_curve.mul_to_tmp(mask2, mask, ws);
63 
64  m_coord_x = m_curve.mul_to_tmp(m_coord_x, mask2, ws);
65  m_coord_y = m_curve.mul_to_tmp(m_coord_y, mask3, ws);
66  m_coord_z = m_curve.mul_to_tmp(m_coord_z, mask, ws);
67  }
68  }
BigInt sqr_to_tmp(const BigInt &x, secure_vector< word > &ws) const
Definition: curve_gfp.h:178
BigInt mul_to_tmp(const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: curve_gfp.h:171

◆ 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 565 of file point_gfp.cpp.

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

566  {
567  m_curve.swap(other.m_curve);
568  m_coord_x.swap(other.m_coord_x);
569  m_coord_y.swap(other.m_coord_y);
570  m_coord_z.swap(other.m_coord_z);
571  }
void swap(BigInt &other)
Definition: bigint.h:150
void swap(CurveGFp &other)
Definition: curve_gfp.h:185

◆ zero()

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

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

Definition at line 254 of file point_gfp.h.

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

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

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