Botan 3.14.1
Crypto and TLS for C&
Botan::IntMod< Rep > Class Template Referencefinal

#include <pcurves_impl.h>

Public Types

using Self = IntMod<Rep>

Public Member Functions

constexpr void _const_time_poison () const
constexpr void _const_time_unpoison () const
constexpr void conditional_assign (CT::Choice cond, const Self &nx)
constexpr Self correct_sign (CT::Choice even) const
Self div2 () const
constexpr IntMod ()
 IntMod (const Self &other)=default
 IntMod (Self &&other)=default
constexpr Self invert () const
constexpr Self invert_vartime () const
constexpr CT::Choice is_even () const
constexpr CT::Choice is_nonzero () const
constexpr CT::Choice is_one () const
constexpr CT::Choice is_zero () const
constexpr BOTAN_FORCE_INLINE Self mul2 () const
 Return (*this) multiplied by 2.
constexpr Self mul3 () const
 Return (*this) multiplied by 3.
constexpr Self mul4 () const
 Return (*this) multiplied by 4.
constexpr Self mul8 () const
 Return (*this) multiplied by 8.
constexpr Self negate () const
constexpr CT::Choice operator!= (const Self &other) const
constexpr BOTAN_FORCE_INLINE Self & operator*= (const Self &other)
IntMod & operator= (const Self &other)=default
IntMod & operator= (Self &&other)=default
constexpr CT::Choice operator== (const Self &other) const
constexpr Self pow_vartime (const std::array< W, N > &exp) const
constexpr void serialize_to (std::span< uint8_t, Self::BYTES > bytes) const
constexpr CT::Option< Self > sqrt () const
constexpr BOTAN_FORCE_INLINE Self square () const
constexpr void square_n (size_t n)
template<size_t L>
std::array< W, L > stash_value () const
constexpr std::array< W, Self::N > to_words () const
 ~IntMod ()=default

Static Public Member Functions

static constexpr void _invert_vartime_div2_helper (Self &a, Self &x)
static constexpr Self choose (CT::Choice choice, const Self &x, const Self &y)
static constexpr void conditional_assign (Self &x, Self &y, CT::Choice cond, const Self &nx, const Self &ny)
static constexpr void conditional_assign (Self &x, Self &y, Self &z, CT::Choice cond, const Self &nx, const Self &ny, const Self &nz)
static constexpr void conditional_swap (CT::Choice cond, Self &x, Self &y)
static consteval Self constant (int8_t x)
static std::optional< Self > deserialize (std::span< const uint8_t > bytes)
template<size_t L>
static Self from_stash (const std::array< W, L > &stash)
template<size_t L>
static constexpr Self from_wide_bytes (std::span< const uint8_t, L > bytes)
static constexpr std::optional< Self > from_wide_bytes_varlen (std::span< const uint8_t > bytes)
template<size_t L>
static constexpr Self from_words (std::array< W, L > w)
static constexpr Self one ()
static Self random (RandomNumberGenerator &rng)
static constexpr Self zero ()

Static Public Attributes

static constexpr size_t BITS = count_bits(P)
static constexpr size_t BYTES = (BITS + 7) / 8
static constexpr auto P_MOD_4 = P[0] % 4

Friends

constexpr BOTAN_FORCE_INLINE Self operator* (const Self &a, const Self &b)
constexpr BOTAN_FORCE_INLINE Self operator+ (const Self &a, const Self &b)
constexpr BOTAN_FORCE_INLINE Self operator- (const Self &a, const Self &b)

Detailed Description

template<typename Rep>
class Botan::IntMod< Rep >

Integers Modulo (a Prime)

This is used to store and manipulate integers modulo the field (for the affine x/y or Jacobian x/y/z coordinates) and group order (for scalar arithmetic).

This class is parameterized by Rep which handles the modular reduction step, as well (if required) any conversions into or out of the inner representation. This is primarily for Montgomery arithmetic; specialized reduction methods instead keep the integer in the "standard" form.

