Botan  1.10.9
Public Types | Public Member Functions | Friends | List of all members
Botan::PointGFp Class Reference

#include <point_gfp.h>

Public Types

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

Public Member Functions

BigInt get_affine_x () const
 
BigInt get_affine_y () const
 
const CurveGFpget_curve () const
 
bool is_zero () const
 
PointGFpnegate ()
 
bool on_the_curve () const
 
PointGFpoperator*= (const BigInt &scalar)
 
PointGFpoperator+= (const PointGFp &rhs)
 
PointGFpoperator-= (const PointGFp &rhs)
 
bool operator== (const PointGFp &other) const
 
 PointGFp ()
 
 PointGFp (const CurveGFp &curve)
 
 PointGFp (const CurveGFp &curve, const BigInt &x, const BigInt &y)
 
void swap (PointGFp &other)
 

Friends

BOTAN_DLL PointGFp multi_exponentiate (const PointGFp &p1, const BigInt &z1, const PointGFp &p2, const BigInt &z2)
 
BOTAN_DLL PointGFp operator* (const BigInt &scalar, const PointGFp &point)
 

Detailed Description

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

Definition at line 41 of file point_gfp.h.

Member Enumeration Documentation

Enumerator
UNCOMPRESSED 
COMPRESSED 
HYBRID 

Definition at line 44 of file point_gfp.h.

Constructor & Destructor Documentation

Botan::PointGFp::PointGFp ( )
inline

Construct an uninitialized PointGFp

Definition at line 53 of file point_gfp.h.

Referenced by operator-=().

53 {}
Botan::PointGFp::PointGFp ( const CurveGFp curve)

Construct the zero point

Parameters
curveThe base curve

Definition at line 17 of file point_gfp.cpp.

References Botan::CurveGFp::get_r2().

17  :
18  curve(curve), ws(2 * (curve.get_p_words() + 2))
19  {
20  coord_x = 0;
21  coord_y = monty_mult(1, curve.get_r2());
22  coord_z = 0;
23  }
size_t get_p_words() const
Definition: curve_gfp.h:89
const BigInt & get_r2() const
Definition: curve_gfp.h:69
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 25 of file point_gfp.cpp.

References Botan::CurveGFp::get_r2().

25  :
26  curve(curve), ws(2 * (curve.get_p_words() + 2))
27  {
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());
31  }
size_t get_p_words() const
Definition: curve_gfp.h:89
const BigInt & get_r2() const
Definition: curve_gfp.h:69

Member Function Documentation

BigInt Botan::PointGFp::get_affine_x ( ) const

get affine x coordinate

Returns
affine x coordinate

Definition at line 392 of file point_gfp.cpp.

References Botan::CurveGFp::get_p(), Botan::CurveGFp::get_r2(), Botan::inverse_mod(), and is_zero().

Referenced by Botan::ECDH_KA_Operation::agree(), Botan::EC2OSP(), operator==(), Botan::ECDSA_Signature_Operation::sign(), Botan::GOST_3410_Signature_Operation::sign(), Botan::ECDSA_Verification_Operation::verify(), Botan::GOST_3410_Verification_Operation::verify(), and Botan::GOST_3410_PublicKey::x509_subject_public_key().

393  {
394  if(is_zero())
395  throw Illegal_Transformation("Cannot convert zero point to affine");
396 
397  const BigInt& r2 = curve.get_r2();
398 
399  BigInt z2 = monty_sqr(coord_z);
400  z2 = inverse_mod(z2, curve.get_p());
401 
402  z2 = monty_mult(z2, r2);
403  return monty_mult(coord_x, z2);
404  }
const BigInt & get_r2() const
Definition: curve_gfp.h:69
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:202
const BigInt & get_p() const
Definition: curve_gfp.h:64
bool is_zero() const
Definition: point_gfp.h:146
BigInt Botan::PointGFp::get_affine_y ( ) const

get affine y coordinate

Returns
affine y coordinate

Definition at line 406 of file point_gfp.cpp.

References Botan::CurveGFp::get_p(), Botan::CurveGFp::get_r2(), Botan::inverse_mod(), and is_zero().

Referenced by Botan::EC2OSP(), operator==(), and Botan::GOST_3410_PublicKey::x509_subject_public_key().

407  {
408  if(is_zero())
409  throw Illegal_Transformation("Cannot convert zero point to affine");
410 
411  const BigInt& r2 = curve.get_r2();
412 
413  BigInt z3 = monty_mult(coord_z, monty_sqr(coord_z));
414  z3 = inverse_mod(z3, curve.get_p());
415  z3 = monty_mult(z3, r2);
416  return monty_mult(coord_y, z3);
417  }
const BigInt & get_r2() const
Definition: curve_gfp.h:69
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:202
const BigInt & get_p() const
Definition: curve_gfp.h:64
bool is_zero() const
Definition: point_gfp.h:146
const CurveGFp& Botan::PointGFp::get_curve ( ) const
inline

