monotone

monotone Mtn Source Tree

Root/botan/dsa_gen.cpp

1/*************************************************
2* DSA Parameter Generation Source File *
3* (C) 1999-2007 The Botan Project *
4*************************************************/
5
6#include <botan/dl_group.h>
7#include <botan/numthry.h>
8#include <botan/libstate.h>
9#include <botan/lookup.h>
10#include <botan/parsing.h>
11#include <botan/rng.h>
12#include <algorithm>
13#include <memory>
14
15namespace Botan {
16
17namespace {
18
19/*************************************************
20* Check if this size is allowed by FIPS 186-3 *
21*************************************************/
22bool fips186_3_valid_size(u32bit pbits, u32bit qbits)
23 {
24 if(pbits == 1024 && qbits == 160)
25 return true;
26 if(pbits == 2048 && (qbits == 224 || qbits == 256))
27 return true;
28 if(pbits == 3072 && qbits == 256)
29 return true;
30 return false;
31 }
32
33}
34
35/*************************************************
36* Attempt DSA prime generation with given seed *
37*************************************************/
38bool DL_Group::generate_dsa_primes(BigInt& p, BigInt& q,
39 u32bit pbits, u32bit qbits,
40 const MemoryRegion<byte>& seed_c)
41 {
42 if(!fips186_3_valid_size(pbits, qbits))
43 throw Invalid_Argument(
44 "FIPS 186-3 does not allow DSA domain parameters of " +
45 to_string(pbits) + "/" + to_string(qbits) + " bits long");
46
47 if(qbits == 224)
48 throw Invalid_Argument(
49 "DSA parameter generation with a q of 224 bits not supported");
50
51 if(seed_c.size() * 8 < qbits)
52 throw Invalid_Argument(
53 "Generating a DSA parameter set with a " + to_string(qbits) +
54 "long q requires a seed at least as many bits long");
55
56 std::auto_ptr<HashFunction> hash(get_hash("SHA-" + to_string(qbits)));
57
58 const u32bit HASH_SIZE = hash->OUTPUT_LENGTH;
59
60 class Seed
61 {
62 public:
63 Seed(const MemoryRegion<byte>& s) : seed(s) {}
64
65 operator MemoryRegion<byte>& () { return seed; }
66
67 Seed& operator++()
68 {
69 for(u32bit j = seed.size(); j > 0; --j)
70 if(++seed[j-1])
71 break;
72 return (*this);
73 }
74 private:
75 SecureVector<byte> seed;
76 };
77
78 Seed seed(seed_c);
79
80 q.binary_decode(hash->process(seed));
81 q.set_bit(qbits-1);
82 q.set_bit(0);
83
84 if(!is_prime(q))
85 return false;
86
87 global_state().pulse(PRIME_FOUND);
88
89 const u32bit n = (pbits-1) / (HASH_SIZE * 8),
90 b = (pbits-1) % (HASH_SIZE * 8);
91
92 BigInt X;
93 SecureVector<byte> V(HASH_SIZE * (n+1));
94
95 for(u32bit j = 0; j != 4096; ++j)
96 {
97 global_state().pulse(PRIME_SEARCHING);
98
99 for(u32bit k = 0; k <= n; ++k)
100 {
101 ++seed;
102 hash->update(seed);
103 hash->final(V + HASH_SIZE * (n-k));
104 }
105
106 X.binary_decode(V + (HASH_SIZE - 1 - b/8),
107 V.size() - (HASH_SIZE - 1 - b/8));
108 X.set_bit(pbits-1);
109
110 p = X - (X % (2*q) - 1);
111
112 if(p.bits() == pbits && is_prime(p))
113 {
114 global_state().pulse(PRIME_FOUND);
115 return true;
116 }
117 }
118 return false;
119 }
120
121/*************************************************
122* Generate DSA Primes *
123*************************************************/
124SecureVector<byte> DL_Group::generate_dsa_primes(BigInt& p, BigInt& q,
125 u32bit pbits, u32bit qbits)
126 {
127 SecureVector<byte> seed(qbits/8);
128
129 while(true)
130 {
131 Global_RNG::randomize(seed, seed.size());
132 global_state().pulse(PRIME_SEARCHING);
133
134 if(generate_dsa_primes(p, q, pbits, qbits, seed))
135 return seed;
136 }
137 }
138
139}

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status