monotone

monotone Mtn Source Tree

Root/botan/make_prm.cpp

1/*************************************************
2* Prime Generation Source File *
3* (C) 1999-2006 The Botan Project *
4*************************************************/
5
6#include <botan/numthry.h>
7#include <botan/libstate.h>
8#include <botan/lookup.h>
9#include <botan/bit_ops.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* Increment the seed by one *
21*************************************************/
22void increment(SecureVector<byte>& seed)
23 {
24 for(u32bit j = seed.size(); j > 0; --j)
25 if(++seed[j-1])
26 break;
27 }
28
29}
30
31/*************************************************
32* Attempt DSA prime generation with given seed *
33*************************************************/
34bool generate_dsa_primes(BigInt& p, BigInt& q, const byte const_seed[],
35 u32bit seed_len, u32bit pbits, u32bit counter_start)
36 {
37 if(seed_len < 20)
38 throw Invalid_Argument("DSA prime generation needs a seed "
39 "at least 160 bits long");
40 if((pbits % 64 != 0) || (pbits > 1024) || (pbits < 512))
41 throw Invalid_Argument("DSA prime generation algorithm does not support "
42 "prime size " + to_string(pbits));
43
44 std::auto_ptr<HashFunction> sha1(get_hash("SHA-1"));
45
46 SecureVector<byte> seed(const_seed, seed_len);
47
48 SecureVector<byte> qhash = sha1->process(seed);
49 increment(seed);
50 SecureVector<byte> qhash2 = sha1->process(seed);
51 xor_buf(qhash, qhash2, qhash.size());
52
53 qhash[0] |= 0x80;
54 qhash[19] |= 0x01;
55 q.binary_decode(qhash, qhash.size());
56 if(!is_prime(q))
57 return false;
58 global_state().pulse(PRIME_FOUND);
59
60 u32bit n = (pbits-1) / 160, b = (pbits-1) % 160;
61 SecureVector<byte> W(20 * (n+1));
62 BigInt X;
63
64 for(u32bit j = 0; j != counter_start; ++j)
65 for(u32bit k = 0; k != n + 1; ++k)
66 increment(seed);
67
68 for(u32bit j = 0; j != 4096 - counter_start; ++j)
69 {
70 global_state().pulse(PRIME_SEARCHING);
71
72 for(u32bit k = 0; k != n + 1; ++k)
73 {
74 increment(seed);
75 sha1->update(seed);
76 sha1->final(W + 20 * (n-k));
77 }
78 X.binary_decode(W + (20 - 1 - b/8), W.size() - (20 - 1 - b/8));
79 X.set_bit(pbits-1);
80
81 p = X - (X % (2*q) - 1);
82
83 if(p.bits() == pbits && is_prime(p))
84 {
85 global_state().pulse(PRIME_FOUND);
86 return true;
87 }
88 }
89 return false;
90 }
91
92/*************************************************
93* Generate DSA Primes *
94*************************************************/
95SecureVector<byte> generate_dsa_primes(BigInt& p, BigInt& q, u32bit pbits)
96 {
97 SecureVector<byte> seed(20);
98
99 while(true)
100 {
101 Global_RNG::randomize(seed, seed.size());
102 global_state().pulse(PRIME_SEARCHING);
103 if(generate_dsa_primes(p, q, seed, seed.size(), pbits))
104 return seed;
105 }
106 }
107
108/*************************************************
109* Generate a random prime *
110*************************************************/
111BigInt random_prime(u32bit bits, const BigInt& coprime,
112 u32bit equiv, u32bit modulo)
113 {
114 if(bits < 48)
115 throw Invalid_Argument("random_prime: Can't make a prime of " +
116 to_string(bits) + " bits");
117
118 if(coprime <= 0)
119 throw Invalid_Argument("random_prime: coprime must be > 0");
120 if(modulo % 2 == 1 || modulo == 0)
121 throw Invalid_Argument("random_prime: Invalid modulo value");
122 if(equiv >= modulo || equiv % 2 == 0)
123 throw Invalid_Argument("random_prime: equiv must be < modulo, and odd");
124
125 while(true)
126 {
127 global_state().pulse(PRIME_SEARCHING);
128
129 BigInt p = random_integer(bits);
130 p.set_bit(bits - 2);
131 p.set_bit(0);
132
133 if(p % modulo != equiv)
134 p += (modulo - p % modulo) + equiv;
135
136 const u32bit sieve_size = std::min(bits / 2, PRIME_TABLE_SIZE);
137 SecureVector<u32bit> sieve(sieve_size);
138
139 for(u32bit j = 0; j != sieve.size(); ++j)
140 {
141 sieve[j] = p % PRIMES[j];
142 global_state().pulse(PRIME_SIEVING);
143 }
144
145 u32bit counter = 0;
146 while(true)
147 {
148 if(counter == 4096 || p.bits() > bits)
149 break;
150
151 global_state().pulse(PRIME_SEARCHING);
152
153 bool passes_sieve = true;
154 ++counter;
155 p += modulo;
156
157 for(u32bit j = 0; j != sieve.size(); ++j)
158 {
159 sieve[j] = (sieve[j] + modulo) % PRIMES[j];
160 global_state().pulse(PRIME_SIEVING);
161 if(sieve[j] == 0)
162 passes_sieve = false;
163 }
164
165 if(!passes_sieve || gcd(p - 1, coprime) != 1)
166 continue;
167 global_state().pulse(PRIME_PASSED_SIEVE);
168 if(passes_mr_tests(p))
169 {
170 global_state().pulse(PRIME_FOUND);
171 return p;
172 }
173 }
174 }
175 }
176
177}

Archive Download this file

Branches

Tags

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