Botan 3.9.0
Crypto and TLS for C&
Botan::EC_Point Class Referencefinal

#include <ec_point.h>

Public Types

enum  : uint8_t { WORKSPACE_SIZE = 8 }
typedef EC_Point_Format Compression_Type

Public Member Functions

bool _is_x_eq_to_v_mod_order (const BigInt &v) const
void add (const EC_Point &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 EC_Point &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)
EC_Point double_of (std::vector< BigInt > &workspace) const
 EC_Point ()=default
 EC_Point (const CurveGFp &curve)
 EC_Point (const CurveGFp &curve, BigInt x, BigInt y)
 EC_Point (const EC_Point &)=default
 EC_Point (EC_Point &&other) noexcept
std::vector< uint8_t > encode (EC_Point_Format 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
EC_Point mul (const BigInt &scalar) const
void mult2 (std::vector< BigInt > &workspace)
void mult2i (size_t i, std::vector< BigInt > &workspace)
EC_Pointnegate ()
bool on_the_curve () const
bool operator!= (const EC_Point &other) const =default
EC_Pointoperator*= (const BigInt &scalar)
EC_Pointoperator+= (const EC_Point &rhs)
EC_Pointoperator-= (const EC_Point &rhs)
EC_Pointoperator= (const EC_Point &)=default
EC_Pointoperator= (EC_Point &&other) noexcept
bool operator== (const EC_Point &other) const
EC_Point plus (const EC_Point &other, std::vector< BigInt > &workspace) const
void randomize_repr (RandomNumberGenerator &rng)
void randomize_repr (RandomNumberGenerator &rng, secure_vector< word > &ws)
void swap (EC_Point &other) noexcept
void swap_coords (BigInt &new_x, BigInt &new_y, BigInt &new_z)
secure_vector< uint8_t > x_bytes () const
secure_vector< uint8_t > xy_bytes () const
secure_vector< uint8_t > y_bytes () const
EC_Point zero () const
 ~EC_Point ()=default

Static Public Member Functions

static void force_all_affine (std::span< EC_Point > points, secure_vector< word > &ws)

Friends

class EC_Point_Base_Point_Precompute
class EC_Point_Multi_Point_Precompute
class EC_Point_Var_Point_Precompute
void swap (EC_Point &x, EC_Point &y) noexcept

Detailed Description

Deprecated elliptic curve type

Use EC_AffinePoint in new code; this type is no longer used internally at all except to support very unfortunate (and deprecated) curve types, specifically those with a cofactor, or with unreasonable sizes (above 521 bits), which cannot be accomodated by the new faster EC library in math/pcurves. For normal curves EC_AffinePoint will typically be 2 or 3 times faster.

This type will be completely removed in Botan4

Definition at line 33 of file ec_point.h.

Member Typedef Documentation

◆ Compression_Type

Definition at line 39 of file ec_point.h.

Member Enumeration Documentation

◆ anonymous enum

anonymous enum : uint8_t
Enumerator
WORKSPACE_SIZE 

Definition at line 42 of file ec_point.h.

42: uint8_t { WORKSPACE_SIZE = 8 };

Constructor & Destructor Documentation

◆ EC_Point() [1/5]

◆ EC_Point() [2/5]

Botan::EC_Point::EC_Point ( const CurveGFp & curve)
explicit

Construct the zero point

Parameters
curveThe base curve

Definition at line 108 of file ec_point.cpp.

108: m_curve(curve), m_x(0), m_y(curve.group().monty().R1()), m_z(0) {}

References EC_Point().

◆ EC_Point() [3/5]

Botan::EC_Point::EC_Point ( const EC_Point & )
default

Copy constructor

References EC_Point().

◆ EC_Point() [4/5]

Botan::EC_Point::EC_Point ( EC_Point && other)
inlinenoexcept

Move Constructor

Definition at line 63 of file ec_point.h.

63{ this->swap(other); }
void swap(EC_Point &other) noexcept
Definition ec_point.cpp:781

References EC_Point(), and swap().

◆ ~EC_Point()

Botan::EC_Point::~EC_Point ( )
default

References EC_Point(), encode(), and mul().

◆ EC_Point() [5/5]

Botan::EC_Point::EC_Point ( const CurveGFp & curve,
BigInt x,
BigInt y )

Construct a point from its affine coordinates

Parameters
curvethe base curve
xaffine x coordinate
yaffine y coordinate

Definition at line 114 of file ec_point.cpp.

114 :
115 m_curve(curve), m_x(std::move(x)), m_y(std::move(y)), m_z(m_curve.group().monty().R1()) {
116 const auto& group = m_curve.group();
117
118 if(m_x < 0 || m_x >= group.p()) {
119 throw Invalid_Argument("Invalid EC_Point affine x");
120 }
121 if(m_y < 0 || m_y >= group.p()) {
122 throw Invalid_Argument("Invalid EC_Point affine y");
123 }
124
125 secure_vector<word> monty_ws(monty_ws_size(group));
126
127 to_rep(group, m_x, monty_ws);
128 to_rep(group, m_y, monty_ws);
129}
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:69

Member Function Documentation

◆ _is_x_eq_to_v_mod_order()

bool Botan::EC_Point::_is_x_eq_to_v_mod_order ( const BigInt & v) const

For internal use only

Definition at line 714 of file ec_point.cpp.

714 {
715 if(this->is_zero()) {
716 return false;
717 }
718
719 const auto& group = m_curve.group();
720
721 /*
722 * The trick used below doesn't work for curves with cofactors
723 */
724 if(group.has_cofactor()) {
725 return group.mod_order().reduce(this->get_affine_x()) == v;
726 }
727
728 /*
729 * Note we're working with the projective coordinate directly here!
730 * Nominally we're comparing v with the affine x coordinate.
731 *
732 * return group.mod_order(this->get_affine_x()) == v;
733 *
734 * However by instead projecting r to an identical z as the x
735 * coordinate, we can compare without having to perform an
736 * expensive inversion in the field.
737 *
738 * That is, given (x*z2) and r, instead of checking if
739 * (x*z2)*z2^-1 == r,
740 * we check if
741 * (x*z2) == (r*z2)
742 */
744 BigInt vr = v;
745 to_rep(group, vr, ws);
746 BigInt z2;
747 BigInt v_z2;
748 fe_sqr(group, z2, this->get_z(), ws);
749 fe_mul(group, v_z2, vr, z2, ws);
750
751 /*
752 * Since (typically) the group order is slightly less than the size
753 * of the field elements, its possible the signer had to reduce the
754 * r component. If they did not reduce r, then this value is correct.
755 *
756 * Due to the Hasse bound, this case occurs almost always; the
757 * probability that a reduction was actually required is
758 * approximately 1 in 2^(n/2) where n is the bit length of the curve.
759 */
760 if(this->get_x() == v_z2) {
761 return true;
762 }
763
764 if(group.order_is_less_than_p()) {
765 vr = v + group.order();
766 if(vr < group.p()) {
767 to_rep(group, vr, ws);
768 fe_mul(group, v_z2, vr, z2, ws);
769
770 if(this->get_x() == v_z2) {
771 return true;
772 }
773 }
774 }
775
776 // Reject:
777 return false;
778}
BigInt get_affine_x() const
Definition ec_point.cpp:631
bool is_zero() const
Definition ec_point.h:164
const BigInt & get_z() const
Definition ec_point.h:253
const BigInt & get_x() const
Definition ec_point.h:239

References get_affine_x(), get_x(), get_z(), and is_zero().

Referenced by operator!=().

◆ add() [1/2]

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

Point addition

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

Definition at line 266 of file ec_point.cpp.

266 {
267 BOTAN_ARG_CHECK(m_curve == other.m_curve, "cannot add points on different curves");
268
269 const size_t p_words = m_curve.get_p_words();
270
271 add(other.m_x._data(),
272 std::min(p_words, other.m_x.size()),
273 other.m_y._data(),
274 std::min(p_words, other.m_y.size()),
275 other.m_z._data(),
276 std::min(p_words, other.m_z.size()),
277 workspace);
278}
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
void add(const EC_Point &other, std::vector< BigInt > &workspace)
Definition ec_point.cpp:266

References Botan::BigInt::_data(), add(), BOTAN_ARG_CHECK, EC_Point(), and Botan::BigInt::size().

Referenced by add(), mul(), Botan::EC_Point_Var_Point_Precompute::mul(), Botan::EC_Point_Multi_Point_Precompute::multi_exp(), operator+=(), and plus().

◆ add() [2/2]

void Botan::EC_Point::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 280 of file ec_point.cpp.

286 {
287 if((CT::all_zeros(x_words, x_size) & CT::all_zeros(z_words, z_size)).as_bool()) {
288 return;
289 }
290
291 const auto& group = m_curve.group();
292
293 if(is_zero()) {
294 m_x.set_words(x_words, x_size);
295 m_y.set_words(y_words, y_size);
296 m_z.set_words(z_words, z_size);
297 return;
298 }
299
300 resize_ws(ws_bn, monty_ws_size(group));
301
302 secure_vector<word>& ws = ws_bn[0].get_word_vector();
303 secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();
304
305 BigInt& T0 = ws_bn[2];
306 BigInt& T1 = ws_bn[3];
307 BigInt& T2 = ws_bn[4];
308 BigInt& T3 = ws_bn[5];
309 BigInt& T4 = ws_bn[6];
310 BigInt& T5 = ws_bn[7];
311
312 /*
313 https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
314 */
315
316 const BigInt& p = group.p();
317
318 fe_sqr(group, T0, z_words, z_size, ws); // z2^2
319 fe_mul(group, T1, m_x, T0, ws); // x1*z2^2
320 fe_mul(group, T3, z_words, z_size, T0, ws); // z2^3
321 fe_mul(group, T2, m_y, T3, ws); // y1*z2^3
322
323 fe_sqr(group, T3, m_z, ws); // z1^2
324 fe_mul(group, T4, x_words, x_size, T3, ws); // x2*z1^2
325
326 fe_mul(group, T5, m_z, T3, ws); // z1^3
327 fe_mul(group, T0, y_words, y_size, T5, ws); // y2*z1^3
328
329 T4.mod_sub(T1, p, sub_ws); // x2*z1^2 - x1*z2^2
330
331 T0.mod_sub(T2, p, sub_ws);
332
333 if(T4.is_zero()) {
334 if(T0.is_zero()) {
335 mult2(ws_bn);
336 return;
337 }
338
339 // setting to zero:
340 m_x.clear();
341 m_y = group.monty().R1();
342 m_z.clear();
343 return;
344 }
345
346 fe_sqr(group, T5, T4, ws);
347
348 fe_mul(group, T3, T1, T5, ws);
349
350 fe_mul(group, T1, T5, T4, ws);
351
352 fe_sqr(group, m_x, T0, ws);
353 m_x.mod_sub(T1, p, sub_ws);
354 m_x.mod_sub(T3, p, sub_ws);
355 m_x.mod_sub(T3, p, sub_ws);
356
357 T3.mod_sub(m_x, p, sub_ws);
358
359 fe_mul(group, m_y, T0, T3, ws);
360 fe_mul(group, T3, T2, T1, ws);
361
362 m_y.mod_sub(T3, p, sub_ws);
363
364 fe_mul(group, T3, z_words, z_size, m_z, ws);
365 fe_mul(group, m_z, T3, T4, ws);
366}
void mult2(std::vector< BigInt > &workspace)
Definition ec_point.cpp:388
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
Definition ct_utils.h:813

References Botan::CT::all_zeros(), Botan::BigInt::is_zero(), is_zero(), Botan::BigInt::mod_sub(), and mult2().

◆ add_affine() [1/2]

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

Point addition - mixed J+A

Warning
This function assumes that other is affine, if this is not correct the result will be invalid.
Parameters
otheraffine point to add - assumed to be affine!
workspacetemp space, at least WORKSPACE_SIZE elements

Definition at line 175 of file ec_point.cpp.

175 {
176 BOTAN_ASSERT_NOMSG(m_curve == other.m_curve);
177 BOTAN_DEBUG_ASSERT(other.is_affine());
178
179 const size_t p_words = m_curve.get_p_words();
180 add_affine(other.m_x._data(),
181 std::min(p_words, other.m_x.size()),
182 other.m_y._data(),
183 std::min(p_words, other.m_y.size()),
184 workspace);
185}
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:75
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:129
void add_affine(const EC_Point &other, std::vector< BigInt > &workspace)
Definition ec_point.cpp:175

References Botan::BigInt::_data(), add_affine(), BOTAN_ASSERT_NOMSG, BOTAN_DEBUG_ASSERT, EC_Point(), is_affine(), and Botan::BigInt::size().

Referenced by add_affine(), Botan::EC_Point_Base_Point_Precompute::mul(), and Botan::EC_Point_Multi_Point_Precompute::multi_exp().

◆ add_affine() [2/2]

void Botan::EC_Point::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 187 of file ec_point.cpp.

188 {
189 if((CT::all_zeros(x_words, x_size) & CT::all_zeros(y_words, y_size)).as_bool()) {
190 return;
191 }
192
193 const auto& group = m_curve.group();
194
195 if(is_zero()) {
196 m_x.set_words(x_words, x_size);
197 m_y.set_words(y_words, y_size);
198 m_z = group.monty().R1();
199 return;
200 }
201
202 resize_ws(ws_bn, monty_ws_size(group));
203
204 secure_vector<word>& ws = ws_bn[0].get_word_vector();
205 secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();
206
207 BigInt& T0 = ws_bn[2];
208 BigInt& T1 = ws_bn[3];
209 BigInt& T2 = ws_bn[4];
210 BigInt& T3 = ws_bn[5];
211 BigInt& T4 = ws_bn[6];
212
213 /*
214 https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
215 simplified with Z2 = 1
216 */
217
218 const BigInt& p = group.p();
219
220 fe_sqr(group, T3, m_z, ws); // z1^2
221 fe_mul(group, T4, x_words, x_size, T3, ws); // x2*z1^2
222
223 fe_mul(group, T2, m_z, T3, ws); // z1^3
224 fe_mul(group, T0, y_words, y_size, T2, ws); // y2*z1^3
225
226 T4.mod_sub(m_x, p, sub_ws); // x2*z1^2 - x1*z2^2
227
228 T0.mod_sub(m_y, p, sub_ws);
229
230 if(T4.is_zero()) {
231 if(T0.is_zero()) {
232 mult2(ws_bn);
233 return;
234 }
235
236 // setting to zero:
237 m_x.clear();
238 m_y = group.monty().R1();
239 m_z.clear();
240 return;
241 }
242
243 fe_sqr(group, T2, T4, ws);
244
245 fe_mul(group, T3, m_x, T2, ws);
246
247 fe_mul(group, T1, T2, T4, ws);
248
249 fe_sqr(group, m_x, T0, ws);
250 m_x.mod_sub(T1, p, sub_ws);
251
252 m_x.mod_sub(T3, p, sub_ws);
253 m_x.mod_sub(T3, p, sub_ws);
254
255 T3.mod_sub(m_x, p, sub_ws);
256
257 fe_mul(group, T2, T0, T3, ws);
258 fe_mul(group, T0, m_y, T1, ws);
259 T2.mod_sub(T0, p, sub_ws);
260 m_y.swap(T2);
261
262 fe_mul(group, T0, m_z, T4, ws);
263 m_z.swap(T0);
264}

References Botan::CT::all_zeros(), Botan::BigInt::is_zero(), is_zero(), Botan::BigInt::mod_sub(), mult2(), and Botan::BigInt::swap().

◆ double_of()

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

Point doubling

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

Definition at line 350 of file ec_point.h.

350 {
351 EC_Point x = (*this);
352 x.mult2(workspace);
353 return x;
354 }
EC_Point()=default

References EC_Point(), and mult2().

◆ encode()

std::vector< uint8_t > Botan::EC_Point::encode ( EC_Point_Format format) const

EC2OSP - elliptic curve to octet string primitive

Parameters
formatwhich format to encode using

Definition at line 802 of file ec_point.cpp.

802 {
803 if(is_zero()) {
804 return std::vector<uint8_t>(1); // single 0 byte
805 }
806
807 const size_t p_bytes = m_curve.group().p_bytes();
808
809 const BigInt x = get_affine_x();
810 const BigInt y = get_affine_y();
811
812 const size_t parts = (format == EC_Point_Format::Compressed) ? 1 : 2;
813
814 std::vector<uint8_t> result(1 + parts * p_bytes);
815 BufferStuffer stuffer(result);
816
817 if(format == EC_Point_Format::Uncompressed) {
818 stuffer.append(0x04);
819 x.serialize_to(stuffer.next(p_bytes));
820 y.serialize_to(stuffer.next(p_bytes));
821 } else if(format == EC_Point_Format::Compressed) {
822 stuffer.append(0x02 | static_cast<uint8_t>(y.get_bit(0)));
823 x.serialize_to(stuffer.next(p_bytes));
824 } else if(format == EC_Point_Format::Hybrid) {
825 stuffer.append(0x06 | static_cast<uint8_t>(y.get_bit(0)));
826 x.serialize_to(stuffer.next(p_bytes));
827 y.serialize_to(stuffer.next(p_bytes));
828 } else {
829 throw Invalid_Argument("EC2OSP illegal point encoding");
830 }
831
832 return result;
833}
BigInt get_affine_y() const
Definition ec_point.cpp:653

References Botan::BufferStuffer::append(), Botan::Compressed, get_affine_x(), get_affine_y(), Botan::BigInt::get_bit(), Botan::Hybrid, is_zero(), Botan::BufferStuffer::next(), Botan::BigInt::serialize_to(), and Botan::Uncompressed.

Referenced by ~EC_Point().

◆ force_affine()

void Botan::EC_Point::force_affine ( )

Force this point to affine coordinates

Convert the point to its equivalent affine coordinates. Throws if this is the point at infinity.

Definition at line 584 of file ec_point.cpp.

584 {
585 if(is_zero()) {
586 throw Invalid_State("Cannot convert zero ECC point to affine");
587 }
588
590
591 const auto& group = m_curve.group();
592
593 const BigInt z_inv = invert_element(group, m_z, ws);
594 const BigInt z2_inv = fe_sqr(group, z_inv, ws);
595 const BigInt z3_inv = fe_mul(group, z_inv, z2_inv, ws);
596 m_x = fe_mul(group, m_x, z2_inv, ws);
597 m_y = fe_mul(group, m_y, z3_inv, ws);
598 m_z = group.monty().R1();
599}

References is_zero().

◆ force_all_affine()

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

Force all points on the list to affine coordinates

Force several points to be affine at once. Uses Montgomery's trick to reduce number of inversions required, so this is much faster than calling force_affine on each point in sequence.

Definition at line 520 of file ec_point.cpp.

520 {
521 if(points.size() <= 1) {
522 for(auto& point : points) {
523 point.force_affine();
524 }
525 return;
526 }
527
528 for(auto& point : points) {
529 if(point.is_zero()) {
530 throw Invalid_State("Cannot convert zero ECC point to affine");
531 }
532 }
533
534 /*
535 For >= 2 points use Montgomery's trick
536
537 See Algorithm 2.26 in "Guide to Elliptic Curve Cryptography"
538 (Hankerson, Menezes, Vanstone)
539
540 TODO is it really necessary to save all k points in c?
541 */
542
543 const auto& group = points[0].m_curve.group();
544 const BigInt& rep_1 = group.monty().R1();
545
546 if(ws.size() < monty_ws_size(group)) {
547 ws.resize(monty_ws_size(group));
548 }
549
550 std::vector<BigInt> c(points.size());
551 c[0] = points[0].m_z;
552
553 for(size_t i = 1; i != points.size(); ++i) {
554 fe_mul(group, c[i], c[i - 1], points[i].m_z, ws);
555 }
556
557 BigInt s_inv = invert_element(group, c[c.size() - 1], ws);
558
559 BigInt z_inv;
560 BigInt z2_inv;
561 BigInt z3_inv;
562
563 for(size_t i = points.size() - 1; i != 0; i--) {
564 EC_Point& point = points[i];
565
566 fe_mul(group, z_inv, s_inv, c[i - 1], ws);
567
568 s_inv = fe_mul(group, s_inv, point.m_z, ws);
569
570 fe_sqr(group, z2_inv, z_inv, ws);
571 fe_mul(group, z3_inv, z2_inv, z_inv, ws);
572 point.m_x = fe_mul(group, point.m_x, z2_inv, ws);
573 point.m_y = fe_mul(group, point.m_y, z3_inv, ws);
574 point.m_z = rep_1;
575 }
576
577 fe_sqr(group, z2_inv, s_inv, ws);
578 fe_mul(group, z3_inv, z2_inv, s_inv, ws);
579 points[0].m_x = fe_mul(group, points[0].m_x, z2_inv, ws);
580 points[0].m_y = fe_mul(group, points[0].m_y, z3_inv, ws);
581 points[0].m_z = rep_1;
582}

References EC_Point().

Referenced by Botan::EC_Point_Base_Point_Precompute::EC_Point_Base_Point_Precompute(), and Botan::EC_Point_Multi_Point_Precompute::EC_Point_Multi_Point_Precompute().

◆ get_affine_x()

BigInt Botan::EC_Point::get_affine_x ( ) const

get affine x coordinate

Returns
affine x coordinate

Definition at line 631 of file ec_point.cpp.

631 {
632 if(is_zero()) {
633 throw Invalid_State("Cannot convert zero point to affine");
634 }
635
636 secure_vector<word> monty_ws;
637
638 const auto& group = m_curve.group();
639
640 if(is_affine()) {
641 return from_rep_to_tmp(group, m_x, monty_ws);
642 }
643
644 BigInt z2 = fe_sqr(group, m_z, monty_ws);
645 z2 = invert_element(group, z2, monty_ws);
646
647 BigInt r;
648 fe_mul(group, r, m_x, z2, monty_ws);
649 from_rep(group, r, monty_ws);
650 return r;
651}
bool is_affine() const
Definition ec_point.cpp:601

References is_affine(), and is_zero().

Referenced by _is_x_eq_to_v_mod_order(), encode(), operator==(), and xy_bytes().

◆ get_affine_y()

BigInt Botan::EC_Point::get_affine_y ( ) const

get affine y coordinate

Returns
affine y coordinate

Definition at line 653 of file ec_point.cpp.

653 {
654 if(is_zero()) {
655 throw Invalid_State("Cannot convert zero point to affine");
656 }
657
658 const auto& group = m_curve.group();
659 secure_vector<word> monty_ws;
660
661 if(is_affine()) {
662 return from_rep_to_tmp(group, m_y, monty_ws);
663 }
664
665 const BigInt z2 = fe_sqr(group, m_z, monty_ws);
666 const BigInt z3 = fe_mul(group, m_z, z2, monty_ws);
667 const BigInt z3_inv = invert_element(group, z3, monty_ws);
668
669 BigInt r;
670 fe_mul(group, r, m_y, z3_inv, monty_ws);
671 from_rep(group, r, monty_ws);
672 return r;
673}

References is_affine(), and is_zero().

Referenced by encode(), operator==(), and xy_bytes().

◆ get_curve()

const CurveGFp & Botan::EC_Point::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 362 of file ec_point.h.

362{ return m_curve; }

References get_curve().

Referenced by get_curve().

◆ get_x()

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

Return the internal x coordinate

Note this may be in Montgomery form

Definition at line 239 of file ec_point.h.

239{ return m_x; }

References get_x().

Referenced by _is_x_eq_to_v_mod_order(), and get_x().

◆ get_y()

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

Return the internal y coordinate

Note this may be in Montgomery form

Definition at line 246 of file ec_point.h.

246{ return m_y; }

References get_y().

Referenced by get_y().

◆ get_z()

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

Return the internal z coordinate

Note this may be in Montgomery form

Definition at line 253 of file ec_point.h.

253{ return m_z; }

References get_z().

Referenced by _is_x_eq_to_v_mod_order(), and get_z().

◆ is_affine()

bool Botan::EC_Point::is_affine ( ) const

Definition at line 601 of file ec_point.cpp.

601 {
602 const auto& group = m_curve.group();
603 return m_z == group.monty().R1();
604}

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

◆ is_zero()

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

Is this the point at infinity?

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

Definition at line 164 of file ec_point.h.

164{ return m_z.is_zero(); }

Referenced by _is_x_eq_to_v_mod_order(), add(), add_affine(), encode(), force_affine(), get_affine_x(), get_affine_y(), mult2(), negate(), on_the_curve(), operator-=(), and operator==().

◆ mul()

EC_Point Botan::EC_Point::mul ( const BigInt & scalar) const

Point multiplication operator

Simple unblinded Montgomery ladder

Warning: prefer the functions on EC_Group such as blinded_var_point_multiply

Parameters
scalarthe scalar value
Returns
*this multiplied by the scalar value

Definition at line 497 of file ec_point.cpp.

497 {
498 const size_t scalar_bits = scalar.bits();
499
500 std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE);
501
502 EC_Point R[2] = {this->zero(), *this};
503
504 for(size_t i = scalar_bits; i > 0; i--) {
505 const size_t b = scalar.get_bit(i - 1) ? 1 : 0;
506 R[b ^ 1].add(R[b], ws);
507 R[b].mult2(ws);
508 }
509
510 if(scalar.is_negative()) {
511 R[0].negate();
512 }
513
515
516 return R[0];
517}
bool on_the_curve() const
Definition ec_point.cpp:675
EC_Point zero() const
Definition ec_point.cpp:110

