Botan 3.14.1
Crypto and TLS for C&
big_ops2.cpp
Go to the documentation of this file.
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
10#include <botan/exceptn.h>
11#include <botan/internal/bit_ops.h>
12#include <botan/internal/mp_core.h>
13
14namespace Botan {
15
17 if(&y == this) {
18 return *this <<= 1;
19 }
20 return add(y._data(), y.sig_words(), y.sign());
21}
22
24 if(&y == this) {
25 this->clear();
26 this->set_sign(Positive);
27 return *this;
28 }
29 return sub(y._data(), y.sig_words(), y.sign());
30}
31
32BigInt& BigInt::add(const word y[], size_t y_words, Sign y_sign) {
33 const size_t x_sw = sig_words();
34
35 grow_to(std::max(x_sw, y_words) + 1);
36
37 if(sign() == y_sign) {
38 const word carry = bigint_add2(mutable_data(), size() - 1, y, y_words);
39 mutable_data()[size() - 1] += carry;
40 } else {
41 const int32_t relative_size = bigint_cmp(_data(), x_sw, y, y_words);
42
43 if(relative_size >= 0) {
44 // *this >= y
45 bigint_sub2(mutable_data(), x_sw, y, y_words);
46 } else {
47 // *this < y: compute *this = y - *this
48 bigint_sub2_rev(mutable_data(), y, y_words);
49 }
50
51 if(relative_size < 0) {
52 set_sign(y_sign);
53 } else if(relative_size == 0) {
55 }
56 }
57
58 return (*this);
59}
60
62 if(this->signum() < 0 || s.signum() < 0 || mod.signum() < 0) {
63 throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");
64 }
65
66 BOTAN_DEBUG_ASSERT(*this < mod);
67 BOTAN_DEBUG_ASSERT(s < mod);
68
69 /*
70 t + s or t + s - p == t - (p - s)
71
72 So first compute ws = p - s
73
74 Then compute t + s and t - ws
75
76 If t - ws does not borrow, then that is the correct valued
77 */
78
79 const size_t mod_sw = mod.sig_words();
80 BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");
81
82 this->grow_to(mod_sw);
83 s.grow_to(mod_sw);
84
85 // First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
86 if(ws.size() < 3 * mod_sw) {
87 ws.resize(3 * mod_sw);
88 }
89
90 // NOLINTBEGIN(readability-container-data-pointer)
91
92 word borrow = bigint_sub3(&ws[0], mod._data(), mod_sw, s._data(), mod_sw);
93 BOTAN_DEBUG_ASSERT(borrow == 0);
94 BOTAN_UNUSED(borrow);
95
96 // Compute t - ws
97 borrow = bigint_sub3(&ws[mod_sw], this->_data(), mod_sw, &ws[0], mod_sw);
98
99 // Compute t + s
100 bigint_add3(&ws[mod_sw * 2], this->_data(), mod_sw, s._data(), mod_sw);
101
102 CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw * 2], &ws[mod_sw], mod_sw);
103 set_words(&ws[0], mod_sw);
104
105 // NOLINTEND(readability-container-data-pointer)
106
107 return (*this);
108}
109
111 if(this->signum() < 0 || s.signum() < 0 || mod.signum() < 0) {
112 throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");
113 }
114
115 // We are assuming in this function that *this and s are no more than mod_sw words long
116 BOTAN_DEBUG_ASSERT(*this < mod);
117 BOTAN_DEBUG_ASSERT(s < mod);
118
119 const size_t mod_sw = mod.sig_words();
120
121 this->grow_to(mod_sw);
122 s.grow_to(mod_sw);
123
124 if(ws.size() < mod_sw) {
125 ws.resize(mod_sw);
126 }
127
128 const word borrow = bigint_sub3(ws.data(), mutable_data(), mod_sw, s._data(), mod_sw);
129
130 // Conditionally add back the modulus
131 bigint_cnd_add(borrow, ws.data(), mod._data(), mod_sw);
132
133 unchecked_copy_memory(mutable_data(), ws.data(), mod_sw);
134
135 return (*this);
136}
137
138BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) {
139 BOTAN_ARG_CHECK(this->signum() >= 0, "*this must be positive");
140 BOTAN_ARG_CHECK(y < 16, "y too large");
141
142 BOTAN_DEBUG_ASSERT(*this < mod);
143
144 *this *= static_cast<word>(y);
145 // Since *this < mod, the product is less than y * mod
146 this->ct_reduce_below(mod, ws, y);
147 return (*this);
148}
149
150BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws) {
151 BOTAN_UNUSED(ws);
152 BigInt y_bn;
153 y_bn.m_data.set_words(y, y_sw);
154 *this = y_bn - *this;
155 return (*this);
156}
157
158/*
159* Multiplication Operator
160*/
163 return this->mul(y, ws);
164}
165
167 const size_t x_sw = sig_words();
168 const size_t y_sw = y.sig_words();
169 set_sign((sign() == y.sign()) ? Positive : Negative);
170
171 if(x_sw == 0 || y_sw == 0) {
172 clear();
174 } else if(x_sw == 1 && y_sw > 0) {
175 grow_to(y_sw + 1);
176 bigint_linmul3(mutable_data(), y._data(), y_sw, word_at(0));
177 } else {
178 const size_t new_size = x_sw + y_sw + 1;
179 if(ws.size() < new_size) {
180 ws.resize(new_size);
181 }
182 secure_vector<word> z_reg(new_size);
183
184 bigint_mul(z_reg.data(), z_reg.size(), _data(), size(), x_sw, y._data(), y.size(), y_sw, ws.data(), ws.size());
185
186 this->swap_reg(z_reg);
187 }
188
189 return (*this);
190}
191
193 const size_t sw = sig_words();
194
195 secure_vector<word> z(2 * sw);
196 ws.resize(z.size());
197
198 bigint_sqr(z.data(), z.size(), _data(), size(), sw, ws.data(), ws.size());
199
200 swap_reg(z);
202
203 return (*this);
204}
205
207 if(y == 0) {
208 clear();
210 }
211
212 const size_t x_sw = sig_words();
213 grow_to(x_sw + 1);
214
215 const word carry = bigint_linmul2(mutable_data(), x_sw, y);
216 mutable_data()[x_sw] = carry;
217
218 return (*this);
219}
220
221/*
222* Division Operator
223*/
225 if(y.sig_words() == 1 && signum() >= 0 && y.signum() >= 0 && is_power_of_2(y.word_at(0))) {
226 (*this) >>= (y.bits() - 1);
227 } else {
228 (*this) = (*this) / y;
229 }
230 return (*this);
231}
232
233/*
234* Modulo Operator
235*/
237 return (*this = (*this) % mod);
238}
239
240/*
241* Modulo Operator
242*/
244 if(mod == 0) {
245 throw Invalid_Argument("BigInt::operator%= divide by zero");
246 }
247
248 word remainder = 0;
249
250 if(is_power_of_2(mod)) {
251 remainder = (word_at(0) & (mod - 1));
252 } else {
253 const auto redc_mod = divide_precomp<word>::setup_vartime(mod);
254 const size_t sw = sig_words();
255 for(size_t i = sw; i > 0; --i) {
256 remainder = redc_mod.mod_2to1(remainder, word_at(i - 1));
257 }
258 }
259
260 if(remainder != 0 && sign() == BigInt::Negative) {
261 remainder = mod - remainder;
262 }
263
264 m_data.set_to_zero();
265 m_data.set_word_at(0, remainder);
267 return remainder;
268}
269
270/*
271* Left Shift Operator
272*/
274 if(shift >= 65536) {
275 throw Invalid_Argument("BigInt left shift count too large");
276 }
277
278 const size_t sw = sig_words();
279 const size_t new_size = sw + (shift + WordInfo<word>::bits - 1) / WordInfo<word>::bits;
280
281 m_data.grow_to(new_size);
282
283 bigint_shl1(m_data.mutable_data(), new_size, sw, shift);
284
285 return (*this);
286}
287
288/*
289* Right Shift Operator
290*/
292 bigint_shr1(m_data.mutable_data(), m_data.size(), shift);
293
294 if(sig_words() == 0 && m_signedness == Negative) {
295 m_signedness = Positive;
296 }
297
298 return (*this);
299}
300
301} // namespace Botan
#define BOTAN_UNUSED
Definition assert.h:151
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
BigInt & operator>>=(size_t shift)
Definition big_ops2.cpp:291
BigInt & mod_mul(uint8_t y, const BigInt &mod, secure_vector< word > &ws)
Definition big_ops2.cpp:138
size_t sig_words() const
Definition bigint.h:687
BigInt & operator/=(const BigInt &y)
Definition big_ops2.cpp:224
BigInt()=default
BigInt & sub(const word y[], size_t y_words, Sign sign)
Definition bigint.h:358
word * mutable_data()
Definition bigint.h:712
size_t size() const
Definition bigint.h:681
BigInt & rev_sub(const word y[], size_t y_words, secure_vector< word > &ws)
Definition big_ops2.cpp:150
void grow_to(size_t n) const
Definition bigint.h:738
void set_words(const word w[], size_t len)
Definition bigint.h:615
BigInt & operator*=(const BigInt &y)
Definition big_ops2.cpp:161
void ct_reduce_below(const BigInt &mod, secure_vector< word > &ws, size_t bound)
Definition bigint.cpp:362
BigInt & mod_add(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition big_ops2.cpp:61
int signum() const
Definition bigint.h:493
word word_at(size_t n) const
Definition bigint.h:601
BigInt & operator-=(const BigInt &y)
Definition big_ops2.cpp:23
BigInt & mul(const BigInt &y, secure_vector< word > &ws)
Definition big_ops2.cpp:166
BigInt & mod_sub(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition big_ops2.cpp:110
size_t bits() const
Definition bigint.cpp:308
BigInt & operator+=(const BigInt &y)
Definition big_ops2.cpp:16
BigInt & operator%=(const BigInt &y)
Definition big_ops2.cpp:236
void clear()
Definition bigint.h:441
const word * _data() const
Definition bigint.h:1033
Sign sign() const
Definition bigint.h:641
BigInt & operator<<=(size_t shift)
Definition big_ops2.cpp:273
BigInt & add(const word y[], size_t y_words, Sign sign)
Definition big_ops2.cpp:32
BigInt & square(secure_vector< word > &ws)
Definition big_ops2.cpp:192
void swap_reg(secure_vector< word > &reg)
Definition bigint.h:218
void set_sign(Sign sign)
Definition bigint.h:663
static constexpr divide_precomp setup_vartime(W divisor)
Definition mp_core.h:687
constexpr Mask< T > conditional_copy_mem(Mask< T > mask, T *dest, const T *if_set, const T *if_unset, size_t elems)
Definition ct_utils.h:737
constexpr auto bigint_add2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:98
constexpr void bigint_linmul3(W z[], const W x[], size_t x_size, W y)
Definition mp_core.h:420
BOTAN_FORCE_INLINE constexpr bool is_power_of_2(T arg)
Definition bit_ops.h:62
constexpr auto bigint_add3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:124
constexpr void bigint_shr1(W x[], size_t x_size, size_t shift)
Definition mp_core.h:335
void bigint_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, word workspace[], size_t ws_size)
Definition mp_karat.cpp:327
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:196
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition mp_karat.cpp:283
constexpr void bigint_shl1(W x[], size_t x_size, size_t x_words, size_t shift)
Definition mp_core.h:313
constexpr int32_t bigint_cmp(const W x[], size_t x_size, const W y[], size_t y_size)
Definition mp_core.h:463
constexpr W bigint_cnd_add(W cnd, W x[], const W y[], size_t size)
Definition mp_core.h:49
void unchecked_copy_memory(T *out, const T *in, size_t n)
Definition mem_utils.h:44
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
constexpr auto bigint_sub2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:152
constexpr void bigint_sub2_rev(W x[], const W y[], size_t y_size)
Definition mp_core.h:178
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131
constexpr auto bigint_linmul2(W x[], size_t x_size, W y) -> W
Definition mp_core.h:409