25650639339

Committed 10 May 2026 07:03PM UTC coverage: 89.326% (-0.002%) from 89.328%

Build # 25650639339

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #5592 from randombit/jack/bn-hardening

Various BigInt/mp related hardenings and bug fixes

Coverage Stats

107853 of 120741 relevant lines covered (89.33%)

11294230.95 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

87.67

/src/lib/math/bigint/big_ops2.cpp

/*
* (C) 1999-2007,2018 Jack Lloyd
*     2016 Matthias Gierlings
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/bigint.h>

#include <botan/exceptn.h>
#include <botan/internal/bit_ops.h>
#include <botan/internal/mp_core.h>

namespace Botan {

BigInt& BigInt::operator+=(const BigInt& y) {
   if(&y == this) {
      return *this <<= 1;
   }
   return add(y._data(), y.sig_words(), y.sign());
}

BigInt& BigInt::operator-=(const BigInt& y) {
   if(&y == this) {
      this->clear();
      this->set_sign(Positive);
      return *this;
   }
   return sub(y._data(), y.sig_words(), y.sign());
}

BigInt& BigInt::add(const word y[], size_t y_words, Sign y_sign) {
   const size_t x_sw = sig_words();

   grow_to(std::max(x_sw, y_words) + 1);

   if(sign() == y_sign) {
      const word carry = bigint_add2(mutable_data(), size() - 1, y, y_words);
      mutable_data()[size() - 1] += carry;
   } else {
      const int32_t relative_size = bigint_cmp(_data(), x_sw, y, y_words);

      if(relative_size >= 0) {
         // *this >= y
         bigint_sub2(mutable_data(), x_sw, y, y_words);
      } else {
         // *this < y: compute *this = y - *this
         bigint_sub2_rev(mutable_data(), y, y_words);
      }

      if(relative_size < 0) {
         set_sign(y_sign);
      } else if(relative_size == 0) {
         set_sign(Positive);
      }
   }

   return (*this);
}

BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {
   if(this->signum() < 0 || s.signum() < 0 || mod.signum() < 0) {
      throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");
   }

   BOTAN_DEBUG_ASSERT(*this < mod);
   BOTAN_DEBUG_ASSERT(s < mod);

   /*
   t + s or t + s - p == t - (p - s)

   So first compute ws = p - s

   Then compute t + s and t - ws

   If t - ws does not borrow, then that is the correct valued
   */

   const size_t mod_sw = mod.sig_words();
   BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");

   this->grow_to(mod_sw);
   s.grow_to(mod_sw);

   // First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
   if(ws.size() < 3 * mod_sw) {
      ws.resize(3 * mod_sw);
   }

   // NOLINTBEGIN(readability-container-data-pointer)

   word borrow = bigint_sub3(&ws[0], mod._data(), mod_sw, s._data(), mod_sw);
   BOTAN_DEBUG_ASSERT(borrow == 0);
   BOTAN_UNUSED(borrow);

   // Compute t - ws
   borrow = bigint_sub3(&ws[mod_sw], this->_data(), mod_sw, &ws[0], mod_sw);

   // Compute t + s
   bigint_add3(&ws[mod_sw * 2], this->_data(), mod_sw, s._data(), mod_sw);

   CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw * 2], &ws[mod_sw], mod_sw);
   set_words(&ws[0], mod_sw);

   // NOLINTEND(readability-container-data-pointer)

   return (*this);
}

BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {
   if(this->signum() < 0 || s.signum() < 0 || mod.signum() < 0) {
      throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");
   }

   // We are assuming in this function that *this and s are no more than mod_sw words long
   BOTAN_DEBUG_ASSERT(*this < mod);
   BOTAN_DEBUG_ASSERT(s < mod);

   const size_t mod_sw = mod.sig_words();

   this->grow_to(mod_sw);
   s.grow_to(mod_sw);

   if(ws.size() < mod_sw) {
      ws.resize(mod_sw);
   }

   const word borrow = bigint_sub3(ws.data(), mutable_data(), mod_sw, s._data(), mod_sw);

   // Conditionally add back the modulus
   bigint_cnd_add(borrow, ws.data(), mod._data(), mod_sw);

   unchecked_copy_memory(mutable_data(), ws.data(), mod_sw);

   return (*this);
}

BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) {
   BOTAN_ARG_CHECK(this->signum() >= 0, "*this must be positive");
   BOTAN_ARG_CHECK(y < 16, "y too large");

   BOTAN_DEBUG_ASSERT(*this < mod);

   *this *= static_cast<word>(y);
   this->reduce_below(mod, ws);
   return (*this);
}

BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws) {
   BOTAN_UNUSED(ws);
   BigInt y_bn;
   y_bn.m_data.set_words(y, y_sw);
   *this = y_bn - *this;
   return (*this);
}

