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

90.32

/src/lib/math/numbertheory/make_prm.cpp

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

#include <botan/internal/primality.h>

#include <botan/exceptn.h>
#include <botan/numthry.h>
#include <botan/rng.h>
#include <botan/internal/barrett.h>
#include <botan/internal/bit_ops.h>
#include <botan/internal/ct_utils.h>
#include <botan/internal/divide.h>
#include <botan/internal/loadstor.h>
#include <botan/internal/monty.h>

namespace Botan {

namespace {

class Prime_Sieve final {
   public:
      Prime_Sieve(const BigInt& init_value, size_t sieve_size, word step, bool check_2p1) :
            m_sieve(std::min(sieve_size, PRIME_TABLE_SIZE)), m_step(step), m_check_2p1(check_2p1) {
         for(size_t i = 0; i != m_sieve.size(); ++i) {
            m_sieve[i] = ct_mod_word(init_value, PRIMES[i]);
         }
      }

      size_t sieve_size() const { return m_sieve.size(); }

      bool check_2p1() const { return m_check_2p1; }

      bool next() {
         auto passes = CT::Mask<word>::set();
         for(size_t i = 0; i != m_sieve.size(); ++i) {
            m_sieve[i] = sieve_step_incr(m_sieve[i], m_step, PRIMES[i]);

            // If m_sieve[i] == 0 then val % p == 0 -> not prime
            passes &= CT::Mask<word>::expand(m_sieve[i]);

            if(this->check_2p1()) {
               /*
               If v % p == (p-1)/2 then 2*v+1 == 0 (mod p)

               So if potentially generating a safe prime, we want to
               avoid this value because 2*v+1 will certainly not be prime.

               See "Safe Prime Generation with a Combined Sieve" M. Wiener
               https://eprint.iacr.org/2003/186.pdf
               */
               passes &= ~CT::Mask<word>::is_equal(m_sieve[i], (PRIMES[i] - 1) / 2);
            }
         }

         return passes.as_bool();
      }

   private:
      // Return (v + step) % mod
      //
      // This assumes v is already < mod, which is an invariant of the sieve
      static constexpr word sieve_step_incr(word v, word step, word mod) {
         BOTAN_DEBUG_ASSERT(v < mod);
         // The sieve step and primes are public so this modulo is ok
         const word stepmod = (step >= mod) ? (step % mod) : step;

         // This sum is at most 2*(mod-1)
         const word next = (v + stepmod);
         return next - CT::Mask<word>::is_gte(next, mod).if_set_return(mod);
      }

      std::vector<word> m_sieve;
      const word m_step;
      const bool m_check_2p1;
};

#if defined(BOTAN_ENABLE_DEBUG_ASSERTS)

bool no_small_multiples(const BigInt& v, const Prime_Sieve& sieve) {
   const size_t sieve_size = sieve.sieve_size();
   const bool check_2p1 = sieve.check_2p1();

   if(v.is_even())
      return false;

   const BigInt v_x2_p1 = 2 * v + 1;

   for(size_t i = 0; i != sieve_size; ++i) {
      if((v % PRIMES[i]) == 0)
         return false;

      if(check_2p1) {
         if(v_x2_p1 % PRIMES[i] == 0)
            return false;
      }
   }

   return true;
}

#endif

BigInt random_prime_with_sieve(RandomNumberGenerator& rng,
                               size_t bits,
                               const BigInt& coprime,
                               size_t equiv,
                               size_t modulo,
                               size_t prob,
                               bool sieve_check_2p1) {
   const size_t MAX_ATTEMPTS = 32 * 1024;

   const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);

