5079590438

Committed 25 May 2023 12:28PM UTC coverage: 92.228% (+0.5%) from 91.723%

Build # 5079590438

Build Type

Pull #3502

github

Pull Request Pull Request #3502: Apply clang-format to the codebase

Run Details

75589 of 81959 relevant lines covered (92.23%)

12139530.51 hits per line

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

92.04

/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/numthry.h>
#include <botan/reducer.h>
#include <botan/rng.h>
#include <botan/internal/bit_ops.h>
#include <botan/internal/ct_utils.h>
#include <botan/internal/loadstor.h>
#include <algorithm>

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] = 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] = (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.is_set();
      }

   private:
      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

}

/*
* 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.is_negative() || (!coprime.is_zero() && coprime.is_even()) || coprime.bits() >= bits) {
      throw Invalid_Argument("random_prime: invalid coprime");
   }
   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) ? 2 : 3));
      } else if(bits == 3) {
         return BigInt::from_word(((rng.next_byte() % 2) ? 5 : 7));
      } else if(bits == 4) {
         return BigInt::from_word(((rng.next_byte() % 2) ? 11 : 13));
      } else {
         for(;;) {
            // This is slightly biased, but for small primes it does not seem to matter
            uint8_t b[4];
            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));

         Modular_Reducer mod_p(p);

         if(coprime > 1) {
            /*
            First do a single M-R iteration to quickly elimate most non-primes,
            before doing the coprimality check which is expensive
            */
            if(is_miller_rabin_probable_prime(p, mod_p, rng, 1) == false)
               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, rng, mr_trials) == false)
            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);

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

         Modular_Reducer mod_p(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, prime_test_rng, 1) == false)
            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, prime_test_rng, mr_trials) == true)
            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, 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;
      }
   }
}

}

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/numthry.h>
11	#include <botan/reducer.h>
12	#include <botan/rng.h>
13	#include <botan/internal/bit_ops.h>
14	#include <botan/internal/ct_utils.h>
15	#include <botan/internal/loadstor.h>
16	#include <algorithm>
17
18	namespace Botan {
19
20	namespace {
21
22	class Prime_Sieve final {	462✔
23	public:
24	Prime_Sieve(const BigInt& init_value, size_t sieve_size, word step, bool check_2p1) :	462✔
25	m_sieve(std::min(sieve_size, PRIME_TABLE_SIZE)), m_step(step), m_check_2p1(check_2p1) {	462✔
26	for(size_t i = 0; i != m_sieve.size(); ++i)	401,309✔
27	m_sieve[i] = init_value % PRIMES[i];	400,847✔
28	}	462✔
29
30	size_t sieve_size() const { return m_sieve.size(); }
31
32	bool check_2p1() const { return m_check_2p1; }	1,027,988,179✔
33
34	bool next() {	882,822✔
35	auto passes = CT::Mask<word>::set();	882,822✔
36	for(size_t i = 0; i != m_sieve.size(); ++i) {	1,028,871,001✔
37	m_sieve[i] = (m_sieve[i] + m_step) % PRIMES[i];	1,027,988,179✔
38
39	// If m_sieve[i] == 0 then val % p == 0 -> not prime
40	passes &= CT::Mask<word>::expand(m_sieve[i]);	1,027,988,179✔
41
42	if(this->check_2p1()) {	1,027,988,179✔
43	/*
44	If v % p == (p-1)/2 then 2*v+1 == 0 (mod p)
45
46	So if potentially generating a safe prime, we want to
47	avoid this value because 2*v+1 will certainly not be prime.
48
49	See "Safe Prime Generation with a Combined Sieve" M. Wiener
50	https://eprint.iacr.org/2003/186.pdf
51	*/
52	passes &= ~CT::Mask<word>::is_equal(m_sieve[i], (PRIMES[i] - 1) / 2);	995,120,467✔
53	}
54	}
55
56	return passes.is_set();	882,822✔
57	}
58
59	private:
60	std::vector<word> m_sieve;
61	const word m_step;
62	const bool m_check_2p1;
63	};
64
65	#if defined(BOTAN_ENABLE_DEBUG_ASSERTS)
66
67	bool no_small_multiples(const BigInt& v, const Prime_Sieve& sieve) {
68	const size_t sieve_size = sieve.sieve_size();
69	const bool check_2p1 = sieve.check_2p1();
70
71	if(v.is_even())
72	return false;
73
74	const BigInt v_x2_p1 = 2 * v + 1;
75
76	for(size_t i = 0; i != sieve_size; ++i) {
77	if((v % PRIMES[i]) == 0)
78	return false;
79
80	if(check_2p1) {
81	if(v_x2_p1 % PRIMES[i] == 0)
82	return false;
83	}
84	}
85
86	return true;
87	}
88
89	#endif
90
91	}
92
93	/*
94	* Generate a random prime
95	*/
96	BigInt random_prime(	348✔
97	RandomNumberGenerator& rng, size_t bits, const BigInt& coprime, size_t equiv, size_t modulo, size_t prob) {
98	if(bits <= 1) {	348✔
99	throw Invalid_Argument("random_prime: Can't make a prime of " + std::to_string(bits) + " bits");	4✔
100	}
101	if(coprime.is_negative() \|\| (!coprime.is_zero() && coprime.is_even()) \|\| coprime.bits() >= bits) {	699✔
102	throw Invalid_Argument("random_prime: invalid coprime");	×
103	}
104	if(modulo == 0 \|\| modulo >= 100000) {	346✔
105	throw Invalid_Argument("random_prime: Invalid modulo value");	×
106	}
107
108	equiv %= modulo;	346✔
109
110	if(equiv == 0)	346✔
111	throw Invalid_Argument("random_prime Invalid value for equiv/modulo");	1✔
112
113	// Handle small values:
114
115	if(bits <= 16) {	345✔
116	if(equiv != 1 \|\| modulo != 2 \|\| coprime != 0)	30✔
117	throw Not_Implemented("random_prime equiv/modulo/coprime options not usable for small primes");	×
118
119	if(bits == 2) {	15✔
120	return BigInt::from_word(((rng.next_byte() % 2) ? 2 : 3));	1✔
121	} else if(bits == 3) {	14✔
122	return BigInt::from_word(((rng.next_byte() % 2) ? 5 : 7));	2✔
123	} else if(bits == 4) {	13✔
124	return BigInt::from_word(((rng.next_byte() % 2) ? 11 : 13));	2✔
125	} else {
126	for(;;) {	9,820✔
127	// This is slightly biased, but for small primes it does not seem to matter
128	uint8_t b[4];	4,916✔
129	rng.randomize(b, 4);	4,916✔
130	const size_t idx = load_le<uint32_t>(b, 0) % PRIME_TABLE_SIZE;	4,916✔
131	const uint16_t small_prime = PRIMES[idx];	4,916✔
132
133	if(high_bit(small_prime) == bits)	9,832✔
134	return BigInt::from_word(small_prime);	12✔
135	}	4,904✔
136	}
137	}
138
139	const size_t MAX_ATTEMPTS = 32 * 1024;	330✔
140
141	const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);	330✔
142
143	while(true) {	330✔
144	BigInt p(rng, bits);	330✔
145
146	// Force lowest and two top bits on
147	p.set_bit(bits - 1);	330✔
148	p.set_bit(bits - 2);	330✔
149	p.set_bit(0);	330✔
150
151	// Force p to be equal to equiv mod modulo
152	p += (modulo - (p % modulo)) + equiv;	330✔
153
154	Prime_Sieve sieve(p, bits, modulo, true);	330✔
155
156	for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt) {	844,057✔
157	p += modulo;	844,057✔
158
159	if(!sieve.next())	844,057✔
160	continue;	843,727✔
161
162	// here p can be even if modulo is odd, continue on in that case
163	if(p.is_even())	50,238✔
164	continue;	12,342✔
165
166	BOTAN_DEBUG_ASSERT(no_small_multiples(p, sieve));	12,777✔
167
168	Modular_Reducer mod_p(p);	12,777✔
169
170	if(coprime > 1) {	12,777✔
171	/*
172	First do a single M-R iteration to quickly elimate most non-primes,
173	before doing the coprimality check which is expensive
174	*/
175	if(is_miller_rabin_probable_prime(p, mod_p, rng, 1) == false)	99✔
176	continue;	93✔
177
178	/*
179	* Check if p - 1 and coprime are relatively prime, using gcd.
180	* The gcd computation is const-time
181	*/
182	if(gcd(p - 1, coprime) > 1)	24✔
183	continue;	×
184	}
185
186	if(p.bits() > bits)	12,684✔
187	break;
188
189	if(is_miller_rabin_probable_prime(p, mod_p, rng, mr_trials) == false)	12,684✔
190	continue;	12,354✔
191
192	if(prob > 32 && !is_lucas_probable_prime(p, mod_p))	330✔
193	continue;	×
194
195	return p;	330✔
196	}	12,777✔
197	}	330✔
198	}
199
200	BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng,	132✔
201	RandomNumberGenerator& prime_test_rng,
202	size_t bits,
203	const BigInt& coprime,
204	size_t prob) {
205	if(bits < 512)	132✔
206	throw Invalid_Argument("generate_rsa_prime bits too small");	×
207
208	/*
209	* The restriction on coprime <= 64 bits is arbitrary but generally speaking
210	* very large RSA public exponents are a bad idea both for performance and due
211	* to attacks on small d.
212	*/
213	if(coprime <= 1 \|\| coprime.is_even() \|\| coprime.bits() > 64)	264✔
214	throw Invalid_Argument("generate_rsa_prime coprime must be small odd positive integer");	×
215
216	const size_t MAX_ATTEMPTS = 32 * 1024;	132✔
217
218	const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);	132✔
219
220	while(true) {	132✔
221	BigInt p(keygen_rng, bits);	132✔
222
223	/*
224	Force high two bits so multiplication always results in expected n bit integer
225
226	Force the two low bits, and step by 4, so the generated prime is always == 3 (mod 4).
227	This way when we perform the inversion modulo phi(n) it is always of the form 2*o
228	with o odd, which allows a fastpath and avoids leaking any information about the
229	structure of the prime.
230	*/
231	p.set_bit(bits - 1);	132✔
232	p.set_bit(bits - 2);	132✔
233	p.set_bit(1);	132✔
234	p.set_bit(0);	132✔
235
236	const word step = 4;	132✔
237
238	Prime_Sieve sieve(p, bits, step, false);	132✔
239
240	for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt) {	38,765✔
241	p += step;	38,765✔
242
243	if(!sieve.next())	38,765✔
244	continue;	38,633✔
245
246	BOTAN_DEBUG_ASSERT(no_small_multiples(p, sieve));	5,030✔
247
248	Modular_Reducer mod_p(p);	5,030✔
249
250	/*
251	* Do a single primality test first before checking coprimality, since
252	* currently a single Miller-Rabin test is faster than computing gcd,
253	* and this eliminates almost all wasted gcd computations.
254	*/
255	if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, 1) == false)	5,030✔
256	continue;	4,898✔
257
258	/*
259	* Check if p - 1 and coprime are relatively prime.
260	*/
261	if(gcd(p - 1, coprime) > 1)	528✔
262	continue;	×
263
264	if(p.bits() > bits)	132✔
265	break;
266
267	if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, mr_trials) == true)	132✔
268	return p;	132✔
269	}	5,030✔
270	}	132✔
271	}
272
273	/*
274	* Generate a random safe prime
275	*/
276	BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits) {	8✔
277	if(bits <= 64)	8✔
278	throw Invalid_Argument("random_safe_prime: Can't make a prime of " + std::to_string(bits) + " bits");	×
279
280	const size_t error_bound = 128;	8✔
281
282	BigInt q, p;	8✔
283	for(;;) {	296✔
284	/*
285	Generate q == 2 (mod 3), since otherwise [in the case of q == 1 (mod 3)],
286	2*q+1 == 3 (mod 3) and so certainly not prime.
287	*/
288	q = random_prime(rng, bits - 1, BigInt::zero(), 2, 3, error_bound);	584✔
289	p = (q << 1) + 1;	880✔
290
291	if(is_prime(p, rng, error_bound, true)) {	296✔
292	return p;	8✔
293	}
294	}
295	}	8✔
296
297	}

randombit / botan / 5079590438

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