Most of the code in this class does work for arbitrary moduli. However at least div2 and invert make assumptions that the modulus is prime.

Any function that does not contain "vartime" or equivalent in the name is written such that it does not leak information about its arguments via control flow or memory access patterns.

Definition at line 165 of file pcurves_impl.h.

Member Typedef Documentation

◆ Self

template<typename Rep>
using Botan::IntMod< Rep >::Self = IntMod<Rep>

Definition at line 179 of file pcurves_impl.h.

Constructor & Destructor Documentation

◆ IntMod() [1/3]

template<typename Rep>
Botan::IntMod< Rep >::IntMod ( )
inlineconstexpr

Definition at line 182 of file pcurves_impl.h.

182: m_val({}) {}

◆ IntMod() [2/3]

template<typename Rep>
Botan::IntMod< Rep >::IntMod ( const Self & other)
default

◆ IntMod() [3/3]

template<typename Rep>
Botan::IntMod< Rep >::IntMod ( Self && other)
default

◆ ~IntMod()

template<typename Rep>
Botan::IntMod< Rep >::~IntMod ( )
default

Member Function Documentation

◆ _const_time_poison()

template<typename Rep>
void Botan::IntMod< Rep >::_const_time_poison ( ) const
inlineconstexpr

Definition at line 891 of file pcurves_impl.h.

891{ CT::poison(m_val); }
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:56

◆ _const_time_unpoison()

template<typename Rep>
void Botan::IntMod< Rep >::_const_time_unpoison ( ) const
inlineconstexpr

Definition at line 893 of file pcurves_impl.h.

893{ CT::unpoison(m_val); }
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:67

◆ _invert_vartime_div2_helper()

template<typename Rep>
constexpr void Botan::IntMod< Rep >::_invert_vartime_div2_helper ( Self & a,
Self & x )
inlinestaticconstexpr

Helper for variable time BEEA

Note this function assumes that its arguments are in the standard domain, not the Montgomery domain. invert_vartime converts its argument out of Montgomery, and then back to Montgomery when returning the result.

Definition at line 549 of file pcurves_impl.h.

549 {
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 }
constexpr auto bigint_add2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:98
consteval std::array< W, N > p_div_2_plus_1(const std::array< W, N > &p)
constexpr W shift_right(std::array< W, N > &x)
Definition mp_core.h:904

Referenced by Botan::IntMod< MontgomeryRep< ScalarParams > >::invert_vartime().

◆ choose()

template<typename Rep>
constexpr Self Botan::IntMod< Rep >::choose ( CT::Choice choice,
const Self & x,
const Self & y )
inlinestaticconstexpr

Return x or y depending on if choice is set or not

Definition at line 258 of file pcurves_impl.h.

258 {
259 auto r = y;
261 return r;
262 }
constexpr void conditional_assign(CT::Choice cond, const Self &nx)

Referenced by Botan::IntMod< MontgomeryRep< ScalarParams > >::correct_sign().

◆ conditional_assign() [1/3]

template<typename Rep>
void Botan::IntMod< Rep >::conditional_assign ( CT::Choice cond,
const Self & nx )
inlineconstexpr

Conditional assignment

If cond is true, sets *this to nx

Definition at line 369 of file pcurves_impl.h.

369 {
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 }
BOTAN_FORCE_INLINE constexpr T choose(T mask, T a, T b)
Definition bit_ops.h:217

Referenced by Botan::IntMod< MontgomeryRep< ScalarParams > >::choose().

◆ conditional_assign() [2/3]

template<typename Rep>
constexpr void Botan::IntMod< Rep >::conditional_assign ( Self & x,
Self & y,
CT::Choice cond,
const Self & nx,
const Self & ny )
inlinestaticconstexpr

Conditional assignment

If cond is true, sets x to nx and y to ny

Definition at line 382 of file pcurves_impl.h.

382 {
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 }