References add(), Botan::BigInt::bits(), BOTAN_DEBUG_ASSERT, EC_Point(), Botan::BigInt::get_bit(), Botan::BigInt::is_negative(), mult2(), negate(), on_the_curve(), WORKSPACE_SIZE, and zero().

Referenced by Botan::operator*(), Botan::operator*(), and ~EC_Point().

◆ mult2()

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

Point doubling

Parameters
workspacetemp space, at least WORKSPACE_SIZE elements

Definition at line 388 of file ec_point.cpp.

388 {
389 if(is_zero()) {
390 return;
391 }
392
393 const auto& group = m_curve.group();
394
395 if(m_y.is_zero()) {
396 *this = EC_Point(m_curve); // setting myself to zero
397 return;
398 }
399
400 resize_ws(ws_bn, monty_ws_size(group));
401
402 secure_vector<word>& ws = ws_bn[0].get_word_vector();
403 secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();
404
405 BigInt& T0 = ws_bn[2];
406 BigInt& T1 = ws_bn[3];
407 BigInt& T2 = ws_bn[4];
408 BigInt& T3 = ws_bn[5];
409 BigInt& T4 = ws_bn[6];
410
411 /*
412 https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-1986-cc
413 */
414 const BigInt& p = group.p();
415
416 fe_sqr(group, T0, m_y, ws);
417
418 fe_mul(group, T1, m_x, T0, ws);
419 fe_smul<4>(T1, p, sub_ws);
420
421 if(group.a_is_zero()) {
422 // if a == 0 then 3*x^2 + a*z^4 is just 3*x^2
423 fe_sqr(group, T4, m_x, ws); // x^2
424 fe_smul<3>(T4, p, sub_ws); // 3*x^2
425 } else if(group.a_is_minus_3()) {
426 /*
427 if a == -3 then
428 3*x^2 + a*z^4 == 3*x^2 - 3*z^4 == 3*(x^2-z^4) == 3*(x-z^2)*(x+z^2)
429 */
430 fe_sqr(group, T3, m_z, ws); // z^2
431
432 // (x-z^2)
433 T2 = m_x;
434 T2.mod_sub(T3, p, sub_ws);
435
436 // (x+z^2)
437 T3.mod_add(m_x, p, sub_ws);
438
439 fe_mul(group, T4, T2, T3, ws); // (x-z^2)*(x+z^2)
440
441 fe_smul<3>(T4, p, sub_ws); // 3*(x-z^2)*(x+z^2)
442 } else {
443 fe_sqr(group, T3, m_z, ws); // z^2
444 fe_sqr(group, T4, T3, ws); // z^4
445 fe_mul(group, T3, group.monty_a(), T4, ws); // a*z^4
446
447 fe_sqr(group, T4, m_x, ws); // x^2
448 fe_smul<3>(T4, p, sub_ws);
449 T4.mod_add(T3, p, sub_ws); // 3*x^2 + a*z^4
450 }
451
452 fe_sqr(group, T2, T4, ws);
453 T2.mod_sub(T1, p, sub_ws);
454 T2.mod_sub(T1, p, sub_ws);
455
456 fe_sqr(group, T3, T0, ws);
457 fe_smul<8>(T3, p, sub_ws);
458
459 T1.mod_sub(T2, p, sub_ws);
460
461 fe_mul(group, T0, T4, T1, ws);
462 T0.mod_sub(T3, p, sub_ws);
463
464 m_x.swap(T2);
465
466 fe_mul(group, T2, m_y, m_z, ws);
467 fe_smul<2>(T2, p, sub_ws);
468
469 m_y.swap(T0);
470 m_z.swap(T2);
471}

