Botan  2.7.0
Crypto and TLS for C++11
bigint.cpp
Go to the documentation of this file.
1 /*
2 * BigInt Base
3 * (C) 1999-2011,2012,2014 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 
14 namespace Botan {
15 
16 BigInt::BigInt(const word words[], size_t length)
17  {
18  m_reg.assign(words, words + length);
19  }
20 
21 /*
22 * Construct a BigInt from a regular number
23 */
24 BigInt::BigInt(uint64_t n)
25  {
26  if(n == 0)
27  return;
28 
29  const size_t limbs_needed = sizeof(uint64_t) / sizeof(word);
30 
31  m_reg.resize(limbs_needed);
32  for(size_t i = 0; i != limbs_needed; ++i)
33  m_reg[i] = ((n >> (i*BOTAN_MP_WORD_BITS)) & MP_WORD_MASK);
34  }
35 
36 /*
37 * Construct a BigInt of the specified size
38 */
39 BigInt::BigInt(Sign s, size_t size)
40  {
41  m_reg.resize(round_up(size, 8));
42  m_signedness = s;
43  }
44 
45 /*
46 * Copy constructor
47 */
48 BigInt::BigInt(const BigInt& other)
49  {
50  m_reg = other.m_reg;
51  m_signedness = other.m_signedness;
52  }
53 
54 /*
55 * Construct a BigInt from a string
56 */
57 BigInt::BigInt(const std::string& str)
58  {
59  Base base = Decimal;
60  size_t markers = 0;
61  bool negative = false;
62 
63  if(str.length() > 0 && str[0] == '-')
64  {
65  markers += 1;
66  negative = true;
67  }
68 
69  if(str.length() > markers + 2 && str[markers ] == '0' &&
70  str[markers + 1] == 'x')
71  {
72  markers += 2;
73  base = Hexadecimal;
74  }
75 
76  *this = decode(cast_char_ptr_to_uint8(str.data()) + markers,
77  str.length() - markers, base);
78 
79  if(negative) set_sign(Negative);
80  else set_sign(Positive);
81  }
82 
83 BigInt::BigInt(const uint8_t input[], size_t length)
84  {
85  binary_decode(input, length);
86  }
87 
88 /*
89 * Construct a BigInt from an encoded BigInt
90 */
91 BigInt::BigInt(const uint8_t input[], size_t length, Base base)
92  {
93  *this = decode(input, length, base);
94  }
95 
96 BigInt::BigInt(const uint8_t buf[], size_t length, size_t max_bits)
97  {
98  const size_t max_bytes = std::min(length, (max_bits + 7) / 8);
99  *this = decode(buf, max_bytes);
100 
101  const size_t b = this->bits();
102  if(b > max_bits)
103  {
104  *this >>= (b - max_bits);
105  }
106  }
107 
108 /*
109 * Construct a BigInt from an encoded BigInt
110 */
111 BigInt::BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit)
112  {
113  randomize(rng, bits, set_high_bit);
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->sig_words(),
143  other.data(), other.sig_words()));
144  }
145 
146  return bigint_cmp(this->data(), this->sig_words(),
147  other.data(), other.sig_words());
148  }
149 
150 void BigInt::encode_words(word out[], size_t size) const
151  {
152  const size_t words = sig_words();
153 
154  if(words > size)
155  throw Encoding_Error("BigInt::encode_words value too large to encode");
156 
157  clear_mem(out, size);
158  copy_mem(out, data(), words);
159  }
160 
161 /*
162 * Return bits {offset...offset+length}
163 */
164 uint32_t BigInt::get_substring(size_t offset, size_t length) const
165  {
166  if(length > 32)
167  throw Invalid_Argument("BigInt::get_substring: Substring size " + std::to_string(length) + " too big");
168 
169  uint64_t piece = 0;
170  for(size_t i = 0; i != 8; ++i)
171  {
172  const uint8_t part = byte_at((offset / 8) + (7-i));
173  piece = (piece << 8) | part;
174  }
175 
176  const uint64_t mask = (static_cast<uint64_t>(1) << length) - 1;
177  const size_t shift = (offset % 8);
178 
179  return static_cast<uint32_t>((piece >> shift) & mask);
180  }
181 
182 /*
183 * Convert this number to a uint32_t, if possible
184 */
185 uint32_t BigInt::to_u32bit() const
186  {
187  if(is_negative())
188  throw Encoding_Error("BigInt::to_u32bit: Number is negative");
189  if(bits() > 32)
190  throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
191 
192  uint32_t out = 0;
193  for(size_t i = 0; i != 4; ++i)
194  out = (out << 8) | byte_at(3-i);
195  return out;
196  }
197 
198 /*
199 * Set bit number n
200 */
201 void BigInt::set_bit(size_t n)
202  {
203  const size_t which = n / BOTAN_MP_WORD_BITS;
204  const word mask = static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS);
205  if(which >= size()) grow_to(which + 1);
206  m_reg[which] |= mask;
207  }
208 
209 /*
210 * Clear bit number n
211 */
212 void BigInt::clear_bit(size_t n)
213  {
214  const size_t which = n / BOTAN_MP_WORD_BITS;
215  const word mask = static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS);
216  if(which < size())
217  m_reg[which] &= ~mask;
218  }
219 
220 size_t BigInt::bytes() const
221  {
222  return round_up(bits(), 8) / 8;
223  }
224 
225 /*
226 * Count how many bits are being used
227 */
228 size_t BigInt::bits() const
229  {
230  const size_t words = sig_words();
231 
232  if(words == 0)
233  return 0;
234 
235  const size_t full_words = words - 1;
236  return (full_words * BOTAN_MP_WORD_BITS + high_bit(word_at(full_words)));
237  }
238 
239 /*
240 * Calcluate the size in a certain base
241 */
242 size_t BigInt::encoded_size(Base base) const
243  {
244  static const double LOG_2_BASE_10 = 0.30102999566;
245 
246  if(base == Binary)
247  return bytes();
248  else if(base == Hexadecimal)
249  return 2*bytes();
250  else if(base == Decimal)
251  return static_cast<size_t>((bits() * LOG_2_BASE_10) + 1);
252  else
253  throw Invalid_Argument("Unknown base for BigInt encoding");
254  }
255 
256 /*
257 * Return the negation of this number
258 */
260  {
261  BigInt x = (*this);
262  x.flip_sign();
263  return x;
264  }
265 
267  {
268  if(p.is_negative())
269  throw Invalid_Argument("BigInt::reduce_below mod must be positive");
270 
271  const size_t p_words = p.sig_words();
272 
273  if(size() < p_words + 1)
274  grow_to(p_words + 1);
275 
276  if(ws.size() < p_words + 1)
277  ws.resize(p_words + 1);
278 
279  clear_mem(ws.data(), ws.size());
280 
281  for(;;)
282  {
283  word borrow = bigint_sub3(ws.data(), data(), p_words + 1, p.data(), p_words);
284 
285  if(borrow)
286  break;
287 
288  m_reg.swap(ws);
289  }
290  }
291 
292 /*
293 * Return the absolute value of this number
294 */
296  {
297  BigInt x = (*this);
298  x.set_sign(Positive);
299  return x;
300  }
301 
302 void BigInt::grow_to(size_t n)
303  {
304  if(n > size())
305  {
306  if(n <= m_reg.capacity())
307  m_reg.resize(m_reg.capacity());
308  else
309  m_reg.resize(round_up(n, 8));
310  }
311  }
312 
313 /*
314 * Encode this number into bytes
315 */
316 void BigInt::binary_encode(uint8_t output[]) const
317  {
318  const size_t sig_bytes = bytes();
319  for(size_t i = 0; i != sig_bytes; ++i)
320  output[sig_bytes-i-1] = byte_at(i);
321  }
322 
323 /*
324 * Set this number to the value in buf
325 */
326 void BigInt::binary_decode(const uint8_t buf[], size_t length)
327  {
328  const size_t WORD_BYTES = sizeof(word);
329 
330  clear();
331  m_reg.resize(round_up((length / WORD_BYTES) + 1, 8));
332 
333  for(size_t i = 0; i != length / WORD_BYTES; ++i)
334  {
335  const size_t top = length - WORD_BYTES*i;
336  for(size_t j = WORD_BYTES; j > 0; --j)
337  m_reg[i] = (m_reg[i] << 8) | buf[top - j];
338  }
339 
340  for(size_t i = 0; i != length % WORD_BYTES; ++i)
341  m_reg[length / WORD_BYTES] = (m_reg[length / WORD_BYTES] << 8) | buf[i];
342  }
343 
344 #if defined(BOTAN_HAS_VALGRIND)
345 void BigInt::const_time_poison() const
346  {
347  CT::poison(m_reg.data(), m_reg.size());
348  }
349 
350 void BigInt::const_time_unpoison() const
351  {
352  CT::unpoison(m_reg.data(), m_reg.size());
353  }
354 #endif
355 
357  const std::vector<BigInt>& vec,
358  size_t idx)
359  {
360  const size_t words = output.size();
361 
362  clear_mem(output.data(), output.size());
363 
364  CT::poison(&idx, sizeof(idx));
365 
366  for(size_t i = 0; i != vec.size(); ++i)
367  {
368  BOTAN_ASSERT(vec[i].size() >= words,
369  "Word size as expected in const_time_lookup");
370 
371  const word mask = CT::is_equal(i, idx);
372 
373  for(size_t w = 0; w != words; ++w)
374  output[w] |= CT::select<word>(mask, vec[i].word_at(w), 0);
375  }
376 
377  CT::unpoison(idx);
378  CT::unpoison(output.data(), output.size());
379  }
380 
381 }
bool is_negative() const
Definition: bigint.h:460
static void const_time_lookup(secure_vector< word > &output, const std::vector< BigInt > &vec, size_t idx)
Definition: bigint.cpp:356
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:456
size_t bits() const
Definition: bigint.cpp:228
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition: big_rand.cpp:17
int32_t cmp(const BigInt &n, bool check_signs=true) const
Definition: bigint.cpp:131
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:97
void set_bit(size_t n)
Definition: bigint.cpp:201
const uint8_t * cast_char_ptr_to_uint8(const char *s)
Definition: mem_ops.h:131
void poison(const T *p, size_t n)
Definition: ct_utils.h:46
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:276
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:210
void binary_encode(uint8_t buf[]) const
Definition: bigint.cpp:316
word word_at(size_t n) const
Definition: bigint.h:440
uint32_t get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:164
BigInt operator-() const
Definition: bigint.cpp:259
T is_equal(T x, T y)
Definition: ct_utils.h:136
const word * data() const
Definition: bigint.h:551
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:43
uint8_t byte_at(size_t n) const
Definition: bigint.h:429
void const_time_poison() const
Definition: bigint.h:623
void encode_words(word out[], size_t size) const
Definition: bigint.cpp:150
int32_t cmp_word(word n) const
Definition: bigint.cpp:116
size_t size() const
Definition: bigint.h:513
size_t high_bit(T n)
Definition: bit_ops.h:37
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:108
Definition: alg_id.cpp:13
size_t sig_words() const
Definition: bigint.h:519
size_t bytes() const
Definition: bigint.cpp:220
void clear()
Definition: bigint.h:314
const word MP_WORD_MASK
Definition: mp_core.h:17
void const_time_unpoison() const
Definition: bigint.h:624
void grow_to(size_t n)
Definition: bigint.cpp:302
size_t encoded_size(Base base=Binary) const
Definition: bigint.cpp:242
BigInt abs() const
Definition: bigint.cpp:295
uint32_t to_u32bit() const
Definition: bigint.cpp:185
void binary_decode(const uint8_t buf[], size_t length)
Definition: bigint.cpp:326
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:57
void reduce_below(const BigInt &mod, secure_vector< word > &ws)
Definition: bigint.cpp:266
BigInt()=default
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88
void flip_sign()
Definition: bigint.h:487
void clear_bit(size_t n)
Definition: bigint.cpp:212
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21
void set_sign(Sign sign)
Definition: bigint.h:496
bool is_positive() const
Definition: bigint.h:466
static BigInt decode(const uint8_t buf[], size_t length, Base base=Binary)
Definition: big_code.cpp:114