1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
/*
* DSA key generation.
*/
#include "misc.h"
#include "ssh.h"
#include "sshkeygen.h"
#include "mpint.h"
int dsa_generate(struct dsa_key *key, int bits, PrimeGenerationContext *pgc,
ProgressReceiver *prog)
{
/*
* Progress-reporting setup.
*
* DSA generation involves three potentially long jobs: inventing
* the small prime q, the large prime p, and finding an order-q
* element of the multiplicative group of p.
*
* The latter is done by finding an element whose order is
* _divisible_ by q and raising it to the power of (p-1)/q. Every
* element whose order is not divisible by q is a qth power of q
* distinct elements whose order _is_ divisible by q, so the
* probability of not finding a suitable element on the first try
* is in the region of 1/q, i.e. at most 2^-159.
*
* (So the probability of success will end up indistinguishable
* from 1 in IEEE standard floating point! But what can you do.)
*/
ProgressPhase phase_q = primegen_add_progress_phase(pgc, prog, 160);
ProgressPhase phase_p = primegen_add_progress_phase(pgc, prog, bits);
double g_failure_probability = 1.0
/ (double)(1ULL << 53)
/ (double)(1ULL << 53)
/ (double)(1ULL << 53);
ProgressPhase phase_g = progress_add_probabilistic(
prog, estimate_modexp_cost(bits), 1.0 - g_failure_probability);
progress_ready(prog);
PrimeCandidateSource *pcs;
/*
* Generate q: a prime of length 160.
*/
progress_start_phase(prog, phase_q);
pcs = pcs_new(160);
mp_int *q = primegen_generate(pgc, pcs, prog);
progress_report_phase_complete(prog);
/*
* Now generate p: a prime of length `bits', such that p-1 is
* divisible by q.
*/
progress_start_phase(prog, phase_p);
pcs = pcs_new(bits);
pcs_require_residue_1_mod_prime(pcs, q);
mp_int *p = primegen_generate(pgc, pcs, prog);
progress_report_phase_complete(prog);
/*
* Next we need g. Raise 2 to the power (p-1)/q modulo p, and
* if that comes out to one then try 3, then 4 and so on. As
* soon as we hit a non-unit (and non-zero!) one, that'll do
* for g.
*/
progress_start_phase(prog, phase_g);
mp_int *power = mp_div(p, q); /* this is floor(p/q) == (p-1)/q */
mp_int *h = mp_from_integer(2);
mp_int *g;
while (1) {
progress_report_attempt(prog);
g = mp_modpow(h, power, p);
if (mp_hs_integer(g, 2))
break; /* got one */
mp_free(g);
mp_add_integer_into(h, h, 1);
}
mp_free(h);
mp_free(power);
progress_report_phase_complete(prog);
/*
* Now we're nearly done. All we need now is our private key x,
* which should be a number between 1 and q-1 exclusive, and
* our public key y = g^x mod p.
*/
mp_int *two = mp_from_integer(2);
mp_int *qm1 = mp_copy(q);
mp_sub_integer_into(qm1, qm1, 1);
mp_int *x = mp_random_in_range(two, qm1);
mp_free(two);
mp_free(qm1);
key->sshk.vt = &ssh_dsa;
key->p = p;
key->q = q;
key->g = g;
key->x = x;
key->y = mp_modpow(key->g, key->x, key->p);
return 1;
}
|
