3 * Generate Diffie-Hellman parameters
5 * (c) 1999 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
28 /*----- Header files ------------------------------------------------------*/
30 #include <mLib/macros.h>
42 /*----- Main code ---------------------------------------------------------*/
46 * Arguments: @dh_param *dp@ = pointer to output parameter block
47 * @unsigned ql@ = length of %$q$% in bits, or zero
48 * @unsigned pl@ = length of %$p$% in bits
49 * @unsigned steps@ = number of steps to go
50 * @grand *r@ = random number source
51 * @pgen_proc *event@ = event handler function
52 * @void *ectx@ = argument for the event handler
54 * Returns: @PGEN_DONE@ if it worked, @PGEN_ABORT@ if it didn't.
56 * Use: Generates Diffie-Hellman parameters.
58 * The parameters are a prime %$q$%, relatively small, and a
59 * large prime %$p = kq + 1$% for some %$k$%, together with a
60 * generator %$g$% of the cyclic subgroup of order %$q$%. These
61 * are actually the same as the DSA parameter set, but the
62 * generation algorithm is different. Also, if @ql@ is zero,
63 * this algorithm forces %$k = 2$%, and chooses %$g = 4$%. Make
64 * sure you have something interesting to do if you choose this
68 int dh_gen(dh_param
*dp
, unsigned ql
, unsigned pl
, unsigned steps
, grand
*r
,
69 pgen_proc
*event
, void *ectx
)
71 /* --- If @ql@ is zero, do the time consuming safe-prime thing --- */
74 pgen_simulprime sp
[2];
77 mp
*m
= mprand(MP_NEW
, pl
- 1, r
, 1);
79 sp
[0].mul
= MP_ONE
; sp
[0].add
= MP_ZERO
; sp
[0].f
= 0;
80 sp
[1].mul
= MP_TWO
; sp
[1].add
= MP_ONE
; sp
[1].f
= PGENF_KEEP
;
81 ss
.v
= sp
; ss
.n
= N(sp
);
82 dp
->q
= pgen("p", MP_NEW
, m
, event
, ectx
, steps
, pgen_simulstep
, &ss
,
83 rabin_iters(pl
), pgen_simultest
, &ss
);
94 /* --- Otherwise the job is much simpler --- *
96 * But doesn't look it...
108 /* --- Generate @q@ first --- */
111 m
= mprand(MP_NEW
, ql
, r
, 1);
112 dp
->q
= pgen("q", MP_NEW
, m
, event
, ectx
, steps
, pgen_filter
, &c
,
113 rabin_iters(ql
), pgen_test
, &rb
);
117 /* --- Now pick a suitable @p@ --- */
119 m
= mp_lsl(m
, dp
->q
, 1);
120 x
= mprand(MP_NEW
, pl
, r
, 0);
121 y
= MP_NEW
; mp_div(0, &y
, x
, m
);
123 x
= mp_add(x
, x
, MP_ONE
);
125 pfilt_create(&c
.f
, m
);
127 dp
->p
= pgen("p", MP_NEW
, x
, event
, ectx
, steps
, pgen_jump
, &j
,
128 rabin_iters(pl
), pgen_test
, &rb
);
134 /* --- And finally a suitable @g@ --- */
136 mpmont_create(&p
.mm
, dp
->p
);
137 mp_div(&m
, 0, dp
->p
, dp
->q
);
141 dp
->g
= pgen("g", MP_NEW
, MP_NEW
, event
, ectx
, 0, prim_step
, &i
,
143 mpmont_destroy(&p
.mm
);
149 /* --- Tidy up --- */
161 /*----- That's all, folks -------------------------------------------------*/