◆ conditional_assign() [3/3]

template<typename Rep>
constexpr void Botan::IntMod< Rep >::conditional_assign ( Self & x,
Self & y,
Self & z,
CT::Choice cond,
const Self & nx,
const Self & ny,
const Self & nz )
inlinestaticconstexpr

Conditional assignment

If cond is true, sets x to nx, y to ny, and z to nz

Definition at line 396 of file pcurves_impl.h.

397 {
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 }

◆ conditional_swap()

template<typename Rep>
constexpr void Botan::IntMod< Rep >::conditional_swap ( CT::Choice cond,
Self & x,
Self & y )
inlinestaticconstexpr

Conditional swap

If cond is true, swaps the values of x and y

Definition at line 412 of file pcurves_impl.h.

412 {
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 }

◆ constant()

template<typename Rep>
consteval Self Botan::IntMod< Rep >::constant ( int8_t x)
inlinestaticconsteval

Create a small compile time constant

Notice this function is consteval, and so can only be called at compile time

Definition at line 884 of file pcurves_impl.h.

884 {
886 v[0] = (x >= 0) ? x : -x;
887 const auto s = Self::from_words(v);
888 return (x >= 0) ? s : s.negate();
889 }
constexpr Self negate() const
static constexpr Self from_words(std::array< W, L > w)

◆ correct_sign()

template<typename Rep>
Self Botan::IntMod< Rep >::correct_sign ( CT::Choice even) const
inlineconstexpr

Return either this or -this depending on which is even

Definition at line 250 of file pcurves_impl.h.

250 {
251 const auto flip = (even != this->is_even());
252 return Self::choose(flip, this->negate(), *this);
253 }
static constexpr Self choose(CT::Choice choice, const Self &x, const Self &y)
constexpr CT::Choice is_even() const

◆ deserialize()

template<typename Rep>
std::optional< Self > Botan::IntMod< Rep >::deserialize ( std::span< const uint8_t > bytes)
inlinestatic

Deserialize an integer from a bytestring

Returns nullopt if the input is an encoding greater than or equal P

This function also requires that the bytestring be exactly of the expected length; short bytestrings, or a long bytestring with leading zero bytes, are also rejected.

Definition at line 794 of file pcurves_impl.h.

794 {
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 }
static constexpr size_t BYTES
constexpr auto bytes_to_words(std::span< const uint8_t, L > bytes)
Definition mp_core.h:1255
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

◆ div2()

template<typename Rep>
Self Botan::IntMod< Rep >::div2 ( ) const
inline

Return the value of this divided by 2

Definition at line 304 of file pcurves_impl.h.

304 {
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 }
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:397
IntMod< Rep > Self
constexpr auto word_add(W x, W y, W *carry) -> W
Definition mp_asmi.h:260

◆ from_stash()

template<typename Rep>
template<size_t L>
Self Botan::IntMod< Rep >::from_stash ( const std::array< W, L > & stash)
inlinestatic

Restore the value previously stashed

See pcurves_wrap.h for why/where this is used

Definition at line 776 of file pcurves_impl.h.

776 {
777 static_assert(L >= N);
779 for(size_t i = 0; i != N; ++i) {
780 val[i] = stash[i];
781 }
782 return Self(val);
783 }

◆ from_wide_bytes()

template<typename Rep>
template<size_t L>
constexpr Self Botan::IntMod< Rep >::from_wide_bytes ( std::span< const uint8_t, L > bytes)
inlinestaticconstexpr

Modular reduce a larger input

This takes a bytestring that is at most twice the length of the modulus, and modular reduces it.

Definition at line 818 of file pcurves_impl.h.

818 {
819 static_assert(8 * L <= 2 * Self::BITS);
823 }
static constexpr size_t BITS
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144

◆ from_wide_bytes_varlen()

template<typename Rep>
constexpr std::optional< Self > Botan::IntMod< Rep >::from_wide_bytes_varlen ( std::span< const uint8_t > bytes)
inlinestaticconstexpr

