Coverage Report

Created: 2020-05-23 13:54

/src/botan/src/lib/math/bigint/big_ops2.cpp
Line
Count
Source (jump to first uncovered line)
1
/*
2
* (C) 1999-2007,2018 Jack Lloyd
3
*     2016 Matthias Gierlings
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/bit_ops.h>
11
#include <algorithm>
12
13
namespace Botan {
14
15
BigInt& BigInt::add(const word y[], size_t y_words, Sign y_sign)
16
13.2M
   {
17
13.2M
   const size_t x_sw = sig_words();
18
13.2M
19
13.2M
   grow_to(std::max(x_sw, y_words) + 1);
20
13.2M
21
13.2M
   if(sign() == y_sign)
22
9.36M
      {
23
9.36M
      bigint_add2(mutable_data(), size() - 1, y, y_words);
24
9.36M
      }
25
3.89M
   else
26
3.89M
      {
27
3.89M
      const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_words);
28
3.89M
29
3.89M
      if(relative_size >= 0)
30
3.29M
         {
31
3.29M
         // *this >= y
32
3.29M
         bigint_sub2(mutable_data(), x_sw, y, y_words);
33
3.29M
         }
34
603k
      else
35
603k
         {
36
603k
         // *this < y
37
603k
         bigint_sub2_rev(mutable_data(), y, y_words);
38
603k
         }
39
3.89M
40
3.89M
      //this->sign_fixup(relative_size, y_sign);
41
3.89M
      if(relative_size < 0)
42
603k
         set_sign(y_sign);
43
3.29M
      else if(relative_size == 0)
44
4.09k
         set_sign(Positive);
45
3.89M
      }
46
13.2M
47
13.2M
   return (*this);
48
13.2M
   }
49
50
BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws)
51
11.8M
   {
52
11.8M
   if(this->is_negative() || s.is_negative() || mod.is_negative())
53
0
      throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");
54
11.8M
55
11.8M
   BOTAN_DEBUG_ASSERT(*this < mod);
56
11.8M
   BOTAN_DEBUG_ASSERT(s < mod);
57
11.8M
58
11.8M
   /*
59
11.8M
   t + s or t + s - p == t - (p - s)
60
11.8M
61
11.8M
   So first compute ws = p - s
62
11.8M
63
11.8M
   Then compute t + s and t - ws
64
11.8M
65
11.8M
   If t - ws does not borrow, then that is the correct valued
66
11.8M
   */
67
11.8M
68
11.8M
   const size_t mod_sw = mod.sig_words();
69
11.8M
   BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");
70
11.8M
71
11.8M
   this->grow_to(mod_sw);
72
11.8M
   s.grow_to(mod_sw);
73
11.8M
74
11.8M
   // First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
75
11.8M
   if(ws.size() < 3*mod_sw)
76
6.34M
      ws.resize(3*mod_sw);
77
11.8M
78
11.8M
   word borrow = bigint_sub3(&ws[0], mod.data(), mod_sw, s.data(), mod_sw);
79
11.8M
   BOTAN_DEBUG_ASSERT(borrow == 0);
80
11.8M
81
11.8M
   // Compute t - ws
82
11.8M
   borrow = bigint_sub3(&ws[mod_sw], this->data(), mod_sw, &ws[0], mod_sw);
83
11.8M
84
11.8M
   // Compute t + s
85
11.8M
   bigint_add3_nc(&ws[mod_sw*2], this->data(), mod_sw, s.data(), mod_sw);
86
11.8M
87
11.8M
   CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw*2], &ws[mod_sw], mod_sw);
88
11.8M
   set_words(&ws[0], mod_sw);
89
11.8M
90
11.8M
   return (*this);
91
11.8M
   }
