Botan  1.11.15
src/lib/math/numbertheory/dsa_gen.cpp
Go to the documentation of this file.
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 }