Botan 3.8.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/internal/bit_ops.h>
11#include <botan/internal/mp_core.h>
12#include <algorithm>
13
14namespace Botan {
15
16BigInt& BigInt::add(const word y[], size_t y_words, Sign y_sign) {
17 const size_t x_sw = sig_words();
18
19 grow_to(std::max(x_sw, y_words) + 1);
20
21 if(sign() == y_sign) {
22 bigint_add2(mutable_data(), size() - 1, y, y_words);
23 } else {
24 const int32_t relative_size = bigint_cmp(_data(), x_sw, y, y_words);
25
26 if(relative_size >= 0) {
27 // *this >= y
28 bigint_sub2(mutable_data(), x_sw, y, y_words);
29 } else {
30 // *this < y
31 bigint_sub2_rev(mutable_data(), y, y_words);
32 }
33
34 //this->sign_fixup(relative_size, y_sign);
35 if(relative_size < 0) {
36 set_sign(y_sign);
37 } else if(relative_size == 0) {
39 }
40 }
41
42 return (*this);
43}
44
46 if(this->is_negative() || s.is_negative() || mod.is_negative()) {
47 throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");
48 }
49
50 BOTAN_DEBUG_ASSERT(*this < mod);
51 BOTAN_DEBUG_ASSERT(s < mod);
52
53 /*
54 t + s or t + s - p == t - (p - s)
55
56 So first compute ws = p - s
57
58 Then compute t + s and t - ws
59
60 If t - ws does not borrow, then that is the correct valued
61 */
62
63 const size_t mod_sw = mod.sig_words();
64 BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");
65
66 this->grow_to(mod_sw);
67 s.grow_to(mod_sw);
68
69 // First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
70 if(ws.size() < 3 * mod_sw) {
71 ws.resize(3 * mod_sw);
72 }
73
74 word borrow = bigint_sub3(&ws[0], mod._data(), mod_sw, s._data(), mod_sw);
75 BOTAN_DEBUG_ASSERT(borrow == 0);
76 BOTAN_UNUSED(borrow);
77
78 // Compute t - ws
79 borrow = bigint_sub3(&ws[mod_sw], this->_data(), mod_sw, &ws[0], mod_sw);
80
81 // Compute t + s
82 bigint_add3_nc(&ws[mod_sw * 2], this->_data(), mod_sw, s._data(), mod_sw);
83
84 CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw * 2], &ws[mod_sw], mod_sw);
85 set_words(&ws[0], mod_sw);
86
87 return (*this);
88}
89
91 if(this->is_negative() || s.is_negative() || mod.is_negative()) {
92 throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");
93 }
94
95 // We are assuming in this function that *this and s are no more than mod_sw words long
96 BOTAN_DEBUG_ASSERT(*this < mod);
97 BOTAN_DEBUG_ASSERT(s < mod);
98
99 const size_t mod_sw = mod.sig_words();
100
101 this->grow_to(mod_sw);
102 s.grow_to(mod_sw);
103
104 if(ws.size() < mod_sw) {
105 ws.resize(mod_sw);
106 }
107
108 bigint_mod_sub(mutable_data(), s._data(), mod._data(), mod_sw, ws.data());
109
110 return (*this);
111}
112
113BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) {
114 BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive");
115 BOTAN_ARG_CHECK(y < 16, "y too large");
116
117 BOTAN_DEBUG_ASSERT(*this < mod);
118
119 *this *= static_cast<word>(y);
120 this->reduce_below(mod, ws);
121 return (*this);
122}
123
124BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws) {
125 if(this->sign() != BigInt::Positive) {
126 throw Invalid_State("BigInt::sub_rev requires this is positive");
127 }
128
129 const size_t x_sw = this->sig_words();
130
131 ws.resize(std::max(x_sw, y_sw));
132 clear_mem(ws.data(), ws.size());
133
134 const int32_t relative_size = bigint_sub_abs(ws.data(), _data(), x_sw, y, y_sw);
135
136 this->cond_flip_sign(relative_size > 0);
137 this->swap_reg(ws);
138
139 return (*this);
140}
141
142/*
143* Multiplication Operator
144*/
147 return this->mul(y, ws);
148}
149
151 const size_t x_sw = sig_words();
152 const size_t y_sw = y.sig_words();
153 set_sign((sign() == y.sign()) ? Positive : Negative);
154
155 if(x_sw == 0 || y_sw == 0) {
156 clear();
158 } else if(x_sw == 1 && y_sw) {
159 grow_to(y_sw + 1);
160 bigint_linmul3(mutable_data(), y._data(), y_sw, word_at(0));
161 } else if(y_sw == 1 && x_sw) {
163 set_word_at(x_sw, carry);
164 } else {
165 const size_t new_size = x_sw + y_sw + 1;
166 if(ws.size() < new_size) {
167 ws.resize(new_size);
168 }
169 secure_vector<word> z_reg(new_size);
170
171 bigint_mul(z_reg.data(), z_reg.size(), _data(), size(), x_sw, y._data(), y.size(), y_sw, ws.data(), ws.size());
172
173 this->swap_reg(z_reg);
174 }
175
176 return (*this);
177}
178
180 const size_t sw = sig_words();
181
182 secure_vector<word> z(2 * sw);
183 ws.resize(z.size());
184
185 bigint_sqr(z.data(), z.size(), _data(), size(), sw, ws.data(), ws.size());
186
187 swap_reg(z);
189
190 return (*this);
191}
192
194 if(y == 0) {
195 clear();
197 }
198
199 const word carry = bigint_linmul2(mutable_data(), size(), y);
201
202 return (*this);
203}
204
205/*
206* Division Operator
207*/
209 if(y.sig_words() == 1 && is_power_of_2(y.word_at(0))) {
210 (*this) >>= (y.bits() - 1);
211 } else {
212 (*this) = (*this) / y;
213 }
214 return (*this);
215}
216
217/*
218* Modulo Operator
219*/
221 return (*this = (*this) % mod);
222}
223
224/*
225* Modulo Operator
226*/
228 if(mod == 0) {
229 throw Invalid_Argument("BigInt::operator%= divide by zero");
230 }
231
232 word remainder = 0;
233
234 if(is_power_of_2(mod)) {
235 remainder = (word_at(0) & (mod - 1));
236 } else {
237 const size_t sw = sig_words();
238 for(size_t i = sw; i > 0; --i) {
239 remainder = bigint_modop_vartime(remainder, word_at(i - 1), mod);
240 }
241 }
242
243 if(remainder && sign() == BigInt::Negative) {
244 remainder = mod - remainder;
245 }
246
247 m_data.set_to_zero();
248 m_data.set_word_at(0, remainder);
250 return remainder;
251}
252
253/*
254* Left Shift Operator
255*/
257 const size_t sw = sig_words();
258 const size_t new_size = sw + (shift + WordInfo<word>::bits - 1) / WordInfo<word>::bits;
259
260 m_data.grow_to(new_size);
261
262 bigint_shl1(m_data.mutable_data(), new_size, sw, shift);
263
264 return (*this);
265}
266
267/*
268* Right Shift Operator
269*/
271 bigint_shr1(m_data.mutable_data(), m_data.size(), shift);
272
273 if(is_negative() && is_zero()) {
275 }
276
277 return (*this);
278}
279
280} // namespace Botan
#define BOTAN_UNUSED
Definition assert.h:120
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:100
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:31
BigInt & operator>>=(size_t shift)
Definition big_ops2.cpp:270
BigInt & mod_mul(uint8_t y, const BigInt &mod, secure_vector< word > &ws)
Definition big_ops2.cpp:113
size_t sig_words() const
Definition bigint.h:615
BigInt & operator/=(const BigInt &y)
Definition big_ops2.cpp:208
BigInt()=default
void set_word_at(size_t i, word w)
Definition bigint.h:549
word * mutable_data()
Definition bigint.h:640
size_t size() const
Definition bigint.h:609
BigInt & rev_sub(const word y[], size_t y_words, secure_vector< word > &ws)
Definition big_ops2.cpp:124
void grow_to(size_t n) const
Definition bigint.h:666
void set_words(const word w[], size_t len)
Definition bigint.h:551
BigInt & operator*=(const BigInt &y)
Definition big_ops2.cpp:145
BigInt & mod_add(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition big_ops2.cpp:45
word word_at(size_t n) const
Definition bigint.h:547
BigInt & mul(const BigInt &y, secure_vector< word > &ws)
Definition big_ops2.cpp:150
void cond_flip_sign(bool predicate)
Definition bigint.cpp:503
BigInt & mod_sub(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition big_ops2.cpp:90
size_t bits() const
Definition bigint.cpp:310
BigInt & operator%=(const BigInt &y)
Definition big_ops2.cpp:220
void clear()
Definition bigint.h:399
const word * _data() const
Definition bigint.h:936
Sign sign() const
Definition bigint.h:571
BigInt & operator<<=(size_t shift)
Definition big_ops2.cpp:256
BigInt & add(const word y[], size_t y_words, Sign sign)
Definition big_ops2.cpp:16
bool is_zero() const
Definition bigint.h:457
size_t reduce_below(const BigInt &mod, secure_vector< word > &ws)
Definition bigint.cpp:332
BigInt & square(secure_vector< word > &ws)
Definition big_ops2.cpp:179
bool is_negative() const
Definition bigint.h:559
void swap_reg(secure_vector< word > &reg)
Definition bigint.h:198
void set_sign(Sign sign)
Definition bigint.h:592
constexpr Mask< T > conditional_copy_mem(Mask< T > mask, T *to, const T *from0, const T *from1, size_t elems)
Definition ct_utils.h:733
constexpr void bigint_linmul3(W z[], const W x[], size_t x_size, W y)
Definition mp_core.h:528
constexpr bool is_power_of_2(T arg)
Definition bit_ops.h:48
constexpr void bigint_shr1(W x[], size_t x_size, size_t shift)
Definition mp_core.h:445
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:326
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:311
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:282
constexpr void bigint_shl1(W x[], size_t x_size, size_t x_words, size_t shift)
Definition mp_core.h:426
constexpr int32_t bigint_cmp(const W x[], size_t x_size, const W y[], size_t y_size)
Definition mp_core.h:551
void carry(int64_t &h0, int64_t &h1)
constexpr auto bigint_modop_vartime(W n1, W n0, W d) -> W
Definition mp_core.h:747
constexpr auto bigint_sub_abs(W z[], const W x[], const W y[], size_t N, W ws[]) -> CT::Mask< W >
Definition mp_core.h:398
constexpr void bigint_add2(W x[], size_t x_size, const W y[], size_t y_size)
Definition mp_core.h:245
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:65
constexpr auto bigint_sub2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:261
constexpr void bigint_sub2_rev(W x[], const W y[], size_t y_size)
Definition mp_core.h:287
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
Definition types.h:119
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:123
constexpr void bigint_mod_sub(W t[], const W s[], const W mod[], size_t mod_sw, W ws[])
Definition mp_core.h:698
constexpr auto bigint_add3_nc(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:213
constexpr auto bigint_linmul2(W x[], size_t x_size, W y) -> W
Definition mp_core.h:511