References EC_Point(), is_zero(), Botan::BigInt::mod_add(), Botan::BigInt::mod_sub(), and Botan::BigInt::swap().

Referenced by add(), add_affine(), double_of(), Botan::EC_Point_Base_Point_Precompute::EC_Point_Base_Point_Precompute(), Botan::EC_Point_Multi_Point_Precompute::EC_Point_Multi_Point_Precompute(), mul(), and mult2i().

◆ mult2i()

void Botan::EC_Point::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 368 of file ec_point.cpp.

368 {
369 if(iterations == 0) {
370 return;
371 }
372
373 if(m_y.is_zero()) {
374 *this = EC_Point(m_curve); // setting myself to zero
375 return;
376 }
377
378 /*
379 TODO we can save 2 squarings per iteration by computing
380 a*Z^4 using values cached from previous iteration
381 */
382 for(size_t i = 0; i != iterations; ++i) {
383 mult2(ws_bn);
384 }
385}

References EC_Point(), and mult2().

Referenced by Botan::EC_Point_Var_Point_Precompute::mul(), and Botan::EC_Point_Multi_Point_Precompute::multi_exp().

◆ negate()

EC_Point & Botan::EC_Point::negate ( )
inline

Negate this point

Returns
*this

Definition at line 134 of file ec_point.h.