/*
* Multiplication Operator
*/
BigInt& BigInt::operator*=(const BigInt& y) {
   secure_vector<word> ws;
   return this->mul(y, ws);
}

BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws) {
   const size_t x_sw = sig_words();
   const size_t y_sw = y.sig_words();
   set_sign((sign() == y.sign()) ? Positive : Negative);

   if(x_sw == 0 || y_sw == 0) {
      clear();
      set_sign(Positive);
   } else if(x_sw == 1 && y_sw > 0) {
      grow_to(y_sw + 1);
      bigint_linmul3(mutable_data(), y._data(), y_sw, word_at(0));
   } else {
      const size_t new_size = x_sw + y_sw + 1;
      if(ws.size() < new_size) {
         ws.resize(new_size);
      }
      secure_vector<word> z_reg(new_size);

      bigint_mul(z_reg.data(), z_reg.size(), _data(), size(), x_sw, y._data(), y.size(), y_sw, ws.data(), ws.size());

      this->swap_reg(z_reg);
   }

   return (*this);
}

BigInt& BigInt::square(secure_vector<word>& ws) {
   const size_t sw = sig_words();

   secure_vector<word> z(2 * sw);
   ws.resize(z.size());

   bigint_sqr(z.data(), z.size(), _data(), size(), sw, ws.data(), ws.size());

   swap_reg(z);
   set_sign(BigInt::Positive);

   return (*this);
}

BigInt& BigInt::operator*=(word y) {
   if(y == 0) {
      clear();
      set_sign(Positive);
   }

   const word carry = bigint_linmul2(mutable_data(), size(), y);
   set_word_at(size(), carry);

   return (*this);
}

/*
* Division Operator
*/
BigInt& BigInt::operator/=(const BigInt& y) {
   if(y.sig_words() == 1 && signum() >= 0 && y.signum() >= 0 && is_power_of_2(y.word_at(0))) {
      (*this) >>= (y.bits() - 1);
   } else {
      (*this) = (*this) / y;
   }
   return (*this);
}

/*
* Modulo Operator
*/
BigInt& BigInt::operator%=(const BigInt& mod) {
   return (*this = (*this) % mod);
}

/*
* Modulo Operator
*/
word BigInt::operator%=(word mod) {
   if(mod == 0) {
      throw Invalid_Argument("BigInt::operator%= divide by zero");
   }

   word remainder = 0;

   if(is_power_of_2(mod)) {
      remainder = (word_at(0) & (mod - 1));
   } else {
      const divide_precomp redc_mod(mod);
      const size_t sw = sig_words();
      for(size_t i = sw; i > 0; --i) {
         remainder = redc_mod.vartime_mod_2to1(remainder, word_at(i - 1));
      }
   }

   if(remainder != 0 && sign() == BigInt::Negative) {
      remainder = mod - remainder;
   }

   m_data.set_to_zero();
   m_data.set_word_at(0, remainder);
   set_sign(BigInt::Positive);
   return remainder;
}

/*
* Left Shift Operator
*/
BigInt& BigInt::operator<<=(size_t shift) {
   if(shift >= 65536) {
      throw Invalid_Argument("BigInt left shift count too large");
   }

   const size_t sw = sig_words();
   const size_t new_size = sw + (shift + WordInfo<word>::bits - 1) / WordInfo<word>::bits;

   m_data.grow_to(new_size);

   bigint_shl1(m_data.mutable_data(), new_size, sw, shift);

   return (*this);
}

