7#include <botan/internal/mod_inv.h>
9#include <botan/numthry.h>
10#include <botan/internal/ct_utils.h>
11#include <botan/internal/divide.h>
12#include <botan/internal/mp_core.h>
13#include <botan/internal/rounding.h>
19BigInt inverse_mod_odd_modulus(
const BigInt& n,
const BigInt& mod) {
45 const size_t mod_words = mod.sig_words();
50 word* v_w = &tmp_mem[0];
51 word* u_w = &tmp_mem[1 * mod_words];
52 word* b_w = &tmp_mem[2 * mod_words];
53 word* a_w = &tmp_mem[3 * mod_words];
54 word* mp1o2 = &tmp_mem[4 * mod_words];
58 copy_mem(a_w, n._data(), std::min(n.size(), mod_words));
59 copy_mem(b_w, mod._data(), std::min(mod.size(), mod_words));
65 copy_mem(mp1o2, mod._data(), std::min(mod.size(), mod_words));
71 const size_t execs = 2 * mod.bits();
73 for(
size_t i = 0; i != execs; ++i) {
74 const word odd_a = a_w[0] & 1;
93 const word odd_u = u_w[0] & 1;
105 for(
size_t i = 1; i != mod_words; ++i) {
113 (~b_is_1).if_set_zero_out(v_w, mod_words);
120 clear_mem(&tmp_mem[mod_words], 4 * mod_words);
129BigInt inverse_mod_pow2(
const BigInt& a1,
size_t k) {
135 if(a1.is_even() || k == 0) {
149 const size_t a_words = a.sig_words();
161 for(
size_t i = 0; i != iter; ++i) {
162 const bool b0 =
b.get_bit(0);
163 X.conditionally_set_bit(i, b0);
165 b.ct_cond_assign(b0, newb);
188 BigInt z = inverse_mod_odd_modulus(x, mod);
202 const size_t mod_bits = mod.
bits();
205 if(mod_lz == mod_bits - 1) {
207 auto z = inverse_mod_pow2(x, mod_lz);
230 const BigInt o = mod >> 1;
250 const BigInt o = mod >> mod_lz;
252 const BigInt inv_2k = inverse_mod_pow2(x, mod_lz);
255 if(inv_o == 0 || inv_2k == 0) {
261 const BigInt c = inverse_mod_pow2(o, mod_lz);
267 BigInt h = c * (inv_2k - inv_o);
288 return inverse_mod_odd_modulus(x, p);
298 BigInt z = inverse_mod_odd_modulus(x, n);
305uint64_t barrett_mod_65537(uint64_t x) {
306 constexpr uint64_t mod = 65537;
307 constexpr size_t s = 32;
308 constexpr uint64_t c = (
static_cast<uint64_t
>(1) << s) / mod;
310 uint64_t q = (x * c) >> s;
311 uint64_t r = x - q * mod;
314 return r - r_gt_mod.if_set_return(mod);
317word inverse_mod_65537(word x) {
321 for(
size_t i = 0; i != 16; ++i) {
322 accum = barrett_mod_65537(accum * accum);
323 accum = barrett_mod_65537(accum * x);
325 return static_cast<word
>(accum);
350 constexpr word e_w = 65537;
353 const word inv_phi_mod_e = inverse_mod_65537(phi_mod_e);
355 const word neg_inv_phi_mod_e = (e_w - inv_phi_mod_e);
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_ARG_CHECK(expr, msg)
#define BOTAN_ASSERT(expr, assertion_made)
void ct_cond_add(bool predicate, const BigInt &value)
void ct_cond_assign(bool predicate, const BigInt &other)
static BigInt power_of_2(size_t n)
bool get_bit(size_t n) const
static constexpr Mask< T > is_gte(T x, T y)
static constexpr Mask< T > is_equal(T x, T y)
static constexpr Mask< T > is_zero(T x)
#define BOTAN_MP_WORD_BITS
constexpr void unpoison(const T *p, size_t n)
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
constexpr void poison(const T *p, size_t n)
constexpr void bigint_cnd_abs(W cnd, W x[], size_t size)
BigInt inverse_mod_secret_prime(const BigInt &x, const BigInt &p)
constexpr void bigint_cnd_swap(W cnd, W x[], W y[], size_t size)
word ct_mod_word(const BigInt &x, word y)
constexpr void bigint_shr1(W x[], size_t x_size, size_t shift)
size_t low_zero_bits(const BigInt &n)
constexpr size_t round_up(size_t n, size_t align_to)
BigInt inverse_mod_public_prime(const BigInt &x, const BigInt &p)
BigInt ct_modulo(const BigInt &x, const BigInt &y)
BigInt compute_rsa_secret_exponent(const BigInt &e, const BigInt &phi_n, const BigInt &p, const BigInt &q)
constexpr auto bigint_cnd_sub(W cnd, W x[], size_t x_size, const W y[], size_t y_size) -> W
void ct_divide_word(const BigInt &x, word y, BigInt &q_out, word &r_out)
constexpr W bigint_cnd_add(W cnd, W x[], size_t x_size, const W y[], size_t y_size)
void carry(int64_t &h0, int64_t &h1)
std::optional< BigInt > inverse_mod_general(const BigInt &x, const BigInt &mod)
BigInt gcd(const BigInt &a, const BigInt &b)
std::vector< T, secure_allocator< T > > secure_vector
BigInt inverse_mod_rsa_public_modulus(const BigInt &x, const BigInt &n)
constexpr auto bigint_add2_nc(W x[], size_t x_size, const W y[], size_t y_size) -> W
constexpr void copy_mem(T *out, const T *in, size_t n)
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
constexpr void clear_mem(T *ptr, size_t n)