134 {
135 if(!is_zero()) {
136 m_y = m_curve.get_p() - m_y;
137 }
138 return *this;
139 }

References EC_Point(), is_zero(), and negate().

Referenced by mul(), Botan::EC_Point_Multi_Point_Precompute::multi_exp(), negate(), and Botan::operator-().

◆ on_the_curve()

bool Botan::EC_Point::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 675 of file ec_point.cpp.

675 {
676 /*
677 Is the point still on the curve?? (If everything is correct, the
678 point is always on its curve; then the function will return true.
679 If somehow the state is corrupted, which suggests a fault attack
680 (or internal computational error), then return false.
681 */
682 if(is_zero()) {
683 return true;
684 }
685
686 const auto& group = m_curve.group();
687 secure_vector<word> monty_ws;
688
689 const BigInt y2 = from_rep_to_tmp(group, fe_sqr(group, m_y, monty_ws), monty_ws);
690 const BigInt x3 = fe_mul(group, m_x, fe_sqr(group, m_x, monty_ws), monty_ws);
691 const BigInt ax = fe_mul(group, m_x, group.monty_a(), monty_ws);
692 const BigInt z2 = fe_sqr(group, m_z, monty_ws);
693
694 const BigInt& monty_b = group.monty_b();
695
696 // Is z equal to 1 (in Montgomery form)?
697 if(m_z == z2) {
698 if(y2 != from_rep_to_tmp(group, x3 + ax + monty_b, monty_ws)) {
699 return false;
700 }
701 }
702
703 const BigInt z3 = fe_mul(group, m_z, z2, monty_ws);
704 const BigInt ax_z4 = fe_mul(group, ax, fe_sqr(group, z2, monty_ws), monty_ws);
705 const BigInt b_z6 = fe_mul(group, monty_b, fe_sqr(group, z3, monty_ws), monty_ws);
706
707 if(y2 != from_rep_to_tmp(group, x3 + ax_z4 + b_z6, monty_ws)) {
708 return false;
709 }
710
711 return true;
712}

