Botan  2.6.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 /*
117 * Comparison Function
118 */
119 int32_t BigInt::cmp(const BigInt& other, bool check_signs) const
120  {
121  if(check_signs)
122  {
123  if(other.is_positive() && this->is_negative())
124  return -1;
125 
126  if(other.is_negative() && this->is_positive())
127  return 1;
128 
129  if(other.is_negative() && this->is_negative())
130  return (-bigint_cmp(this->data(), this->sig_words(),
131  other.data(), other.sig_words()));
132  }
133 
134  return bigint_cmp(this->data(), this->sig_words(),
135  other.data(), other.sig_words());
136  }
137 
138 void BigInt::encode_words(word out[], size_t size) const
139  {
140  const size_t words = sig_words();
141 
142  if(words > size)
143  throw Encoding_Error("BigInt::encode_words value too large to encode");
144 
145  clear_mem(out, size);
146  copy_mem(out, data(), words);
147  }
148 
149 /*
150 * Return bits {offset...offset+length}
151 */
152 uint32_t BigInt::get_substring(size_t offset, size_t length) const
153  {
154  if(length > 32)
155  throw Invalid_Argument("BigInt::get_substring: Substring size " + std::to_string(length) + " too big");
156 
157  uint64_t piece = 0;
158  for(size_t i = 0; i != 8; ++i)
159  {
160  const uint8_t part = byte_at((offset / 8) + (7-i));
161  piece = (piece << 8) | part;
162  }
163 
164  const uint64_t mask = (static_cast<uint64_t>(1) << length) - 1;
165  const size_t shift = (offset % 8);
166 
167  return static_cast<uint32_t>((piece >> shift) & mask);
168  }
169 
170 /*
171 * Convert this number to a uint32_t, if possible
172 */
173 uint32_t BigInt::to_u32bit() const
174  {
175  if(is_negative())
176  throw Encoding_Error("BigInt::to_u32bit: Number is negative");
177  if(bits() > 32)
178  throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
179 
180  uint32_t out = 0;
181  for(size_t i = 0; i != 4; ++i)
182  out = (out << 8) | byte_at(3-i);
183  return out;
184  }
185 
186 /*
187 * Set bit number n
188 */
189 void BigInt::set_bit(size_t n)
190  {
191  const size_t which = n / BOTAN_MP_WORD_BITS;
192  const word mask = static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS);
193  if(which >= size()) grow_to(which + 1);
194  m_reg[which] |= mask;
195  }
196 
197 /*
198 * Clear bit number n
199 */
200 void BigInt::clear_bit(size_t n)
201  {
202  const size_t which = n / BOTAN_MP_WORD_BITS;
203  const word mask = static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS);
204  if(which < size())
205  m_reg[which] &= ~mask;
206  }
207 
208 size_t BigInt::bytes() const
209  {
210  return round_up(bits(), 8) / 8;
211  }
212 
213 /*
214 * Count how many bits are being used
215 */
216 size_t BigInt::bits() const
217  {
218  const size_t words = sig_words();
219 
220  if(words == 0)
221  return 0;
222 
223  const size_t full_words = words - 1;
224  return (full_words * BOTAN_MP_WORD_BITS + high_bit(word_at(full_words)));
225  }
226 
227 /*
228 * Calcluate the size in a certain base
229 */
230 size_t BigInt::encoded_size(Base base) const
231  {
232  static const double LOG_2_BASE_10 = 0.30102999566;
233 
234  if(base == Binary)
235  return bytes();
236  else if(base == Hexadecimal)
237  return 2*bytes();
238  else if(base == Decimal)
239  return static_cast<size_t>((bits() * LOG_2_BASE_10) + 1);
240  else
241  throw Invalid_Argument("Unknown base for BigInt encoding");
242  }
243 
244 /*
245 * Return the negation of this number
246 */
248  {
249  BigInt x = (*this);
250  x.flip_sign();
251  return x;
252  }
253 
255  {
256  if(p.is_negative())
257  throw Invalid_Argument("BigInt::reduce_below mod must be positive");
258 
259  const size_t p_words = p.sig_words();
260 
261  if(size() < p_words + 1)
262  grow_to(p_words + 1);
263 
264  if(ws.size() < p_words + 1)
265  ws.resize(p_words + 1);
266 
267  clear_mem(ws.data(), ws.size());
268 
269  for(;;)
270  {
271  word borrow = bigint_sub3(ws.data(), data(), p_words + 1, p.data(), p_words);
272 
273  if(borrow)
274  break;
275 
276  m_reg.swap(ws);
277  }
278  }
279 
280 /*
281 * Return the absolute value of this number
282 */
284  {
285  BigInt x = (*this);
286  x.set_sign(Positive);
287  return x;
288  }
289 
290 void BigInt::grow_to(size_t n)
291  {
292  if(n > size())
293  {
294  if(n <= m_reg.capacity())
295  m_reg.resize(m_reg.capacity());
296  else
297  m_reg.resize(round_up(n, 8));
298  }
299  }
300 
301 /*
302 * Encode this number into bytes
303 */
304 void BigInt::binary_encode(uint8_t output[]) const
305  {
306  const size_t sig_bytes = bytes();
307  for(size_t i = 0; i != sig_bytes; ++i)
308  output[sig_bytes-i-1] = byte_at(i);
309  }
310 
311 /*
312 * Set this number to the value in buf
313 */
314 void BigInt::binary_decode(const uint8_t buf[], size_t length)
315  {
316  const size_t WORD_BYTES = sizeof(word);
317 
318  clear();
319  m_reg.resize(round_up((length / WORD_BYTES) + 1, 8));
320 
321  for(size_t i = 0; i != length / WORD_BYTES; ++i)
322  {
323  const size_t top = length - WORD_BYTES*i;
324  for(size_t j = WORD_BYTES; j > 0; --j)
325  m_reg[i] = (m_reg[i] << 8) | buf[top - j];
326  }
327 
328  for(size_t i = 0; i != length % WORD_BYTES; ++i)
329  m_reg[length / WORD_BYTES] = (m_reg[length / WORD_BYTES] << 8) | buf[i];
330  }
331 
332 void BigInt::shrink_to_fit(size_t min_size)
333  {
334  const size_t words = std::max(min_size, sig_words());
335  m_reg.resize(words);
336  }
337 
339  const std::vector<BigInt>& vec,
340  size_t idx)
341  {
342  const size_t words = output.size();
343 
344  clear_mem(output.data(), output.size());
345 
346  CT::poison(&idx, sizeof(idx));
347 
348  for(size_t i = 0; i != vec.size(); ++i)
349  {
350  BOTAN_ASSERT(vec[i].size() >= words,
351  "Word size as expected in const_time_lookup");
352 
353  const word mask = CT::is_equal(i, idx);
354 
355  for(size_t w = 0; w != words; ++w)
356  output[w] |= CT::select<word>(mask, vec[i].word_at(w), 0);
357  }
358 
359  CT::unpoison(idx);
360  CT::unpoison(output.data(), output.size());
361  }
362 
363 }
bool is_negative() const
Definition: bigint.h:413
static void const_time_lookup(secure_vector< word > &output, const std::vector< BigInt > &vec, size_t idx)
Definition: bigint.cpp:338
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:398
size_t bits() const
Definition: bigint.cpp:216
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:119
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:97
void set_bit(size_t n)
Definition: bigint.cpp:189
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:218
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:145
void binary_encode(uint8_t buf[]) const
Definition: bigint.cpp:304
word word_at(size_t n) const
Definition: bigint.h:399
uint32_t get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:152
BigInt operator-() const
Definition: bigint.cpp:247
T is_equal(T x, T y)
Definition: ct_utils.h:124
const word * data() const
Definition: bigint.h:504
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:30
uint8_t byte_at(size_t n) const
Definition: bigint.h:388
void encode_words(word out[], size_t size) const
Definition: bigint.cpp:138
size_t size() const
Definition: bigint.h:466
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:472
size_t bytes() const
Definition: bigint.cpp:208
void clear()
Definition: bigint.h:281
const word MP_WORD_MASK
Definition: mp_core.h:17
void grow_to(size_t n)
Definition: bigint.cpp:290
size_t encoded_size(Base base=Binary) const
Definition: bigint.cpp:230
BigInt abs() const
Definition: bigint.cpp:283
uint32_t to_u32bit() const
Definition: bigint.cpp:173
void binary_decode(const uint8_t buf[], size_t length)
Definition: bigint.cpp:314
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:254
BigInt()=default
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88
void flip_sign()
Definition: bigint.h:440
void clear_bit(size_t n)
Definition: bigint.cpp:200
void shrink_to_fit(size_t min_size=0)
Definition: bigint.cpp:332
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21
void set_sign(Sign sign)
Definition: bigint.h:449
bool is_positive() const
Definition: bigint.h:419
static BigInt decode(const uint8_t buf[], size_t length, Base base=Binary)
Definition: big_code.cpp:114