Botan::IntMod< Rep > Class Template Reference

#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 163 of file pcurves_impl.h.

Member Typedef Documentation

Self

template<typename Rep>

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

Definition at line 177 of file pcurves_impl.h.

Constructor & Destructor Documentation

IntMod() [1/3]

template<typename Rep>

Botan::IntMod< Rep >::IntMod ( )

inlineconstexpr

Definition at line 180 of file pcurves_impl.h.

: 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 889 of file pcurves_impl.h.

{ CT::poison(m_val); }

_const_time_unpoison()

template<typename Rep>

void Botan::IntMod< Rep >::_const_time_unpoison ( ) const

inlineconstexpr

Definition at line 891 of file pcurves_impl.h.

{ CT::unpoison(m_val); }

_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 547 of file pcurves_impl.h.

                                                                          {
         constexpr auto INV_2 = p_div_2_plus_1(Rep::P);
 
         // Conditional ok: this function is variable time
         while((a.m_val[0] & 1) != 1) {
            shift_right<1>(a.m_val);
 
            const W borrow = shift_right<1>(x.m_val);
 
            // Conditional ok: this function is variable time
            if(borrow) {
               bigint_add2(x.m_val.data(), N, INV_2.data(), N);
            }
         }
      }

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 256 of file pcurves_impl.h.

                                                                                  {
         auto r = y;
         r.conditional_assign(choice, x);
         return r;
      }

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 367 of file pcurves_impl.h.

                                                                       {
         const W mask = cond.into_bitmask<W>();
 
         for(size_t i = 0; i != N; ++i) {
            m_val[i] = Botan::choose(mask, nx.m_val[i], m_val[i]);
         }
      }

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 380 of file pcurves_impl.h.

                                                                                                                {
         const W mask = cond.into_bitmask<W>();
 
         for(size_t i = 0; i != N; ++i) {
            x.m_val[i] = Botan::choose(mask, nx.m_val[i], x.m_val[i]);
            y.m_val[i] = Botan::choose(mask, ny.m_val[i], y.m_val[i]);
         }
      }

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 394 of file pcurves_impl.h.

                                                                                                   {
         const W mask = cond.into_bitmask<W>();
 
         for(size_t i = 0; i != N; ++i) {
            x.m_val[i] = Botan::choose(mask, nx.m_val[i], x.m_val[i]);
            y.m_val[i] = Botan::choose(mask, ny.m_val[i], y.m_val[i]);
            z.m_val[i] = Botan::choose(mask, nz.m_val[i], z.m_val[i]);
         }
      }

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 410 of file pcurves_impl.h.

                                                                              {
         const W mask = cond.into_bitmask<W>();
 
         for(size_t i = 0; i != N; ++i) {
            auto nx = Botan::choose(mask, y.m_val[i], x.m_val[i]);
            auto ny = Botan::choose(mask, x.m_val[i], y.m_val[i]);
            x.m_val[i] = nx;
            y.m_val[i] = ny;
         }
      }

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 882 of file pcurves_impl.h.

                                               {
         std::array<W, 1> v{};
         v[0] = (x >= 0) ? x : -x;
         auto s = Self::from_words(v);
         return (x >= 0) ? s : s.negate();
      }

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 248 of file pcurves_impl.h.

                                                       {
         const auto flip = (even != this->is_even());
         return Self::choose(flip, this->negate(), *this);
      }

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 792 of file pcurves_impl.h.

                                                                         {
         // Conditional ok: input length is public
         if(bytes.size() != Self::BYTES) {
            return {};
         }
 
         const auto words = bytes_to_words<W, N, BYTES>(bytes.first<Self::BYTES>());
 
         // Conditional acceptable: std::optional is implicitly not constant time
         if(!bigint_ct_is_lt(words.data(), N, P.data(), N).as_bool()) {
            return {};
         }
 
         // Safe because we checked above that words is an integer < P
         return Self::from_words(words);
      }

div2()

template<typename Rep>

Self Botan::IntMod< Rep >::div2 ( ) const

inline

Return the value of this divided by 2