   while(true) {
      BigInt p(rng, bits);

      // Force lowest and two top bits on
      p.set_bit(bits - 1);
      p.set_bit(bits - 2);
      p.set_bit(0);

      // Force p to be equal to equiv mod modulo
      p += (modulo - (p % modulo)) + equiv;

      Prime_Sieve sieve(p, bits, modulo, sieve_check_2p1);

      for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt) {
         p += modulo;

         if(!sieve.next()) {
            continue;
         }

         // here p can be even if modulo is odd, continue on in that case
         if(p.is_even()) {
            continue;
         }

         BOTAN_DEBUG_ASSERT(no_small_multiples(p, sieve));

         auto mod_p = Barrett_Reduction::for_secret_modulus(p);
         const Montgomery_Params monty_p(p, mod_p);

         if(coprime > 1) {
            /*
            First do a single M-R iteration to quickly eliminate most non-primes,
            before doing the coprimality check which is expensive
            */
            if(!is_miller_rabin_probable_prime(p, mod_p, monty_p, rng, 1)) {
               continue;
            }

            /*
            * Check if p - 1 and coprime are relatively prime, using gcd.
            * The gcd computation is const-time
            */
            if(gcd(p - 1, coprime) > 1) {
               continue;
            }
         }

         if(p.bits() > bits) {
            break;
         }

         if(!is_miller_rabin_probable_prime(p, mod_p, monty_p, rng, mr_trials)) {
            continue;
         }

         if(prob > 32 && !is_lucas_probable_prime(p, mod_p)) {
            continue;
         }

         return p;
      }
   }
}

}  // namespace

/*
* Generate a random prime
*/
BigInt random_prime(
   RandomNumberGenerator& rng, size_t bits, const BigInt& coprime, size_t equiv, size_t modulo, size_t prob) {
   if(bits <= 1) {
      throw Invalid_Argument("random_prime: Can't make a prime of " + std::to_string(bits) + " bits");
   }
   if(coprime.signum() < 0 || (coprime.signum() != 0 && coprime.is_even()) || coprime.bits() >= bits) {
      throw Invalid_Argument("random_prime: invalid coprime");
   }
   // TODO(Botan4) reduce this to ~1000
   if(modulo == 0 || modulo >= 100000) {
      throw Invalid_Argument("random_prime: Invalid modulo value");
   }

   equiv %= modulo;

   if(equiv == 0) {
      throw Invalid_Argument("random_prime Invalid value for equiv/modulo");
   }

   // Handle small values:

   if(bits <= 16) {
      if(equiv != 1 || modulo != 2 || coprime != 0) {
         throw Not_Implemented("random_prime equiv/modulo/coprime options not usable for small primes");
      }

      if(bits == 2) {
         return BigInt::from_word(((rng.next_byte() % 2) == 0 ? 2 : 3));
      } else if(bits == 3) {
         return BigInt::from_word(((rng.next_byte() % 2) == 0 ? 5 : 7));
      } else if(bits == 4) {
         return BigInt::from_word(((rng.next_byte() % 2) == 0 ? 11 : 13));
      } else {
         for(;;) {
            // This is slightly biased, but for small primes it does not seem to matter
            uint8_t b[4] = {0};
            rng.randomize(b, 4);
            const size_t idx = load_le<uint32_t>(b, 0) % PRIME_TABLE_SIZE;
            const uint16_t small_prime = PRIMES[idx];

            if(high_bit(small_prime) == bits) {
               return BigInt::from_word(small_prime);
            }
         }
      }
   }

   // The check_2p1 sieve filter is only appropriate when generating q for a
   // safe prime; for arbitrary equiv/modulo it can pre-reject every candidate
   // (eg equiv=1, modulo=3 makes the residue mod 3 always equal (3-1)/2).
   return random_prime_with_sieve(rng, bits, coprime, equiv, modulo, prob, false);
}

BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng,
                          RandomNumberGenerator& prime_test_rng,
                          size_t bits,
                          const BigInt& coprime,
                          size_t prob) {
   if(bits < 512) {
      throw Invalid_Argument("generate_rsa_prime bits too small");
   }

   /*
   * The restriction on coprime <= 64 bits is arbitrary but generally speaking
   * very large RSA public exponents are a bad idea both for performance and due
   * to attacks on small d.
   */
   if(coprime <= 1 || coprime.is_even() || coprime.bits() > 64) {
      throw Invalid_Argument("generate_rsa_prime coprime must be small odd positive integer");
   }

   const size_t MAX_ATTEMPTS = 32 * 1024;

   const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);

   while(true) {
      BigInt p(keygen_rng, bits);

      auto scope = CT::scoped_poison(p);

      /*
      Force high two bits so multiplication always results in expected n bit integer

      Force the two low bits, and step by 4, so the generated prime is always == 3 (mod 4).
      This way when we perform the inversion modulo phi(n) it is always of the form 2*o
      with o odd, which allows a fastpath and avoids leaking any information about the
      structure of the prime.
      */
      p.set_bit(bits - 1);
      p.set_bit(bits - 2);
      p.set_bit(1);
      p.set_bit(0);

      const word step = 4;

      Prime_Sieve sieve(p, bits, step, false);

      for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt) {
         p += step;

         if(!sieve.next()) {
            continue;
         }

         BOTAN_DEBUG_ASSERT(no_small_multiples(p, sieve));

         auto mod_p = Barrett_Reduction::for_secret_modulus(p);
         const Montgomery_Params monty_p(p, mod_p);

         /*
         * Do a single primality test first before checking coprimality, since
         * currently a single Miller-Rabin test is faster than computing gcd,
         * and this eliminates almost all wasted gcd computations.
         */
         if(!is_miller_rabin_probable_prime(p, mod_p, monty_p, prime_test_rng, 1)) {
            continue;
         }

         /*
         * Check if p - 1 and coprime are relatively prime.
         */
         if(gcd(p - 1, coprime) > 1) {
            continue;
         }

         if(p.bits() > bits) {
            break;
         }

         if(is_miller_rabin_probable_prime(p, mod_p, monty_p, prime_test_rng, mr_trials)) {
            return p;
         }
      }
   }
}

/*
* Generate a random safe prime
*/
BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits) {
   if(bits <= 64) {
      throw Invalid_Argument("random_safe_prime: Can't make a prime of " + std::to_string(bits) + " bits");
   }

   const size_t error_bound = 128;

   BigInt q;
   BigInt p;
   for(;;) {
      /*
      Generate q == 2 (mod 3), since otherwise [in the case of q == 1 (mod 3)],
      2*q+1 == 3 (mod 3) and so certainly not prime.
      */
      q = random_prime_with_sieve(rng, bits - 1, BigInt::zero(), 2, 3, error_bound, true);
      p = (q << 1) + 1;

      if(is_prime(p, rng, error_bound, true)) {
         return p;
      }
   }
}

}  // namespace Botan