92
93
BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws)
94
115M
   {
95
115M
   if(this->is_negative() || s.is_negative() || mod.is_negative())
96
0
      throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");
97
115M
98
115M
   // We are assuming in this function that *this and s are no more than mod_sw words long
99
115M
   BOTAN_DEBUG_ASSERT(*this < mod);
100
115M
   BOTAN_DEBUG_ASSERT(s < mod);
101
115M
102
115M
   const size_t mod_sw = mod.sig_words();
103
115M
104
115M
   this->grow_to(mod_sw);
105
115M
   s.grow_to(mod_sw);
106
115M
107
115M
   if(ws.size() < mod_sw)
108
0
      ws.resize(mod_sw);
109
115M
110
115M
   if(mod_sw == 4)
111
25.7M
      bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data());
112
89.3M
   else if(mod_sw == 6)
113
24.3M
      bigint_mod_sub_n<6>(mutable_data(), s.data(), mod.data(), ws.data());
114
65.0M
   else
115
65.0M
      bigint_mod_sub(mutable_data(), s.data(), mod.data(), mod_sw, ws.data());
116
115M
117
115M
   return (*this);
118
115M
   }
119
120
BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws)
121
47.7M
   {
122
47.7M
   BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive");
123
47.7M
   BOTAN_ARG_CHECK(y < 16, "y too large");
124
47.7M
125
47.7M
   BOTAN_DEBUG_ASSERT(*this < mod);
126
47.7M
127
47.7M
   *this *= static_cast<word>(y);
128
47.7M
   this->reduce_below(mod, ws);
129
47.7M
   return (*this);
130
47.7M
   }
131
132
BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws)
133
5.81M
   {
134
5.81M
   if(this->sign() != BigInt::Positive)
135
0
      throw Invalid_State("BigInt::sub_rev requires this is positive");
136
5.81M
137
5.81M
   const size_t x_sw = this->sig_words();
138
5.81M
139
5.81M
   ws.resize(std::max(x_sw, y_sw));
140
5.81M
   clear_mem(ws.data(), ws.size());
141
5.81M
142
5.81M
   const int32_t relative_size = bigint_sub_abs(ws.data(), data(), x_sw, y, y_sw);
143
5.81M
144
5.81M
   this->cond_flip_sign(relative_size > 0);
145
5.81M
   this->swap_reg(ws);
146
5.81M
147
5.81M
   return (*this);
148
5.81M
   }
149
150
/*
151
* Multiplication Operator
152
*/
153
BigInt& BigInt::operator*=(const BigInt& y)
154
476
   {
155
476
   secure_vector<word> ws;
156
476
   return this->mul(y, ws);
157
476
   }
158
159
BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws)
160
11.6M
   {
161
11.6M
   const size_t x_sw = sig_words();
162
11.6M
   const size_t y_sw = y.sig_words();
163
11.6M
   set_sign((sign() == y.sign()) ? Positive : Negative);
164
11.6M
165
11.6M
   if(x_sw == 0 || y_sw == 0)
166
1.11M
      {
167
1.11M
      clear();
168
1.11M
      set_sign(Positive);
169
1.11M
      }
170
10.5M
   else if(x_sw == 1 && y_sw)
171
2.01M
      {
172
2.01M
      grow_to(y_sw + 1);
173
2.01M
      bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0));
174
2.01M
      }
175
8.50M
   else if(y_sw == 1 && x_sw)
176
172
      {
177
172
      word carry = bigint_linmul2(mutable_data(), x_sw, y.word_at(0));
178
172
      set_word_at(x_sw, carry);
179
172
      }
180
8.50M
   else
181
8.50M
      {
182
8.50M
      const size_t new_size = x_sw + y_sw + 1;
183
8.50M
      ws.resize(new_size);
184
8.50M
      secure_vector<word> z_reg(new_size);
185
8.50M
186
8.50M
      bigint_mul(z_reg.data(), z_reg.size(),
187
8.50M
                 data(), size(), x_sw,
188
8.50M
                 y.data(), y.size(), y_sw,
189
8.50M
                 ws.data(), ws.size());
190
8.50M
191
8.50M
      this->swap_reg(z_reg);
192
8.50M
      }
