24063525848

Committed 06 Apr 2026 10:36PM UTC coverage: 89.448% (-0.007%) from 89.455%

Build # 24063525848

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #5521 from randombit/jack/fix-rollup

Rollup of small fixes

Coverage Stats

105878 of 118368 relevant lines covered (89.45%)

11475460.89 hits per line

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

90.16

/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

}  // 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);
            }
         }
      }
   }

   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, true);

      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;
      }
   }
}

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(rng, bits - 1, BigInt::zero(), 2, 3, error_bound);
      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) :	717✔
27	m_sieve(std::min(sieve_size, PRIME_TABLE_SIZE)), m_step(step), m_check_2p1(check_2p1) {	717✔
28	for(size_t i = 0; i != m_sieve.size(); ++i) {	280,282✔
29	m_sieve[i] = ct_mod_word(init_value, PRIMES[i]);	279,565✔
30	}
31	}	717✔
32
33	size_t sieve_size() const { return m_sieve.size(); }
34
35	bool check_2p1() const { return m_check_2p1; }	291,232,670✔
36
37	bool next() {	637,258✔
38	auto passes = CT::Mask<word>::set();	637,258✔
39	for(size_t i = 0; i != m_sieve.size(); ++i) {	291,869,928✔
40	m_sieve[i] = sieve_step_incr(m_sieve[i], m_step, PRIMES[i]);	291,232,670✔
41
42	// If m_sieve[i] == 0 then val % p == 0 -> not prime
43	passes &= CT::Mask<word>::expand(m_sieve[i]);	291,232,670✔
44
45	if(this->check_2p1()) {	291,232,670✔
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);	270,517,662✔
56	}
57	}
58
59	return passes.as_bool();	637,258✔
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) {	291,232,670✔
67	BOTAN_DEBUG_ASSERT(v < mod);	291,232,670✔
68	// The sieve step and primes are public so this modulo is ok
69	const word stepmod = (step >= mod) ? (step % mod) : step;	291,232,670✔
70
71	// This sum is at most 2*(mod-1)
72	const word next = (v + stepmod);	291,232,670✔
73	return next - CT::Mask<word>::is_gte(next, mod).if_set_return(mod);	291,232,670✔
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	} // namespace
108
109	/*
110	* Generate a random prime
111	*/
112	BigInt random_prime(	579✔
113	RandomNumberGenerator& rng, size_t bits, const BigInt& coprime, size_t equiv, size_t modulo, size_t prob) {
114	if(bits <= 1) {	579✔
115	throw Invalid_Argument("random_prime: Can't make a prime of " + std::to_string(bits) + " bits");	8✔
116	}
117	if(coprime.signum() < 0 \|\| (coprime.signum() != 0 && coprime.is_even()) \|\| coprime.bits() >= bits) {	584✔
118	throw Invalid_Argument("random_prime: invalid coprime");	×
119	}
120	// TODO(Botan4) reduce this to ~1000
121	if(modulo == 0 \|\| modulo >= 100000) {	577✔
122	throw Invalid_Argument("random_prime: Invalid modulo value");	×
123	}
124
125	equiv %= modulo;	577✔
126
127	if(equiv == 0) {	577✔
128	throw Invalid_Argument("random_prime Invalid value for equiv/modulo");	1✔
129	}
130
131	// Handle small values:
132
133	if(bits <= 16) {	576✔
134	if(equiv != 1 \|\| modulo != 2 \|\| coprime != 0) {	38✔
135	throw Not_Implemented("random_prime equiv/modulo/coprime options not usable for small primes");	×
136	}
137
138	if(bits == 2) {	19✔
139	return BigInt::from_word(((rng.next_byte() % 2) == 0 ? 2 : 3));	1✔
140	} else if(bits == 3) {	18✔
141	return BigInt::from_word(((rng.next_byte() % 2) == 0 ? 5 : 7));	2✔
142	} else if(bits == 4) {	17✔
143	return BigInt::from_word(((rng.next_byte() % 2) == 0 ? 11 : 13));	2✔
144	} else {
145	for(;;) {	7,738✔
146	// This is slightly biased, but for small primes it does not seem to matter
147	uint8_t b[4] = {0};	3,877✔
148	rng.randomize(b, 4);	3,877✔
149	const size_t idx = load_le<uint32_t>(b, 0) % PRIME_TABLE_SIZE;	3,877✔
150	const uint16_t small_prime = PRIMES[idx];	3,877✔
151
152	if(high_bit(small_prime) == bits) {	7,754✔
153	return BigInt::from_word(small_prime);	16✔
154	}
155	}	3,861✔
156	}
157	}
158
159	const size_t MAX_ATTEMPTS = 32 * 1024;	557✔
160
161	const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);	557✔
162
163	while(true) {	×
164	BigInt p(rng, bits);	557✔
165
166	// Force lowest and two top bits on
167	p.set_bit(bits - 1);	557✔
168	p.set_bit(bits - 2);	557✔
169	p.set_bit(0);	557✔
170
171	// Force p to be equal to equiv mod modulo
172	p += (modulo - (p % modulo)) + equiv;	557✔
173
174	Prime_Sieve sieve(p, bits, modulo, true);	557✔
175
176	for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt) {	605,498✔
177	p += modulo;	605,498✔
178
179	if(!sieve.next()) {	605,498✔
180	continue;	604,941✔
181	}
182
183	// here p can be even if modulo is odd, continue on in that case
184	if(p.is_even()) {	18,836✔
185	continue;	810✔
186	}
187
188	BOTAN_DEBUG_ASSERT(no_small_multiples(p, sieve));	8,608✔
189
190	auto mod_p = Barrett_Reduction::for_secret_modulus(p);	8,608✔
191	const Montgomery_Params monty_p(p, mod_p);	8,608✔
192
193	if(coprime > 1) {	8,608✔
194	/*
195	First do a single M-R iteration to quickly eliminate most non-primes,
196	before doing the coprimality check which is expensive
197	*/
198	if(!is_miller_rabin_probable_prime(p, mod_p, monty_p, rng, 1)) {	186✔
199	continue;	180✔
200	}
201
202	/*
203	* Check if p - 1 and coprime are relatively prime, using gcd.
204	* The gcd computation is const-time
205	*/
206	if(gcd(p - 1, coprime) > 1) {	12✔
207	continue;	×
208	}
209	}
210
211	if(p.bits() > bits) {	8,428✔
212	break;
213	}
214
215	if(!is_miller_rabin_probable_prime(p, mod_p, monty_p, rng, mr_trials)) {	8,428✔
216	continue;	7,871✔
217	}
218
219	if(prob > 32 && !is_lucas_probable_prime(p, mod_p)) {	557✔
220	continue;	×
221	}
222
223	return p;	557✔
224	}	17,216✔
225	}	557✔
226	}
227
228	BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng,	160✔
229	RandomNumberGenerator& prime_test_rng,
230	size_t bits,
231	const BigInt& coprime,
232	size_t prob) {
233	if(bits < 512) {	160✔
234	throw Invalid_Argument("generate_rsa_prime bits too small");	×
235	}
236
237	/*
238	* The restriction on coprime <= 64 bits is arbitrary but generally speaking
239	* very large RSA public exponents are a bad idea both for performance and due
240	* to attacks on small d.
241	*/
242	if(coprime <= 1 \|\| coprime.is_even() \|\| coprime.bits() > 64) {	320✔
243	throw Invalid_Argument("generate_rsa_prime coprime must be small odd positive integer");	×
244	}
245
246	const size_t MAX_ATTEMPTS = 32 * 1024;	160✔
247
248	const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);	160✔
249
250	while(true) {	×
251	BigInt p(keygen_rng, bits);	160✔
252
253	auto scope = CT::scoped_poison(p);	160✔
254
255	/*
256	Force high two bits so multiplication always results in expected n bit integer
257
258	Force the two low bits, and step by 4, so the generated prime is always == 3 (mod 4).
259	This way when we perform the inversion modulo phi(n) it is always of the form 2*o
260	with o odd, which allows a fastpath and avoids leaking any information about the
261	structure of the prime.
262	*/
263	p.set_bit(bits - 1);	160✔
264	p.set_bit(bits - 2);	160✔
265	p.set_bit(1);	160✔
266	p.set_bit(0);	160✔
267
268	const word step = 4;	160✔
269
270	Prime_Sieve sieve(p, bits, step, false);	160✔
271
272	for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt) {	31,760✔
273	p += step;	31,760✔
274
275	if(!sieve.next()) {	31,760✔
276	continue;	31,600✔
277	}
278
279	BOTAN_DEBUG_ASSERT(no_small_multiples(p, sieve));	4,259✔
280
281	auto mod_p = Barrett_Reduction::for_secret_modulus(p);	4,259✔
282	const Montgomery_Params monty_p(p, mod_p);	4,259✔
283
284	/*
285	* Do a single primality test first before checking coprimality, since
286	* currently a single Miller-Rabin test is faster than computing gcd,
287	* and this eliminates almost all wasted gcd computations.
288	*/
289	if(!is_miller_rabin_probable_prime(p, mod_p, monty_p, prime_test_rng, 1)) {	4,259✔
290	continue;	4,099✔
291	}
292
293	/*
294	* Check if p - 1 and coprime are relatively prime.
295	*/
296	if(gcd(p - 1, coprime) > 1) {	320✔
297	continue;	×
298	}
299
300	if(p.bits() > bits) {	160✔
301	break;
302	}
303
304	if(is_miller_rabin_probable_prime(p, mod_p, monty_p, prime_test_rng, mr_trials)) {	160✔
305	return p;	320✔
306	}
307	}	8,518✔
308	}	320✔
309	}
310
311	/*
312	* Generate a random safe prime
313	*/
314	BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits) {	2✔
315	if(bits <= 64) {	2✔
316	throw Invalid_Argument("random_safe_prime: Can't make a prime of " + std::to_string(bits) + " bits");	×
317	}
318
319	const size_t error_bound = 128;	2✔
320
321	BigInt q;	2✔
322	BigInt p;	2✔
323	for(;;) {	26✔
324	/*
325	Generate q == 2 (mod 3), since otherwise [in the case of q == 1 (mod 3)],
326	2*q+1 == 3 (mod 3) and so certainly not prime.
327	*/
328	q = random_prime(rng, bits - 1, BigInt::zero(), 2, 3, error_bound);	26✔
329	p = (q << 1) + 1;	52✔
330
331	if(is_prime(p, rng, error_bound, true)) {	26✔
332	return p;	2✔
333	}
334	}
335	}	2✔
336
337	} // namespace Botan

randombit / botan / 24063525848

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