Botan
1.11.15
|
00001 /* 00002 * DSA Parameter 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/lookup.h> 00010 #include <botan/hash.h> 00011 #include <botan/parsing.h> 00012 #include <algorithm> 00013 00014 namespace Botan { 00015 00016 namespace { 00017 00018 /* 00019 * Check if this size is allowed by FIPS 186-3 00020 */ 00021 bool fips186_3_valid_size(size_t pbits, size_t qbits) 00022 { 00023 if(qbits == 160) 00024 return (pbits == 512 || pbits == 768 || pbits == 1024); 00025 00026 if(qbits == 224) 00027 return (pbits == 2048); 00028 00029 if(qbits == 256) 00030 return (pbits == 2048 || pbits == 3072); 00031 00032 return false; 00033 } 00034 00035 } 00036 00037 /* 00038 * Attempt DSA prime generation with given seed 00039 */ 00040 bool generate_dsa_primes(RandomNumberGenerator& rng, 00041 BigInt& p, BigInt& q, 00042 size_t pbits, size_t qbits, 00043 const std::vector<byte>& seed_c) 00044 { 00045 if(!fips186_3_valid_size(pbits, qbits)) 00046 throw Invalid_Argument( 00047 "FIPS 186-3 does not allow DSA domain parameters of " + 00048 std::to_string(pbits) + "/" + std::to_string(qbits) + " bits long"); 00049 00050 if(seed_c.size() * 8 < qbits) 00051 throw Invalid_Argument( 00052 "Generating a DSA parameter set with a " + std::to_string(qbits) + 00053 "long q requires a seed at least as many bits long"); 00054 00055 std::unique_ptr<HashFunction> hash(get_hash("SHA-" + std::to_string(qbits))); 00056 00057 const size_t HASH_SIZE = hash->output_length(); 00058 00059 class Seed 00060 { 00061 public: 00062 Seed(const std::vector<byte>& s) : seed(s) {} 00063 00064 operator std::vector<byte>& () { return seed; } 00065 00066 Seed& operator++() 00067 { 00068 for(size_t j = seed.size(); j > 0; --j) 00069 if(++seed[j-1]) 00070 break; 00071 return (*this); 00072 } 00073 private: 00074 std::vector<byte> seed; 00075 }; 00076 00077 Seed seed(seed_c); 00078 00079 q.binary_decode(hash->process(seed)); 00080 q.set_bit(qbits-1); 00081 q.set_bit(0); 00082 00083 if(!is_prime(q, rng)) 00084 return false; 00085 00086 const size_t n = (pbits-1) / (HASH_SIZE * 8), 00087 b = (pbits-1) % (HASH_SIZE * 8); 00088 00089 BigInt X; 00090 std::vector<byte> V(HASH_SIZE * (n+1)); 00091 00092 for(size_t j = 0; j != 4096; ++j) 00093 { 00094 for(size_t k = 0; k <= n; ++k) 00095 { 00096 ++seed; 00097 hash->update(seed); 00098 hash->final(&V[HASH_SIZE * (n-k)]); 00099 } 00100 00101 X.binary_decode(&V[HASH_SIZE - 1 - b/8], 00102 V.size() - (HASH_SIZE - 1 - b/8)); 00103 X.set_bit(pbits-1); 00104 00105 p = X - (X % (2*q) - 1); 00106 00107 if(p.bits() == pbits && is_prime(p, rng)) 00108 return true; 00109 } 00110 return false; 00111 } 00112 00113 /* 00114 * Generate DSA Primes 00115 */ 00116 std::vector<byte> generate_dsa_primes(RandomNumberGenerator& rng, 00117 BigInt& p, BigInt& q, 00118 size_t pbits, size_t qbits) 00119 { 00120 while(true) 00121 { 00122 std::vector<byte> seed(qbits / 8); 00123 rng.randomize(&seed[0], seed.size()); 00124 00125 if(generate_dsa_primes(rng, p, q, pbits, qbits, seed)) 00126 return seed; 00127 } 00128 } 00129 00130 }