Botan 3.7.1
Crypto and TLS for C&
reducer.cpp
Go to the documentation of this file.
1/*
2* Modular Reducer
3* (C) 1999-2011,2018 Jack Lloyd
4*
5* Botan is released under the Simplified BSD License (see license.txt)
6*/
7
8#include <botan/reducer.h>
9
10#include <botan/internal/ct_utils.h>
11#include <botan/internal/divide.h>
12#include <botan/internal/mp_core.h>
13
14namespace Botan {
15
16/*
17* Modular_Reducer Constructor
18*/
20 if(mod < 0) {
21 throw Invalid_Argument("Modular_Reducer: modulus must be positive");
22 }
23
24 // Left uninitialized if mod == 0
25 m_mod_words = 0;
26
27 if(mod > 0) {
29 }
30}
31
33 BOTAN_ARG_CHECK(!mod.is_zero(), "Modulus cannot be zero");
34 BOTAN_ARG_CHECK(!mod.is_negative(), "Modulus cannot be negative");
35
36 size_t mod_words = mod.sig_words();
37
38 // Compute mu = floor(2^{2k} / m)
39 const size_t mu_bits = 2 * BOTAN_MP_WORD_BITS * mod_words;
40 return Modular_Reducer(mod, ct_divide_pow2k(mu_bits, mod), mod_words);
41}
42
44 BOTAN_ARG_CHECK(!mod.is_zero(), "Modulus cannot be zero");
45 BOTAN_ARG_CHECK(!mod.is_negative(), "Modulus cannot be negative");
46
47 size_t mod_words = mod.sig_words();
48
49 // Compute mu = floor(2^{2k} / m)
50 const size_t mu_bits = 2 * BOTAN_MP_WORD_BITS * mod_words;
51 return Modular_Reducer(mod, BigInt::power_of_2(mu_bits) / mod, mod_words);
52}
53
55 BigInt r;
57 reduce(r, x, ws);
58 return r;
59}
60
63 BigInt x2 = x;
64 x2.square(ws);
65 BigInt r;
66 reduce(r, x2, ws);
67 return r;
68}
69
70namespace {
71
72/*
73* Like if(cnd) x.rev_sub(...) but in const time
74*/
75void cnd_rev_sub(bool cnd, BigInt& x, const word y[], size_t y_sw, secure_vector<word>& ws) {
76 if(x.sign() != BigInt::Positive) {
77 throw Invalid_State("BigInt::sub_rev requires this is positive");
78 }
79
80 const size_t x_sw = x.sig_words();
81
82 const size_t max_words = std::max(x_sw, y_sw);
83 ws.resize(std::max(x_sw, y_sw));
84 clear_mem(ws.data(), ws.size());
85 x.grow_to(max_words);
86
87 const int32_t relative_size = bigint_sub_abs(ws.data(), x._data(), x_sw, y, y_sw);
88
89 x.cond_flip_sign((relative_size > 0) && cnd);
90 bigint_cnd_swap(static_cast<word>(cnd), x.mutable_data(), ws.data(), max_words);
91}
92
93} // namespace
94
96 if(&t1 == &x) {
97 throw Invalid_State("Modular_Reducer arguments cannot alias");
98 }
99 if(m_mod_words == 0) {
100 throw Invalid_State("Modular_Reducer: Never initalized");
101 }
102
103 const size_t x_sw = x.sig_words();
104
105 if(x_sw > 2 * m_mod_words) {
106 // too big, fall back to slow boat division
107 t1 = ct_modulo(x, m_modulus);
108 return;
109 }
110
111 t1 = x;
113 t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words - 1));
114
115 t1.mul(m_mu, ws);
116 t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words + 1));
117
118 // TODO add masked mul to avoid computing high bits
119 t1.mul(m_modulus, ws);
120 t1.mask_bits(BOTAN_MP_WORD_BITS * (m_mod_words + 1));
121
122 t1.rev_sub(x._data(), std::min(x_sw, m_mod_words + 1), ws);
123
124 /*
125 * If t1 < 0 then we must add b^(k+1) where b = 2^w. To avoid a
126 * side channel perform the addition unconditionally, with ws set
127 * to either b^(k+1) or else 0.
128 */
129 const word t1_neg = t1.is_negative();
130
131 if(ws.size() < m_mod_words + 2) {
132 ws.resize(m_mod_words + 2);
133 }
134 clear_mem(ws.data(), ws.size());
135 ws[m_mod_words + 1] = t1_neg;
136
137 t1.add(ws.data(), m_mod_words + 2, BigInt::Positive);
138
139 // Per HAC this step requires at most 2 subtractions
140 t1.ct_reduce_below(m_modulus, ws, 2);
141
142 cnd_rev_sub(t1.is_nonzero() && x.is_negative(), t1, m_modulus._data(), m_modulus.size(), ws);
143}
144
145} // namespace Botan
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:29
size_t sig_words() const
Definition bigint.h:616
word * mutable_data()
Definition bigint.h:641
size_t size() const
Definition bigint.h:610
BigInt & rev_sub(const word y[], size_t y_words, secure_vector< word > &ws)
Definition big_ops2.cpp:124
void grow_to(size_t n) const
Definition bigint.h:667
void ct_reduce_below(const BigInt &mod, secure_vector< word > &ws, size_t bound)
Definition bigint.cpp:349
BigInt & mul(const BigInt &y, secure_vector< word > &ws)
Definition big_ops2.cpp:150
void mask_bits(size_t n)
Definition bigint.h:490
void cond_flip_sign(bool predicate)
Definition bigint.cpp:488
static BigInt power_of_2(size_t n)
Definition bigint.h:830
const word * _data() const
Definition bigint.h:936
Sign sign() const
Definition bigint.h:572
BigInt & add(const word y[], size_t y_words, Sign sign)
Definition big_ops2.cpp:16
bool is_zero() const
Definition bigint.h:458
BigInt & square(secure_vector< word > &ws)
Definition big_ops2.cpp:177
bool is_negative() const
Definition bigint.h:560
bool is_nonzero() const
Definition bigint.h:452
void set_sign(Sign sign)
Definition bigint.h:593
static Modular_Reducer for_public_modulus(const BigInt &m)
Definition reducer.cpp:43
BigInt square(const BigInt &x) const
Definition reducer.cpp:61
static Modular_Reducer for_secret_modulus(const BigInt &m)
Definition reducer.cpp:32
BigInt reduce(const BigInt &x) const
Definition reducer.cpp:54
#define BOTAN_MP_WORD_BITS
Definition build.h:71
constexpr void bigint_cnd_swap(W cnd, W x[], W y[], size_t size)
Definition mp_core.h:31
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition divide.cpp:181
BigInt ct_divide_pow2k(size_t k, const BigInt &y)
Definition divide.cpp:80
constexpr auto bigint_sub_abs(W z[], const W x[], const W y[], size_t N, W ws[]) -> CT::Mask< W >
Definition mp_core.h:420
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:121