1	/*
2	* Prime Generation
3	* (C) 1999-2007,2018,2019 Jack Lloyd
4	*
5	* Botan is released under the Simplified BSD License (see license.txt)
6	*/
7
8	#include <botan/internal/primality.h>
9
10	#include <botan/exceptn.h>
11	#include <botan/numthry.h>
12	#include <botan/rng.h>
13	#include <botan/internal/barrett.h>
14	#include <botan/internal/bit_ops.h>
15	#include <botan/internal/ct_utils.h>
16	#include <botan/internal/divide.h>
17	#include <botan/internal/loadstor.h>
18	#include <botan/internal/monty.h>
19
20	namespace Botan {
21
22	namespace {
23
24	class Prime_Sieve final {	×
25	public:
26	Prime_Sieve(const BigInt& init_value, size_t sieve_size, word step, bool check_2p1) :	713✔
27	m_sieve(std::min(sieve_size, PRIME_TABLE_SIZE)), m_step(step), m_check_2p1(check_2p1) {	713✔
28	for(size_t i = 0; i != m_sieve.size(); ++i) {	275,222✔
29	m_sieve[i] = ct_mod_word(init_value, PRIMES[i]);	274,509✔
30	}
31	}	713✔
32
33	size_t sieve_size() const { return m_sieve.size(); }
34
35	bool check_2p1() const { return m_check_2p1; }	119,606,877✔
36
37	bool next() {	169,823✔
38	auto passes = CT::Mask<word>::set();	169,823✔
39	for(size_t i = 0; i != m_sieve.size(); ++i) {	119,776,700✔
40	m_sieve[i] = sieve_step_incr(m_sieve[i], m_step, PRIMES[i]);	119,606,877✔
41
42	// If m_sieve[i] == 0 then val % p == 0 -> not prime
43	passes &= CT::Mask<word>::expand(m_sieve[i]);	119,606,877✔
44
45	if(this->check_2p1()) {	119,606,877✔
46	/*
47	If v % p == (p-1)/2 then 2*v+1 == 0 (mod p)
48
49	So if potentially generating a safe prime, we want to
50	avoid this value because 2*v+1 will certainly not be prime.
51
52	See "Safe Prime Generation with a Combined Sieve" M. Wiener
53	https://eprint.iacr.org/2003/186.pdf
54	*/
55	passes &= ~CT::Mask<word>::is_equal(m_sieve[i], (PRIMES[i] - 1) / 2);	71,039,424✔
56	}
57	}
58
59	return passes.as_bool();	169,823✔
60	}
61
62	private:
63	// Return (v + step) % mod
64	//
65	// This assumes v is already < mod, which is an invariant of the sieve
66	static constexpr word sieve_step_incr(word v, word step, word mod) {	119,606,877✔
67	BOTAN_DEBUG_ASSERT(v < mod);	119,606,877✔
68	// The sieve step and primes are public so this modulo is ok
69	const word stepmod = (step >= mod) ? (step % mod) : step;	119,606,877✔
70
71	// This sum is at most 2*(mod-1)
72	const word next = (v + stepmod);	119,606,877✔
73	return next - CT::Mask<word>::is_gte(next, mod).if_set_return(mod);	119,606,877✔
74	}
75
76	std::vector<word> m_sieve;
77	const word m_step;
78	const bool m_check_2p1;
79	};
80
81	#if defined(BOTAN_ENABLE_DEBUG_ASSERTS)
82
83	bool no_small_multiples(const BigInt& v, const Prime_Sieve& sieve) {
84	const size_t sieve_size = sieve.sieve_size();
85	const bool check_2p1 = sieve.check_2p1();
86
87	if(v.is_even())
88	return false;
89
90	const BigInt v_x2_p1 = 2 * v + 1;
91
92	for(size_t i = 0; i != sieve_size; ++i) {
93	if((v % PRIMES[i]) == 0)
94	return false;
95
96	if(check_2p1) {
97	if(v_x2_p1 % PRIMES[i] == 0)
98	return false;
99	}
100	}
101
102	return true;
103	}
104
105	#endif
106
107	BigInt random_prime_with_sieve(RandomNumberGenerator& rng,	551✔
108	size_t bits,
109	const BigInt& coprime,
110	size_t equiv,
111	size_t modulo,
112	size_t prob,
113	bool sieve_check_2p1) {
114	const size_t MAX_ATTEMPTS = 32 * 1024;	551✔
115
116	const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);	551✔
117
118	while(true) {	×
119	BigInt p(rng, bits);	551✔
120
121	// Force lowest and two top bits on
122	p.set_bit(bits - 1);	551✔
123	p.set_bit(bits - 2);	551✔
124	p.set_bit(0);	551✔
125
126	// Force p to be equal to equiv mod modulo
127	p += (modulo - (p % modulo)) + equiv;	551✔
128
129	Prime_Sieve sieve(p, bits, modulo, sieve_check_2p1);	551✔
130
131	for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt) {	126,956✔
132	p += modulo;	126,956✔
133
134	if(!sieve.next()) {	126,956✔
135	continue;	126,405✔
136	}
137
138	// here p can be even if modulo is odd, continue on in that case
139	if(p.is_even()) {	21,290✔
140	continue;	1,061✔
141	}
142
143	BOTAN_DEBUG_ASSERT(no_small_multiples(p, sieve));	9,584✔
144
145	auto mod_p = Barrett_Reduction::for_secret_modulus(p);	9,584✔
146	const Montgomery_Params monty_p(p, mod_p);	9,584✔
147
148	if(coprime > 1) {	9,584✔
149	/*
150	First do a single M-R iteration to quickly eliminate most non-primes,
151	before doing the coprimality check which is expensive
152	*/
153	if(!is_miller_rabin_probable_prime(p, mod_p, monty_p, rng, 1)) {	310✔
154	continue;	304✔
155	}
156
157	/*
158	* Check if p - 1 and coprime are relatively prime, using gcd.
159	* The gcd computation is const-time
160	*/
161	if(gcd(p - 1, coprime) > 1) {	12✔
162	continue;	×
163	}
164	}
165
166	if(p.bits() > bits) {	9,280✔
167	break;
168	}
169
170	if(!is_miller_rabin_probable_prime(p, mod_p, monty_p, rng, mr_trials)) {	9,280✔
171	continue;	8,729✔
172	}
173
174	if(prob > 32 && !is_lucas_probable_prime(p, mod_p)) {	551✔
175	continue;	×
176	}
177
178	return p;	1,102✔
179	}	19,168✔
180	}	551✔
181	}
182
183	} // namespace
184
185	/*
186	* Generate a random prime
187	*/
188	BigInt random_prime(	557✔
189	RandomNumberGenerator& rng, size_t bits, const BigInt& coprime, size_t equiv, size_t modulo, size_t prob) {
190	if(bits <= 1) {	557✔
191	throw Invalid_Argument("random_prime: Can't make a prime of " + std::to_string(bits) + " bits");	8✔
192	}
193	if(coprime.signum() < 0 \|\| (coprime.signum() != 0 && coprime.is_even()) \|\| coprime.bits() >= bits) {	562✔
194	throw Invalid_Argument("random_prime: invalid coprime");	×
195	}
196	// TODO(Botan4) reduce this to ~1000
197	if(modulo == 0 \|\| modulo >= 100000) {	555✔
198	throw Invalid_Argument("random_prime: Invalid modulo value");	×
199	}
200
201	equiv %= modulo;	555✔
202
203	if(equiv == 0) {	555✔
204	throw Invalid_Argument("random_prime Invalid value for equiv/modulo");	1✔
205	}
206
207	// Handle small values:
208
209	if(bits <= 16) {	554✔
210	if(equiv != 1 \|\| modulo != 2 \|\| coprime != 0) {	38✔
211	throw Not_Implemented("random_prime equiv/modulo/coprime options not usable for small primes");	×
212	}
213
214	if(bits == 2) {	19✔
215	return BigInt::from_word(((rng.next_byte() % 2) == 0 ? 2 : 3));	1✔
216	} else if(bits == 3) {	18✔
217	return BigInt::from_word(((rng.next_byte() % 2) == 0 ? 5 : 7));	2✔
218	} else if(bits == 4) {	17✔
219	return BigInt::from_word(((rng.next_byte() % 2) == 0 ? 11 : 13));	2✔
220	} else {
221	for(;;) {	9,562✔
222	// This is slightly biased, but for small primes it does not seem to matter
223	uint8_t b[4] = {0};	4,789✔
224	rng.randomize(b, 4);	4,789✔
225	const size_t idx = load_le<uint32_t>(b, 0) % PRIME_TABLE_SIZE;	4,789✔
226	const uint16_t small_prime = PRIMES[idx];	4,789✔
227
228	if(high_bit(small_prime) == bits) {	9,578✔
229	return BigInt::from_word(small_prime);	16✔
230	}
231	}	4,773✔
232	}
233	}
234
235	// The check_2p1 sieve filter is only appropriate when generating q for a
236	// safe prime; for arbitrary equiv/modulo it can pre-reject every candidate
237	// (eg equiv=1, modulo=3 makes the residue mod 3 always equal (3-1)/2).
238	return random_prime_with_sieve(rng, bits, coprime, equiv, modulo, prob, false);	535✔
239	}
240
241	BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng,	162✔
242	RandomNumberGenerator& prime_test_rng,
243	size_t bits,
244	const BigInt& coprime,
245	size_t prob) {
246	if(bits < 512) {	162✔
247	throw Invalid_Argument("generate_rsa_prime bits too small");	×
248	}
249
250	/*
251	* The restriction on coprime <= 64 bits is arbitrary but generally speaking
252	* very large RSA public exponents are a bad idea both for performance and due
253	* to attacks on small d.
254	*/
255	if(coprime <= 1 \|\| coprime.is_even() \|\| coprime.bits() > 64) {	324✔
256	throw Invalid_Argument("generate_rsa_prime coprime must be small odd positive integer");	×
257	}
258
259	const size_t MAX_ATTEMPTS = 32 * 1024;	162✔
260
261	const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);	162✔
262
263	while(true) {	×
264	BigInt p(keygen_rng, bits);	162✔
265
266	auto scope = CT::scoped_poison(p);	162✔
267
268	/*
269	Force high two bits so multiplication always results in expected n bit integer
270
271	Force the two low bits, and step by 4, so the generated prime is always == 3 (mod 4).
272	This way when we perform the inversion modulo phi(n) it is always of the form 2*o
273	with o odd, which allows a fastpath and avoids leaking any information about the
274	structure of the prime.
275	*/
276	p.set_bit(bits - 1);	162✔
277	p.set_bit(bits - 2);	162✔
278	p.set_bit(1);	162✔
279	p.set_bit(0);	162✔
280
281	const word step = 4;	162✔
282
283	Prime_Sieve sieve(p, bits, step, false);	162✔
284
285	for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt) {	42,867✔
286	p += step;	42,867✔
287
288	if(!sieve.next()) {	42,867✔
289	continue;	42,705✔
290	}
291
292	BOTAN_DEBUG_ASSERT(no_small_multiples(p, sieve));	5,843✔
293
294	auto mod_p = Barrett_Reduction::for_secret_modulus(p);	5,843✔
295	const Montgomery_Params monty_p(p, mod_p);	5,843✔
296
297	/*
298	* Do a single primality test first before checking coprimality, since
299	* currently a single Miller-Rabin test is faster than computing gcd,
300	* and this eliminates almost all wasted gcd computations.
301	*/
302	if(!is_miller_rabin_probable_prime(p, mod_p, monty_p, prime_test_rng, 1)) {	5,843✔
303	continue;	5,681✔
304	}
305
306	/*
307	* Check if p - 1 and coprime are relatively prime.
308	*/
309	if(gcd(p - 1, coprime) > 1) {	324✔
310	continue;	×
311	}
312
313	if(p.bits() > bits) {	162✔
314	break;
315	}
316
317	if(is_miller_rabin_probable_prime(p, mod_p, monty_p, prime_test_rng, mr_trials)) {	162✔
318	return p;	324✔
319	}
320	}	11,686✔
321	}	324✔
322	}
323
324	/*
325	* Generate a random safe prime
326	*/
327	BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits) {	2✔
328	if(bits <= 64) {	2✔
329	throw Invalid_Argument("random_safe_prime: Can't make a prime of " + std::to_string(bits) + " bits");	×
330	}
331
332	const size_t error_bound = 128;	2✔
333
334	BigInt q;	2✔
335	BigInt p;	2✔
336	for(;;) {	16✔
337	/*
338	Generate q == 2 (mod 3), since otherwise [in the case of q == 1 (mod 3)],
339	2*q+1 == 3 (mod 3) and so certainly not prime.
340	*/
341	q = random_prime_with_sieve(rng, bits - 1, BigInt::zero(), 2, 3, error_bound, true);	16✔
342	p = (q << 1) + 1;	32✔
343
344	if(is_prime(p, rng, error_bound, true)) {	16✔
345	return p;	2✔
346	}
347	}
348	}	2✔
349
350	} // 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