Modular reduce a larger input

This takes a bytestring that is at most twice the length of the modulus, and modular reduces it.

Definition at line 831 of file pcurves_impl.h.

831 {
832 // Conditional ok: input length is public
833 if(bytes.size() > 2 * Self::BYTES) {
834 return {};
835 }
836
838 copy_mem(std::span{padded_bytes}.last(bytes.size()), bytes);
840 }

◆ from_words()

template<typename Rep>
template<size_t L>
constexpr Self Botan::IntMod< Rep >::from_words ( std::array< W, L > w)
inlinestaticconstexpr

Consume an array of words and convert it to an IntMod

This handles the Montgomery conversion, if required.

Note that this function assumes that w represents an integer that is less than the modulus.

Definition at line 213 of file pcurves_impl.h.

213 {
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 }

Referenced by Botan::IntMod< MontgomeryRep< ScalarParams > >::constant(), and Botan::IntMod< MontgomeryRep< ScalarParams > >::deserialize().

◆ invert()

template<typename Rep>
Self Botan::IntMod< Rep >::invert ( ) const
inlineconstexpr

Returns the modular inverse, or 0 if no modular inverse exists.

If the modulus is prime the only value that has no modular inverse is 0.

This uses Fermat's little theorem, and so assumes that p is prime

Since P is public, P-2 is as well, thus using a variable time modular exponentiation routine is safe.

This function is only used if the curve does not provide an addition chain for specific inversions (see for example pcurves_secp256r1.cpp)

Definition at line 540 of file pcurves_impl.h.

540{ return pow_vartime(Self::P_MINUS_2); }
constexpr Self pow_vartime(const std::array< W, N > &exp) const

◆ invert_vartime()

template<typename Rep>
Self Botan::IntMod< Rep >::invert_vartime ( ) const
inlineconstexpr

Returns the modular inverse, or 0 if no modular inverse exists.

This function assumes that the modulus is prime

This function does something a bit nasty and converts from the normal representation (for scalars, Montgomery) into the "standard" representation. This relies on the fact that we aren't doing any multiplications within this function, just additions, subtractions, division by 2, and comparisons.

The reason is there is no good way to compare integers in the Montgomery domain; we could convert out for each comparison but this is slower than just doing a constant-time inversion.

This is loosely based on the algorithm BoringSSL uses in BN_mod_inverse_odd, which is a variant of the Binary Extended Euclidean algorithm. It is optimized somewhat by taking advantage of a couple of observations.

In the first two iterations, the control flow is known because a is less than the modulus and not zero, and we know that the modulus is odd. So we peel out those iterations. This also avoids having to initialize a with the modulus, because we instead set it directly to what the first loop iteration would have updated it to. This ensures that all values are always less than or equal to the modulus.

Then we take advantage of the fact that in each iteration of the loop, at the end we update either b/x or a/y, but never both. In the next iteration of the loop, we attempt to modify b/x or a/y depending on the low zero bits of b or a. But if a or b were not updated in the previous iteration than they will still be odd, and nothing will happen. Instead update just the pair we need to update, right after writing to b/x or a/y resp.

Definition at line 600 of file pcurves_impl.h.

600 {
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 }
constexpr CT::Choice is_zero() const
static constexpr void _invert_vartime_div2_helper(Self &a, Self &x)
constexpr std::array< W, Self::N > to_words() const
static constexpr Self zero()
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

◆ is_even()

template<typename Rep>
CT::Choice Botan::IntMod< Rep >::is_even ( ) const
inlineconstexpr

Check in constant time if this is an even integer

Definition at line 242 of file pcurves_impl.h.

242 {
243 auto v = Rep::from_rep(m_val);
244 return !CT::Choice::from_int(v[0] & 0x01);
245 }
static constexpr Choice from_int(T v)
Definition ct_utils.h:268