References is_zero().

Referenced by Botan::EC_Point_Multi_Point_Precompute::EC_Point_Multi_Point_Precompute(), mul(), Botan::EC_Point_Base_Point_Precompute::mul(), Botan::EC_Point_Var_Point_Precompute::mul(), Botan::OS2ECP(), and Botan::EC_Group::verify_group().

◆ operator!=()

bool Botan::EC_Point::operator!= ( const EC_Point & other) const
default

◆ operator*=()

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

*= Operator

Parameters
scalarthe EC_Point to multiply with *this
Returns
resulting EC_Point

Definition at line 492 of file ec_point.cpp.

492 {
493 *this = scalar * *this;
494 return *this;
495}

References EC_Point().

◆ operator+=()

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

+= Operator

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

Definition at line 474 of file ec_point.cpp.

474 {
475 std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE);
476 add(rhs, ws);
477 return *this;
478}

References add(), EC_Point(), and WORKSPACE_SIZE.

◆ operator-=()

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

-= Operator

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

Definition at line 480 of file ec_point.cpp.

480 {
481 EC_Point minus_rhs = EC_Point(rhs).negate();
482
483 if(is_zero()) {
484 *this = minus_rhs;
485 } else {
486 *this += minus_rhs;
487 }
488
489 return *this;
490}