Return base curve of this point

Returns
the curve over GF(p) of this point

Definition at line 128 of file point_gfp.h.

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

128 { return curve; }
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 146 of file point_gfp.h.

Referenced by Botan::EC2OSP(), get_affine_x(), get_affine_y(), on_the_curve(), operator-=(), operator==(), Botan::ECDSA_Verification_Operation::verify(), and Botan::GOST_3410_Verification_Operation::verify().

147  { return (coord_x.is_zero() && coord_z.is_zero()); }
bool is_zero() const
Definition: bigint.h:176
PointGFp& Botan::PointGFp::negate ( )
inline

Negate this point

Returns
*this

Definition at line 117 of file point_gfp.h.

Referenced by Botan::multi_exponentiate(), Botan::operator*(), and Botan::operator-().

118  {
119  if(!is_zero())
120  coord_y = curve.get_p() - coord_y;
121  return *this;
122  }
const BigInt & get_p() const
Definition: curve_gfp.h:64
bool is_zero() const
Definition: point_gfp.h:146
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 419 of file point_gfp.cpp.

References Botan::CurveGFp::get_a_r(), Botan::CurveGFp::get_b_r(), and is_zero().

Referenced by Botan::ECDH_KA_Operation::agree(), Botan::EC_PublicKey::check_key(), Botan::EC_PrivateKey::EC_PrivateKey(), Botan::GOST_3410_PublicKey::GOST_3410_PublicKey(), Botan::OS2ECP(), and Botan::GOST_3410_Signature_Operation::sign().

420  {
421  /*
422  Is the point still on the curve?? (If everything is correct, the
423  point is always on its curve; then the function will return true.
424  If somehow the state is corrupted, which suggests a fault attack
425  (or internal computational error), then return false.
426  */
427 
428  if(is_zero())
429  return true;
430 
431  BigInt y2 = monty_mult(monty_sqr(coord_y), 1);
432  BigInt x3 = monty_mult(coord_x, monty_sqr(coord_x));
433 
434  BigInt ax = monty_mult(coord_x, curve.get_a_r());
435 
436  const BigInt& b_r = curve.get_b_r();
437 
438  BigInt z2 = monty_sqr(coord_z);
439 
440  if(coord_z == z2) // Is z equal to 1 (in Montgomery form)?
441  {
442  if(y2 != monty_mult(x3 + ax + b_r, 1))
443  return false;
444  }
445 
446  BigInt z3 = monty_mult(coord_z, z2);
447 
448  BigInt ax_z4 = monty_mult(ax, monty_sqr(z2));
449 
450  BigInt b_z6 = monty_mult(b_r, monty_sqr(z3));
451 
452  if(y2 != monty_mult(x3 + ax_z4 + b_z6, 1))
453  return false;
454 
455  return true;
456  }
const BigInt & get_b_r() const
Definition: curve_gfp.h:79
const BigInt & get_a_r() const
Definition: curve_gfp.h:74
bool is_zero() const
Definition: point_gfp.h:146
PointGFp & Botan::PointGFp::operator*= ( const BigInt scalar)

*= Operator

Parameters
scalarthe PointGFp to multiply with *this
Returns
resulting PointGFp

Definition at line 251 of file point_gfp.cpp.

252  {
253  *this = scalar * *this;
254  return *this;
255  }
PointGFp & Botan::PointGFp::operator+= ( const PointGFp rhs)

+= Operator

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

Definition at line 232 of file point_gfp.cpp.

233  {
234  std::vector<BigInt> ws(9);
235  add(rhs, ws);
236  return *this;
237  }
PointGFp & Botan::PointGFp::operator-= ( const PointGFp rhs)

-= Operator

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

Definition at line 239 of file point_gfp.cpp.

References is_zero(), and PointGFp().

240  {
241  PointGFp minus_rhs = PointGFp(rhs).negate();
242 
243  if(is_zero())
244  *this = minus_rhs;
245  else
246  *this += minus_rhs;
247 
248  return *this;
249  }
bool is_zero() const
Definition: point_gfp.h:146
bool Botan::PointGFp::operator== ( const PointGFp other) const

Equality operator

Definition at line 468 of file point_gfp.cpp.

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

