Botan 3.14.1
Crypto and TLS for C&
pcurves_impl.h
Go to the documentation of this file.
1/*
2* (C) 2024,2025,2026 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#ifndef BOTAN_PCURVES_IMPL_H_
8#define BOTAN_PCURVES_IMPL_H_
9
10#include <botan/rng.h>
11#include <botan/internal/buffer_stuffer.h>
12#include <botan/internal/ct_utils.h>
13#include <botan/internal/loadstor.h>
14#include <botan/internal/mem_utils.h>
15#include <botan/internal/pcurves_algos.h>
16#include <botan/internal/pcurves_mul.h>
17#include <botan/internal/pcurves_util.h>
18#include <botan/internal/target_info.h>
19#include <concepts>
20#include <utility>
21#include <vector>
22
23namespace Botan {
24
25/*
26 * @brief Helper class to pass literal strings to C++ templates
27 *
28 * This is a generic utility so it may make sense to move this into utils
29 * if someday such functionality is useful outside of pcurves.
30 */
31template <size_t N>
32class StringLiteral final {
33 public:
34 // NOLINTNEXTLINE(*-explicit-conversions,*-explicit-constructor)
35 consteval StringLiteral(const char (&str)[N]) : value() {
36 for(size_t i = 0; i != N; ++i) {
37 value[i] = str[i];
38 }
39 }
40
41 // NOLINTNEXTLINE(*non-private-member-variable*)
42 char value[N];
43};
44
45/*
46This file implements a system for compile-time instantiation of elliptic curve arithmetic.
47
48All computations including point multiplication are implemented to be constant time,
49with the exception of any function which includes "vartime" or equivalent in its
50name. Randomization techniques (scalar blinding, point rerandomization) are also
51used, largely to guard against situations where a compiler inserts a conditional jump
52where not expected.
53
54A specific elliptic curve is created by creating a set of EllipticCurveParameters,
55which are templatized over the relevant constants (p, a, b, etc) and then
56passing that set of parameters to an EllipticCurve template.
57
58For a simple example of how these are used see pcurves_brainpool256r1.cpp
59
60The system also includes various hooks which allow for specialized representations of
61field elements (for curves where a modular reduction technique faster than Montgomery
62is available) and to provide pre-computed addition chains for field and scalar
63inversions. See pcurves_secp256r1.cpp or pcurves_secp256k1.cpp for examples with all
64the bells and whistles.
65*/
66
67/**
68* Montomgomery Representation of Integers
69*
70* Integers modulo a prime (IntMod, see below) use some representation that
71* allows for fast arithmetic.
72*
73* The default representation used is Montgomery arithmetic. Curves with
74* specialized fields (eg Mersenne primes, Solinas primes, or Crandall primes)
75* provide a different type as the FieldRep parameter to the EllipticCurve
76* template.
77*
78* Since the curve parameters are public and known at compile time, we can
79* similarly compute the Montgomery parameters at compile time.
80*/
81template <typename Params>
82class MontgomeryRep final {
83 public:
85
86 static constexpr auto P = Params::P;
87 static constexpr size_t N = Params::N;
88 typedef typename Params::W W;
89
90 static_assert(N > 0 && (Params::P[0] & 1) == 1, "Invalid Montgomery modulus");
91
92 static constexpr auto P_dash = monty_inverse(P[0]);
93
94 static constexpr auto R1 = montygomery_r(P);
95 static constexpr auto R2 = mul_mod(R1, R1, P);
96 static constexpr auto R3 = mul_mod(R1, R2, P);
97
98 /**
99 * Return the constant one, pre-converted into Montgomery form
100 */
101 constexpr static std::array<W, N> one() { return R1; }
102
103 /**
104 * Modular reduction
105 */
106 constexpr static std::array<W, N> redc(const std::array<W, 2 * N>& z) {
107 if constexpr(P_dash == 1) {
108 return monty_redc_pdash1(z, P);
109 } else {
110 return monty_redc(z, P, P_dash);
111 }
112 }
113
114 /**
115 * Convert an integer into Montgomery representation
116 */
117 constexpr static std::array<W, N> to_rep(const std::array<W, N>& x) {
118 std::array<W, 2 * N> z; // NOLINT(*-member-init)
119 comba_mul<N>(z.data(), x.data(), R2.data());
120 return Self::redc(z);
121 }
122
123 /**
124 * Wide reduction modulo the prime
125 *
126 * Modular reduces an input of up to twice the length of the modulus, and
127 * converts it into Montgomery form.
128 */
129 constexpr static std::array<W, N> wide_to_rep(const std::array<W, 2 * N>& x) {
130 auto redc_x = Self::redc(x);
131 std::array<W, 2 * N> z; // NOLINT(*-member-init)
132 comba_mul<N>(z.data(), redc_x.data(), R3.data());
133 return Self::redc(z);
134 }
135
136 /**
137 * Convert an integer out of Montgomery representation
138 */
139 constexpr static std::array<W, N> from_rep(const std::array<W, N>& z) {
140 std::array<W, 2 * N> ze = {};
141 copy_mem(std::span{ze}.template first<N>(), z);
142 return Self::redc(ze);
143 }
144};
145
146/**
147* Integers Modulo (a Prime)
148*
149* This is used to store and manipulate integers modulo the field (for the affine
150* x/y or Jacobian x/y/z coordinates) and group order (for scalar arithmetic).
151*
152* This class is parameterized by Rep which handles the modular reduction step,
153* as well (if required) any conversions into or out of the inner
154* representation. This is primarily for Montgomery arithmetic; specialized
155* reduction methods instead keep the integer in the "standard" form.
156*
157* _Most_ of the code in this class does work for arbitrary moduli. However
158* at least div2 and invert make assumptions that the modulus is prime.
159*
160* Any function that does not contain "vartime" or equivalent in the name is
161* written such that it does not leak information about its arguments via control
162* flow or memory access patterns.
163*/
164template <typename Rep>
165class IntMod final {
166 private:
167 static constexpr auto P = Rep::P;
168 static constexpr size_t N = Rep::N;
169 typedef typename Rep::W W;
170
171 static constexpr auto P_MINUS_2 = p_minus<2>(P);
172
173 public:
174 static constexpr size_t BITS = count_bits(P);
175 static constexpr size_t BYTES = (BITS + 7) / 8;
176
177 static constexpr auto P_MOD_4 = P[0] % 4;
178
180
181 // Default value is zero
182 constexpr IntMod() : m_val({}) {}
183
184 IntMod(const Self& other) = default;
185 IntMod(Self&& other) = default;
186 IntMod& operator=(const Self& other) = default;
187 IntMod& operator=(Self&& other) = default;
188 ~IntMod() = default;
189
190 /**
191 * Return integer zero
192 *
193 * Note this assumes that the representation of zero is an all zero
194 * sequence of words. This is true for both Montgomery and standard
195 * representations.
196 */
197 static constexpr Self zero() { return Self(std::array<W, N>{0}); }
198
199 /**
200 * Return integer one
201 */
202 static constexpr Self one() { return Self(Rep::one()); }
203
204 /**
205 * Consume an array of words and convert it to an IntMod
206 *
207 * This handles the Montgomery conversion, if required.
208 *
209 * Note that this function assumes that `w` represents an integer that is
210 * less than the modulus.
211 */
212 template <size_t L>
213 static constexpr Self from_words(std::array<W, L> w) {
214 if constexpr(L == N) {
215 return Self(Rep::to_rep(w));
216 } else {
217 static_assert(L < N);
218 std::array<W, N> ew = {};
219 copy_mem(std::span{ew}.template first<L>(), w);
220 return Self(Rep::to_rep(ew));
221 }
222 }
223
224 /**
225 * Check in constant time if this is equal to zero
226 */
227 constexpr CT::Choice is_zero() const { return CT::all_zeros(m_val.data(), m_val.size()).as_choice(); }
228
229 /**
230 * Check in constant time if this not equal to zero
231 */
232 constexpr CT::Choice is_nonzero() const { return !is_zero(); }
233
234 /**
235 * Check in constant time if this equal to one
236 */
237 constexpr CT::Choice is_one() const { return (*this == Self::one()); }
238
239 /**
240 * Check in constant time if this is an even integer
241 */
242 constexpr CT::Choice is_even() const {
243 auto v = Rep::from_rep(m_val);
244 return !CT::Choice::from_int(v[0] & 0x01);
245 }
246
247 /**
248 * Return either this or -this depending on which is even
249 */
250 constexpr Self correct_sign(CT::Choice even) const {
251 const auto flip = (even != this->is_even());
252 return Self::choose(flip, this->negate(), *this);
253 }
254
255 /**
256 * Return x or y depending on if choice is set or not
257 */
258 static constexpr Self choose(CT::Choice choice, const Self& x, const Self& y) {
259 auto r = y;
260 r.conditional_assign(choice, x);
261 return r;
262 }
263
264 /**
265 * Modular addition; return c = a + b
266 */
267 friend constexpr BOTAN_FORCE_INLINE Self operator+(const Self& a, const Self& b) {
268 std::array<W, N> t; // NOLINT(*-member-init)
269
270 W carry = 0;
271 for(size_t i = 0; i != N; ++i) {
272 t[i] = word_add(a.m_val[i], b.m_val[i], &carry);
273 }
274
275 std::array<W, N> r; // NOLINT(*-member-init)
276 bigint_monty_maybe_sub<N>(r.data(), carry, t.data(), P.data());
277 return Self(r);
278 }
279
280 /**
281 * Modular subtraction; return c = a - b
282 */
283 friend constexpr BOTAN_FORCE_INLINE Self operator-(const Self& a, const Self& b) {
284 std::array<W, N> r; // NOLINT(*-member-init)
285 W carry = 0;
286 for(size_t i = 0; i != N; ++i) {
287 r[i] = word_sub(a.m_val[i], b.m_val[i], &carry);
288 }
289
290 const auto mask = CT::Mask<W>::expand(carry).value();
291
292 carry = 0;
293
294 for(size_t i = 0; i != N; ++i) {
295 r[i] = word_add(r[i], P[i] & mask, &carry);
296 }
297
298 return Self(r);
299 }
300
301 /**
302 * Return the value of this divided by 2
303 */
304 Self div2() const {
305 // The inverse of 2 modulo P is (P/2)+1; this avoids a constexpr time
306 // general inversion, which some compilers can't handle
307 constexpr auto INV_2 = p_div_2_plus_1(Rep::P);
308
309 // We could multiply by INV_2 but there is a better way ...
310
311 std::array<W, N> t = value();
312 const W borrow = shift_right<1>(t);
313
314 // If value was odd, add (P/2)+1
315 const auto mask = CT::Mask<W>::expand(borrow).value();
316
317 W carry = 0;
318
319 for(size_t i = 0; i != N; ++i) {
320 t[i] = word_add(t[i], INV_2[i] & mask, &carry);
321 }
322
323 return Self(t);
324 }
325
326 /// Return (*this) multiplied by 2
327 constexpr BOTAN_FORCE_INLINE Self mul2() const {
328 std::array<W, N> t = value();
329 const W carry = shift_left<1>(t);
330
331 std::array<W, N> r; // NOLINT(*-member-init)
332 bigint_monty_maybe_sub<N>(r.data(), carry, t.data(), P.data());
333 return Self(r);
334 }
335
336 /// Return (*this) multiplied by 3
337 constexpr inline Self mul3() const { return mul2() + (*this); }
338
339 /// Return (*this) multiplied by 4
340 constexpr inline Self mul4() const { return mul2().mul2(); }
341
342 /// Return (*this) multiplied by 8
343 constexpr inline Self mul8() const { return mul2().mul2().mul2(); }
344
345 /**
346 * Modular multiplication; return c = a * b
347 */
348 friend constexpr BOTAN_FORCE_INLINE Self operator*(const Self& a, const Self& b) {
349 std::array<W, 2 * N> z; // NOLINT(*-member-init)
350 comba_mul<N>(z.data(), a.data(), b.data());
351 return Self(Rep::redc(z));
352 }
353
354 /**
355 * Modular multiplication; set this to this * other
356 */
357 constexpr BOTAN_FORCE_INLINE Self& operator*=(const Self& other) {
358 std::array<W, 2 * N> z; // NOLINT(*-member-init)
359 comba_mul<N>(z.data(), data(), other.data());
360 m_val = Rep::redc(z);
361 return (*this);
362 }
363
364 /**
365 * Conditional assignment
366 *
367 * If `cond` is true, sets *this to `nx`
368 */
369 constexpr void conditional_assign(CT::Choice cond, const Self& nx) {
370 const W mask = cond.into_bitmask<W>();
371
372 for(size_t i = 0; i != N; ++i) {
373 m_val[i] = Botan::choose(mask, nx.m_val[i], m_val[i]);
374 }
375 }
376
377 /**
378 * Conditional assignment
379 *
380 * If `cond` is true, sets `x` to `nx` and `y` to `ny`
381 */
382 static constexpr void conditional_assign(Self& x, Self& y, CT::Choice cond, const Self& nx, const Self& ny) {
383 const W mask = cond.into_bitmask<W>();
384
385 for(size_t i = 0; i != N; ++i) {
386 x.m_val[i] = Botan::choose(mask, nx.m_val[i], x.m_val[i]);
387 y.m_val[i] = Botan::choose(mask, ny.m_val[i], y.m_val[i]);
388 }
389 }
390
391 /**
392 * Conditional assignment
393 *
394 * If `cond` is true, sets `x` to `nx`, `y` to `ny`, and `z` to `nz`
395 */
396 static constexpr void conditional_assign(
397 Self& x, Self& y, Self& z, CT::Choice cond, const Self& nx, const Self& ny, const Self& nz) {
398 const W mask = cond.into_bitmask<W>();
399
400 for(size_t i = 0; i != N; ++i) {
401 x.m_val[i] = Botan::choose(mask, nx.m_val[i], x.m_val[i]);
402 y.m_val[i] = Botan::choose(mask, ny.m_val[i], y.m_val[i]);
403 z.m_val[i] = Botan::choose(mask, nz.m_val[i], z.m_val[i]);
404 }
405 }
406
407 /**
408 * Conditional swap
409 *
410 * If `cond` is true, swaps the values of `x` and `y`
411 */
412 static constexpr void conditional_swap(CT::Choice cond, Self& x, Self& y) {
413 const W mask = cond.into_bitmask<W>();
414
415 for(size_t i = 0; i != N; ++i) {
416 const auto nx = Botan::choose(mask, y.m_val[i], x.m_val[i]);
417 const auto ny = Botan::choose(mask, x.m_val[i], y.m_val[i]);
418 x.m_val[i] = nx;
419 y.m_val[i] = ny;
420 }
421 }
422
423 /**
424 * Modular squaring
425 *
426 * Returns the square of this after modular reduction
427 */
428 constexpr BOTAN_FORCE_INLINE Self square() const {
429 std::array<W, 2 * N> z; // NOLINT(*-member-init)
430 comba_sqr<N>(z.data(), this->data());
431 return Self(Rep::redc(z));
432 }
433
434 /**
435 * Repeated modular squaring
436 *
437 * Returns the nth square of this
438 *
439 * (Alternate view, returns this raised to the 2^nth power)
440 */
441 constexpr void square_n(size_t n) {
442 std::array<W, 2 * N> z; // NOLINT(*-member-init)
443 for(size_t i = 0; i != n; ++i) {
444 comba_sqr<N>(z.data(), this->data());
445 m_val = Rep::redc(z);
446 }
447 }
448
449 /**
450 * Modular negation
451 *
452 * Returns the additive inverse of (*this)
453 */
454 constexpr Self negate() const {
455 const W x_is_zero = ~CT::all_zeros(this->data(), N).value();
456
457 std::array<W, N> r; // NOLINT(*-member-init)
458 W carry = 0;
459 for(size_t i = 0; i != N; ++i) {
460 r[i] = word_sub(P[i] & x_is_zero, m_val[i], &carry);
461 }
462
463 return Self(r);
464 }
465
466 /**
467 * Modular Exponentiation (Variable Time)
468 *
469 * This function is variable time with respect to the exponent. It should
470 * only be used when exp is not secret. In the current code, `exp` is
471 * always a compile-time constant.
472 *
473 * This function should not leak any information about *this, since the
474 * value being operated on may be a secret.
475 *
476 * TODO: this interface should be changed so that the exponent is always a
477 * compile-time constant; this should allow some interesting optimizations.
478 */
479 constexpr Self pow_vartime(const std::array<W, N>& exp) const {
480 constexpr size_t WindowBits = (Self::BITS <= 256) ? 4 : 5;
481 constexpr size_t WindowElements = (1 << WindowBits) - 1;
482
483 constexpr size_t Windows = (Self::BITS + WindowBits - 1) / WindowBits;
484
485 /*
486 A simple fixed width window modular multiplication.
487
488 TODO: investigate using sliding window here
489 */
490
491 std::array<Self, WindowElements> tbl;
492
493 tbl[0] = (*this);
494
495 for(size_t i = 1; i != WindowElements; ++i) {
496 // Conditional ok: table indexes are public here
497 if(i % 2 == 1) {
498 tbl[i] = tbl[i / 2].square();
499 } else {
500 tbl[i] = tbl[i - 1] * tbl[0];
501 }
502 }
503
504 auto r = Self::one();
505
506 const size_t w0 = read_window_bits<WindowBits>(std::span{exp}, (Windows - 1) * WindowBits);
507
508 // Conditional ok: this function is variable time
509 if(w0 > 0) {
510 r = tbl[w0 - 1];
511 }
512
513 for(size_t i = 1; i != Windows; ++i) {
514 r.square_n(WindowBits);
515
516 const size_t w = read_window_bits<WindowBits>(std::span{exp}, (Windows - i - 1) * WindowBits);
517
518 // Conditional ok: this function is variable time
519 if(w > 0) {
520 r *= tbl[w - 1];
521 }
522 }
523
524 return r;
525 }
526
527 /**
528 * Returns the modular inverse, or 0 if no modular inverse exists.
529 *
530 * If the modulus is prime the only value that has no modular inverse is 0.
531 *
532 * This uses Fermat's little theorem, and so assumes that p is prime
533 *
534 * Since P is public, P-2 is as well, thus using a variable time modular
535 * exponentiation routine is safe.
536 *
537 * This function is only used if the curve does not provide an addition
538 * chain for specific inversions (see for example pcurves_secp256r1.cpp)
539 */
540 constexpr Self invert() const { return pow_vartime(Self::P_MINUS_2); }
541
542 /**
543 * Helper for variable time BEEA
544 *
545 * Note this function assumes that its arguments are in the standard
546 * domain, not the Montgomery domain. invert_vartime converts its argument
547 * out of Montgomery, and then back to Montgomery when returning the result.
548 */
549 static constexpr void _invert_vartime_div2_helper(Self& a, Self& x) {
550 constexpr auto INV_2 = p_div_2_plus_1(Rep::P);
551
552 // Conditional ok: this function is variable time
553 while((a.m_val[0] & 1) != 1) {
554 shift_right<1>(a.m_val);
555
556 const W borrow = shift_right<1>(x.m_val);
557
558 // Conditional ok: this function is variable time
559 if(borrow) {
560 bigint_add2(x.m_val.data(), N, INV_2.data(), N);
561 }
562 }
563 }
564
565 /**
566 * Returns the modular inverse, or 0 if no modular inverse exists.
567 *
568 * This function assumes that the modulus is prime
569 *
570 * This function does something a bit nasty and converts from the normal
571 * representation (for scalars, Montgomery) into the "standard"
572 * representation. This relies on the fact that we aren't doing any
573 * multiplications within this function, just additions, subtractions,
574 * division by 2, and comparisons.
575 *
576 * The reason is there is no good way to compare integers in the Montgomery
577 * domain; we could convert out for each comparison but this is slower than
578 * just doing a constant-time inversion.
579 *
580 * This is loosely based on the algorithm BoringSSL uses in
581 * BN_mod_inverse_odd, which is a variant of the Binary Extended Euclidean
582 * algorithm. It is optimized somewhat by taking advantage of a couple of
583 * observations.
584 *
585 * In the first two iterations, the control flow is known because `a` is
586 * less than the modulus and not zero, and we know that the modulus is
587 * odd. So we peel out those iterations. This also avoids having to
588 * initialize `a` with the modulus, because we instead set it directly to
589 * what the first loop iteration would have updated it to. This ensures
590 * that all values are always less than or equal to the modulus.
591 *
592 * Then we take advantage of the fact that in each iteration of the loop,
593 * at the end we update either b/x or a/y, but never both. In the next
594 * iteration of the loop, we attempt to modify b/x or a/y depending on the
595 * low zero bits of b or a. But if a or b were not updated in the previous
596 * iteration than they will still be odd, and nothing will happen. Instead
597 * update just the pair we need to update, right after writing to b/x or
598 * a/y resp.
599 */
600 constexpr Self invert_vartime() const {
601 // Conditional ok: this function is variable time
602 if(this->is_zero().as_bool()) {
603 return Self::zero();
604 }
605
606 auto x = Self(std::array<W, N>{1}); // 1 in standard domain
607 auto b = Self(this->to_words()); // *this in standard domain
608
609 // First loop iteration
611
612 auto a = b.negate();
613 // y += x but y is zero at the outset
614 auto y = x;
615
616 // First half of second loop iteration
618
619 for(;;) {
620 // Conditional ok: this function is variable time
621 if(a.m_val == b.m_val) {
622 // At this point it should be that a == b == 1
623 auto r = y.negate();
624
625 // Convert back to Montgomery if required
626 r.m_val = Rep::to_rep(r.m_val);
627 return r;
628 }
629
630 const auto nx = x + y;
631
632 /*
633 * Otherwise either b > a or a > b
634 *
635 * If b > a we want to set b to b - a
636 * Otherwise we want to set a to a - b
637 *
638 * Compute r = b - a and check if it underflowed
639 * If it did not then we are in the b > a path
640 */
641 std::array<W, N> r; // NOLINT(*-member-init)
642 const word carry = bigint_sub3(r.data(), b.data(), N, a.data(), N);
643
644 // Conditional ok: this function is variable time
645 if(carry == 0) {
646 // b > a
647 b.m_val = r;
648 x = nx;
650 } else {
651 // We know this can't underflow because a > b
652 bigint_sub3(r.data(), a.data(), N, b.data(), N);
653 a.m_val = r;
654 y = nx;
656 }
657 }
658 }
659
660 /**
661 * Return the modular square root if it exists
662 *
663 * The CT::Option will be unset if the square root does not exist
664 */
665 constexpr CT::Option<Self> sqrt() const {
666 if constexpr(Self::P_MOD_4 == 3) {
667 // The easy case for square root is when p == 3 (mod 4)
668
669 constexpr auto P_PLUS_1_OVER_4 = p_plus_1_over_4(P);
670 auto z = pow_vartime(P_PLUS_1_OVER_4);
671
672 // Zero out the return value if it would otherwise be incorrect
673 const CT::Choice correct = (z.square() == *this);
674 z.conditional_assign(!correct, Self::zero());
675 return CT::Option<Self>(z, correct);
676 } else {
677 // Shanks-Tonelli, following I.4 in RFC 9380
678
679 /*
680 Constants:
681 1. c1, the largest integer such that 2^c1 divides q - 1.
682 2. c2 = (q - 1) / (2^c1) # Integer arithmetic
683 3. c3 = (c2 - 1) / 2 # Integer arithmetic
684 4. c4, a non-square value in F
685 5. c5 = c4^c2 in F
686 */
687 constexpr auto C1_C2 = shanks_tonelli_c1c2(Self::P);
688 constexpr std::array<W, N> C3 = shanks_tonelli_c3(C1_C2.second);
689 constexpr std::array<W, N> P_MINUS_1_OVER_2 = p_minus_1_over_2(Self::P);
690 constexpr Self C4 = shanks_tonelli_c4<Self>(P_MINUS_1_OVER_2);
691 constexpr Self C5 = C4.pow_vartime(C1_C2.second);
692
693 const Self& x = (*this);
694
695 auto z = x.pow_vartime(C3);
696 auto t = z.square();
697 t *= x;
698 z *= x;
699 auto b = t;
700 auto c = C5;
701
702 for(size_t i = C1_C2.first; i >= 2; i--) {
703 b.square_n(i - 2);
704 const CT::Choice e = b.is_one();
705 z.conditional_assign(!e, z * c);
706 c.square_n(1);
707 t.conditional_assign(!e, t * c);
708 b = t;
709 }
710
711 // Zero out the return value if it would otherwise be incorrect
712 const CT::Choice correct = (z.square() == *this);
713 z.conditional_assign(!correct, Self::zero());
714 return CT::Option<Self>(z, correct);
715 }
716 }
717
718 /**
719 * Constant time integer equality test
720 *
721 * Since both this and other are in Montgomery representation (if applicable),
722 * we can always compare the words directly, without having to convert out.
723 */
724 constexpr CT::Choice operator==(const Self& other) const {
725 return CT::is_equal(this->data(), other.data(), N).as_choice();
726 }
727
728 /**
729 * Constant time integer inequality test
730 */
731 constexpr CT::Choice operator!=(const Self& other) const { return !(*this == other); }
732
733 /**
734 * Convert the integer to standard representation and return the sequence of words
735 */
736 constexpr std::array<W, Self::N> to_words() const { return Rep::from_rep(m_val); }
737
738 /**
739 * Serialize the integer to a bytestring
740 */
741 constexpr void serialize_to(std::span<uint8_t, Self::BYTES> bytes) const {
742 auto v = Rep::from_rep(m_val);
743 std::reverse(v.begin(), v.end());
744
745 if constexpr(Self::BYTES == N * WordInfo<W>::bytes) {
746 store_be(bytes, v);
747 } else {
748 // Remove leading zero bytes
749 const auto padded_bytes = store_be(v);
750 constexpr size_t extra = N * WordInfo<W>::bytes - Self::BYTES;
751 copy_mem(bytes, std::span{padded_bytes}.template subspan<extra, Self::BYTES>());
752 }
753 }
754
755 /**
756 * Store the raw words to an array
757 *
758 * See pcurves_wrap.h for why/where this is used
759 */
760 template <size_t L>
761 std::array<W, L> stash_value() const {
762 static_assert(L >= N);
763 std::array<W, L> stash = {};
764 for(size_t i = 0; i != N; ++i) {
765 stash[i] = m_val[i];
766 }
767 return stash;
768 }
769
770 /**
771 * Restore the value previously stashed
772 *
773 * See pcurves_wrap.h for why/where this is used
774 */
775 template <size_t L>
776 static Self from_stash(const std::array<W, L>& stash) {
777 static_assert(L >= N);
778 std::array<W, N> val = {};
779 for(size_t i = 0; i != N; ++i) {
780 val[i] = stash[i];
781 }
782 return Self(val);
783 }
784
785 /**
786 * Deserialize an integer from a bytestring
787 *
788 * Returns nullopt if the input is an encoding greater than or equal P
789 *
790 * This function also requires that the bytestring be exactly of the expected
791 * length; short bytestrings, or a long bytestring with leading zero bytes, are
792 * also rejected.
793 */
794 static std::optional<Self> deserialize(std::span<const uint8_t> bytes) {
795 // Conditional ok: input length is public
796 if(bytes.size() != Self::BYTES) {
797 return {};
798 }
799
800 const auto words = bytes_to_words<W, N, BYTES>(bytes.first<Self::BYTES>());
801
802 // Conditional acceptable: std::optional is implicitly not constant time
803 if(!bigint_ct_is_lt(words.data(), N, P.data(), N).as_bool()) {
804 return {};
805 }
806
807 // Safe because we checked above that words is an integer < P
808 return Self::from_words(words);
809 }
810
811 /**
812 * Modular reduce a larger input
813 *
814 * This takes a bytestring that is at most twice the length of the modulus, and
815 * modular reduces it.
816 */
817 template <size_t L>
818 static constexpr Self from_wide_bytes(std::span<const uint8_t, L> bytes) {
819 static_assert(8 * L <= 2 * Self::BITS);
820 std::array<uint8_t, 2 * BYTES> padded_bytes = {};
821 copy_mem(std::span{padded_bytes}.template last<L>(), bytes);
822 return Self(Rep::wide_to_rep(bytes_to_words<W, 2 * N, 2 * BYTES>(std::span{padded_bytes})));
823 }
824
825 /**
826 * Modular reduce a larger input
827 *
828 * This takes a bytestring that is at most twice the length of the modulus, and
829 * modular reduces it.
830 */
831 static constexpr std::optional<Self> from_wide_bytes_varlen(std::span<const uint8_t> bytes) {
832 // Conditional ok: input length is public
833 if(bytes.size() > 2 * Self::BYTES) {
834 return {};
835 }
836
837 std::array<uint8_t, 2 * Self::BYTES> padded_bytes = {};
838 copy_mem(std::span{padded_bytes}.last(bytes.size()), bytes);
839 return Self(Rep::wide_to_rep(bytes_to_words<W, 2 * N, 2 * BYTES>(std::span{padded_bytes})));
840 }
841
842 /**
843 * Return a random integer value in [1,p)
844 *
845 * This uses rejection sampling. This could have alternatively been implemented
846 * by oversampling the random number generator and then performing a wide
847 * reduction. The main reason that approach is avoided here is because it makes
848 * testing ECDSA-style known answer tests more difficult.
849 *
850 * This function avoids returning zero since in almost all contexts where a
851 * random integer is desired we want a random integer in Z_p*
852 */
854 constexpr size_t MAX_ATTEMPTS = 1000;
855
856 std::array<uint8_t, Self::BYTES> buf{};
857
858 for(size_t i = 0; i != MAX_ATTEMPTS; ++i) {
859 rng.randomize(buf);
860
861 // Zero off high bits that if set would certainly cause us
862 // to be out of range
863 if constexpr(Self::BITS % 8 != 0) {
864 constexpr uint8_t mask = 0xFF >> (8 - (Self::BITS % 8));
865 buf[0] &= mask;
866 }
867
868 // Conditionals ok: rejection sampling reveals only values we didn't use
869 if(auto s = Self::deserialize(buf)) {
870 if(s.value().is_nonzero().as_bool()) {
871 return s.value();
872 }
873 }
874 }
875
876 throw Internal_Error("Failed to generate random Scalar within bounded number of attempts");
877 }
878
879 /**
880 * Create a small compile time constant
881 *
882 * Notice this function is consteval, and so can only be called at compile time
883 */
884 static consteval Self constant(int8_t x) {
885 std::array<W, 1> v{};
886 v[0] = (x >= 0) ? x : -x;
887 const auto s = Self::from_words(v);
888 return (x >= 0) ? s : s.negate();
889 }
890
891 constexpr void _const_time_poison() const { CT::poison(m_val); }
892
893 constexpr void _const_time_unpoison() const { CT::unpoison(m_val); }
894
895 private:
896 constexpr const std::array<W, N>& value() const { return m_val; }
897
898 constexpr const W* data() const { return m_val.data(); }
899
900#if defined(BOTAN_BUILD_COMPILER_IS_GCC)
901 // Initialized word by word since GCC copies arrays using 16 byte loads,
902 // which stall when v was just written by 8 byte stores
903 explicit constexpr IntMod(const std::array<W, N>& v) : IntMod(v, std::make_index_sequence<N>{}) {}
904
905 template <size_t... I>
906 constexpr IntMod(const std::array<W, N>& v, std::index_sequence<I...> /*unused*/) : m_val{v[I]...} {}
907#else
908 explicit constexpr IntMod(std::array<W, N> v) : m_val(v) {}
909#endif
910
911 std::array<W, N> m_val;
912};
913
914/**
915* Affine Curve Point
916*
917* This contains a pair of integers (x,y) which satisfy the curve equation
918*/
919template <typename FieldElement>
920class AffineCurvePoint final {
921 public:
922 static constexpr size_t BYTES = 1 + 2 * FieldElement::BYTES;
923
925
926 // Note this constructor does not check the validity of the x/y pair
927 // This must be verified prior to this constructor being called
928 constexpr AffineCurvePoint(const FieldElement& x, const FieldElement& y) : m_x(x), m_y(y) {}
929
930 constexpr AffineCurvePoint() : m_x(FieldElement::zero()), m_y(FieldElement::zero()) {}
931
932 static constexpr Self identity() { return Self(FieldElement::zero(), FieldElement::zero()); }
933
934 // Helper for ct_select of pcurves_generic
935 static constexpr Self identity(const Self& /*unused*/) {
936 return Self(FieldElement::zero(), FieldElement::zero());
937 }
938
939 constexpr CT::Choice is_identity() const { return x().is_zero() && y().is_zero(); }
940
941 AffineCurvePoint(const Self& other) = default;
942 AffineCurvePoint(Self&& other) = default;
943 AffineCurvePoint& operator=(const Self& other) = default;
944 AffineCurvePoint& operator=(Self&& other) = default;
945 ~AffineCurvePoint() = default;
946
947 constexpr Self negate() const { return Self(x(), y().negate()); }
948
949 /**
950 * Serialize the point in uncompressed format
951 */
952 constexpr void serialize_to(std::span<uint8_t, Self::BYTES> bytes) const {
953 BOTAN_STATE_CHECK(this->is_identity().as_bool() == false);
954 BufferStuffer pack(bytes);
955 pack.append(0x04);
956 x().serialize_to(pack.next<FieldElement::BYTES>());
957 y().serialize_to(pack.next<FieldElement::BYTES>());
958 BOTAN_DEBUG_ASSERT(pack.full());
959 }
960
961 /**
962 * If idx is zero then return the identity element. Otherwise return pts[idx - 1]
963 *
964 * Returns the identity element also if idx is out of range
965 */
966 static constexpr auto ct_select(std::span<const Self> pts, size_t idx) {
967 auto result = Self::identity(pts[0]);
968
969 // Intentionally wrapping; set to maximum size_t if idx == 0
970 const size_t idx1 = idx - 1;
971 for(size_t i = 0; i != pts.size(); ++i) {
972 const auto found = CT::Mask<size_t>::is_equal(idx1, i).as_choice();
973 result.conditional_assign(found, pts[i]);
974 }
975
976 return result;
977 }
978
979 /**
980 * Return the affine x coordinate
981 */
982 constexpr const FieldElement& x() const { return m_x; }
983
984 /**
985 * Return the affine y coordinate
986 */
987 constexpr const FieldElement& y() const { return m_y; }
988
989 /**
990 * Conditional assignment of an affine point
991 */
992 constexpr void conditional_assign(CT::Choice cond, const Self& pt) {
993 FieldElement::conditional_assign(m_x, m_y, cond, pt.x(), pt.y());
994 }
995
996 constexpr void _const_time_poison() const { CT::poison_all(m_x, m_y); }
997
998 constexpr void _const_time_unpoison() const { CT::unpoison_all(m_x, m_y); }
999
1000 private:
1001 FieldElement m_x;
1002 FieldElement m_y;
1003};
1004
1005/**
1006* Projective curve point
1007*
1008* This uses Jacobian coordinates
1009*/
1010template <typename FieldElement, typename Params>
1012 public:
1013 // We can't pass a FieldElement directly because FieldElement is
1014 // not "structural" due to having private members, so instead
1015 // recreate it here from the words.
1016 static constexpr FieldElement A = FieldElement::from_words(Params::AW);
1017
1018 static constexpr bool A_is_zero = A.is_zero().as_bool();
1019 static constexpr bool A_is_minus_3 = (A == FieldElement::constant(-3)).as_bool();
1020
1023
1024 /**
1025 * Convert a point from affine to projective form
1026 */
1027 static constexpr Self from_affine(const AffinePoint& pt) {
1028 /*
1029 * If the point is the identity element (x=0, y=0) then instead of
1030 * creating (x, y, 1) = (0, 0, 1) we want our projective identity
1031 * encoding of (0, 1, 0)
1032 *
1033 * Which we can achieve by a conditional swap of y and z if the
1034 * affine point is the identity.
1035 */
1036
1037 const auto x = pt.x();
1038 auto y = pt.y();
1039 auto z = FieldElement::one();
1040
1041 FieldElement::conditional_swap(pt.is_identity(), y, z);
1042
1043 return ProjectiveCurvePoint(x, y, z);
1044 }
1045
1046 /**
1047 * Return the identity element
1048 */
1049 static constexpr Self identity() { return Self(FieldElement::zero(), FieldElement::one(), FieldElement::zero()); }
1050
1051 /**
1052 * Default constructor: the identity element
1053 */
1055 m_x(FieldElement::zero()), m_y(FieldElement::one()), m_z(FieldElement::zero()) {}
1056
1057 /**
1058 * Affine constructor: take x/y coordinates
1059 */
1060 constexpr ProjectiveCurvePoint(const FieldElement& x, const FieldElement& y) :
1061 m_x(x), m_y(y), m_z(FieldElement::one()) {}
1062
1063 /**
1064 * Projective constructor: take x/y/z coordinates
1065 */
1066 constexpr ProjectiveCurvePoint(const FieldElement& x, const FieldElement& y, const FieldElement& z) :
1067 m_x(x), m_y(y), m_z(z) {}
1068
1069 ProjectiveCurvePoint(const Self& other) = default;
1070 ProjectiveCurvePoint(Self&& other) = default;
1071 ProjectiveCurvePoint& operator=(const Self& other) = default;
1074
1075 friend constexpr Self operator+(const Self& a, const Self& b) { return Self::add(a, b); }
1076
1077 friend constexpr Self operator+(const Self& a, const AffinePoint& b) { return Self::add_mixed(a, b); }
1078
1079 friend constexpr Self operator+(const AffinePoint& a, const Self& b) { return Self::add_mixed(b, a); }
1080
1081 constexpr Self& operator+=(const Self& other) {
1082 (*this) = (*this) + other;
1083 return (*this);
1084 }
1085
1086 constexpr Self& operator+=(const AffinePoint& other) {
1087 (*this) = (*this) + other;
1088 return (*this);
1089 }
1090
1091 friend constexpr Self operator-(const Self& a, const Self& b) { return a + b.negate(); }
1092
1093 constexpr CT::Choice is_identity() const { return z().is_zero(); }
1094
1095 constexpr void conditional_assign(CT::Choice cond, const Self& pt) {
1096 FieldElement::conditional_assign(m_x, m_y, m_z, cond, pt.x(), pt.y(), pt.z());
1097 }
1098
1099 /**
1100 * Mixed (projective + affine) point addition
1101 */
1102 constexpr static Self add_mixed(const Self& a, const AffinePoint& b) {
1103 return point_add_mixed<Self, AffinePoint, FieldElement>(a, b, FieldElement::one(), A);
1104 }
1105
1106 /**
1107 * Mixed point addition on an isomorphic curve with the given a coefficient
1108 */
1109 constexpr static Self add_mixed_iso(const Self& a, const AffinePoint& b, const FieldElement& curve_a) {
1110 return point_add_mixed<Self, AffinePoint, FieldElement>(a, b, FieldElement::one(), curve_a);
1111 }
1112
1113 /**
1114 * Mixed point addition, additionally returning H (the sum has Z = a.z * H)
1115 */
1116 constexpr static std::pair<Self, FieldElement> add_mixed_h(const Self& a, const AffinePoint& b) {
1117 return point_add_mixed_h<Self, AffinePoint, FieldElement>(a, b, FieldElement::one(), A);
1118 }
1119
1120 // Either add or subtract based on the CT::Choice
1121 constexpr static Self add_or_sub(const Self& a, const AffinePoint& b, CT::Choice sub) {
1122 return point_add_or_sub_mixed<Self, AffinePoint, FieldElement>(a, b, sub, FieldElement::one(), A);
1123 }
1124
1125 /**
1126 * Either add or subtract, on an isomorphic curve with the given a coefficient
1127 */
1128 constexpr static Self add_or_sub_iso(const Self& a,
1129 const AffinePoint& b,
1130 CT::Choice sub,
1131 const FieldElement& curve_a) {
1132 return point_add_or_sub_mixed<Self, AffinePoint, FieldElement>(a, b, sub, FieldElement::one(), curve_a);
1133 }
1134
1135 /**
1136 * Projective point addition
1137 */
1138 constexpr static Self add(const Self& a, const Self& b) { return point_add<Self, FieldElement>(a, b); }
1139
1140 /**
1141 * Iterated point doubling
1142 */
1143 constexpr Self dbl_n(size_t n) const {
1144 if constexpr(Self::A_is_minus_3) {
1145 return dbl_n_a_minus_3(*this, n);
1146 } else if constexpr(Self::A_is_zero) {
1147 return dbl_n_a_zero(*this, n);
1148 } else {
1149 return dbl_n_generic(*this, A, n);
1150 }
1151 }
1152
1153 /**
1154 * Iterated point doubling on an isomorphic curve with the given a coefficient
1155 *
1156 * If a is zero on this curve it is zero on any isomorphic curve, so the
1157 * argument is ignored in that case.
1158 */
1159 constexpr Self dbl_n_iso(const FieldElement& a, size_t n) const {
1160 if constexpr(Self::A_is_zero) {
1161 return dbl_n_a_zero(*this, n);
1162 } else {
1163 return dbl_n_generic(*this, a, n);
1164 }
1165 }
1166
1167 /**
1168 * Point doubling on an isomorphic curve with the given a coefficient
1169 */
1170 constexpr Self dbl_iso(const FieldElement& a) const {
1171 if constexpr(Self::A_is_zero) {
1172 return dbl_a_zero(*this);
1173 } else {
1174 return dbl_generic(*this, a);
1175 }
1176 }
1177
1178 /**
1179 * Point doubling
1180 */
1181 constexpr Self dbl() const {
1182 if constexpr(Self::A_is_minus_3) {
1183 return dbl_a_minus_3(*this);
1184 } else if constexpr(Self::A_is_zero) {
1185 return dbl_a_zero(*this);
1186 } else {
1187 return dbl_generic(*this, A);
1188 }
1189 }
1190
1191 /**
1192 * Point negation
1193 */
1194 constexpr Self negate() const { return Self(x(), y().negate(), z()); }
1195
1196 /**
1197 * Randomize the point representation
1198 *
1199 * Projective coordinates are redundant; if (x,y,z) is a projective
1200 * point then so is (x*r^2,y*r^3,z*r) for any non-zero r.
1201 */
1202 void randomize_rep(const FieldElement& r) {
1203 const auto r2 = r.square();
1204 const auto r3 = r2 * r;
1205
1206 m_x *= r2;
1207 m_y *= r3;
1208 m_z *= r;
1209 }
1210
1211 /**
1212 * Return the projective x coordinate
1213 */
1214 constexpr const FieldElement& x() const { return m_x; }
1215
1216 /**
1217 * Return the projective y coordinate
1218 */
1219 constexpr const FieldElement& y() const { return m_y; }
1220
1221 /**
1222 * Return the projective z coordinate
1223 */
1224 constexpr const FieldElement& z() const { return m_z; }
1225
1226 constexpr void _const_time_poison() const { CT::poison_all(m_x, m_y, m_z); }
1227
1228 constexpr void _const_time_unpoison() const { CT::unpoison_all(m_x, m_y, m_z); }
1229
1230 private:
1231 FieldElement m_x;
1232 FieldElement m_y;
1233 FieldElement m_z;
1234};
1235
1236/**
1237* Elliptic Curve Parameters
1238*
1239* These are constructed using compile time strings which contain the relevant values
1240* (P, A, B, the group order, and the group generator x/y coordinates)
1241*/
1242template <StringLiteral PS,
1243 StringLiteral AS,
1244 StringLiteral BS,
1245 StringLiteral NS,
1246 StringLiteral GXS,
1247 StringLiteral GYS,
1248 int8_t ZI = 0>
1250 public:
1251 typedef word W;
1252
1253 static constexpr auto PW = hex_to_words<W>(PS.value);
1254 static constexpr auto NW = hex_to_words<W>(NS.value);
1255 static constexpr auto AW = hex_to_words<W>(AS.value);
1256 static constexpr auto BW = hex_to_words<W>(BS.value);
1257 static constexpr auto GXW = hex_to_words<W>(GXS.value);
1258 static constexpr auto GYW = hex_to_words<W>(GYS.value);
1259
1260 static constexpr int8_t Z = ZI;
1261};
1262
1263/**
1264* This exists solely as a hack which somewhat reduces symbol lengths
1265*/
1266template <WordType WI, size_t NI, std::array<WI, NI> PI>
1268 public:
1269 typedef WI W;
1270 static constexpr size_t N = NI;
1271 static constexpr auto P = PI;
1272};
1273
1274/**
1275* Elliptic Curve
1276*
1277* Takes as input a set of parameters, and instantiates the elliptic curve
1278*/
1279template <typename Params, template <typename FieldParamsT> typename FieldRep = MontgomeryRep>
1281 public:
1282 typedef typename Params::W W;
1283
1284 typedef W WordType;
1285
1286 static constexpr auto PW = Params::PW;
1287 static constexpr auto NW = Params::NW;
1288 static constexpr auto AW = Params::AW;
1289
1290 // Simplifying assumption
1291 static_assert(PW.size() == NW.size());
1292
1293 static constexpr size_t Words = PW.size();
1294
1295 class ScalarParams final : public IntParams<W, Words, NW> {};
1296
1298
1299 class FieldParams final : public IntParams<W, Words, PW> {};
1300
1302
1305
1306 static constexpr size_t OrderBits = Scalar::BITS;
1307 static constexpr size_t PrimeFieldBits = FieldElement::BITS;
1308
1309 static constexpr FieldElement A = FieldElement::from_words(Params::AW);
1310 static constexpr FieldElement B = FieldElement::from_words(Params::BW);
1311
1312 static_assert(B.is_nonzero().as_bool(), "B must be non-zero");
1313
1314 static constexpr AffinePoint G =
1316
1317 static constexpr FieldElement SSWU_Z = FieldElement::constant(Params::Z);
1318
1319 static constexpr bool ValidForSswuHash =
1320 (Params::Z != 0 && A.is_nonzero().as_bool() && B.is_nonzero().as_bool() && FieldElement::P_MOD_4 == 3);
1321
1322 static constexpr bool OrderIsLessThanField = bigint_cmp(NW.data(), Words, PW.data(), Words) == -1;
1323
1324 /**
1325 * Return (x^3 + A*x + B) mod p
1326 */
1327 static constexpr FieldElement x3_ax_b(const FieldElement& x) { return (x.square() + A) * x + B; }
1328};
1329
1330/**
1331* Blinded Scalar
1332*
1333* This randomizes the scalar representation by computing s + n*k,
1334* where n is the group order and k is a random value
1335*
1336* Note that the field arithmetic and point multiplication algorithms
1337* implemented in this file are already constant time; blinding is used here as
1338* an additional precaution to guard against compilers introducing conditional
1339* jumps where not expected.
1340*
1341* If the provided RNG is not seeded, blinding is skipped and the scalar
1342* is used directly. This allows blinding to be disabled at runtime.
1343*/
1344template <typename C, size_t WindowBits>
1346 private:
1347 typedef typename C::W W;
1348
1349 static constexpr size_t BlindingBits = scalar_blinding_bits(C::OrderBits);
1350
1351 static_assert(BlindingBits < C::Scalar::BITS);
1352
1353 public:
1354 using Curve = C;
1355
1356 // Maximum number of bits (used for table sizing)
1357 static constexpr size_t Bits = C::Scalar::BITS + BlindingBits;
1358
1359 static constexpr size_t MaskWords = (BlindingBits + WordInfo<W>::bits - 1) / WordInfo<W>::bits;
1360 static constexpr size_t MaskBytes = MaskWords * WordInfo<W>::bytes;
1361
1362 size_t bits() const { return m_bits; }
1363
1364 /**
1365 * Blind the scalar using the idx'th mask of the provided BlindingRandomness
1366 */
1367 template <typename Randomness>
1368 BlindedScalarBits(const typename C::Scalar& scalar, const Randomness& randomness, size_t idx = 0) {
1369 // Conditional ok: caller's RNG state (seeded vs not) is presumed public
1370 if(BlindingBits > 0 && randomness.seeded()) {
1371 constexpr size_t n_words = C::Words;
1372
1373 W mask[n_words] = {0};
1374 load_le(mask, randomness.mask(idx).data(), MaskWords);
1375
1376 // Mask to exactly BlindingBits
1377 constexpr size_t ExcessBits = MaskWords * WordInfo<W>::bits - BlindingBits;
1378 if constexpr(ExcessBits > 0) {
1379 constexpr W ExcessMask = (static_cast<W>(1) << (WordInfo<W>::bits - ExcessBits)) - 1;
1380 mask[MaskWords - 1] &= ExcessMask;
1381 }
1382
1383 // Set top and bottom bits of mask
1384 constexpr size_t TopMaskBit = (BlindingBits - 1) % WordInfo<W>::bits;
1385 mask[(BlindingBits - 1) / WordInfo<W>::bits] |= static_cast<W>(1) << TopMaskBit;
1386 mask[0] |= 1;
1387
1388 W mask_n[2 * n_words] = {0};
1389
1390 const auto sw = scalar.to_words();
1391
1392 // Compute masked scalar s + k*n
1393 comba_mul<n_words>(mask_n, mask, C::NW.data());
1394 bigint_add2(mask_n, 2 * n_words, sw.data(), sw.size());
1395
1396 std::reverse(mask_n, mask_n + 2 * n_words);
1397 m_bytes = store_be<std::vector<uint8_t>>(mask_n);
1398 m_bits = C::Scalar::BITS + BlindingBits;
1399 } else {
1400 // No RNG available, skip blinding
1401 m_bytes.resize(C::Scalar::BYTES);
1402 scalar.serialize_to(std::span{m_bytes}.template first<C::Scalar::BYTES>());
1403 m_bits = C::Scalar::BITS;
1404 }
1405 }
1406
1407 size_t get_window(size_t offset) const {
1408 // Extract a WindowBits sized window out of s, depending on offset.
1409 return read_window_bits<WindowBits>(std::span{m_bytes}, offset);
1410 }
1411
1412 ~BlindedScalarBits() { secure_zeroize_buffer(m_bytes.data(), m_bytes.size()); }
1413
1414 BlindedScalarBits(const BlindedScalarBits& other) = delete;
1418
1419 private:
1420 std::vector<uint8_t> m_bytes;
1421 size_t m_bits;
1422};
1423
1424/**
1425* The randomness consumed by one blinded scalar multiplication
1426*
1427* The scalar masks, the projective re-randomizations, and the random curve
1428* isomorphism of the point table are drawn from the RNG with a single request,
1429* since each request has a fixed cost that dominates for small outputs.
1430*
1431* If the provided RNG is not seeded, no randomness is drawn and blinding is
1432* skipped; the isomorphism parameter is then one.
1433*/
1434template <typename BlindedScalar, size_t Scalars = 1>
1436 public:
1437 /// Each multiplication re-randomizes the accumulator this many times
1438 static constexpr size_t Rerandomizations = 4;
1439
1440 private:
1441 using C = typename BlindedScalar::Curve;
1442 using FieldElement = typename C::FieldElement;
1443
1444 static constexpr size_t MaskBytes = BlindedScalar::MaskBytes;
1445
1446 // Reducing 64 extra bits mod p leaves a negligible bias
1447 static constexpr size_t WideBytes = FieldElement::BYTES + 8;
1448
1449 public:
1450 explicit BlindingRandomness(RandomNumberGenerator& rng) : m_seeded(rng.is_seeded()) {
1451 // Conditional ok: caller's RNG state (seeded vs not) is presumed public
1452 if(m_seeded) {
1453 std::array<uint8_t, Scalars * MaskBytes + (Rerandomizations + 1) * WideBytes> buf{};
1454 rng.randomize(buf);
1455
1456 const std::span<const uint8_t> bytes(buf);
1457
1458 copy_mem(m_masks, bytes.first<Scalars * MaskBytes>());
1459
1460 for(size_t i = 0; i != Rerandomizations; ++i) {
1461 const auto wide = bytes.subspan(Scalars * MaskBytes + i * WideBytes).first<WideBytes>();
1462 m_rerandomizers[i] = FieldElement::from_wide_bytes(wide);
1463 }
1464
1465 const auto iso = bytes.subspan(Scalars * MaskBytes + Rerandomizations * WideBytes).first<WideBytes>();
1466 m_isomorphism = FieldElement::from_wide_bytes(iso);
1467 m_isomorphism.conditional_assign(m_isomorphism.is_zero(), FieldElement::one());
1468 }
1469 }
1470
1471 bool seeded() const { return m_seeded; }
1472
1473 std::span<const uint8_t, MaskBytes> mask(size_t idx) const {
1474 BOTAN_ASSERT_NOMSG(idx < Scalars);
1475 return std::span{m_masks}.subspan(idx * MaskBytes).template first<MaskBytes>();
1476 }
1477
1478 /**
1479 * Randomize the projective representation of pt using the idx'th element
1480 */
1481 void randomize_rep(typename C::ProjectivePoint& pt, size_t idx) const {
1483 // Conditional ok: caller's RNG state (seeded vs not) is presumed public
1484 if(m_seeded) {
1485 pt.randomize_rep(m_rerandomizers[idx]);
1486 }
1487 }
1488
1489 /**
1490 * Return the random curve isomorphism parameter for the point table
1491 */
1492 const FieldElement& isomorphism() const { return m_isomorphism; }
1493
1494 private:
1495 bool m_seeded;
1496 std::array<uint8_t, Scalars * MaskBytes> m_masks{};
1497 std::array<FieldElement, Rerandomizations> m_rerandomizers{};
1498 FieldElement m_isomorphism = FieldElement::one();
1499};
1500
1501template <typename C, size_t WindowBits>
1503 public:
1504 static constexpr size_t Bits = C::Scalar::BITS;
1505
1506 explicit UnblindedScalarBits(const typename C::Scalar& scalar) { scalar.serialize_to(std::span{m_bytes}); }
1507
1508 size_t bits() const { return Bits; }
1509
1510 size_t get_window(size_t offset) const {
1511 // Extract a WindowBits sized window out of s, depending on offset.
1512 return read_window_bits<WindowBits>(std::span{m_bytes}, offset);
1513 }
1514
1515 private:
1516 std::array<uint8_t, C::Scalar::BYTES> m_bytes;
1517};
1518
1519/**
1520* Width W non-adjacent form of a public scalar
1521*
1522* Each digit is either zero or an odd integer with absolute value less
1523* than 2^(W-1). The recoding is variable time and the digits are stored
1524* in plain memory, so this is only usable when the scalar is public.
1525*/
1526template <typename C, size_t W>
1527class WnafScalar final {
1528 public:
1529 static_assert(W >= 2 && W <= 7);
1530
1531 // A wNAF has at most one more digit than the scalar has bits
1532 static constexpr size_t MaxDigits = C::Scalar::BITS + 1;
1533
1534 explicit WnafScalar(const typename C::Scalar& scalar) : m_digits{}, m_len(0) {
1535 using Word = typename C::W;
1536 constexpr size_t WordBits = WordInfo<Word>::bits;
1537 constexpr Word WindowMask = (static_cast<Word>(1) << W) - 1;
1538 constexpr Word HalfWindow = static_cast<Word>(1) << (W - 1);
1539
1540 // One extra word so that subtracting a negative digit cannot overflow
1541 std::array<Word, C::Words + 1> k = {};
1542 const auto sw = scalar.to_words();
1543 std::copy(sw.begin(), sw.end(), k.begin());
1544
1545 // Conditionals ok: this function is variable time
1546 size_t i = 0;
1547 for(;;) {
1548 bool k_is_zero = true;
1549 for(const auto w : k) {
1550 k_is_zero = k_is_zero && (w == 0);
1551 }
1552 if(k_is_zero) {
1553 break;
1554 }
1555
1556 size_t shift = 1;
1557
1558 if((k[0] & 1) == 1) {
1560
1561 const Word d = k[0] & WindowMask;
1562
1563 if(d >= HalfWindow) {
1564 // Negative digit (d - 2^W); subtracting it adds 2^W - d to k
1565 m_digits[i] = static_cast<int8_t>(static_cast<int>(d) - (1 << W));
1566 Word carry = (static_cast<Word>(1) << W) - d;
1567 for(size_t j = 0; j != k.size() && carry > 0; ++j) {
1568 const Word t = k[j] + carry;
1569 carry = (t < k[j]) ? 1 : 0;
1570 k[j] = t;
1571 }
1572 } else {
1573 m_digits[i] = static_cast<int8_t>(d);
1574 Word borrow = d;
1575 for(size_t j = 0; j != k.size() && borrow > 0; ++j) {
1576 const Word t = k[j] - borrow;
1577 borrow = (k[j] < borrow) ? 1 : 0;
1578 k[j] = t;
1579 }
1580 }
1581
1582 m_len = i + 1;
1583
1584 // k is now a multiple of 2^W, so the next W-1 digits are zero
1585 shift = W;
1586 }
1587
1588 for(size_t j = 0; j != k.size(); ++j) {
1589 k[j] >>= shift;
1590 if(j + 1 != k.size()) {
1591 k[j] |= k[j + 1] << (WordBits - shift);
1592 }
1593 }
1594
1595 i += shift;
1596 }
1597 }
1598
1599 /// Return the number of digits, ie one more than the index of the top nonzero digit
1600 size_t length() const { return m_len; }
1601
1602 int8_t digit(size_t i) const { return m_digits[i]; }
1603
1604 private:
1605 std::array<int8_t, MaxDigits> m_digits;
1606 size_t m_len;
1607};
1608
1609template <typename C, size_t W>
1611 public:
1612 typedef typename C::Scalar Scalar;
1613 typedef typename C::AffinePoint AffinePoint;
1614 typedef typename C::ProjectivePoint ProjectivePoint;
1615
1616 static constexpr size_t WindowBits = W;
1617 static_assert(WindowBits >= 1 && WindowBits <= 8);
1618
1619 // W+1 bit extraction windows for Booth recoding overlap
1621
1622 // +1 for Booth carry: if the top window's sign bit is set, the
1623 // carry propagates into an extra window
1625 m_table(basemul_booth_setup<C, WindowBits>(p, BlindedScalar::Bits + 1)) {}
1626
1628 const BlindingRandomness<BlindedScalar> blinding(rng);
1629 const BlindedScalar scalar(s, blinding);
1630 return basemul_booth_exec<C, WindowBits>(m_table, scalar, blinding);
1631 }
1632
1633 /**
1634 * Variable time multiplication, returning accum + s*P
1635 *
1636 * Only for use with public scalars, eg during signature verification
1637 */
1638 ProjectivePoint mul_vartime(const Scalar& s, const ProjectivePoint& accum) const {
1640 return basemul_booth_exec_vartime<C, WindowBits>(m_table, scalar, accum);
1641 }
1642
1643 private:
1644 std::vector<AffinePoint> m_table;
1645};
1646
1647// Number of full windows in a scalar of sb bits, and the size of the leading partial window
1648constexpr size_t booth_full_windows(size_t sb, size_t wb) {
1649 if(sb % wb == 0) {
1650 return (sb - 1) / wb;
1651 } else {
1652 return sb / wb;
1653 }
1654}
1655
1656constexpr size_t booth_initial_shift(size_t sb, size_t wb) {
1657 if(sb % wb == 0) {
1658 return wb;
1659 } else {
1660 return sb - (sb / wb) * wb;
1661 }
1662}
1663
1664/**
1665* Variable point multiplication
1666*
1667* This is a fixed window multiplication with Booth recoding, using a table
1668* [1*P, 2*P, ..., 2^W*P] with a shared Z coordinate. The scalar blinding,
1669* the accumulator re-randomizations, and the random curve isomorphism of
1670* the table all come from a single RNG request.
1671*/
1672template <typename C, size_t W>
1673typename C::ProjectivePoint varpoint_mul(const typename C::AffinePoint& p,
1674 const typename C::Scalar& s,
1675 RandomNumberGenerator& rng) {
1676 using ProjectivePoint = typename C::ProjectivePoint;
1677
1678 constexpr size_t TableBits = W;
1679 static_assert(TableBits >= 1 && TableBits <= 7);
1680
1681 constexpr size_t WindowBits = TableBits + 1;
1682
1683 using BlindedScalar = BlindedScalarBits<C, WindowBits + 1>;
1684 using Blinding = BlindingRandomness<BlindedScalar>;
1685
1686 // 2^W elements [1*P, 2*P, ..., 2^W*P]
1687 constexpr size_t TableSize = 1 << TableBits;
1688
1689 const Blinding blinding(rng);
1690 const SharedZPointTable<C> table(p, TableSize, C::A, blinding.isomorphism());
1691 const BlindedScalar bits(s, blinding);
1692
1693 const size_t scalar_bits = bits.bits();
1694 const size_t full_windows = booth_full_windows(scalar_bits + 1, WindowBits);
1695 const size_t initial_shift = booth_initial_shift(scalar_bits + 1, WindowBits);
1696
1697 BOTAN_DEBUG_ASSERT(full_windows * WindowBits + initial_shift == scalar_bits + 1);
1698 BOTAN_DEBUG_ASSERT(initial_shift > 0);
1699
1700 auto accum = ProjectivePoint::identity();
1701
1702 for(size_t i = 0; i != full_windows; ++i) {
1703 const size_t idx = scalar_bits - initial_shift - WindowBits * i;
1704
1705 const size_t w_i = bits.get_window(idx);
1706 const auto [tidx, tneg] = booth_recode<WindowBits>(w_i);
1707
1708 // Conditional ok: loop iteration count is public
1709 if(i == 0) {
1710 accum = ProjectivePoint::from_affine(table.ct_select(tidx));
1711 accum.conditional_assign(tneg, accum.negate());
1712 } else {
1713 accum = ProjectivePoint::add_or_sub_iso(accum, table.ct_select(tidx), tneg, table.a());
1714 }
1715
1716 accum = accum.dbl_n_iso(table.a(), WindowBits);
1717
1718 // Conditional ok: loop iteration count is public
1719 if(i < Blinding::Rerandomizations) {
1720 blinding.randomize_rep(accum, i);
1721 }
1722 }
1723
1724 // final window (note one bit shorter than previous reads)
1725 const size_t w_l = bits.get_window(0) & ((1 << WindowBits) - 1);
1726 const auto [tidx, tneg] = booth_recode<WindowBits>(w_l << 1);
1727 accum = ProjectivePoint::add_or_sub_iso(accum, table.ct_select(tidx), tneg, table.a());
1728
1729 // Map back from the isomorphic curve
1730 return ProjectivePoint(accum.x(), accum.y(), accum.z() * table.z());
1731}
1732
1733/**
1734* Constant time 2-ary multiplication x*P + y*Q
1735*
1736* Uses a joint table of all combinations of W bit windows of the two
1737* scalars, with a shared Z coordinate.
1738*/
1739template <typename C, size_t W>
1740typename C::ProjectivePoint varpoint_mul2(const typename C::AffinePoint& p,
1741 const typename C::Scalar& x,
1742 const typename C::AffinePoint& q,
1743 const typename C::Scalar& y,
1744 RandomNumberGenerator& rng) {
1745 // We look at W bits of each scalar per iteration
1746 static_assert(W >= 1 && W <= 4);
1747
1748 using BlindedScalar = BlindedScalarBits<C, W>;
1749
1750 const BlindingRandomness<BlindedScalar, 2> blinding(rng);
1751 const SharedZPointTable<C> table(mul2_setup<C, W>(p, q), C::A, C::FieldElement::one(), blinding.isomorphism());
1752 const BlindedScalar x_bits(x, blinding, 0);
1753 const BlindedScalar y_bits(y, blinding, 1);
1754
1755 return mul2_exec<C, W>(table, x_bits, y_bits, blinding);
1756}
1757
1758/**
1759* Variable time 2-ary multiplication x*G + y*Q
1760*
1761* A common use of 2-ary multiplication is when verifying the commitments
1762* of an elliptic curve signature. Since in this case the inputs are all
1763* public, there is no problem with variable time computation.
1764*
1765* The generator half is read out of the precomputed base point table and
1766* so needs no doublings. The variable point half uses a small table of odd
1767* multiples of Q, indexed by the width W non-adjacent form of y.
1768*/
1769template <typename C, size_t W>
1770class VartimeMul2Table final {
1771 public:
1772 static_assert(W >= 2 && W <= 7);
1773
1774 using Scalar = typename C::Scalar;
1775 using AffinePoint = typename C::AffinePoint;
1776 using ProjectivePoint = typename C::ProjectivePoint;
1777
1778 explicit VartimeMul2Table(const AffinePoint& q) : m_table(odd_multiples_setup_vartime<C, W>(q)) {}
1779
1780 template <size_t GW>
1782 const Scalar& x,
1783 const Scalar& y) const {
1784 // Conditional ok: this function is variable time
1785 if(x.is_zero().as_bool() && y.is_zero().as_bool()) {
1786 return ProjectivePoint::identity();
1787 }
1788
1789 return g_table.mul_vartime(x, this->mul_vartime(y));
1790 }
1791
1792 private:
1793 // Returns s*Q
1794 ProjectivePoint mul_vartime(const Scalar& s) const {
1795 const WnafScalar<C, W> naf(s);
1796
1797 size_t i = naf.length();
1798
1799 // Conditional ok: this function is variable time
1800 if(i == 0) {
1801 return ProjectivePoint::identity();
1802 }
1803
1804 const auto lookup = [&](int8_t d) -> const AffinePoint& {
1805 const size_t mag = static_cast<size_t>((d < 0) ? -d : d);
1806 return m_table[(mag - 1) / 2];
1807 };
1808
1809 --i;
1810 auto accum = ProjectivePoint::from_affine(lookup(naf.digit(i)));
1811 if(naf.digit(i) < 0) {
1812 accum = accum.negate();
1813 }
1814
1815 size_t pending_dbl = 0;
1816
1817 while(i > 0) {
1818 --i;
1819 pending_dbl += 1;
1820
1821 const int8_t d = naf.digit(i);
1822 if(d != 0) {
1823 accum = accum.dbl_n(pending_dbl);
1824 pending_dbl = 0;
1825 accum = ProjectivePoint::add_or_sub(accum, lookup(d), CT::Choice::from_int(static_cast<uint8_t>(d < 0)));
1826 }
1827 }
1828
1829 if(pending_dbl > 0) {
1830 accum = accum.dbl_n(pending_dbl);
1831 }
1832
1833 return accum;
1834 }
1835
1836 std::vector<AffinePoint> m_table;
1837};
1838
1839/**
1840* SSWU constant C2 - (B / (Z * A))
1841*
1842* See RFC 9380 section 6.6.2
1843*/
1844template <typename C>
1845const auto& SSWU_C2()
1846 requires C::ValidForSswuHash
1847{
1848 // TODO(Botan4) Make this a constexpr once compilers have caught up
1849 static const typename C::FieldElement C2 = C::B * invert_field_element<C>(C::SSWU_Z * C::A);
1850 return C2;
1851}
1852
1853/**
1854* SSWU constant C1 - (-B / A)
1855*
1856* See RFC 9380 section 6.6.2
1857*/
1858template <typename C>
1859const auto& SSWU_C1()
1860 requires C::ValidForSswuHash
1861{
1862 // TODO(Botan4) Make this a constexpr
1863 // We derive it from C2 to avoid a second inversion
1864 static const typename C::FieldElement C1 = (SSWU_C2<C>() * C::SSWU_Z).negate();
1865 return C1;
1866}
1867
1868/**
1869* Map to curve (SSWU)
1870*
1871* See RFC 9380 ("Hashing to Elliptic Curves") section 6.6.2
1872*/
1873template <typename C>
1874inline auto map_to_curve_sswu(const typename C::FieldElement& u) -> typename C::AffinePoint {
1875 CT::poison(u);
1876 const auto z_u2 = C::SSWU_Z * u.square(); // z * u^2
1877 const auto z2_u4 = z_u2.square();
1878 const auto tv1 = invert_field_element<C>(z2_u4 + z_u2);
1879 auto x1 = SSWU_C1<C>() * (C::FieldElement::one() + tv1);
1880 x1.conditional_assign(tv1.is_zero(), SSWU_C2<C>());
1881 const auto x2 = z_u2 * x1;
1882
1883 // By design one of gx1 and gx2 must be a quadratic residue
1886
1887 const auto use_y1 = y1.has_value();
1888
1889 const auto x = C::FieldElement::choose(use_y1, x1, x2);
1890 const auto y =
1891 C::FieldElement::choose(use_y1, y1.value_or(C::FieldElement::zero()), y2.value_or(C::FieldElement::zero()));
1892
1893 auto pt = typename C::AffinePoint(x, y.correct_sign(u.is_even()));
1894
1895 CT::unpoison(pt);
1896 return pt;
1897}
1898
1899/**
1900* Hash to curve (SSWU); RFC 9380
1901*
1902* This is the Simplified Shallue-van de Woestijne-Ulas (SSWU) map.
1903*
1904* The parameter expand_message models the function of RFC 9380 and is provided
1905* by higher levels. For the curves implemented here it will typically be XMD,
1906* but could also be an XOF (expand_message_xof) or a MHF like Argon2.
1907*
1908* For details see RFC 9380 sections 3, 5.2 and 6.6.2.
1909*/
1910template <typename C, bool RO, std::invocable<std::span<uint8_t>> ExpandMsg>
1911 requires C::ValidForSswuHash
1912inline auto hash_to_curve_sswu(const ExpandMsg& expand_message)
1913 -> std::conditional_t<RO, typename C::ProjectivePoint, typename C::AffinePoint> {
1914 constexpr size_t SecurityLevel = (C::OrderBits + 1) / 2;
1915 constexpr size_t L = (C::PrimeFieldBits + SecurityLevel + 7) / 8;
1916 constexpr size_t Cnt = RO ? 2 : 1;
1917
1918 std::array<uint8_t, L * Cnt> uniform_bytes = {};
1919 expand_message(uniform_bytes);
1920
1921 if constexpr(RO) {
1922 const auto u0 = C::FieldElement::from_wide_bytes(std::span<const uint8_t, L>(uniform_bytes.data(), L));
1923 const auto u1 = C::FieldElement::from_wide_bytes(std::span<const uint8_t, L>(uniform_bytes.data() + L, L));
1924
1925 auto accum = C::ProjectivePoint::from_affine(map_to_curve_sswu<C>(u0));
1926 accum += map_to_curve_sswu<C>(u1);
1927 return accum;
1928 } else {
1929 const auto u = C::FieldElement::from_wide_bytes(std::span<const uint8_t, L>(uniform_bytes.data(), L));
1930 return map_to_curve_sswu<C>(u);
1931 }
1932}
1933
1934} // namespace Botan
1935
1936#endif
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
#define BOTAN_STATE_CHECK(expr)
Definition assert.h:49
constexpr Self negate() const
constexpr void serialize_to(std::span< uint8_t, Self::BYTES > bytes) const
AffineCurvePoint(Self &&other)=default
constexpr void _const_time_unpoison() const
static constexpr Self identity()
constexpr void _const_time_poison() const
AffineCurvePoint & operator=(const Self &other)=default
constexpr const FieldElement & y() const
static constexpr Self identity(const Self &)
constexpr void conditional_assign(CT::Choice cond, const Self &pt)
AffineCurvePoint< FieldElement > Self
AffineCurvePoint & operator=(Self &&other)=default
constexpr AffineCurvePoint(const FieldElement &x, const FieldElement &y)
static constexpr auto ct_select(std::span< const Self > pts, size_t idx)
constexpr CT::Choice is_identity() const
AffineCurvePoint(const Self &other)=default
constexpr const FieldElement & x() const
static constexpr size_t BYTES
BlindedScalarBits(const BlindedScalarBits &other)=delete
BlindedScalarBits & operator=(BlindedScalarBits &&other)=delete
size_t get_window(size_t offset) const
BlindedScalarBits(BlindedScalarBits &&other)=delete
BlindedScalarBits(const typename C::Scalar &scalar, const Randomness &randomness, size_t idx=0)
BlindedScalarBits & operator=(const BlindedScalarBits &other)=delete
const FieldElement & isomorphism() const
BlindingRandomness(RandomNumberGenerator &rng)
static constexpr size_t Rerandomizations
Each multiplication re-randomizes the accumulator this many times.
void randomize_rep(typename C::ProjectivePoint &pt, size_t idx) const
std::span< const uint8_t, MaskBytes > mask(size_t idx) const
Helper class to ease in-place marshalling of concatenated fixed-length values.
constexpr T into_bitmask() const
Definition ct_utils.h:291
static constexpr Choice from_int(T v)
Definition ct_utils.h:268
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:397
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:447
constexpr Choice has_value() const
Return true if this Option contains a value.
Definition ct_utils.h:669
constexpr T value_or(T other) const
Definition ct_utils.h:693
static constexpr int8_t Z
static constexpr auto GXW
static constexpr auto GYW
static constexpr auto NW
static constexpr size_t PrimeFieldBits
static constexpr FieldElement SSWU_Z
static constexpr auto PW
IntMod< MontgomeryRep< ScalarParams > > Scalar
static constexpr bool ValidForSswuHash
static constexpr FieldElement x3_ax_b(const FieldElement &x)
static constexpr FieldElement A
static constexpr bool OrderIsLessThanField
static constexpr size_t Words
AffineCurvePoint< FieldElement > AffinePoint
ProjectiveCurvePoint< FieldElement, Params > ProjectivePoint
static constexpr size_t OrderBits
static constexpr auto AW
static constexpr AffinePoint G
IntMod< FieldRep< FieldParams > > FieldElement
static constexpr FieldElement B
Self div2() const
static constexpr void conditional_assign(Self &x, Self &y, CT::Choice cond, const Self &nx, const Self &ny)
static constexpr std::optional< Self > from_wide_bytes_varlen(std::span< const uint8_t > bytes)
constexpr void serialize_to(std::span< uint8_t, Self::BYTES > bytes) const
constexpr CT::Choice is_zero() const
static constexpr void _invert_vartime_div2_helper(Self &a, Self &x)
std::array< W, L > stash_value() const
constexpr CT::Choice is_nonzero() const
constexpr BOTAN_FORCE_INLINE Self & operator*=(const Self &other)
~IntMod()=default
constexpr void _const_time_unpoison() const
IntMod(const Self &other)=default
friend constexpr BOTAN_FORCE_INLINE Self operator*(const Self &a, const Self &b)
constexpr Self correct_sign(CT::Choice even) const
IntMod< Rep > Self
constexpr void conditional_assign(CT::Choice cond, const Self &nx)
constexpr Self negate() const
constexpr Self invert_vartime() const
static consteval Self constant(int8_t x)
constexpr std::array< W, Self::N > to_words() const
constexpr BOTAN_FORCE_INLINE Self mul2() const
Return (*this) multiplied by 2.
static constexpr Self zero()
static Self from_stash(const std::array< W, L > &stash)
IntMod(Self &&other)=default
static std::optional< Self > deserialize(std::span< const uint8_t > bytes)
constexpr Self mul8() const
Return (*this) multiplied by 8.
constexpr Self pow_vartime(const std::array< W, N > &exp) const
constexpr void square_n(size_t n)
constexpr CT::Option< Self > sqrt() const
constexpr void _const_time_poison() const
constexpr BOTAN_FORCE_INLINE Self square() const
static constexpr Self one()
static constexpr Self choose(CT::Choice choice, const Self &x, const Self &y)
constexpr CT::Choice operator==(const Self &other) const
constexpr Self invert() const
constexpr Self mul3() const
Return (*this) multiplied by 3.
friend constexpr BOTAN_FORCE_INLINE Self operator+(const Self &a, const Self &b)
static constexpr void conditional_assign(Self &x, Self &y, Self &z, CT::Choice cond, const Self &nx, const Self &ny, const Self &nz)
constexpr CT::Choice is_even() const
IntMod & operator=(const Self &other)=default
static constexpr Self from_words(std::array< W, L > w)
friend constexpr BOTAN_FORCE_INLINE Self operator-(const Self &a, const Self &b)
IntMod & operator=(Self &&other)=default
constexpr Self mul4() const
Return (*this) multiplied by 4.
static constexpr Self from_wide_bytes(std::span< const uint8_t, L > bytes)
static Self random(RandomNumberGenerator &rng)
constexpr CT::Choice is_one() const
static constexpr void conditional_swap(CT::Choice cond, Self &x, Self &y)
constexpr CT::Choice operator!=(const Self &other) const
constexpr IntMod()
static constexpr std::array< W, N > wide_to_rep(const std::array< W, 2 *N > &x)
static constexpr auto P_dash
static constexpr std::array< W, N > from_rep(const std::array< W, N > &z)
static constexpr size_t N
static constexpr auto R3
static constexpr auto P
MontgomeryRep< Params > Self
static constexpr auto R1
static constexpr std::array< W, N > one()
static constexpr auto R2
static constexpr std::array< W, N > to_rep(const std::array< W, N > &x)
static constexpr std::array< W, N > redc(const std::array< W, 2 *N > &z)
static constexpr size_t WindowBits
ProjectivePoint mul_vartime(const Scalar &s, const ProjectivePoint &accum) const
BlindedScalarBits< C, WindowBits+1 > BlindedScalar
PrecomputedBaseMulTable(const AffinePoint &p)
C::ProjectivePoint ProjectivePoint
ProjectivePoint mul(const Scalar &s, RandomNumberGenerator &rng) const
static constexpr Self add_or_sub(const Self &a, const AffinePoint &b, CT::Choice sub)
ProjectiveCurvePoint< FieldElement, Params > Self
ProjectiveCurvePoint(const Self &other)=default
friend constexpr Self operator+(const AffinePoint &a, const Self &b)
ProjectiveCurvePoint(Self &&other)=default
static constexpr bool A_is_zero
ProjectiveCurvePoint & operator=(Self &&other)=default
constexpr Self dbl_n_iso(const FieldElement &a, size_t n) const
constexpr const FieldElement & x() const
friend constexpr Self operator-(const Self &a, const Self &b)
friend constexpr Self operator+(const Self &a, const AffinePoint &b)
static constexpr bool A_is_minus_3
ProjectiveCurvePoint & operator=(const Self &other)=default
static constexpr Self from_affine(const AffinePoint &pt)
static constexpr Self add(const Self &a, const Self &b)
constexpr Self & operator+=(const AffinePoint &other)
void randomize_rep(const FieldElement &r)
constexpr void conditional_assign(CT::Choice cond, const Self &pt)
constexpr void _const_time_unpoison() const
constexpr const FieldElement & z() const
constexpr const FieldElement & y() const
constexpr CT::Choice is_identity() const
constexpr Self negate() const
static constexpr Self add_or_sub_iso(const Self &a, const AffinePoint &b, CT::Choice sub, const FieldElement &curve_a)
AffineCurvePoint< FieldElement > AffinePoint
friend constexpr Self operator+(const Self &a, const Self &b)
static constexpr FieldElement A
constexpr ProjectiveCurvePoint(const FieldElement &x, const FieldElement &y)
static constexpr std::pair< Self, FieldElement > add_mixed_h(const Self &a, const AffinePoint &b)
static constexpr Self add_mixed(const Self &a, const AffinePoint &b)
constexpr Self dbl_iso(const FieldElement &a) const
static constexpr Self add_mixed_iso(const Self &a, const AffinePoint &b, const FieldElement &curve_a)
static constexpr Self identity()
constexpr void _const_time_poison() const
constexpr Self dbl_n(size_t n) const
constexpr ProjectiveCurvePoint(const FieldElement &x, const FieldElement &y, const FieldElement &z)
constexpr Self dbl() const
constexpr Self & operator+=(const Self &other)
void randomize(std::span< uint8_t > output)
Definition rng.h:86
const FieldElement & z() const
AffinePoint ct_select(size_t idx) const
const FieldElement & a() const
consteval StringLiteral(const char(&str)[N])
static constexpr size_t Bits
UnblindedScalarBits(const typename C::Scalar &scalar)
size_t get_window(size_t offset) const
ProjectivePoint mul2_vartime(const PrecomputedBaseMulTable< C, GW > &g_table, const Scalar &x, const Scalar &y) const
VartimeMul2Table(const AffinePoint &q)
typename C::AffinePoint AffinePoint
typename C::Scalar Scalar
typename C::ProjectivePoint ProjectivePoint
WnafScalar(const typename C::Scalar &scalar)
static constexpr size_t MaxDigits
size_t length() const
Return the number of digits, ie one more than the index of the top nonzero digit.
int8_t digit(size_t i) const
#define BOTAN_FORCE_INLINE
Definition compiler.h:86
constexpr void poison_all(const Ts &... ts)
Definition ct_utils.h:201
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
Definition ct_utils.h:803
constexpr void unpoison_all(const Ts &... ts)
Definition ct_utils.h:207
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:67
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
Definition ct_utils.h:790
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:56
std::string lookup(const OID &oid)
Definition oids.h:87
constexpr auto bigint_add2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:98
auto map_to_curve_sswu(const typename C::FieldElement &u) -> typename C::AffinePoint
consteval std::array< W, N > shanks_tonelli_c3(const std::array< W, N > &c2)
C::ProjectivePoint basemul_booth_exec(std::span< const typename C::AffinePoint > table, const BlindedScalar &scalar, const Blinding &blinding)
consteval std::array< W, N > p_plus_1_over_4(const std::array< W, N > &p)
constexpr auto bytes_to_words(std::span< const uint8_t, L > bytes)
Definition mp_core.h:1255
constexpr W shift_left(std::array< W, N > &x)
Definition mp_core.h:888
constexpr auto word_sub(W x, W y, W *carry) -> W
Definition mp_asmi.h:355
consteval std::array< W, N > p_minus_1_over_2(const std::array< W, N > &p)
constexpr CT::Option< typename C::FieldElement > sqrt_field_element(const typename C::FieldElement &fe)
constexpr auto word_add(W x, W y, W *carry) -> W
Definition mp_asmi.h:260
C::ProjectivePoint varpoint_mul(const typename C::AffinePoint &p, const typename C::Scalar &s, RandomNumberGenerator &rng)
constexpr ProjectivePoint dbl_n_generic(const ProjectivePoint &pt, const FieldElement &A, size_t n)
constexpr void comba_sqr(W z[2 *N], const W x[N])
Definition mp_core.h:1017
consteval auto shanks_tonelli_c4(const std::array< W, N > &p_minus_1_over_2) -> Z
constexpr size_t read_window_bits(std::span< const W, N > words, size_t offset)
Definition mp_core.h:1284
constexpr ProjectivePoint dbl_a_minus_3(const ProjectivePoint &pt)
constexpr size_t scalar_blinding_bits(size_t scalar_bits)
Definition pcurves_mul.h:42
constexpr std::pair< size_t, CT::Choice > booth_recode(size_t x, size_t window_bits)
Definition mp_core.h:1312
constexpr void comba_mul(W z[2 *N], const W x[N], const W y[N])
Definition mp_core.h:981
const auto & SSWU_C1()
consteval std::array< W, N > p_div_2_plus_1(const std::array< W, N > &p)
constexpr auto monty_redc(const std::array< W, 2 *N > &z, const std::array< W, N > &p, W p_dash) -> std::array< W, N >
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:196
constexpr auto monty_inverse(W a) -> W
Definition mp_core.h:866
C::ProjectivePoint mul2_exec(const SharedZPointTable< C > &table, const BlindedScalar &x, const BlindedScalar &y, const Blinding &blinding)
constexpr ProjectivePoint dbl_n_a_zero(const ProjectivePoint &pt, size_t n)
constexpr ProjectivePoint dbl_a_zero(const ProjectivePoint &pt)
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
std::vector< typename C::ProjectivePoint > mul2_setup(const typename C::AffinePoint &p, const typename C::AffinePoint &q)
std::vector< typename C::AffinePoint > odd_multiples_setup_vartime(const typename C::AffinePoint &p)
consteval std::array< W, N > mul_mod(const std::array< W, N > &x, const std::array< W, N > &y, const std::array< W, N > &p)
constexpr int32_t bigint_cmp(const W x[], size_t x_size, const W y[], size_t y_size)
Definition mp_core.h:463
std::vector< typename C::AffinePoint > basemul_booth_setup(const typename C::AffinePoint &p, size_t max_scalar_bits)
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
Definition mp_core.h:229
constexpr auto invert_field_element(const typename C::FieldElement &fe)
void secure_zeroize_buffer(void *ptr, size_t n)
Definition mem_utils.cpp:28
BOTAN_FORCE_INLINE constexpr T choose(T mask, T a, T b)
Definition bit_ops.h:217
C::ProjectivePoint basemul_booth_exec_vartime(std::span< const typename C::AffinePoint > table, const ScalarBits &scalar, typename C::ProjectivePoint accum)
constexpr ProjectivePoint point_add_or_sub_mixed(const ProjectivePoint &a, const AffinePoint &b, CT::Choice sub, const FieldElement &one, const FieldElement &curve_a)
constexpr ProjectivePoint dbl_n_a_minus_3(const ProjectivePoint &pt, size_t n)
auto hash_to_curve_sswu(const ExpandMsg &expand_message) -> std::conditional_t< RO, typename C::ProjectivePoint, typename C::AffinePoint >
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495
constexpr auto bigint_ct_is_lt(const W x[], size_t x_size, const W y[], size_t y_size, bool lt_or_equal=false) -> CT::Mask< W >
Definition mp_core.h:510
C::ProjectivePoint varpoint_mul2(const typename C::AffinePoint &p, const typename C::Scalar &x, const typename C::AffinePoint &q, const typename C::Scalar &y, RandomNumberGenerator &rng)
constexpr size_t booth_full_windows(size_t sb, size_t wb)
constexpr size_t booth_initial_shift(size_t sb, size_t wb)
constexpr auto hex_to_words(const char(&s)[N])
Definition mp_core.h:921
constexpr ProjectivePoint dbl_generic(const ProjectivePoint &pt, const FieldElement &A)
consteval std::array< W, N > p_minus(const std::array< W, N > &p)
constexpr ProjectivePoint point_add(const ProjectivePoint &a, const ProjectivePoint &b)
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131
consteval size_t count_bits(const std::array< W, N > &p)
constexpr auto store_be(ParamTs &&... params)
Definition loadstor.h:745
constexpr std::pair< ProjectivePoint, FieldElement > point_add_mixed_h(const ProjectivePoint &a, const AffinePoint &b, const FieldElement &one, const FieldElement &curve_a)
constexpr auto monty_redc_pdash1(const std::array< W, 2 *N > &z, const std::array< W, N > &p) -> std::array< W, N >
constexpr ProjectivePoint point_add_mixed(const ProjectivePoint &a, const AffinePoint &b, const FieldElement &one, const FieldElement &curve_a)
consteval std::array< W, N > montygomery_r(const std::array< W, N > &p)
constexpr W shift_right(std::array< W, N > &x)
Definition mp_core.h:904
consteval std::pair< size_t, std::array< W, N > > shanks_tonelli_c1c2(const std::array< W, N > &p)
const auto & SSWU_C2()
static constexpr auto P
static constexpr size_t N