References EC_Point(), and is_zero().

◆ operator=() [1/2]

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

Standard Assignment

References EC_Point().

◆ operator=() [2/2]

EC_Point & Botan::EC_Point::operator= ( EC_Point && other)
inlinenoexcept

Move Assignment

Definition at line 73 of file ec_point.h.

73 {
74 if(this != &other) {
75 this->swap(other);
76 }
77 return (*this);
78 }

References EC_Point(), and swap().

◆ operator==()

bool Botan::EC_Point::operator== ( const EC_Point & other) const

Equality operator

Definition at line 788 of file ec_point.cpp.

788 {
789 if(m_curve != other.m_curve) {
790 return false;
791 }
792
793 // If this is zero, only equal if other is also zero
794 if(is_zero()) {
795 return other.is_zero();
796 }
797
798 return (get_affine_x() == other.get_affine_x() && get_affine_y() == other.get_affine_y());
799}

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

◆ plus()

EC_Point Botan::EC_Point::plus ( const EC_Point & 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 339 of file ec_point.h.

339 {
340 EC_Point x = (*this);
341 x.add(other, workspace);
342 return x;
343 }

References add(), and EC_Point().

Referenced by Botan::EC_Point_Base_Point_Precompute::EC_Point_Base_Point_Precompute(), and Botan::EC_Point_Multi_Point_Precompute::EC_Point_Multi_Point_Precompute().

◆ randomize_repr() [1/2]

void Botan::EC_Point::randomize_repr ( RandomNumberGenerator & rng)

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

Definition at line 131 of file ec_point.cpp.

131 {
132 const auto& group = m_curve.group();
133 secure_vector<word> ws(monty_ws_size(group));
134 randomize_repr(rng, ws);
135}
void randomize_repr(RandomNumberGenerator &rng)
Definition ec_point.cpp:131

References randomize_repr().

Referenced by Botan::EC_Point_Var_Point_Precompute::EC_Point_Var_Point_Precompute(), Botan::EC_Point_Base_Point_Precompute::mul(), Botan::EC_Point_Var_Point_Precompute::mul(), and randomize_repr().

◆ randomize_repr() [2/2]

void Botan::EC_Point::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 137 of file ec_point.cpp.

137 {
138 if(!rng.is_seeded()) {
139 return;
140 }
141
142 const auto& group = m_curve.group();
143
144 const BigInt mask = BigInt::random_integer(rng, BigInt::from_s32(2), group.p());
145
146 /*
147 * No reason to convert this to Montgomery representation first,
148 * just pretend the random mask was chosen as Redc(mask) and the
149 * random mask we generated above is in the Montgomery
150 * representation.
151 */
152
153 const BigInt mask2 = fe_sqr(group, mask, ws);
154 const BigInt mask3 = fe_mul(group, mask2, mask, ws);
155
156 m_x = fe_mul(group, m_x, mask2, ws);
157 m_y = fe_mul(group, m_y, mask3, ws);
158 m_z = fe_mul(group, m_z, mask, ws);
159}
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
Definition big_rand.cpp:43
static BigInt from_s32(int32_t n)
Definition bigint.cpp:41

References Botan::BigInt::from_s32(), Botan::RandomNumberGenerator::is_seeded(), and Botan::BigInt::random_integer().

◆ swap()

void Botan::EC_Point::swap ( EC_Point & other)
noexcept

swaps the states of *this and other

Parameters
otherthe object to swap values with

Definition at line 781 of file ec_point.cpp.

781 {
782 m_curve.swap(other.m_curve);
783 m_x.swap(other.m_x);
784 m_y.swap(other.m_y);
785 m_z.swap(other.m_z);
786}

References EC_Point().

Referenced by EC_Point(), Botan::EC_Point_Base_Point_Precompute::EC_Point_Base_Point_Precompute(), operator!=(), and operator=().

◆ swap_coords()

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

Definition at line 257 of file ec_point.h.

257 {
258 m_x.swap(new_x);
259 m_y.swap(new_y);
260 m_z.swap(new_z);
261 }

References swap_coords().

Referenced by swap_coords().

◆ x_bytes()

secure_vector< uint8_t > Botan::EC_Point::x_bytes ( ) const

Return the fixed length big endian encoding of x coordinate

Definition at line 606 of file ec_point.cpp.

606 {
607 const auto& group = m_curve.group();
608 const size_t p_bytes = group.p_bytes();
609 secure_vector<uint8_t> b(p_bytes);
610 BigInt::encode_1363(b.data(), b.size(), this->get_affine_x());
611 return b;
612}
static secure_vector< uint8_t > encode_1363(const BigInt &n, size_t bytes)
Definition bigint.h:895

References Botan::BigInt::encode_1363().

◆ xy_bytes()

secure_vector< uint8_t > Botan::EC_Point::xy_bytes ( ) const

Return the fixed length concatenation of the x and y coordinates

Definition at line 622 of file ec_point.cpp.

622 {
623 const auto& group = m_curve.group();
624 const size_t p_bytes = group.p_bytes();
625 secure_vector<uint8_t> b(2 * p_bytes);
626 BigInt::encode_1363(&b[0], p_bytes, this->get_affine_x()); // NOLINT(*container-data-pointer)
627 BigInt::encode_1363(&b[p_bytes], p_bytes, this->get_affine_y());
628 return b;
629}

References Botan::BigInt::encode_1363(), get_affine_x(), and get_affine_y().

◆ y_bytes()

secure_vector< uint8_t > Botan::EC_Point::y_bytes ( ) const

Return the fixed length big endian encoding of y coordinate

Definition at line 614 of file ec_point.cpp.

614 {
615 const auto& group = m_curve.group();
616 const size_t p_bytes = group.p_bytes();
617 secure_vector<uint8_t> b(p_bytes);
618 BigInt::encode_1363(b.data(), b.size(), this->get_affine_y());
619 return b;
620}

References Botan::BigInt::encode_1363().

◆ zero()

EC_Point Botan::EC_Point::zero ( ) const

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

Definition at line 110 of file ec_point.cpp.

110 {
111 return EC_Point(m_curve);
112}

References EC_Point().

Referenced by Botan::EC_Point_Multi_Point_Precompute::EC_Point_Multi_Point_Precompute(), mul(), Botan::EC_Point_Base_Point_Precompute::mul(), and Botan::EC_Point_Multi_Point_Precompute::multi_exp().

◆ EC_Point_Base_Point_Precompute

friend class EC_Point_Base_Point_Precompute
friend

Definition at line 37 of file ec_point.h.

References EC_Point_Base_Point_Precompute.

Referenced by EC_Point_Base_Point_Precompute.

◆ EC_Point_Multi_Point_Precompute

friend class EC_Point_Multi_Point_Precompute
friend

Definition at line 36 of file ec_point.h.

References EC_Point_Multi_Point_Precompute.

Referenced by EC_Point_Multi_Point_Precompute.

◆ EC_Point_Var_Point_Precompute

friend class EC_Point_Var_Point_Precompute
friend

Definition at line 35 of file ec_point.h.

References EC_Point_Var_Point_Precompute.

Referenced by EC_Point_Var_Point_Precompute.

◆ swap

void swap ( EC_Point & x,
EC_Point & y )
friend

Definition at line 263 of file ec_point.h.

263{ x.swap(y); }

References EC_Point().


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