Definition at line 302 of file pcurves_impl.h.

                        {
         // The inverse of 2 modulo P is (P/2)+1; this avoids a constexpr time
         // general inversion, which some compilers can't handle
         constexpr auto INV_2 = p_div_2_plus_1(Rep::P);
 
         // We could multiply by INV_2 but there is a better way ...
 
         std::array<W, N> t = value();
         const W borrow = shift_right<1>(t);
 
         // If value was odd, add (P/2)+1
         const auto mask = CT::Mask<W>::expand(borrow).value();
 
         W carry = 0;
 
         for(size_t i = 0; i != N; ++i) {
            t[i] = word_add(t[i], INV_2[i] & mask, &carry);
         }
 
         return Self(t);
      }

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 774 of file pcurves_impl.h.

                                                          {
         static_assert(L >= N);
         std::array<W, N> val = {};
         for(size_t i = 0; i != N; ++i) {
            val[i] = stash[i];
         }
         return Self(val);
      }

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 816 of file pcurves_impl.h.

                                                                             {
         static_assert(8 * L <= 2 * Self::BITS);
         std::array<uint8_t, 2 * BYTES> padded_bytes = {};
         copy_mem(std::span{padded_bytes}.template last<L>(), bytes);
         return Self(Rep::wide_to_rep(bytes_to_words<W, 2 * N, 2 * BYTES>(std::span{padded_bytes})));
      }

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 829 of file pcurves_impl.h.

                                                                                              {
         // Conditional ok: input length is public
         if(bytes.size() > 2 * Self::BYTES) {
            return {};
         }
 
         std::array<uint8_t, 2 * Self::BYTES> padded_bytes = {};
         copy_mem(std::span{padded_bytes}.last(bytes.size()), bytes);
         return Self(Rep::wide_to_rep(bytes_to_words<W, 2 * N, 2 * BYTES>(std::span{padded_bytes})));
      }

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 211 of file pcurves_impl.h.

                                                         {
         if constexpr(L == N) {
            return Self(Rep::to_rep(w));
         } else {
            static_assert(L < N);
            std::array<W, N> ew = {};
            copy_mem(std::span{ew}.template first<L>(), w);
            return Self(Rep::to_rep(ew));
         }
      }

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 538 of file pcurves_impl.h.

{ return pow_vartime(Self::P_MINUS_2); }

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 598 of file pcurves_impl.h.

                                            {
         // Conditional ok: this function is variable time
         if(this->is_zero().as_bool()) {
            return Self::zero();
         }
 
         auto x = Self(std::array<W, N>{1});  // 1 in standard domain
         auto b = Self(this->to_words());     // *this in standard domain
 
         // First loop iteration
         Self::_invert_vartime_div2_helper(b, x);
 
         auto a = b.negate();
         // y += x but y is zero at the outset
         auto y = x;
 
         // First half of second loop iteration
         Self::_invert_vartime_div2_helper(a, y);
 
         for(;;) {
            // Conditional ok: this function is variable time
            if(a.m_val == b.m_val) {
               // At this point it should be that a == b == 1
               auto r = y.negate();
 
               // Convert back to Montgomery if required
               r.m_val = Rep::to_rep(r.m_val);
               return r;
            }
 
            auto nx = x + y;
 
            /*
            * Otherwise either b > a or a > b
            *
            * If b > a we want to set b to b - a
            * Otherwise we want to set a to a - b
            *
            * Compute r = b - a and check if it underflowed
            * If it did not then we are in the b > a path
            */
            std::array<W, N> r;  // NOLINT(*-member-init)
            const word carry = bigint_sub3(r.data(), b.data(), N, a.data(), N);
 
            // Conditional ok: this function is variable time
            if(carry == 0) {
               // b > a
               b.m_val = r;
               x = nx;
               Self::_invert_vartime_div2_helper(b, x);
            } else {
               // We know this can't underflow because a > b
               bigint_sub3(r.data(), a.data(), N, b.data(), N);
               a.m_val = r;
               y = nx;
               Self::_invert_vartime_div2_helper(a, y);
            }
         }
      }

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 240 of file pcurves_impl.h.

                                         {
         auto v = Rep::from_rep(m_val);
         return !CT::Choice::from_int(v[0] & 0x01);
      }

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 230 of file pcurves_impl.h.

