Botan 3.9.0
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_vartime(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 if(x3 != y3) {
41 return (y3 > x3);
42 }
43 if(x2 != y2) {
44 return (y2 > x2);
45 }
46 return (y1 > x1);
47}
48
49} // namespace
50
51void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out) {
52 if(y.is_zero()) {
53 throw Invalid_Argument("ct_divide: cannot divide by zero");
54 }
55
56 const size_t x_words = x.sig_words();
57 const size_t y_words = y.sig_words();
58
59 const size_t x_bits = x.bits();
60
61 BigInt q = BigInt::with_capacity(x_words);
62 BigInt r = BigInt::with_capacity(y_words);
63 BigInt t = BigInt::with_capacity(y_words); // a temporary
64
65 for(size_t i = 0; i != x_bits; ++i) {
66 const size_t b = x_bits - 1 - i;
67 const bool x_b = x.get_bit(b);
68
69 r <<= 1;
70 r.conditionally_set_bit(0, x_b);
71
72 const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;
73
74 q.conditionally_set_bit(b, r_gte_y);
75 r.ct_cond_swap(r_gte_y, t);
76 }
77
78 sign_fixup(x, y, q, r);
79 r_out = r;
80 q_out = q;
81}
82
83BigInt ct_divide_pow2k(size_t k, const BigInt& y) {
84 BOTAN_ARG_CHECK(!y.is_zero(), "Cannot divide by zero");
85 BOTAN_ARG_CHECK(!y.is_negative(), "Negative divisor not supported");
86 BOTAN_ARG_CHECK(k > 1, "Invalid k");
87
88 const size_t x_bits = k + 1;
89 const size_t y_bits = y.bits();
90
91 if(x_bits < y_bits) {
92 return BigInt::zero();
93 }
94
95 BOTAN_ASSERT_NOMSG(y_bits >= 1);
96 const size_t x_words = (x_bits + WordInfo<word>::bits - 1) / WordInfo<word>::bits;
97 const size_t y_words = y.sig_words();
98
99 BigInt q = BigInt::with_capacity(x_words);
100 BigInt r = BigInt::with_capacity(y_words + 1);
101 BigInt t = BigInt::with_capacity(y_words + 1); // a temporary
102
103 r.set_bit(y_bits - 1);
104 for(size_t i = y_bits - 1; i != x_bits; ++i) {
105 const size_t b = x_bits - 1 - i;
106
107 if(i >= y_bits) {
108 bigint_shl1(r.mutable_data(), r.size(), r.size(), 1);
109 }
110
111 const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;
112
113 q.conditionally_set_bit(b, r_gte_y);
114
115 bigint_cnd_swap(static_cast<word>(r_gte_y), r.mutable_data(), t.mutable_data(), y_words + 1);
116 }
117
118 // No need for sign fixup
119
120 return q;
121}
122
123void ct_divide_word(const BigInt& x, word y, BigInt& q_out, word& r_out) {
124 if(y == 0) {
125 throw Invalid_Argument("ct_divide_word: cannot divide by zero");
126 }
127
128 const size_t x_words = x.sig_words();
129 const size_t x_bits = x.bits();
130
131 BigInt q = BigInt::with_capacity(x_words);
132 word r = 0;
133
134 for(size_t i = 0; i != x_bits; ++i) {
135 const size_t b = x_bits - 1 - i;
136 const bool x_b = x.get_bit(b);
137
138 const auto r_carry = CT::Mask<word>::expand_top_bit(r);
139
140 r <<= 1;
141 r += static_cast<word>(x_b);
142
143 const auto r_gte_y = CT::Mask<word>::is_gte(r, y) | r_carry;
144 q.conditionally_set_bit(b, r_gte_y.as_bool());
145 r = r_gte_y.select(r - y, r);
146 }
147
148 if(x.is_negative()) {
149 q.flip_sign();
150 if(r != 0) {
151 --q;
152 r = y - r;
153 }
154 }
155
156 r_out = r;
157 q_out = q;
158}
159
161 BigInt q;
162 word r = 0;
163 ct_divide_word(x, y, q, r);
164 BOTAN_UNUSED(r);
165 return q;
166}
167
169 BOTAN_ARG_CHECK(x.is_positive(), "The argument x must be positive");
170 BOTAN_ARG_CHECK(y != 0, "Cannot divide by zero");
171
172 const size_t x_bits = x.bits();
173
174 word r = 0;
175
176 for(size_t i = 0; i != x_bits; ++i) {
177 const size_t b = x_bits - 1 - i;
178 const bool x_b = x.get_bit(b);
179
180 const auto r_carry = CT::Mask<word>::expand_top_bit(r);
181
182 r <<= 1;
183 r += static_cast<word>(x_b);
184
185 const auto r_gte_y = CT::Mask<word>::is_gte(r, y) | r_carry;
186 r = r_gte_y.select(r - y, r);
187 }
188
189 return r;
190}
191
192BigInt ct_modulo(const BigInt& x, const BigInt& y) {
193 if(y.is_negative() || y.is_zero()) {
194 throw Invalid_Argument("ct_modulo requires y > 0");
195 }
196
197 const size_t y_words = y.sig_words();
198
199 const size_t x_bits = x.bits();
200
201 BigInt r = BigInt::with_capacity(y_words);
202 BigInt t = BigInt::with_capacity(y_words);
203
204 for(size_t i = 0; i != x_bits; ++i) {
205 const size_t b = x_bits - 1 - i;
206 const bool x_b = x.get_bit(b);
207
208 r <<= 1;
209 r.conditionally_set_bit(0, x_b);
210
211 const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;
212
213 r.ct_cond_swap(r_gte_y, t);
214 }
215
216 if(x.is_negative()) {
217 if(r.is_nonzero()) {
218 r = y - r;
219 }
220 }
221
222 return r;
223}
224
225/*
226* Solve x = q * y + r
227*
228* See Handbook of Applied Cryptography section 14.2.5
229*/
230void vartime_divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out) {
231 if(y_arg.is_zero()) {
232 throw Invalid_Argument("vartime_divide: cannot divide by zero");
233 }
234
235 const size_t y_words = y_arg.sig_words();
236
237 BOTAN_ASSERT_NOMSG(y_words > 0);
238
239 BigInt y = y_arg;
240
241 BigInt r = x;
242 BigInt q = BigInt::zero();
244
247
248 // Calculate shifts needed to normalize y with high bit set
249 const size_t shifts = y.top_bits_free();
250
251 if(shifts > 0) {
252 y <<= shifts;
253 r <<= shifts;
254 }
255
256 // we know y has not changed size, since we only shifted up to set high bit
257 const size_t t = y_words - 1;
258 const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however
259
260 BOTAN_ASSERT_NOMSG(n >= t);
261
262 q.grow_to(n - t + 1);
263
264 word* q_words = q.mutable_data();
265
266 BigInt shifted_y = y << (WordInfo<word>::bits * (n - t));
267
268 // Set q_{n-t} to number of times r > shifted_y
269 q_words[n - t] = r.reduce_below(shifted_y, ws);
270
271 const word y_t0 = y.word_at(t);
272 const word y_t1 = y.word_at(t - 1);
273 BOTAN_DEBUG_ASSERT((y_t0 >> (WordInfo<word>::bits - 1)) == 1);
274
275 for(size_t j = n; j != t; --j) {
276 const word x_j0 = r.word_at(j);
277 const word x_j1 = r.word_at(j - 1);
278 const word x_j2 = r.word_at(j - 2);
279
280 word qjt = (x_j0 == y_t0) ? WordInfo<word>::max : bigint_divop_vartime(x_j0, x_j1, y_t0);
281
282 // Per HAC 14.23, this operation is required at most twice
283 for(size_t k = 0; k != 2; ++k) {
284 if(division_check_vartime(qjt, y_t0, y_t1, x_j0, x_j1, x_j2)) {
285 qjt--;
286 } else {
287 break;
288 }
289 }
290
291 shifted_y >>= WordInfo<word>::bits;
292 // Now shifted_y == y << (WordInfo<word>::bits * (j-t-1))
293
294 // TODO this sequence could be better
295 r -= qjt * shifted_y;
296 if(r.is_negative()) {
297 qjt--;
298 r += shifted_y;
300 }
301
302 q_words[j - t - 1] = qjt;
303 }
304
305 if(shifts > 0) {
306 r >>= shifts;
307 }
308
309 sign_fixup(x, y_arg, q, r);
310
311 r_out = r;
312 q_out = q;
313}
314
315} // namespace Botan
#define BOTAN_UNUSED
Definition assert.h:144
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:75
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:129
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
static BigInt zero()
Definition bigint.h:49
size_t sig_words() const
Definition bigint.h:615
void conditionally_set_bit(size_t n, bool set_it)
Definition bigint.h:473
word * mutable_data()
Definition bigint.h:640
size_t size() const
Definition bigint.h:609
void grow_to(size_t n) const
Definition bigint.h:666
void flip_sign()
Definition bigint.h:586
size_t top_bits_free() const
Definition bigint.cpp:302
word word_at(size_t n) const
Definition bigint.h:547
void set_bit(size_t n)
Definition bigint.h:463
size_t bits() const
Definition bigint.cpp:311
const word * _data() const
Definition bigint.h:936
void ct_cond_swap(bool predicate, BigInt &other)
Definition bigint.cpp:511
bool is_zero() const
Definition bigint.h:457
size_t reduce_below(const BigInt &mod, secure_vector< word > &ws)
Definition bigint.cpp:333
bool is_negative() const
Definition bigint.h:559
bool is_nonzero() const
Definition bigint.h:451
bool is_positive() const
Definition bigint.h:565
bool get_bit(size_t n) const
Definition bigint.h:496
static BigInt with_capacity(size_t n)
Definition bigint.cpp:50
void set_sign(Sign sign)
Definition bigint.h:592
static constexpr Mask< T > is_gte(T x, T y)
Definition ct_utils.h:496
static constexpr Mask< T > expand_top_bit(T v)
Definition ct_utils.h:443
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:230
word ct_mod_word(const BigInt &x, word y)
Definition divide.cpp:168
constexpr auto word_madd2(W a, W b, W *c) -> W
Definition mp_asmi.h:86
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:194
constexpr void bigint_shl1(W x[], size_t x_size, size_t x_words, size_t shift)
Definition mp_core.h:309
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition divide.cpp:192
void ct_divide(const BigInt &x, const BigInt &y, BigInt &q_out, BigInt &r_out)
Definition divide.cpp:51
void ct_divide_word(const BigInt &x, word y, BigInt &q_out, word &r_out)
Definition divide.cpp:123
BigInt ct_divide_pow2k(size_t k, const BigInt &y)
Definition divide.cpp:83
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:69
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
Definition types.h:119
constexpr auto bigint_divop_vartime(W n1, W n0, W d) -> W
Definition mp_core.h:535