193
11.6M
194
11.6M
   return (*this);
195
11.6M
   }
196
197
BigInt& BigInt::square(secure_vector<word>& ws)
198
3.66M
   {
199
3.66M
   const size_t sw = sig_words();
200
3.66M
201
3.66M
   secure_vector<word> z(2*sw);
202
3.66M
   ws.resize(z.size());
203
3.66M
204
3.66M
   bigint_sqr(z.data(), z.size(),
205
3.66M
              data(), size(), sw,
206
3.66M
              ws.data(), ws.size());
207
3.66M
208
3.66M
   swap_reg(z);
209
3.66M
   set_sign(BigInt::Positive);
210
3.66M
211
3.66M
   return (*this);
212
3.66M
   }
213
214
BigInt& BigInt::operator*=(word y)
215
191M
   {
216
191M
   if(y == 0)
217
0
      {
218
0
      clear();
219
0
      set_sign(Positive);
220
0
      }
221
191M
222
191M
   const word carry = bigint_linmul2(mutable_data(), size(), y);
223
191M
   set_word_at(size(), carry);
224
191M
225
191M
   return (*this);
226
191M
   }
227
228
/*
229
* Division Operator
230
*/
231
BigInt& BigInt::operator/=(const BigInt& y)
232
0
   {
233
0
   if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
234
0
      (*this) >>= (y.bits() - 1);
235
0
   else
236
0
      (*this) = (*this) / y;
237
0
   return (*this);
238
0
   }
239
240
/*
241
* Modulo Operator
242
*/
243
BigInt& BigInt::operator%=(const BigInt& mod)
244
2.28M
   {
245
2.28M
   return (*this = (*this) % mod);
246
2.28M
   }
247
248
/*
249
* Modulo Operator
250
*/
251
word BigInt::operator%=(word mod)
252
0
   {
253
0
   if(mod == 0)
254
0
      throw BigInt::DivideByZero();
255
0
256
0
   word remainder = 0;
257
0
258
0
   if(is_power_of_2(mod))
259
0
       {
260
0
       remainder = (word_at(0) & (mod - 1));
261
0
       }
262
0
   else
263
0
      {
264
0
      const size_t sw = sig_words();
265
0
      for(size_t i = sw; i > 0; --i)
266
0
         remainder = bigint_modop(remainder, word_at(i-1), mod);
267
0
      }
268
0
269
0
   if(remainder && sign() == BigInt::Negative)
270
0
      remainder = mod - remainder;
271
0
272
0
   m_data.set_to_zero();
273
0
   m_data.set_word_at(0, remainder);
274
0
   set_sign(BigInt::Positive);
275
0
   return remainder;
276
0
   }
277
278
/*
279
* Left Shift Operator
280
*/
281
BigInt& BigInt::operator<<=(size_t shift)
282
4.55M
   {
283
4.55M
   const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
284
4.55M
   const size_t shift_bits  = shift % BOTAN_MP_WORD_BITS;
285
4.55M
   const size_t size = sig_words();
286
4.55M
287
4.55M
   const size_t bits_free = top_bits_free();
288
4.55M
289
4.55M
   const size_t new_size = size + shift_words + (bits_free < shift_bits);
290
4.55M
291
4.55M
   m_data.grow_to(new_size);
292
4.55M
293
4.55M
   bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits);
294
4.55M
295
4.55M
   return (*this);
296
4.55M
   }
297
298
/*
299
* Right Shift Operator
300
*/
301
BigInt& BigInt::operator>>=(size_t shift)
302
23.4M
   {
303
23.4M
   const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
304
23.4M
   const size_t shift_bits  = shift % BOTAN_MP_WORD_BITS;
305
23.4M
306
23.4M
   bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits);
307
23.4M
308
23.4M
   if(is_negative() && is_zero())
309
0
      set_sign(Positive);
310
23.4M
311
23.4M
   return (*this);
312
23.4M
   }
313
314
}