{ 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 235 of file pcurves_impl.h.

{ return (*this == 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 225 of file pcurves_impl.h.

{ return CT::all_zeros(m_val.data(), m_val.size()).as_choice(); }

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 325 of file pcurves_impl.h.

                                                     {
         std::array<W, N> t = value();
         const W carry = shift_left<1>(t);
 
         std::array<W, N> r;  // NOLINT(*-member-init)
         bigint_monty_maybe_sub<N>(r.data(), carry, t.data(), P.data());
         return Self(r);
      }

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 335 of file pcurves_impl.h.

{ return mul2() + (*this); }

mul4()

template<typename Rep>

Self Botan::IntMod< Rep >::mul4 ( ) const

inlineconstexpr

Return (*this) multiplied by 4.

Definition at line 338 of file pcurves_impl.h.

{ return mul2().mul2(); }

mul8()

template<typename Rep>

Self Botan::IntMod< Rep >::mul8 ( ) const

inlineconstexpr

Return (*this) multiplied by 8.

Definition at line 341 of file pcurves_impl.h.

{ 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 452 of file pcurves_impl.h.

                                    {
         const W x_is_zero = ~CT::all_zeros(this->data(), N).value();
 
         std::array<W, N> r;  // NOLINT(*-member-init)
         W carry = 0;
         for(size_t i = 0; i != N; ++i) {
            r[i] = word_sub(P[i] & x_is_zero, m_val[i], &carry);
         }
 
         return Self(r);
      }

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 200 of file pcurves_impl.h.

{ 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 729 of file pcurves_impl.h.

{ 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 355 of file pcurves_impl.h.

                                                                       {
         std::array<W, 2 * N> z;  // NOLINT(*-member-init)
         comba_mul<N>(z.data(), data(), other.data());
         m_val = Rep::redc(z);
         return (*this);
      }

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 722 of file pcurves_impl.h.

                                                             {
         return CT::is_equal(this->data(), other.data(), N).as_choice();
      }

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 477 of file pcurves_impl.h.

                                                                  {
         constexpr size_t WindowBits = (Self::BITS <= 256) ? 4 : 5;
         constexpr size_t WindowElements = (1 << WindowBits) - 1;
 
         constexpr size_t Windows = (Self::BITS + WindowBits - 1) / WindowBits;
 
         /*
         A simple fixed width window modular multiplication.
 
         TODO: investigate using sliding window here
         */
 
         std::array<Self, WindowElements> tbl;
 
         tbl[0] = (*this);
 
         for(size_t i = 1; i != WindowElements; ++i) {
            // Conditional ok: table indexes are public here
            if(i % 2 == 1) {
               tbl[i] = tbl[i / 2].square();
            } else {
               tbl[i] = tbl[i - 1] * tbl[0];
            }
         }
 
         auto r = Self::one();
 
         const size_t w0 = read_window_bits<WindowBits>(std::span{exp}, (Windows - 1) * WindowBits);
 
         // Conditional ok: this function is variable time
         if(w0 > 0) {
            r = tbl[w0 - 1];
         }
 
         for(size_t i = 1; i != Windows; ++i) {
            r.square_n(WindowBits);
 
            const size_t w = read_window_bits<WindowBits>(std::span{exp}, (Windows - i - 1) * WindowBits);
 
            // Conditional ok: this function is variable time
            if(w > 0) {
               r *= tbl[w - 1];
            }
         }
 
         return r;
      }

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 851 of file pcurves_impl.h.

                                                     {
         constexpr size_t MAX_ATTEMPTS = 1000;
 
         std::array<uint8_t, Self::BYTES> buf{};
 
         for(size_t i = 0; i != MAX_ATTEMPTS; ++i) {
            rng.randomize(buf);
 
            // Zero off high bits that if set would certainly cause us
            // to be out of range
            if constexpr(Self::BITS % 8 != 0) {
               constexpr uint8_t mask = 0xFF >> (8 - (Self::BITS % 8));
               buf[0] &= mask;
            }
 
            // Conditionals ok: rejection sampling reveals only values we didn't use
            if(auto s = Self::deserialize(buf)) {
               if(s.value().is_nonzero().as_bool()) {
                  return s.value();
               }
            }
         }
 
         throw Internal_Error("Failed to generate random Scalar within bounded number of attempts");
      }

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 739 of file pcurves_impl.h.

                                                                           {
         auto v = Rep::from_rep(m_val);
         std::reverse(v.begin(), v.end());
 
         if constexpr(Self::BYTES == N * WordInfo<W>::bytes) {
            store_be(bytes, v);
         } else {
            // Remove leading zero bytes
            const auto padded_bytes = store_be(v);
            constexpr size_t extra = N * WordInfo<W>::bytes - Self::BYTES;
            copy_mem(bytes, std::span{padded_bytes}.template subspan<extra, Self::BYTES>());
         }
      }

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 663 of file pcurves_impl.h.

                                            {
         if constexpr(Self::P_MOD_4 == 3) {
            // The easy case for square root is when p == 3 (mod 4)
 
            constexpr auto P_PLUS_1_OVER_4 = p_plus_1_over_4(P);
            auto z = pow_vartime(P_PLUS_1_OVER_4);
 
            // Zero out the return value if it would otherwise be incorrect
            const CT::Choice correct = (z.square() == *this);
            z.conditional_assign(!correct, Self::zero());
            return CT::Option<Self>(z, correct);
         } else {
            // Shanks-Tonelli, following I.4 in RFC 9380
 
            /*
            Constants:
            1. c1, the largest integer such that 2^c1 divides q - 1.
            2. c2 = (q - 1) / (2^c1)        # Integer arithmetic
            3. c3 = (c2 - 1) / 2            # Integer arithmetic
            4. c4, a non-square value in F
            5. c5 = c4^c2 in F
            */
            constexpr auto C1_C2 = shanks_tonelli_c1c2(Self::P);
            constexpr std::array<W, N> C3 = shanks_tonelli_c3(C1_C2.second);
            constexpr std::array<W, N> P_MINUS_1_OVER_2 = p_minus_1_over_2(Self::P);
            constexpr Self C4 = shanks_tonelli_c4<Self>(P_MINUS_1_OVER_2);
            constexpr Self C5 = C4.pow_vartime(C1_C2.second);
 
            const Self& x = (*this);
 
            auto z = x.pow_vartime(C3);
            auto t = z.square();
            t *= x;
            z *= x;
            auto b = t;
            auto c = C5;
 
            for(size_t i = C1_C2.first; i >= 2; i--) {
               b.square_n(i - 2);
               const CT::Choice e = b.is_one();
               z.conditional_assign(!e, z * c);
               c.square_n(1);
               t.conditional_assign(!e, t * c);
               b = t;
            }
 
            // Zero out the return value if it would otherwise be incorrect
            const CT::Choice correct = (z.square() == *this);
            z.conditional_assign(!correct, Self::zero());
            return CT::Option<Self>(z, correct);
         }
      }

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 426 of file pcurves_impl.h.

                                                       {
         std::array<W, 2 * N> z;  // NOLINT(*-member-init)
         comba_sqr<N>(z.data(), this->data());
         return Self(Rep::redc(z));
      }

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 439 of file pcurves_impl.h.

                                        {
         std::array<W, 2 * N> z;  // NOLINT(*-member-init)
         for(size_t i = 0; i != n; ++i) {
            comba_sqr<N>(z.data(), this->data());
            m_val = Rep::redc(z);
         }
      }

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 759 of file pcurves_impl.h.

                                         {
         static_assert(L >= N);
         std::array<W, L> stash = {};
         for(size_t i = 0; i != N; ++i) {
            stash[i] = m_val[i];
         }
         return stash;
      }

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 734 of file pcurves_impl.h.

{ 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 195 of file pcurves_impl.h.

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

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

Friends And Related Symbol Documentation

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 346 of file pcurves_impl.h.

                                                                                       {
         std::array<W, 2 * N> z;  // NOLINT(*-member-init)
         comba_mul<N>(z.data(), a.data(), b.data());
         return Self(Rep::redc(z));
      }

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 265 of file pcurves_impl.h.

                                                                                       {
         std::array<W, N> t;  // NOLINT(*-member-init)
 
         W carry = 0;
         for(size_t i = 0; i != N; ++i) {
            t[i] = word_add(a.m_val[i], b.m_val[i], &carry);
         }
 
         std::array<W, N> r;  // NOLINT(*-member-init)
         bigint_monty_maybe_sub<N>(r.data(), carry, t.data(), P.data());
         return Self(r);
      }

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 281 of file pcurves_impl.h.

                                                                                       {
         std::array<W, N> r;  // NOLINT(*-member-init)
         W carry = 0;
         for(size_t i = 0; i != N; ++i) {
            r[i] = word_sub(a.m_val[i], b.m_val[i], &carry);
         }
 
         const auto mask = CT::Mask<W>::expand(carry).value();
 
         carry = 0;
 
         for(size_t i = 0; i != N; ++i) {
            r[i] = word_add(r[i], P[i] & mask, &carry);
         }
 
         return Self(r);
      }

Member Data Documentation

BITS

template<typename Rep>

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

staticconstexpr

Definition at line 172 of file pcurves_impl.h.

BYTES

template<typename Rep>

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

staticconstexpr

Definition at line 173 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 175 of file pcurves_impl.h.

---

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

• src/lib/math/pcurves/pcurves_impl/pcurves_impl.h