469  {
470  if(get_curve() != other.get_curve())
471  return false;
472 
473  // If this is zero, only equal if other is also zero
474  if(is_zero())
475  return other.is_zero();
476 
477  return (get_affine_x() == other.get_affine_x() &&
478  get_affine_y() == other.get_affine_y());
479  }
BigInt get_affine_y() const
Definition: point_gfp.cpp:406
const CurveGFp & get_curve() const
Definition: point_gfp.h:128
BigInt get_affine_x() const
Definition: point_gfp.cpp:392
bool is_zero() const
Definition: point_gfp.h:146
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 459 of file point_gfp.cpp.

References Botan::CurveGFp::swap(), Botan::MemoryRegion< T >::swap(), and Botan::BigInt::swap().

460  {
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);
465  ws.swap(other.ws);
466  }
void swap(BigInt &other)
Definition: bigint.cpp:106
void swap(CurveGFp &other)
Definition: curve_gfp.h:95
void swap(MemoryRegion< T > &other)
Definition: secmem.h:254

Friends And Related Function Documentation

BOTAN_DLL PointGFp multi_exponentiate ( const PointGFp p1,
const BigInt z1,
const PointGFp p2,
const BigInt z2 
)
friend

Multiexponentiation

Parameters
p1a point
z1a scalar
p2a point
z2a scalar
Returns
(p1 * z1 + p2 * z2)

Definition at line 257 of file point_gfp.cpp.

259  {
260  const PointGFp p3 = p1 + p2;
261 
262  PointGFp H(p1.curve); // create as zero
263  size_t bits_left = std::max(z1.bits(), z2.bits());
264 
265  std::vector<BigInt> ws(9);
266 
267  while(bits_left)
268  {
269  H.mult2(ws);
270 
271  const bool z1_b = z1.get_bit(bits_left - 1);
272  const bool z2_b = z2.get_bit(bits_left - 1);
273 
274  if(z1_b == true && z2_b == true)
275  H.add(p3, ws);
276  else if(z1_b)
277  H.add(p1, ws);
278  else if(z2_b)
279  H.add(p2, ws);
280 
281  --bits_left;
282  }
283 
284  if(z1.is_negative() != z2.is_negative())
285  H.negate();
286 
287  return H;
288  }
BOTAN_DLL PointGFp operator* ( const BigInt scalar,
const PointGFp point 
)
friend

Multiplication Operator

Parameters
scalarthe scalar value
pointthe point value
Returns
scalar*point on the curve

Definition at line 290 of file point_gfp.cpp.

291  {
292  const CurveGFp& curve = point.get_curve();
293 
294  if(scalar.is_zero())
295  return PointGFp(curve); // zero point
296 
297  std::vector<BigInt> ws(9);
298 
299  if(scalar.abs() <= 2) // special cases for small values
300  {
301  byte value = scalar.abs().byte_at(0);
302 
303  PointGFp result = point;
304 
305  if(value == 2)
306  result.mult2(ws);
307 
308  if(scalar.is_negative())
309  result.negate();
310 
311  return result;
312  }
313 
314  const size_t scalar_bits = scalar.bits();
315 
316 #if 0
317 
318  PointGFp x1 = PointGFp(curve);
319  PointGFp x2 = point;
320 
321  size_t bits_left = scalar_bits;
322 
323  // Montgomery Ladder
324  while(bits_left)
325  {
326  const bool bit_set = scalar.get_bit(bits_left - 1);
327 
328  if(bit_set)
329  {
330  x1.add(x2, ws);
331  x2.mult2(ws);
332  }
333  else
334  {
335  x2.add(x1, ws);
336  x1.mult2(ws);
337  }
338 
339  --bits_left;
340  }
341 
342  if(scalar.is_negative())
343  x1.negate();
344 
345  return x1;
346 
347 #else
348  const size_t window_size = 4;
349 
350  std::vector<PointGFp> Ps(1 << window_size);
351  Ps[0] = PointGFp(curve);
352  Ps[1] = point;
353 
354  for(size_t i = 2; i != Ps.size(); ++i)
355  {
356  Ps[i] = Ps[i-1];
357  Ps[i].add(point, ws);
358  }
359 
360  PointGFp H(curve); // create as zero
361  size_t bits_left = scalar_bits;
362 
363  while(bits_left >= window_size)
364  {
365  for(size_t i = 0; i != window_size; ++i)
366  H.mult2(ws);
367 
368  const u32bit nibble = scalar.get_substring(bits_left - window_size,
369  window_size);
370 
371  H.add(Ps[nibble], ws);
372 
373  bits_left -= window_size;
374  }
375 
376  while(bits_left)
377  {
378  H.mult2(ws);
379  if(scalar.get_bit(bits_left-1))
380  H.add(point, ws);
381 
382  --bits_left;
383  }
384 
385  if(scalar.is_negative())
386  H.negate();
387 
388  return H;
389 #endif
390  }
unsigned char byte
Definition: types.h:22
unsigned int u32bit
Definition: types.h:32

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