Botan
1.11.15
|
00001 /* 00002 * Prime Generation 00003 * (C) 1999-2007 Jack Lloyd 00004 * 00005 * Botan is released under the Simplified BSD License (see license.txt) 00006 */ 00007 00008 #include <botan/numthry.h> 00009 #include <botan/parsing.h> 00010 #include <algorithm> 00011 00012 namespace Botan { 00013 00014 /* 00015 * Generate a random prime 00016 */ 00017 BigInt random_prime(RandomNumberGenerator& rng, 00018 size_t bits, const BigInt& coprime, 00019 size_t equiv, size_t modulo) 00020 { 00021 if(bits <= 1) 00022 throw Invalid_Argument("random_prime: Can't make a prime of " + 00023 std::to_string(bits) + " bits"); 00024 else if(bits == 2) 00025 return ((rng.next_byte() % 2) ? 2 : 3); 00026 else if(bits == 3) 00027 return ((rng.next_byte() % 2) ? 5 : 7); 00028 else if(bits == 4) 00029 return ((rng.next_byte() % 2) ? 11 : 13); 00030 00031 if(coprime <= 0) 00032 throw Invalid_Argument("random_prime: coprime must be > 0"); 00033 if(modulo % 2 == 1 || modulo == 0) 00034 throw Invalid_Argument("random_prime: Invalid modulo value"); 00035 if(equiv >= modulo || equiv % 2 == 0) 00036 throw Invalid_Argument("random_prime: equiv must be < modulo, and odd"); 00037 00038 while(true) 00039 { 00040 BigInt p(rng, bits); 00041 00042 // Force lowest and two top bits on 00043 p.set_bit(bits - 1); 00044 p.set_bit(bits - 2); 00045 p.set_bit(0); 00046 00047 if(p % modulo != equiv) 00048 p += (modulo - p % modulo) + equiv; 00049 00050 const size_t sieve_size = std::min(bits / 2, PRIME_TABLE_SIZE); 00051 secure_vector<u16bit> sieve(sieve_size); 00052 00053 for(size_t j = 0; j != sieve.size(); ++j) 00054 sieve[j] = p % PRIMES[j]; 00055 00056 size_t counter = 0; 00057 while(true) 00058 { 00059 if(counter == 4096 || p.bits() > bits) 00060 break; 00061 00062 bool passes_sieve = true; 00063 ++counter; 00064 p += modulo; 00065 00066 if(p.bits() > bits) 00067 break; 00068 00069 for(size_t j = 0; j != sieve.size(); ++j) 00070 { 00071 sieve[j] = (sieve[j] + modulo) % PRIMES[j]; 00072 if(sieve[j] == 0) 00073 passes_sieve = false; 00074 } 00075 00076 if(!passes_sieve || gcd(p - 1, coprime) != 1) 00077 continue; 00078 if(is_prime(p, rng, 64, true)) 00079 return p; 00080 } 00081 } 00082 } 00083 00084 /* 00085 * Generate a random safe prime 00086 */ 00087 BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits) 00088 { 00089 if(bits <= 64) 00090 throw Invalid_Argument("random_safe_prime: Can't make a prime of " + 00091 std::to_string(bits) + " bits"); 00092 00093 BigInt p; 00094 do 00095 p = (random_prime(rng, bits - 1) << 1) + 1; 00096 while(!is_prime(p, rng, 64, true)); 00097 return p; 00098 } 00099 00100 }