Referenced by Botan::IntMod< MontgomeryRep< ScalarParams > >::correct_sign().

◆ is_nonzero()

template<typename Rep>
CT::Choice Botan::IntMod< Rep >::is_nonzero ( ) const
inlineconstexpr

Check in constant time if this not equal to zero

Definition at line 232 of file pcurves_impl.h.

232{ return !is_zero(); }

◆ is_one()

template<typename Rep>
CT::Choice Botan::IntMod< Rep >::is_one ( ) const
inlineconstexpr

Check in constant time if this equal to one

Definition at line 237 of file pcurves_impl.h.

237{ return (*this == Self::one()); }
static constexpr Self one()

◆ is_zero()

template<typename Rep>
CT::Choice Botan::IntMod< Rep >::is_zero ( ) const
inlineconstexpr

Check in constant time if this is equal to zero

Definition at line 227 of file pcurves_impl.h.

227{ return CT::all_zeros(m_val.data(), m_val.size()).as_choice(); }
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
Definition ct_utils.h:790

Referenced by Botan::IntMod< MontgomeryRep< ScalarParams > >::invert_vartime(), and Botan::IntMod< MontgomeryRep< ScalarParams > >::is_nonzero().

◆ mul2()

template<typename Rep>
BOTAN_FORCE_INLINE Self Botan::IntMod< Rep >::mul2 ( ) const
inlineconstexpr

Return (*this) multiplied by 2.

Definition at line 327 of file pcurves_impl.h.

327 {
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 }
constexpr W shift_left(std::array< W, N > &x)
Definition mp_core.h:888
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
Definition mp_core.h:229

Referenced by Botan::IntMod< MontgomeryRep< ScalarParams > >::mul3(), Botan::IntMod< MontgomeryRep< ScalarParams > >::mul4(), and Botan::IntMod< MontgomeryRep< ScalarParams > >::mul8().

◆ mul3()

template<typename Rep>
Self Botan::IntMod< Rep >::mul3 ( ) const
inlineconstexpr

Return (*this) multiplied by 3.

Definition at line 337 of file pcurves_impl.h.

337{ return mul2() + (*this); }
constexpr BOTAN_FORCE_INLINE Self mul2() const
Return (*this) multiplied by 2.

◆ mul4()

template<typename Rep>
Self Botan::IntMod< Rep >::mul4 ( ) const
inlineconstexpr

Return (*this) multiplied by 4.

Definition at line 340 of file pcurves_impl.h.

340{ return mul2().mul2(); }

◆ mul8()

template<typename Rep>
Self Botan::IntMod< Rep >::mul8 ( ) const
inlineconstexpr

Return (*this) multiplied by 8.

Definition at line 343 of file pcurves_impl.h.

343{ return mul2().mul2().mul2(); }

◆ negate()

template<typename Rep>
Self Botan::IntMod< Rep >::negate ( ) const
inlineconstexpr

Modular negation

Returns the additive inverse of (*this)

Definition at line 454 of file pcurves_impl.h.

454 {
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 }
constexpr auto word_sub(W x, W y, W *carry) -> W
Definition mp_asmi.h:355

Referenced by Botan::IntMod< MontgomeryRep< ScalarParams > >::correct_sign(), and Botan::IntMod< MontgomeryRep< ScalarParams > >::invert_vartime().

◆ one()

template<typename Rep>
constexpr Self Botan::IntMod< Rep >::one ( )
inlinestaticconstexpr

Return integer one

Definition at line 202 of file pcurves_impl.h.

202{ return Self(Rep::one()); }

Referenced by Botan::IntMod< MontgomeryRep< ScalarParams > >::pow_vartime().

◆ operator!=()

template<typename Rep>
CT::Choice Botan::IntMod< Rep >::operator!= ( const Self & other) const
inlineconstexpr

Constant time integer inequality test

Definition at line 731 of file pcurves_impl.h.

731{ return !(*this == other); }

◆ operator*=()

