monotone

monotone Mtn Source Tree

Root/botan/make_prm.cpp

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

Archive Download this file

Branches

Tags

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