/*
* Right Shift Operator
*/
BigInt& BigInt::operator>>=(size_t shift) {
   bigint_shr1(m_data.mutable_data(), m_data.size(), shift);

   if(sig_words() == 0 && m_signedness == Negative) {
      m_signedness = Positive;
   }

   return (*this);
}

}  // namespace Botan

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
14	namespace Botan {
15
16	BigInt& BigInt::operator+=(const BigInt& y) {	97,643✔
17	if(&y == this) {	97,643✔
18	return *this <<= 1;	×
19	}
20	return add(y._data(), y.sig_words(), y.sign());	99,893✔
21	}
22
23	BigInt& BigInt::operator-=(const BigInt& y) {	3,825,138✔
24	if(&y == this) {	3,825,138✔
25	this->clear();	×
26	this->set_sign(Positive);	×
27	return *this;	×
28	}
29	return sub(y._data(), y.sig_words(), y.sign());	7,527,445✔
30	}
31
32	BigInt& BigInt::add(const word y[], size_t y_words, Sign y_sign) {	4,316,999✔
33	const size_t x_sw = sig_words();	4,316,999✔
34
35	grow_to(std::max(x_sw, y_words) + 1);	4,386,015✔
36
37	if(sign() == y_sign) {	4,316,999✔
38	const word carry = bigint_add2(mutable_data(), size() - 1, y, y_words);	498,682✔
39	mutable_data()[size() - 1] += carry;	498,682✔
40	} else {
41	const int32_t relative_size = bigint_cmp(_data(), x_sw, y, y_words);	3,818,317✔
42
43	if(relative_size >= 0) {	3,818,317✔
44	// *this >= y
45	bigint_sub2(mutable_data(), x_sw, y, y_words);	3,764,707✔
46	} else {
47	// this < y: compute this = y - *this
48	bigint_sub2_rev(mutable_data(), y, y_words);	53,610✔
49	}
50
51	if(relative_size < 0) {	3,818,317✔
52	set_sign(y_sign);	53,610✔
53	} else if(relative_size == 0) {	3,764,707✔
54	set_sign(Positive);	3,158✔
55	}
56	}
57
58	return (*this);	4,316,999✔
59	}
60
61	BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {	1,010,006✔
62	if(this->signum() < 0 \|\| s.signum() < 0 \|\| mod.signum() < 0) {	1,010,006✔
63	throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");	×
64	}
65
66	BOTAN_DEBUG_ASSERT(*this < mod);	1,010,006✔
67	BOTAN_DEBUG_ASSERT(s < mod);	1,010,006✔
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();	1,010,006✔
80	BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");	1,010,006✔
81
82	this->grow_to(mod_sw);	1,010,006✔
83	s.grow_to(mod_sw);	1,010,006✔
84
85	// First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
86	if(ws.size() < 3 * mod_sw) {	1,010,006✔
87	ws.resize(3 * mod_sw);	641,089✔
88	}
89
90	// NOLINTBEGIN(readability-container-data-pointer)
91
92	word borrow = bigint_sub3(&ws[0], mod._data(), mod_sw, s._data(), mod_sw);	1,010,006✔
93	BOTAN_DEBUG_ASSERT(borrow == 0);	1,010,006✔
94	BOTAN_UNUSED(borrow);	1,010,006✔
95
96	// Compute t - ws
97	borrow = bigint_sub3(&ws[mod_sw], this->_data(), mod_sw, &ws[0], mod_sw);	1,010,006✔
98
99	// Compute t + s
100	bigint_add3(&ws[mod_sw * 2], this->_data(), mod_sw, s._data(), mod_sw);	1,010,006✔
101
102	CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw * 2], &ws[mod_sw], mod_sw);	1,010,006✔
103	set_words(&ws[0], mod_sw);	1,010,006✔
104
105	// NOLINTEND(readability-container-data-pointer)
106
107	return (*this);	1,010,006✔
108	}
109
110	BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) {	15,667,662✔
111	if(this->signum() < 0 \|\| s.signum() < 0 \|\| mod.signum() < 0) {	15,667,662✔
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);	15,667,662✔
117	BOTAN_DEBUG_ASSERT(s < mod);	15,667,662✔
118
119	const size_t mod_sw = mod.sig_words();	15,667,662✔
120
121	this->grow_to(mod_sw);	15,667,662✔
122	s.grow_to(mod_sw);	15,667,662✔
123
124	if(ws.size() < mod_sw) {	15,667,662✔
125	ws.resize(mod_sw);	×
126	}
127
128	const word borrow = bigint_sub3(ws.data(), mutable_data(), mod_sw, s._data(), mod_sw);	15,667,662✔
129
130	// Conditionally add back the modulus
131	bigint_cnd_add(borrow, ws.data(), mod._data(), mod_sw);	15,667,662✔
132
133	unchecked_copy_memory(mutable_data(), ws.data(), mod_sw);	15,667,662✔
134
135	return (*this);	15,667,662✔
136	}
137
138	BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) {	6,975,088✔
139	BOTAN_ARG_CHECK(this->signum() >= 0, "*this must be positive");	6,975,088✔
140	BOTAN_ARG_CHECK(y < 16, "y too large");	6,975,088✔
141
142	BOTAN_DEBUG_ASSERT(*this < mod);	6,975,088✔
143
144	this = static_cast<word>(y);	6,975,088✔
145	this->reduce_below(mod, ws);	6,975,088✔
146	return (*this);	6,975,088✔
147	}
148
149	BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws) {	×
150	BOTAN_UNUSED(ws);	×
151	BigInt y_bn;	×
152	y_bn.m_data.set_words(y, y_sw);	×
153	this = y_bn - this;	×
154	return (*this);	×
155	}	×
156
157	/*
158	* Multiplication Operator
159	*/
160	BigInt& BigInt::operator*=(const BigInt& y) {	525✔
161	secure_vector<word> ws;	525✔
162	return this->mul(y, ws);	525✔
163	}	525✔
164
165	BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws) {	8,600✔
166	const size_t x_sw = sig_words();	8,600✔
167	const size_t y_sw = y.sig_words();	8,600✔
168	set_sign((sign() == y.sign()) ? Positive : Negative);	8,670✔
169
170	if(x_sw == 0 \|\| y_sw == 0) {	8,600✔
171	clear();	32✔
172	set_sign(Positive);	32✔
173	} else if(x_sw == 1 && y_sw > 0) {	8,568✔
174	grow_to(y_sw + 1);	328✔
175	bigint_linmul3(mutable_data(), y._data(), y_sw, word_at(0));	656✔
176	} else {
177	const size_t new_size = x_sw + y_sw + 1;	8,240✔
178	if(ws.size() < new_size) {	8,240✔
179	ws.resize(new_size);	8,240✔
180	}
181	secure_vector<word> z_reg(new_size);	8,240✔
182
183	bigint_mul(z_reg.data(), z_reg.size(), _data(), size(), x_sw, y._data(), y.size(), y_sw, ws.data(), ws.size());	8,240✔
184
185	this->swap_reg(z_reg);	8,240✔
186	}	8,240✔
187
188	return (*this);	8,600✔
189	}
190
191	BigInt& BigInt::square(secure_vector<word>& ws) {	9,096✔
192	const size_t sw = sig_words();	9,096✔
193
194	secure_vector<word> z(2 * sw);	9,096✔
195	ws.resize(z.size());	9,096✔
196
197	bigint_sqr(z.data(), z.size(), _data(), size(), sw, ws.data(), ws.size());	9,096✔
198
199	swap_reg(z);	9,096✔
200	set_sign(BigInt::Positive);	9,096✔
201
202	return (*this);	9,096✔
203	}	9,096✔
204
205	BigInt& BigInt::operator*=(word y) {	6,993,979✔
206	if(y == 0) {	6,993,979✔
207	clear();	×
208	set_sign(Positive);	×
209	}
210
211	const word carry = bigint_linmul2(mutable_data(), size(), y);	6,993,979✔
212	set_word_at(size(), carry);	6,993,979✔
213
214	return (*this);	6,993,979✔
215	}
216
217	/*
218	* Division Operator
219	*/
220	BigInt& BigInt::operator/=(const BigInt& y) {	938✔
221	if(y.sig_words() == 1 && signum() >= 0 && y.signum() >= 0 && is_power_of_2(y.word_at(0))) {	1,628✔
222	(*this) >>= (y.bits() - 1);	85✔
223	} else {
224	(this) = (this) / y;	853✔
225	}
226	return (*this);	938✔
227	}
228
229	/*
230	* Modulo Operator
231	*/
232	BigInt& BigInt::operator%=(const BigInt& mod) {	333,601✔
233	return (this = (this) % mod);	333,601✔
234	}
235
236	/*
237	* Modulo Operator
238	*/
239	word BigInt::operator%=(word mod) {	34✔
240	if(mod == 0) {	34✔
241	throw Invalid_Argument("BigInt::operator%= divide by zero");	×
242	}
243
244	word remainder = 0;	34✔
245
246	if(is_power_of_2(mod)) {	34✔
247	remainder = (word_at(0) & (mod - 1));	10✔
248	} else {
249	const divide_precomp redc_mod(mod);	29✔
250	const size_t sw = sig_words();	29✔
251	for(size_t i = sw; i > 0; --i) {	81✔
252	remainder = redc_mod.vartime_mod_2to1(remainder, word_at(i - 1));	104✔
253	}
254	}
255
256	if(remainder != 0 && sign() == BigInt::Negative) {	34✔
257	remainder = mod - remainder;	13✔
258	}
259
260	m_data.set_to_zero();	34✔
261	m_data.set_word_at(0, remainder);	34✔
262	set_sign(BigInt::Positive);	34✔
263	return remainder;	34✔
264	}
265
266	/*
267	* Left Shift Operator
268	*/
269	BigInt& BigInt::operator<<=(size_t shift) {	976,364✔
270	if(shift >= 65536) {	976,364✔
271	throw Invalid_Argument("BigInt left shift count too large");	×
272	}
273
274	const size_t sw = sig_words();	976,364✔
275	const size_t new_size = sw + (shift + WordInfo<word>::bits - 1) / WordInfo<word>::bits;	976,364✔
276
277	m_data.grow_to(new_size);	976,364✔
278
279	bigint_shl1(m_data.mutable_data(), new_size, sw, shift);	976,364✔
280
281	return (*this);	976,364✔
282	}
283
284	/*
285	* Right Shift Operator
286	*/
287	BigInt& BigInt::operator>>=(size_t shift) {	7,200,913✔
288	bigint_shr1(m_data.mutable_data(), m_data.size(), shift);	7,200,913✔
289
290	if(sig_words() == 0 && m_signedness == Negative) {	14,401,826✔
291	m_signedness = Positive;	8✔
292	}
293
294	return (*this);	7,200,913✔
295	}
296
297	} // namespace Botan

randombit / botan / 25650639339

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous