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 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 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 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 Self	operator* (const Self &a, const Self &b)
constexpr Self	operator+ (const Self &a, const Self &b)
constexpr 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 142 of file pcurves_impl.h.

Member Typedef Documentation

Self

template<typename Rep>

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

Definition at line 156 of file pcurves_impl.h.

Constructor & Destructor Documentation

IntMod() [1/3]

template<typename Rep>

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

inlineconstexpr

Definition at line 159 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 855 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 857 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 513 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);
 
            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 235 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 333 of file pcurves_impl.h.

                                                                       {
         const W mask = CT::Mask<W>::from_choice(cond).value();
 
         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 346 of file pcurves_impl.h.

                                                                                                                {
         const W mask = CT::Mask<W>::from_choice(cond).value();
 
         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 360 of file pcurves_impl.h.

                                                                                                   {
         const W mask = CT::Mask<W>::from_choice(cond).value();
 
         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 376 of file pcurves_impl.h.

                                                                              {
         const W mask = CT::Mask<W>::from_choice(cond).value();
 
         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 848 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 227 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 758 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 274 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();
         W borrow = shift_right<1>(t);
 
         // If value was odd, add (P/2)+1
         bigint_cnd_add(borrow, t.data(), INV_2.data(), N);
 
         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 740 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 782 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 795 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 190 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 504 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 564 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)
            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 219 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 209 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 214 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 204 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>

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

inlineconstexpr

Return (*this) multiplied by 2.

Definition at line 291 of file pcurves_impl.h.

                                  {
         std::array<W, N> t = value();
         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 301 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 304 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 307 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 418 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 179 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 695 of file pcurves_impl.h.

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

operator*=()

template<typename Rep>

Self & Botan::IntMod< Rep >::operator*= ( const Self & other )

inlineconstexpr

Modular multiplication; set this to this * other

Definition at line 321 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 688 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 443 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 817 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 705 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 629 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>

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

inlineconstexpr

Modular squaring

Returns the square of this after modular reduction

Definition at line 392 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 405 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 725 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 700 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 174 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>

Self operator* ( const Self & a, const Self & b )

friend

Modular multiplication; return c = a * b

Definition at line 312 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>

Self operator+ ( const Self & a, const Self & b )

friend

Modular addition; return c = a + b

Definition at line 244 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>

Self operator- ( const Self & a, const Self & b )

friend

Modular subtraction; return c = a - b

Definition at line 260 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);
         }
 
         bigint_cnd_add(carry, r.data(), P.data(), N);
         return Self(r);
      }

Member Data Documentation

BITS

template<typename Rep>

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

staticconstexpr

Definition at line 151 of file pcurves_impl.h.

BYTES

template<typename Rep>

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

staticconstexpr

Definition at line 152 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 154 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