Botan 3.7.1
Crypto and TLS for C&
divide.cpp
Go to the documentation of this file.
1/*
2* Division Algorithms
3* (C) 1999-2007,2012,2018,2021 Jack Lloyd
4*
5* Botan is released under the Simplified BSD License (see license.txt)
6*/
7
8#include <botan/internal/divide.h>
9
10#include <botan/internal/bit_ops.h>
11#include <botan/internal/ct_utils.h>
12#include <botan/internal/mp_core.h>
13
14namespace Botan {
15
16namespace {
17
18/*
19* Handle signed operands, if necessary
20*/
21void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r) {
22 q.cond_flip_sign(x.sign() != y.sign());
23
24 if(x.is_negative() && r.is_nonzero()) {
25 q -= 1;
26 r = y.abs() - r;
27 }
28}
29
30inline bool division_check(word q, word y2, word y1, word x3, word x2, word x1) {
31 /*
32 Compute (y3,y2,y1) = (y2,y1) * q
33 and return true if (y3,y2,y1) > (x3,x2,x1)
34 */
35
36 word y3 = 0;
37 y1 = word_madd2(q, y1, &y3);
38 y2 = word_madd2(q, y2, &y3);
39
40 const word x[3] = {x1, x2, x3};
41 const word y[3] = {y1, y2, y3};
42
43 return bigint_ct_is_lt(x, 3, y, 3).as_bool();
44}
45
46} // namespace
47
48void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out) {
49 if(y.is_zero()) {
50 throw Invalid_Argument("ct_divide: cannot divide by zero");
51 }
52
53 const size_t x_words = x.sig_words();
54 const size_t y_words = y.sig_words();
55
56 const size_t x_bits = x.bits();
57
58 BigInt q = BigInt::with_capacity(x_words);
59 BigInt r = BigInt::with_capacity(y_words);
60 BigInt t = BigInt::with_capacity(y_words); // a temporary
61
62 for(size_t i = 0; i != x_bits; ++i) {
63 const size_t b = x_bits - 1 - i;
64 const bool x_b = x.get_bit(b);
65
66 r <<= 1;
67 r.conditionally_set_bit(0, x_b);
68
69 const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;
70
71 q.conditionally_set_bit(b, r_gte_y);
72 r.ct_cond_swap(r_gte_y, t);
73 }
74
75 sign_fixup(x, y, q, r);
76 r_out = r;
77 q_out = q;
78}
79
80BigInt ct_divide_pow2k(size_t k, const BigInt& y) {
81 BOTAN_ARG_CHECK(!y.is_zero(), "Cannot divide by zero");
82 BOTAN_ARG_CHECK(!y.is_negative(), "Negative divisor not supported");
83 BOTAN_ARG_CHECK(k > 1, "Invalid k");
84
85 const size_t x_bits = k + 1;
86 const size_t y_bits = y.bits();
87
88 if(x_bits < y_bits) {
89 return BigInt::zero();
90 }
91
92 BOTAN_ASSERT_NOMSG(y_bits >= 1);
93 const size_t x_words = (x_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS;
94 const size_t y_words = y.sig_words();
95
96 BigInt q = BigInt::with_capacity(x_words);
97 BigInt r = BigInt::with_capacity(y_words + 1);
98 BigInt t = BigInt::with_capacity(y_words + 1); // a temporary
99
100 r.set_bit(y_bits - 1);
101 for(size_t i = y_bits - 1; i != x_bits; ++i) {
102 const size_t b = x_bits - 1 - i;
103
104 if(i >= y_bits) {
105 bigint_shl1(r.mutable_data(), r.size(), r.size(), 1);
106 }
107
108 const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;
109
110 q.conditionally_set_bit(b, r_gte_y);
111
112 bigint_cnd_swap(static_cast<word>(r_gte_y), r.mutable_data(), t.mutable_data(), y_words + 1);
113 }
114
115 // No need for sign fixup
116
117 return q;
118}
119
120void ct_divide_word(const BigInt& x, word y, BigInt& q_out, word& r_out) {
121 if(y == 0) {
122 throw Invalid_Argument("ct_divide_word: cannot divide by zero");
123 }
124
125 const size_t x_words = x.sig_words();
126 const size_t x_bits = x.bits();
127
128 BigInt q = BigInt::with_capacity(x_words);
129 word r = 0;
130
131 for(size_t i = 0; i != x_bits; ++i) {
132 const size_t b = x_bits - 1 - i;
133 const bool x_b = x.get_bit(b);
134
135 const auto r_carry = CT::Mask<word>::expand_top_bit(r);
136
137 r <<= 1;
138 r += x_b;
139
140 const auto r_gte_y = CT::Mask<word>::is_gte(r, y) | r_carry;
141 q.conditionally_set_bit(b, r_gte_y.as_bool());
142 r = r_gte_y.select(r - y, r);
143 }
144
145 if(x.is_negative()) {
146 q.flip_sign();
147 if(r != 0) {
148 --q;
149 r = y - r;
150 }
151 }
152
153 r_out = r;
154 q_out = q;
155}
156
157word ct_mod_word(const BigInt& x, word y) {
158 BOTAN_ARG_CHECK(x.is_positive(), "The argument x must be positive");
159 BOTAN_ARG_CHECK(y != 0, "Cannot divide by zero");
160
161 const size_t x_bits = x.bits();
162
163 word r = 0;
164
165 for(size_t i = 0; i != x_bits; ++i) {
166 const size_t b = x_bits - 1 - i;
167 const bool x_b = x.get_bit(b);
168
169 const auto r_carry = CT::Mask<word>::expand_top_bit(r);
170
171 r <<= 1;
172 r += x_b;
173
174 const auto r_gte_y = CT::Mask<word>::is_gte(r, y) | r_carry;
175 r = r_gte_y.select(r - y, r);
176 }
177
178 return r;
179}
180
181BigInt ct_modulo(const BigInt& x, const BigInt& y) {
182 if(y.is_negative() || y.is_zero()) {
183 throw Invalid_Argument("ct_modulo requires y > 0");
184 }
185
186 const size_t y_words = y.sig_words();
187
188 const size_t x_bits = x.bits();
189
190 BigInt r = BigInt::with_capacity(y_words);
191 BigInt t = BigInt::with_capacity(y_words);
192
193 for(size_t i = 0; i != x_bits; ++i) {
194 const size_t b = x_bits - 1 - i;
195 const bool x_b = x.get_bit(b);
196
197 r <<= 1;
198 r.conditionally_set_bit(0, x_b);
199
200 const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;
201
202 r.ct_cond_swap(r_gte_y, t);
203 }
204
205 if(x.is_negative()) {
206 if(r.is_nonzero()) {
207 r = y - r;
208 }
209 }
210
211 return r;
212}
213
214/*
215* Solve x = q * y + r
216*
217* See Handbook of Applied Cryptography section 14.2.5
218*/
219void vartime_divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out) {
220 if(y_arg.is_zero()) {
221 throw Invalid_Argument("vartime_divide: cannot divide by zero");
222 }
223
224 const size_t y_words = y_arg.sig_words();
225
226 BOTAN_ASSERT_NOMSG(y_words > 0);
227
228 BigInt y = y_arg;
229
230 BigInt r = x;
231 BigInt q = BigInt::zero();
233
236
237 // Calculate shifts needed to normalize y with high bit set
238 const size_t shifts = y.top_bits_free();
239
240 y <<= shifts;
241 r <<= shifts;
242
243 // we know y has not changed size, since we only shifted up to set high bit
244 const size_t t = y_words - 1;
245 const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however
246
247 BOTAN_ASSERT_NOMSG(n >= t);
248
249 q.grow_to(n - t + 1);
250
251 word* q_words = q.mutable_data();
252
253 BigInt shifted_y = y << (BOTAN_MP_WORD_BITS * (n - t));
254
255 // Set q_{n-t} to number of times r > shifted_y
256 q_words[n - t] = r.reduce_below(shifted_y, ws);
257
258 const word y_t0 = y.word_at(t);
259 const word y_t1 = y.word_at(t - 1);
260 BOTAN_DEBUG_ASSERT((y_t0 >> (BOTAN_MP_WORD_BITS - 1)) == 1);
261
262 for(size_t j = n; j != t; --j) {
263 const word x_j0 = r.word_at(j);
264 const word x_j1 = r.word_at(j - 1);
265 const word x_j2 = r.word_at(j - 2);
266
267 word qjt = bigint_divop_vartime(x_j0, x_j1, y_t0);
268
269 qjt = CT::Mask<word>::is_equal(x_j0, y_t0).select(WordInfo<word>::max, qjt);
270
271 // Per HAC 14.23, this operation is required at most twice
272 qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);
273 qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);
274 BOTAN_DEBUG_ASSERT(division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2) == false);
275
276 shifted_y >>= BOTAN_MP_WORD_BITS;
277 // Now shifted_y == y << (BOTAN_MP_WORD_BITS * (j-t-1))
278
279 // TODO this sequence could be better
280 r -= qjt * shifted_y;
281 qjt -= r.is_negative();
282 r += static_cast<word>(r.is_negative()) * shifted_y;
283
284 q_words[j - t - 1] = qjt;
285 }
286
287 r >>= shifts;
288
289 sign_fixup(x, y_arg, q, r);
290
291 r_out = r;
292 q_out = q;
293}
294
295} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:98
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:29
static BigInt zero()
Definition bigint.h:50
size_t sig_words() const
Definition bigint.h:616
void conditionally_set_bit(size_t n, bool set_it)
Definition bigint.h:474
word * mutable_data()
Definition bigint.h:641
size_t size() const
Definition bigint.h:610
void grow_to(size_t n) const
Definition bigint.h:667
void flip_sign()
Definition bigint.h:587
size_t top_bits_free() const
Definition bigint.cpp:286
word word_at(size_t n) const
Definition bigint.h:548
void set_bit(size_t n)
Definition bigint.h:464
size_t bits() const
Definition bigint.cpp:295
const word * _data() const
Definition bigint.h:936
void ct_cond_swap(bool predicate, BigInt &other)
Definition bigint.cpp:480
bool is_zero() const
Definition bigint.h:458
size_t reduce_below(const BigInt &mod, secure_vector< word > &ws)
Definition bigint.cpp:317
bool is_negative() const
Definition bigint.h:560
bool is_nonzero() const
Definition bigint.h:452
bool is_positive() const
Definition bigint.h:566
bool get_bit(size_t n) const
Definition bigint.h:497
static BigInt with_capacity(size_t n)
Definition bigint.cpp:58
void set_sign(Sign sign)
Definition bigint.h:593
static constexpr Mask< T > is_gte(T x, T y)
Definition ct_utils.h:479
static constexpr Mask< T > expand_top_bit(T v)
Definition ct_utils.h:426
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:453
#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
void vartime_divide(const BigInt &x, const BigInt &y_arg, BigInt &q_out, BigInt &r_out)
Definition divide.cpp:219
word ct_mod_word(const BigInt &x, word y)
Definition divide.cpp:157
constexpr auto word_madd2(W a, W b, W *c) -> W
Definition mp_asmi.h:67
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:322
constexpr void bigint_shl1(W x[], size_t x_size, size_t x_words, size_t shift)
Definition mp_core.h:448
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition divide.cpp:181
void ct_divide(const BigInt &x, const BigInt &y, BigInt &q_out, BigInt &r_out)
Definition divide.cpp:48
void ct_divide_word(const BigInt &x, word y, BigInt &q_out, word &r_out)
Definition divide.cpp:120
BigInt ct_divide_pow2k(size_t k, const BigInt &y)
Definition divide.cpp:80
constexpr auto bigint_ct_is_lt(const W x[], size_t x_size, const W y[], size_t y_size, bool lt_or_equal=false) -> CT::Mask< W >
Definition mp_core.h:620
const SIMD_8x32 & b
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61
constexpr auto bigint_divop_vartime(W n1, W n0, W d) -> W
Definition mp_core.h:734