template<typename Rep>
BOTAN_FORCE_INLINE Self & Botan::IntMod< Rep >::operator*= ( const Self & other)
inlineconstexpr

Modular multiplication; set this to this * other

Definition at line 357 of file pcurves_impl.h.

357 {
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 }
constexpr void comba_mul(W z[2 *N], const W x[N], const W y[N])
Definition mp_core.h:981

◆ operator=() [1/2]

template<typename Rep>
IntMod & Botan::IntMod< Rep >::operator= ( const Self & other)
default

◆ operator=() [2/2]

template<typename Rep>
IntMod & Botan::IntMod< Rep >::operator= ( Self && other)
default

◆ operator==()

template<typename Rep>
CT::Choice Botan::IntMod< Rep >::operator== ( const Self & other) const
inlineconstexpr

Constant time integer equality test

Since both this and other are in Montgomery representation (if applicable), we can always compare the words directly, without having to convert out.

Definition at line 724 of file pcurves_impl.h.

724 {
725 return CT::is_equal(this->data(), other.data(), N).as_choice();
726 }
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
Definition ct_utils.h:803

◆ pow_vartime()

template<typename Rep>
Self Botan::IntMod< Rep >::pow_vartime ( const std::array< W, N > & exp) const
inlineconstexpr

Modular Exponentiation (Variable Time)

This function is variable time with respect to the exponent. It should only be used when exp is not secret. In the current code, exp is always a compile-time constant.

This function should not leak any information about *this, since the value being operated on may be a secret.

TODO: this interface should be changed so that the exponent is always a compile-time constant; this should allow some interesting optimizations.

Definition at line 479 of file pcurves_impl.h.

479 {
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
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
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) {
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 }
constexpr void square_n(size_t n)
constexpr BOTAN_FORCE_INLINE Self square() const
constexpr size_t read_window_bits(std::span< const W, N > words, size_t offset)
Definition mp_core.h:1284

Referenced by Botan::IntMod< MontgomeryRep< ScalarParams > >::invert(), and Botan::IntMod< MontgomeryRep< ScalarParams > >::sqrt().

◆ random()

template<typename Rep>
Self Botan::IntMod< Rep >::random ( RandomNumberGenerator & rng)
inlinestatic

Return a random integer value in [1,p)

This uses rejection sampling. This could have alternatively been implemented by oversampling the random number generator and then performing a wide reduction. The main reason that approach is avoided here is because it makes testing ECDSA-style known answer tests more difficult.

This function avoids returning zero since in almost all contexts where a random integer is desired we want a random integer in Z_p*

Definition at line 853 of file pcurves_impl.h.

853 {
854 constexpr size_t MAX_ATTEMPTS = 1000;
855
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 }
static std::optional< Self > deserialize(std::span< const uint8_t > bytes)

◆ serialize_to()

template<typename Rep>
void Botan::IntMod< Rep >::serialize_to ( std::span< uint8_t, Self::BYTES > bytes) const
inlineconstexpr

Serialize the integer to a bytestring

Definition at line 741 of file pcurves_impl.h.

741 {
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;
752 }
753 }
constexpr auto store_be(ParamTs &&... params)
Definition loadstor.h:745

◆ sqrt()

template<typename Rep>
CT::Option< Self > Botan::IntMod< Rep >::sqrt ( ) const
inlineconstexpr

Return the modular square root if it exists

The CT::Option will be unset if the square root does not exist

Definition at line 665 of file pcurves_impl.h.

665 {
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);
671
672 // Zero out the return value if it would otherwise be incorrect
673 const CT::Choice correct = (z.square() == *this);
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);
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);
714 return CT::Option<Self>(z, correct);
715 }
716 }
static constexpr auto P_MOD_4
constexpr CT::Choice is_one() const
consteval std::array< W, N > shanks_tonelli_c3(const std::array< W, N > &c2)
consteval std::array< W, N > p_plus_1_over_4(const std::array< W, N > &p)
consteval std::array< W, N > p_minus_1_over_2(const std::array< W, N > &p)
consteval auto shanks_tonelli_c4(const std::array< W, N > &p_minus_1_over_2) -> Z
consteval std::pair< size_t, std::array< W, N > > shanks_tonelli_c1c2(const std::array< W, N > &p)

