7#include <botan/numthry.h>
8#include <botan/divide.h>
9#include <botan/internal/ct_utils.h>
10#include <botan/internal/mp_core.h>
11#include <botan/internal/rounding.h>
33 BigInt u = p, v = a, r = 0, s = 1;
80 for(
size_t i = 0; i != k; ++i)
92BigInt inverse_mod_odd_modulus(
const BigInt& n,
const BigInt& mod)
119 const size_t mod_words = mod.sig_words();
122 secure_vector<word> tmp_mem(5*mod_words);
124 word* v_w = &tmp_mem[0];
125 word* u_w = &tmp_mem[1*mod_words];
126 word* b_w = &tmp_mem[2*mod_words];
127 word* a_w = &tmp_mem[3*mod_words];
128 word* mp1o2 = &tmp_mem[4*mod_words];
132 copy_mem(a_w, n.data(), std::min(n.size(), mod_words));
133 copy_mem(b_w, mod.data(), std::min(mod.size(), mod_words));
139 copy_mem(mp1o2, mod.data(), std::min(mod.size(), mod_words));
145 const size_t execs = 2 * mod.bits();
147 for(
size_t i = 0; i != execs; ++i)
149 const word odd_a = a_w[0] & 1;
168 const word odd_u = u_w[0] & 1;
178 for(
size_t i = 0; i != mod_words; ++i)
182 for(
size_t i = 1; i != mod_words; ++i)
189 (~b_is_1).if_set_zero_out(v_w, mod_words);
196 clear_mem(&tmp_mem[mod_words], 4*mod_words);
205BigInt inverse_mod_pow2(
const BigInt& a1,
size_t k)
222 const size_t a_words = a.sig_words();
224 X.grow_to(
round_up(k, BOTAN_MP_WORD_BITS) / BOTAN_MP_WORD_BITS);
232 const size_t iter =
round_up(k, BOTAN_MP_WORD_BITS);
234 for(
size_t i = 0; i != iter; ++i)
236 const bool b0 = b.get_bit(0);
237 X.conditionally_set_bit(i, b0);
239 b.ct_cond_assign(b0, newb);
244 X.const_time_unpoison();
266 return inverse_mod_odd_modulus(n, mod);
268 return inverse_mod_odd_modulus(
ct_modulo(n, mod), mod);
273 const size_t mod_bits = mod.
bits();
276 if(mod_lz == mod_bits - 1)
279 return inverse_mod_pow2(n, mod_lz);
289 const BigInt o = mod >> mod_lz;
291 const BigInt inv_o = inverse_mod_odd_modulus(n_redc, o);
292 const BigInt inv_2k = inverse_mod_pow2(n, mod_lz);
295 if(inv_o == 0 || inv_2k == 0)
300 const BigInt c = inverse_mod_pow2(o, mod_lz);
303 BigInt h = c * (inv_2k - inv_o);
324 return inverse_mod_odd_modulus(n, mod);
340 for(
size_t i = 0; i != BOTAN_MP_WORD_BITS; ++i)
342 const word bi = b % 2;
344 r += bi << (BOTAN_MP_WORD_BITS - 1);
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_ASSERT(expr, assertion_made)
void ct_cond_assign(bool predicate, const BigInt &other)
static BigInt power_of_2(size_t n)
static Mask< T > is_equal(T x, T y)
static Mask< T > is_zero(T x)
void poison(const T *p, size_t n)
void unpoison(const T *p, size_t n)
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
BigInt inverse_euclid(const BigInt &x, const BigInt &modulus)
word bigint_cnd_add(word cnd, word x[], word x_size, const word y[], size_t y_size)
size_t low_zero_bits(const BigInt &n)
word bigint_cnd_sub(word cnd, word x[], size_t x_size, const word y[], size_t y_size)
void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
word monty_inverse(word a)
void carry(int64_t &h0, int64_t &h1)
void copy_mem(T *out, const T *in, size_t n)
BigInt ct_inverse_mod_odd_modulus(const BigInt &n, const BigInt &mod)
word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
BigInt normalized_montgomery_inverse(const BigInt &a, const BigInt &p)
void bigint_cnd_abs(word cnd, word x[], size_t size)
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
size_t almost_montgomery_inverse(BigInt &result, const BigInt &a, const BigInt &p)
void clear_mem(T *ptr, size_t n)
size_t round_up(size_t n, size_t align_to)
BigInt ct_modulo(const BigInt &x, const BigInt &y)