Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

bigint.cpp
Go to the documentation of this file.
1 /*
2 * BigInt Base
3 * (C) 1999-2011,2012,2014,2019 Jack Lloyd
4 *
5 * Botan is released under the Simplified BSD License (see license.txt)
6 */
7
8 #include <botan/bigint.h>
9 #include <botan/internal/mp_core.h>
10 #include <botan/internal/rounding.h>
11 #include <botan/internal/bit_ops.h>
12 #include <botan/internal/ct_utils.h>
13 #include <botan/loadstor.h>
14
15 namespace Botan {
16
17 BigInt::BigInt(const word words[], size_t length)
18 {
19 m_data.set_words(words, length);
20 }
21
22 /*
23 * Construct a BigInt from a regular number
24 */
25 BigInt::BigInt(uint64_t n)
26 {
27 if(n > 0)
28 {
29 #if BOTAN_MP_WORD_BITS == 32
30 m_data.set_word_at(0, static_cast<word>(n));
31 m_data.set_word_at(1, static_cast<word>(n >> 32));
32 #else
33 m_data.set_word_at(0, n);
34 #endif
35 }
36
37 }
38
39 /*
40 * Construct a BigInt of the specified size
41 */
42 BigInt::BigInt(Sign s, size_t size)
43 {
44 m_data.set_size(size);
45 m_signedness = s;
46 }
47
48 /*
49 * Construct a BigInt from a string
50 */
51 BigInt::BigInt(const std::string& str)
52 {
53 Base base = Decimal;
54 size_t markers = 0;
55 bool negative = false;
56
57 if(str.length() > 0 && str[0] == '-')
58 {
59 markers += 1;
60 negative = true;
61 }
62
63 if(str.length() > markers + 2 && str[markers ] == '0' &&
64 str[markers + 1] == 'x')
65 {
66 markers += 2;
67 base = Hexadecimal;
68 }
69
70 *this = decode(cast_char_ptr_to_uint8(str.data()) + markers,
71 str.length() - markers, base);
72
73 if(negative) set_sign(Negative);
74 else set_sign(Positive);
75 }
76
77 BigInt::BigInt(const uint8_t input[], size_t length)
78 {
79 binary_decode(input, length);
80 }
81
82 /*
83 * Construct a BigInt from an encoded BigInt
84 */
85 BigInt::BigInt(const uint8_t input[], size_t length, Base base)
86 {
87 *this = decode(input, length, base);
88 }
89
90 BigInt::BigInt(const uint8_t buf[], size_t length, size_t max_bits)
91 {
92 const size_t max_bytes = std::min(length, (max_bits + 7) / 8);
93 binary_decode(buf, max_bytes);
94
95 const size_t b = this->bits();
96 if(b > max_bits)
97 {
98 *this >>= (b - max_bits);
99 }
100 }
101
102 /*
103 * Construct a BigInt from an encoded BigInt
104 */
105 BigInt::BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit)
106 {
107 randomize(rng, bits, set_high_bit);
108 }
109
110 uint8_t BigInt::byte_at(size_t n) const
111 {
112 return get_byte(sizeof(word) - (n % sizeof(word)) - 1,
113 word_at(n / sizeof(word)));
114 }
115
116 int32_t BigInt::cmp_word(word other) const
117 {
118 if(is_negative())
119 return -1; // other is positive ...
120
121 const size_t sw = this->sig_words();
122 if(sw > 1)
123 return 1; // must be larger since other is just one word ...
124
125 return bigint_cmp(this->data(), sw, &other, 1);
126 }
127
128 /*
129 * Comparison Function
130 */
131 int32_t BigInt::cmp(const BigInt& other, bool check_signs) const
132 {
133 if(check_signs)
134 {
135 if(other.is_positive() && this->is_negative())
136 return -1;
137
138 if(other.is_negative() && this->is_positive())
139 return 1;
140
141 if(other.is_negative() && this->is_negative())
142 return (-bigint_cmp(this->data(), this->size(),
143 other.data(), other.size()));
144 }
145
146 return bigint_cmp(this->data(), this->size(),
147 other.data(), other.size());
148 }
149
150 bool BigInt::is_equal(const BigInt& other) const
151 {
152 if(this->sign() != other.sign())
153 return false;
154
155 return bigint_ct_is_eq(this->data(), this->sig_words(),
156 other.data(), other.sig_words()).is_set();
157 }
158
159 bool BigInt::is_less_than(const BigInt& other) const
160 {
161 if(this->is_negative() && other.is_positive())
162 return true;
163
164 if(this->is_positive() && other.is_negative())
165 return false;
166
167 if(other.is_negative() && this->is_negative())
168 {
169 return !bigint_ct_is_lt(other.data(), other.sig_words(),
170 this->data(), this->sig_words(), true).is_set();
171 }
172
173 return bigint_ct_is_lt(this->data(), this->sig_words(),
174 other.data(), other.sig_words()).is_set();
175 }
176
177 void BigInt::encode_words(word out[], size_t size) const
178 {
179 const size_t words = sig_words();
180
181 if(words > size)
182 throw Encoding_Error("BigInt::encode_words value too large to encode");
183
184 clear_mem(out, size);
185 copy_mem(out, data(), words);
186 }
187
188 size_t BigInt::Data::calc_sig_words() const
189 {
190 const size_t sz = m_reg.size();
191 size_t sig = sz;
192
193 word sub = 1;
194
195 for(size_t i = 0; i != sz; ++i)
196 {
197 const word w = m_reg[sz - i - 1];
198 sub &= ct_is_zero(w);
199 sig -= sub;
200 }
201
202 /*
203 * This depends on the data so is poisoned, but unpoison it here as
204 * later conditionals are made on the size.
205 */
206 CT::unpoison(sig);
207
208 return sig;
209 }
210
211 /*
212 * Return bits {offset...offset+length}
213 */
214 uint32_t BigInt::get_substring(size_t offset, size_t length) const
215 {
216 if(length == 0 || length > 32)
217 throw Invalid_Argument("BigInt::get_substring invalid substring length");
218
219 const size_t byte_offset = offset / 8;
220 const size_t shift = (offset % 8);
221 const uint32_t mask = 0xFFFFFFFF >> (32 - length);
222
223 const uint8_t b0 = byte_at(byte_offset);
224 const uint8_t b1 = byte_at(byte_offset + 1);
225 const uint8_t b2 = byte_at(byte_offset + 2);
226 const uint8_t b3 = byte_at(byte_offset + 3);
227 const uint8_t b4 = byte_at(byte_offset + 4);
228 const uint64_t piece = make_uint64(0, 0, 0, b4, b3, b2, b1, b0);
229
230 return static_cast<uint32_t>((piece >> shift) & mask);
231 }
232
233 /*
234 * Convert this number to a uint32_t, if possible
235 */
236 uint32_t BigInt::to_u32bit() const
237 {
238 if(is_negative())
239 throw Encoding_Error("BigInt::to_u32bit: Number is negative");
240 if(bits() > 32)
241 throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
242
243 uint32_t out = 0;
244 for(size_t i = 0; i != 4; ++i)
245 out = (out << 8) | byte_at(3-i);
246 return out;
247 }
248
249 /*
250 * Set bit number n
251 */
252 void BigInt::conditionally_set_bit(size_t n, bool set_it)
253 {
254 const size_t which = n / BOTAN_MP_WORD_BITS;
255 const word mask = static_cast<word>(set_it) << (n % BOTAN_MP_WORD_BITS);
256 m_data.set_word_at(which, word_at(which) | mask);
257 }
258
259 /*
260 * Clear bit number n
261 */
262 void BigInt::clear_bit(size_t n)
263 {
264 const size_t which = n / BOTAN_MP_WORD_BITS;
265
266 if(which < size())
267 {
268 const word mask = ~(static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS));
269 m_data.set_word_at(which, word_at(which) & mask);
270 }
271 }
272
273 size_t BigInt::bytes() const
274 {
275 return round_up(bits(), 8) / 8;
276 }
277
278 size_t BigInt::top_bits_free() const
279 {
280 const size_t words = sig_words();
281
282 const word top_word = word_at(words - 1);
283 const size_t bits_used = high_bit(top_word);
284 CT::unpoison(bits_used);
285 return BOTAN_MP_WORD_BITS - bits_used;
286 }
287
288 size_t BigInt::bits() const
289 {
290 const size_t words = sig_words();
291
292 if(words == 0)
293 return 0;
294
295 const size_t full_words = (words - 1) * BOTAN_MP_WORD_BITS;
296 const size_t top_bits = BOTAN_MP_WORD_BITS - top_bits_free();
297
298 return full_words + top_bits;
299 }
300
301 /*
302 * Calcluate the size in a certain base
303 */
304 size_t BigInt::encoded_size(Base base) const
305 {
306 static const double LOG_2_BASE_10 = 0.30102999566;
307
308 if(base == Binary)
309 return bytes();
310 else if(base == Hexadecimal)
311 return 2*bytes();
312 else if(base == Decimal)
313 return static_cast<size_t>((bits() * LOG_2_BASE_10) + 1);
314 else
315 throw Invalid_Argument("Unknown base for BigInt encoding");
316 }
317
318 /*
319 * Return the negation of this number
320 */
321 BigInt BigInt::operator-() const
322 {
323 BigInt x = (*this);
324 x.flip_sign();
325 return x;
326 }
327
328 size_t BigInt::reduce_below(const BigInt& p, secure_vector<word>& ws)
329 {
330 if(p.is_negative() || this->is_negative())
331 throw Invalid_Argument("BigInt::reduce_below both values must be positive");
332
333 const size_t p_words = p.sig_words();
334
335 if(size() < p_words + 1)
336 grow_to(p_words + 1);
337
338 if(ws.size() < p_words + 1)
339 ws.resize(p_words + 1);
340
341 clear_mem(ws.data(), ws.size());
342
343 size_t reductions = 0;
344
345 for(;;)
346 {
347 word borrow = bigint_sub3(ws.data(), data(), p_words + 1, p.data(), p_words);
348 if(borrow)
349 break;
350
351 ++reductions;
352 swap_reg(ws);
353 }
354
355 return reductions;
356 }
357
358 void BigInt::ct_reduce_below(const BigInt& mod, secure_vector<word>& ws, size_t bound)
359 {
360 if(mod.is_negative() || this->is_negative())
361 throw Invalid_Argument("BigInt::ct_reduce_below both values must be positive");
362
363 const size_t mod_words = mod.sig_words();
364
365 grow_to(mod_words);
366
367 const size_t sz = size();
368
369 ws.resize(sz);
370
371 clear_mem(ws.data(), sz);
372
373 for(size_t i = 0; i != bound; ++i)
374 {
375 word borrow = bigint_sub3(ws.data(), data(), sz, mod.data(), mod_words);
376
377 CT::Mask<word>::is_zero(borrow).select_n(mutable_data(), ws.data(), data(), sz);
378 }
379 }
380
381 /*
382 * Return the absolute value of this number
383 */
384 BigInt BigInt::abs() const
385 {
386 BigInt x = (*this);
387 x.set_sign(Positive);
388 return x;
389 }
390
391 void BigInt::binary_encode(uint8_t buf[]) const
392 {
393 this->binary_encode(buf, bytes());
394 }
395
396 /*
397 * Encode this number into bytes
398 */
399 void BigInt::binary_encode(uint8_t output[], size_t len) const
400 {
401 const size_t full_words = len / sizeof(word);
402 const size_t extra_bytes = len % sizeof(word);
403
404 for(size_t i = 0; i != full_words; ++i)
405 {
406 const word w = word_at(i);
407 store_be(w, output + (len - (i+1)*sizeof(word)));
408 }
409
410 if(extra_bytes > 0)
411 {
412 const word w = word_at(full_words);
413
414 for(size_t i = 0; i != extra_bytes; ++i)
415 {
416 output[extra_bytes - i - 1] = get_byte(sizeof(word) - i - 1, w);
417 }
418 }
419 }
420
421 /*
422 * Set this number to the value in buf
423 */
424 void BigInt::binary_decode(const uint8_t buf[], size_t length)
425 {
426 clear();
427
428 const size_t full_words = length / sizeof(word);
429 const size_t extra_bytes = length % sizeof(word);
430
431 secure_vector<word> reg((round_up(full_words + (extra_bytes > 0 ? 1 : 0), 8)));
432
433 for(size_t i = 0; i != full_words; ++i)
434 {
435 reg[i] = load_be<word>(buf + length - sizeof(word)*(i+1), 0);
436 }
437
438 if(extra_bytes > 0)
439 {
440 for(size_t i = 0; i != extra_bytes; ++i)
441 reg[full_words] = (reg[full_words] << 8) | buf[i];
442 }
443
444 m_data.swap(reg);
445 }
446
447 void BigInt::ct_cond_swap(bool predicate, BigInt& other)
448 {
449 const size_t max_words = std::max(size(), other.size());
450 grow_to(max_words);
451 other.grow_to(max_words);
452
453 bigint_cnd_swap(predicate, this->mutable_data(), other.mutable_data(), max_words);
454 }
455
456 void BigInt::cond_flip_sign(bool predicate)
457 {
458 // This code is assuming Negative == 0, Positive == 1
459
460 const auto mask = CT::Mask<uint8_t>::expand(predicate);
461
462 const uint8_t current_sign = static_cast<uint8_t>(sign());
463
464 const uint8_t new_sign = mask.select(current_sign ^ 1, current_sign);
465
466 set_sign(static_cast<Sign>(new_sign));
467 }
468
469 void BigInt::ct_cond_assign(bool predicate, const BigInt& other)
470 {
471 const size_t t_words = size();
472 const size_t o_words = other.size();
473
474 if(o_words < t_words)
475 grow_to(o_words);
476
477 const size_t r_words = std::max(t_words, o_words);
478
479 const auto mask = CT::Mask<word>::expand(predicate);
480
481 for(size_t i = 0; i != r_words; ++i)
482 {
483 const word o_word = other.word_at(i);
484 const word t_word = this->word_at(i);
485 this->set_word_at(i, mask.select(o_word, t_word));
486 }
487
488 if(sign() != other.sign())
489 {
490 cond_flip_sign(predicate);
491 }
492 }
493
494 #if defined(BOTAN_HAS_VALGRIND)
495 void BigInt::const_time_poison() const
496 {
497 CT::poison(m_data.const_data(), m_data.size());
498 }
499
500 void BigInt::const_time_unpoison() const
501 {
502 CT::unpoison(m_data.const_data(), m_data.size());
503 }
504 #endif
505
506 void BigInt::const_time_lookup(secure_vector<word>& output,
507 const std::vector<BigInt>& vec,
508 size_t idx)
509 {
510 const size_t words = output.size();
511
512 clear_mem(output.data(), output.size());
513
514 CT::poison(&idx, sizeof(idx));
515
516 for(size_t i = 0; i != vec.size(); ++i)
517 {
518 BOTAN_ASSERT(vec[i].size() >= words,
519 "Word size as expected in const_time_lookup");
520
521 const auto mask = CT::Mask<word>::is_equal(i, idx);
522
523 for(size_t w = 0; w != words; ++w)
524 {
525 const word viw = vec[i].word_at(w);
526 output[w] = mask.if_set_return(viw);
527 }
528 }
529
530 CT::unpoison(idx);
531 CT::unpoison(output.data(), output.size());
532 }
533
534 }
Botan::BigInt::encoded_size
size_t encoded_size(Base base=Binary) const
Definition: bigint.cpp:304
Botan::BigInt::word_at
word word_at(size_t n) const
Definition: bigint.h:506
Botan::BigInt::binary_encode
void binary_encode(uint8_t buf[]) const
Definition: bigint.cpp:391
Botan::BigInt::sig_words
size_t sig_words() const
Definition: bigint.h:584
Botan::Invalid_Argument
Definition: exceptn.h:136
Botan::BigInt::Hexadecimal
Definition: bigint.h:30
Botan::BigInt::is_equal
bool is_equal(const BigInt &n) const
Definition: bigint.cpp:150
Botan::BigInt::const_time_lookup
static void const_time_lookup(secure_vector< word > &output, const std::vector< BigInt > &vec, size_t idx)
Definition: bigint.cpp:506
Botan::BigInt
Definition: bigint.h:24
Botan::BigInt::Positive
Definition: bigint.h:35
Botan::BigInt::Decimal
Definition: bigint.h:30
Botan::RandomNumberGenerator
Definition: rng.h:24
Botan::store_be
void store_be(uint16_t in, uint8_t out[2])
Definition: loadstor.h:438
Botan::bigint_cmp
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:523
Botan::BigInt::to_u32bit
uint32_t to_u32bit() const
Definition: bigint.cpp:236
Botan::BigInt::randomize
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition: big_rand.cpp:17
Botan::clear_mem
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:112
Botan::BigInt::const_time_unpoison
void const_time_unpoison() const
Definition: bigint.h:733
Botan::get_byte
constexpr uint8_t get_byte(size_t byte_num, T input)
Definition: loadstor.h:41
Botan::cast_char_ptr_to_uint8
const uint8_t * cast_char_ptr_to_uint8(const char *s)
Definition: mem_ops.h:189
Botan::make_uint64
constexpr uint64_t make_uint64(uint8_t i0, uint8_t i1, uint8_t i2, uint8_t i3, uint8_t i4, uint8_t i5, uint8_t i6, uint8_t i7)
Definition: loadstor.h:87
Botan::BigInt::abs
BigInt abs() const
Definition: bigint.cpp:384
Botan::BigInt::mutable_data
word * mutable_data()
Definition: bigint.h:612
Botan::BigInt::swap_reg
void swap_reg(secure_vector< word > &reg)
Definition: bigint.h:165
Botan::BigInt::is_negative
bool is_negative() const
Definition: bigint.h:525
Botan::CT::poison
void poison(const T *p, size_t n)
Definition: ct_utils.h:48
Botan::bigint_sub3
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:342
Botan::BigInt::size
size_t size() const
Definition: bigint.h:578
BOTAN_ASSERT
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
Botan::BigInt::Negative
Definition: bigint.h:35
Botan::BigInt::cmp
int32_t cmp(const BigInt &n, bool check_signs=true) const
Definition: bigint.cpp:131
Botan::BigInt::bits
size_t bits() const
Definition: bigint.cpp:288
Botan::CT::Mask::expand
static Mask< T > expand(T v)
Definition: ct_utils.h:123
Botan::secure_vector
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:65
Botan::BigInt::top_bits_free
size_t top_bits_free() const
Definition: bigint.cpp:278
Botan::BigInt::ct_cond_swap
void ct_cond_swap(bool predicate, BigInt &other)
Definition: bigint.cpp:447
Botan::bigint_cnd_swap
void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
Definition: mp_core.h:29
Botan::ct_is_zero
T ct_is_zero(T x)
Definition: bit_ops.h:32
Botan::bigint_ct_is_eq
CT::Mask< word > bigint_ct_is_eq(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:611
Botan::BigInt::Sign
Sign
Definition: bigint.h:35
Botan::BigInt::data
const word * data() const
Definition: bigint.h:618
Botan::high_bit
size_t high_bit(T n)
Definition: bit_ops.h:55
Botan::copy_mem
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:132
Botan
Definition: alg_id.cpp:13
Botan::BigInt::Binary
Definition: bigint.h:30
Botan::BigInt::clear
void clear()
Definition: bigint.h:364
Botan::BigInt::conditionally_set_bit
void conditionally_set_bit(size_t n, bool set_it)
Definition: bigint.cpp:252
Botan::BigInt::encode_words
void encode_words(word out[], size_t size) const
Definition: bigint.cpp:177
Botan::BigInt::cond_flip_sign
void cond_flip_sign(bool predicate)
Definition: bigint.cpp:456
Botan::BigInt::Base
Base
Definition: bigint.h:30
Botan::BigInt::get_substring
uint32_t get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:214
Botan::bigint_ct_is_lt
CT::Mask< word > bigint_ct_is_lt(const word x[], size_t x_size, const word y[], size_t y_size, bool lt_or_equal=false)
Definition: mp_core.h:574
Botan::Encoding_Error
Definition: exceptn.h:184
Botan::BigInt::decode
static BigInt decode(const uint8_t buf[], size_t length)
Definition: bigint.h:798
Botan::BigInt::reduce_below
size_t reduce_below(const BigInt &mod, secure_vector< word > &ws)
Definition: bigint.cpp:328
Botan::BigInt::grow_to
void grow_to(size_t n) const
Definition: bigint.h:634
Botan::BigInt::is_positive
bool is_positive() const
Definition: bigint.h:531
Botan::BigInt::set_word_at
void set_word_at(size_t i, word w)
Definition: bigint.h:511
Botan::BigInt::binary_decode
void binary_decode(const uint8_t buf[], size_t length)
Definition: bigint.cpp:424
Botan::BigInt::is_less_than
bool is_less_than(const BigInt &n) const
Definition: bigint.cpp:159
Botan::CT::unpoison
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:59
Botan::BigInt::ct_reduce_below
void ct_reduce_below(const BigInt &mod, secure_vector< word > &ws, size_t bound)
Definition: bigint.cpp:358
Botan::BigInt::operator-
BigInt operator-() const
Definition: bigint.cpp:321
Botan::BigInt::BigInt
BigInt()=default
Botan::BigInt::flip_sign
void flip_sign()
Definition: bigint.h:552
Botan::BigInt::cmp_word
int32_t cmp_word(word n) const
Definition: bigint.cpp:116
Botan::BigInt::clear_bit
void clear_bit(size_t n)
Definition: bigint.cpp:262
Botan::CT::Mask::is_zero
static Mask< T > is_zero(T x)
Definition: ct_utils.h:141
Botan::round_up
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21
Botan::BigInt::set_sign
void set_sign(Sign sign)
Definition: bigint.h:561
Botan::CT::Mask::is_equal
static Mask< T > is_equal(T x, T y)
Definition: ct_utils.h:149
Botan::BigInt::byte_at
uint8_t byte_at(size_t n) const
Definition: bigint.cpp:110
Botan::BigInt::ct_cond_assign
void ct_cond_assign(bool predicate, const BigInt &other)
Definition: bigint.cpp:469
Botan::BigInt::sign
Sign sign() const
Definition: bigint.h:537
Botan::BigInt::const_time_poison
void const_time_poison() const
Definition: bigint.h:732
Botan::BigInt::bytes
size_t bytes() const
Definition: bigint.cpp:273