4805055462

Committed 26 Apr 2023 05:37AM UTC coverage: 92.146% (-0.002%) from 92.148%

Build # 4805055462

Build Type

push

github

Run Details

77579 of 84191 relevant lines covered (92.15%)

11871996.41 hits per line

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

91.38

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

randombit / botan / 4805055462

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