◆ square()

template<typename Rep>
BOTAN_FORCE_INLINE Self Botan::IntMod< Rep >::square ( ) const
inlineconstexpr

Modular squaring

Returns the square of this after modular reduction

Definition at line 428 of file pcurves_impl.h.

428 {
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 }
constexpr void comba_sqr(W z[2 *N], const W x[N])
Definition mp_core.h:1017

Referenced by Botan::IntMod< MontgomeryRep< ScalarParams > >::sqrt(), and Botan::EllipticCurve< Params, FieldRep >::x3_ax_b().

◆ square_n()

template<typename Rep>
void Botan::IntMod< Rep >::square_n ( size_t n)
inlineconstexpr

Repeated modular squaring

Returns the nth square of this

(Alternate view, returns this raised to the 2^nth power)

Definition at line 441 of file pcurves_impl.h.

441 {
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 }

◆ stash_value()

template<typename Rep>
template<size_t L>
std::array< W, L > Botan::IntMod< Rep >::stash_value ( ) const
inline

Store the raw words to an array

See pcurves_wrap.h for why/where this is used

Definition at line 761 of file pcurves_impl.h.

761 {
762 static_assert(L >= N);
764 for(size_t i = 0; i != N; ++i) {
765 stash[i] = m_val[i];
766 }
767 return stash;
768 }

◆ to_words()

template<typename Rep>
std::array< W, Self::N > Botan::IntMod< Rep >::to_words ( ) const
inlineconstexpr

Convert the integer to standard representation and return the sequence of words

Definition at line 736 of file pcurves_impl.h.

736{ return Rep::from_rep(m_val); }

Referenced by Botan::IntMod< MontgomeryRep< ScalarParams > >::invert_vartime().

◆ zero()

template<typename Rep>
constexpr Self Botan::IntMod< Rep >::zero ( )
inlinestaticconstexpr

Return integer zero

Note this assumes that the representation of zero is an all zero sequence of words. This is true for both Montgomery and standard representations.

Definition at line 197 of file pcurves_impl.h.

197{ return Self(std::array<W, N>{0}); }

Referenced by Botan::IntMod< MontgomeryRep< ScalarParams > >::invert_vartime().

◆ operator*

template<typename Rep>
BOTAN_FORCE_INLINE Self operator* ( const Self & a,
const Self & b )
friend

Modular multiplication; return c = a * b

Definition at line 348 of file pcurves_impl.h.

348 {
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 }

◆ operator+

template<typename Rep>
BOTAN_FORCE_INLINE Self operator+ ( const Self & a,
const Self & b )
friend

Modular addition; return c = a + b

Definition at line 267 of file pcurves_impl.h.

267 {
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 }

◆ operator-

template<typename Rep>
BOTAN_FORCE_INLINE Self operator- ( const Self & a,
const Self & b )
friend

Modular subtraction; return c = a - b

Definition at line 283 of file pcurves_impl.h.

283 {
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 }

Member Data Documentation

◆ BITS

template<typename Rep>
size_t Botan::IntMod< Rep >::BITS = count_bits(P)
staticconstexpr

Definition at line 174 of file pcurves_impl.h.

◆ BYTES

template<typename Rep>
size_t Botan::IntMod< Rep >::BYTES = (BITS + 7) / 8
staticconstexpr

Definition at line 175 of file pcurves_impl.h.

◆ P_MOD_4

template<typename Rep>
auto Botan::IntMod< Rep >::P_MOD_4 = P[0] % 4
staticconstexpr

Definition at line 177 of file pcurves_impl.h.


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