/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 | 14.9M | { |
17 | 14.9M | const size_t x_sw = sig_words(); |
18 | 14.9M | |
19 | 14.9M | grow_to(std::max(x_sw, y_words) + 1); |
20 | 14.9M | |
21 | 14.9M | if(sign() == y_sign) |
22 | 10.6M | { |
23 | 10.6M | bigint_add2(mutable_data(), size() - 1, y, y_words); |
24 | 10.6M | } |
25 | 4.34M | else |
26 | 4.34M | { |
27 | 4.34M | const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_words); |
28 | 4.34M | |
29 | 4.34M | if(relative_size >= 0) |
30 | 3.69M | { |
31 | 3.69M | // *this >= y |
32 | 3.69M | bigint_sub2(mutable_data(), x_sw, y, y_words); |
33 | 3.69M | } |
34 | 656k | else |
35 | 656k | { |
36 | 656k | // *this < y |
37 | 656k | bigint_sub2_rev(mutable_data(), y, y_words); |
38 | 656k | } |
39 | 4.34M | |
40 | 4.34M | //this->sign_fixup(relative_size, y_sign); |
41 | 4.34M | if(relative_size < 0) |
42 | 656k | set_sign(y_sign); |
43 | 3.69M | else if(relative_size == 0) |
44 | 4.33k | set_sign(Positive); |
45 | 4.34M | } |
46 | 14.9M | |
47 | 14.9M | return (*this); |
48 | 14.9M | } |
49 | | |
50 | | BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) |
51 | 13.6M | { |
52 | 13.6M | if(this->is_negative() || s.is_negative() || mod.is_negative()) |
53 | 0 | throw Invalid_Argument("BigInt::mod_add expects all arguments are positive"); |
54 | 13.6M | |
55 | 13.6M | BOTAN_DEBUG_ASSERT(*this < mod); |
56 | 13.6M | BOTAN_DEBUG_ASSERT(s < mod); |
57 | 13.6M | |
58 | 13.6M | /* |
59 | 13.6M | t + s or t + s - p == t - (p - s) |
60 | 13.6M | |
61 | 13.6M | So first compute ws = p - s |
62 | 13.6M | |
63 | 13.6M | Then compute t + s and t - ws |
64 | 13.6M | |
65 | 13.6M | If t - ws does not borrow, then that is the correct valued |
66 | 13.6M | */ |
67 | 13.6M | |
68 | 13.6M | const size_t mod_sw = mod.sig_words(); |
69 | 13.6M | BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive"); |
70 | 13.6M | |
71 | 13.6M | this->grow_to(mod_sw); |
72 | 13.6M | s.grow_to(mod_sw); |
73 | 13.6M | |
74 | 13.6M | // First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace |
75 | 13.6M | if(ws.size() < 3*mod_sw) |
76 | 7.25M | ws.resize(3*mod_sw); |
77 | 13.6M | |
78 | 13.6M | word borrow = bigint_sub3(&ws[0], mod.data(), mod_sw, s.data(), mod_sw); |
79 | 13.6M | BOTAN_DEBUG_ASSERT(borrow == 0); |
80 | 13.6M | |
81 | 13.6M | // Compute t - ws |
82 | 13.6M | borrow = bigint_sub3(&ws[mod_sw], this->data(), mod_sw, &ws[0], mod_sw); |
83 | 13.6M | |
84 | 13.6M | // Compute t + s |
85 | 13.6M | bigint_add3_nc(&ws[mod_sw*2], this->data(), mod_sw, s.data(), mod_sw); |
86 | 13.6M | |
87 | 13.6M | CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw*2], &ws[mod_sw], mod_sw); |
88 | 13.6M | set_words(&ws[0], mod_sw); |
89 | 13.6M | |
90 | 13.6M | return (*this); |
91 | 13.6M | } |
92 | | |
93 | | BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) |
94 | 132M | { |
95 | 132M | if(this->is_negative() || s.is_negative() || mod.is_negative()) |
96 | 0 | throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive"); |
97 | 132M | |
98 | 132M | // We are assuming in this function that *this and s are no more than mod_sw words long |
99 | 132M | BOTAN_DEBUG_ASSERT(*this < mod); |
100 | 132M | BOTAN_DEBUG_ASSERT(s < mod); |
101 | 132M | |
102 | 132M | const size_t mod_sw = mod.sig_words(); |
103 | 132M | |
104 | 132M | this->grow_to(mod_sw); |
105 | 132M | s.grow_to(mod_sw); |
106 | 132M | |
107 | 132M | if(ws.size() < mod_sw) |
108 | 0 | ws.resize(mod_sw); |
109 | 132M | |
110 | 132M | if(mod_sw == 4) |
111 | 29.5M | bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data()); |
112 | 102M | else if(mod_sw == 6) |
113 | 28.2M | bigint_mod_sub_n<6>(mutable_data(), s.data(), mod.data(), ws.data()); |
114 | 74.5M | else |
115 | 74.5M | bigint_mod_sub(mutable_data(), s.data(), mod.data(), mod_sw, ws.data()); |
116 | 132M | |
117 | 132M | return (*this); |
118 | 132M | } |
119 | | |
120 | | BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) |
121 | 55.1M | { |
122 | 55.1M | BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive"); |
123 | 55.1M | BOTAN_ARG_CHECK(y < 16, "y too large"); |
124 | 55.1M | |
125 | 55.1M | BOTAN_DEBUG_ASSERT(*this < mod); |
126 | 55.1M | |
127 | 55.1M | *this *= static_cast<word>(y); |
128 | 55.1M | this->reduce_below(mod, ws); |
129 | 55.1M | return (*this); |
130 | 55.1M | } |
131 | | |
132 | | BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws) |
133 | 6.61M | { |
134 | 6.61M | if(this->sign() != BigInt::Positive) |
135 | 0 | throw Invalid_State("BigInt::sub_rev requires this is positive"); |
136 | 6.61M | |
137 | 6.61M | const size_t x_sw = this->sig_words(); |
138 | 6.61M | |
139 | 6.61M | ws.resize(std::max(x_sw, y_sw)); |
140 | 6.61M | clear_mem(ws.data(), ws.size()); |
141 | 6.61M | |
142 | 6.61M | const int32_t relative_size = bigint_sub_abs(ws.data(), data(), x_sw, y, y_sw); |
143 | 6.61M | |
144 | 6.61M | this->cond_flip_sign(relative_size > 0); |
145 | 6.61M | this->swap_reg(ws); |
146 | 6.61M | |
147 | 6.61M | return (*this); |
148 | 6.61M | } |
149 | | |
150 | | /* |
151 | | * Multiplication Operator |
152 | | */ |
153 | | BigInt& BigInt::operator*=(const BigInt& y) |
154 | 537 | { |
155 | 537 | secure_vector<word> ws; |
156 | 537 | return this->mul(y, ws); |
157 | 537 | } |
158 | | |
159 | | BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws) |
160 | 13.2M | { |
161 | 13.2M | const size_t x_sw = sig_words(); |
162 | 13.2M | const size_t y_sw = y.sig_words(); |
163 | 13.2M | set_sign((sign() == y.sign()) ? Positive : Negative); |
164 | 13.2M | |
165 | 13.2M | if(x_sw == 0 || y_sw == 0) |
166 | 1.16M | { |
167 | 1.16M | clear(); |
168 | 1.16M | set_sign(Positive); |
169 | 1.16M | } |
170 | 12.0M | else if(x_sw == 1 && y_sw) |
171 | 2.23M | { |
172 | 2.23M | grow_to(y_sw + 1); |
173 | 2.23M | bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0)); |
174 | 2.23M | } |
175 | 9.82M | else if(y_sw == 1 && x_sw) |
176 | 212 | { |
177 | 212 | word carry = bigint_linmul2(mutable_data(), x_sw, y.word_at(0)); |
178 | 212 | set_word_at(x_sw, carry); |
179 | 212 | } |
180 | 9.82M | else |
181 | 9.82M | { |
182 | 9.82M | const size_t new_size = x_sw + y_sw + 1; |
183 | 9.82M | ws.resize(new_size); |
184 | 9.82M | secure_vector<word> z_reg(new_size); |
185 | 9.82M | |
186 | 9.82M | bigint_mul(z_reg.data(), z_reg.size(), |
187 | 9.82M | data(), size(), x_sw, |
188 | 9.82M | y.data(), y.size(), y_sw, |
189 | 9.82M | ws.data(), ws.size()); |
190 | 9.82M | |
191 | 9.82M | this->swap_reg(z_reg); |
192 | 9.82M | } |
193 | 13.2M | |
194 | 13.2M | return (*this); |
195 | 13.2M | } |
196 | | |
197 | | BigInt& BigInt::square(secure_vector<word>& ws) |
198 | 4.19M | { |
199 | 4.19M | const size_t sw = sig_words(); |
200 | 4.19M | |
201 | 4.19M | secure_vector<word> z(2*sw); |
202 | 4.19M | ws.resize(z.size()); |
203 | 4.19M | |
204 | 4.19M | bigint_sqr(z.data(), z.size(), |
205 | 4.19M | data(), size(), sw, |
206 | 4.19M | ws.data(), ws.size()); |
207 | 4.19M | |
208 | 4.19M | swap_reg(z); |
209 | 4.19M | set_sign(BigInt::Positive); |
210 | 4.19M | |
211 | 4.19M | return (*this); |
212 | 4.19M | } |
213 | | |
214 | | BigInt& BigInt::operator*=(word y) |
215 | 206M | { |
216 | 206M | if(y == 0) |
217 | 0 | { |
218 | 0 | clear(); |
219 | 0 | set_sign(Positive); |
220 | 0 | } |
221 | 206M | |
222 | 206M | const word carry = bigint_linmul2(mutable_data(), size(), y); |
223 | 206M | set_word_at(size(), carry); |
224 | 206M | |
225 | 206M | return (*this); |
226 | 206M | } |
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.60M | { |
245 | 2.60M | return (*this = (*this) % mod); |
246 | 2.60M | } |
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 | 5.18M | { |
283 | 5.18M | const size_t shift_words = shift / BOTAN_MP_WORD_BITS; |
284 | 5.18M | const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; |
285 | 5.18M | const size_t size = sig_words(); |
286 | 5.18M | |
287 | 5.18M | const size_t bits_free = top_bits_free(); |
288 | 5.18M | |
289 | 5.18M | const size_t new_size = size + shift_words + (bits_free < shift_bits); |
290 | 5.18M | |
291 | 5.18M | m_data.grow_to(new_size); |
292 | 5.18M | |
293 | 5.18M | bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits); |
294 | 5.18M | |
295 | 5.18M | return (*this); |
296 | 5.18M | } |
297 | | |
298 | | /* |
299 | | * Right Shift Operator |
300 | | */ |
301 | | BigInt& BigInt::operator>>=(size_t shift) |
302 | 26.6M | { |
303 | 26.6M | const size_t shift_words = shift / BOTAN_MP_WORD_BITS; |
304 | 26.6M | const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; |
305 | 26.6M | |
306 | 26.6M | bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits); |
307 | 26.6M | |
308 | 26.6M | if(is_negative() && is_zero()) |
309 | 0 | set_sign(Positive); |
310 | 26.6M | |
311 | 26.6M | return (*this); |
312 | 26.6M | } |
313 | | |
314 | | } |