3 * $Id: dh-gen.c,v 1.2 2000/07/29 10:01:58 mdw Exp $
5 * Generate Diffie-Hellman parameters
7 * (c) 1999 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
14 * Catacomb is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU Library General Public License as
16 * published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
19 * Catacomb is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU Library General Public License for more details.
24 * You should have received a copy of the GNU Library General Public
25 * License along with Catacomb; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
30 /*----- Revision history --------------------------------------------------*
33 * Revision 1.2 2000/07/29 10:01:58 mdw
34 * Track change in primitive-element generation.
36 * Revision 1.1 2000/02/12 18:21:02 mdw
37 * Overhaul of key management (again).
41 /*----- Header files ------------------------------------------------------*/
53 /*----- Main code ---------------------------------------------------------*/
57 * Arguments: @dh_param *dp@ = pointer to output parameter block
58 * @unsigned ql@ = length of %$q$% in bits, or zero
59 * @unsigned pl@ = length of %$p$% in bits
60 * @unsigned steps@ = number of steps to go
61 * @grand *r@ = random number source
62 * @pgen_proc *event@ = event handler function
63 * @void *ectx@ = argument for the event handler
65 * Returns: @PGEN_DONE@ if it worked, @PGEN_ABORT@ if it didn't.
67 * Use: Generates Diffie-Hellman parameters.
69 * The parameters are a prime %$q$%, relatively small, and a
70 * large prime %$p = kq + 1$% for some %$k$%, together with a
71 * generator %$g$% of the cyclic subgroup of order %$q$%. These
72 * are actually the same as the DSA parameter set, but the
73 * generation algorithm is different. Also, if @ql@ is zero,
74 * this algorithm forces %$k = 2$%, and chooses %$g = 4$%. Make
75 * sure you have something interesting to do if you choose this
79 int dh_gen(dh_param
*dp
, unsigned ql
, unsigned pl
, unsigned steps
, grand
*r
,
80 pgen_proc
*event
, void *ectx
)
82 /* --- If @ql@ is zero, do the time consuming safe-prime thing --- */
87 mp
*m
= mprand(MP_NEW
, pl
, r
, 3);
88 dp
->p
= pgen("p", MP_NEW
, m
, event
, ectx
, steps
, pgen_safestep
, &c
.c
,
89 rabin_iters(pl
), pgen_safetest
, &c
);
93 dp
->q
= mp_lsr(MP_NEW
, dp
->p
, 1);
98 /* --- Otherwise the job is much simpler --- *
100 * But doesn't look it...
112 /* --- Generate @q@ first --- */
115 m
= mprand(MP_NEW
, ql
, r
, 1);
116 dp
->q
= pgen("q", MP_NEW
, m
, event
, ectx
, steps
, pgen_filter
, &c
,
117 rabin_iters(ql
), pgen_test
, &rb
);
121 /* --- Now pick a suitable @p@ --- */
123 m
= mp_lsl(m
, dp
->q
, 1);
124 x
= mprand(MP_NEW
, pl
, r
, 0);
125 y
= MP_NEW
; mp_div(0, &y
, x
, m
);
127 x
= mp_add(x
, x
, MP_ONE
);
129 pfilt_create(&c
.f
, m
);
131 dp
->p
= pgen("p", MP_NEW
, x
, event
, ectx
, steps
, pgen_jump
, &j
,
132 rabin_iters(pl
), pgen_test
, &rb
);
138 /* --- And finally a suitable @g@ --- */
140 mpmont_create(&p
.mm
, dp
->p
);
141 mp_div(&m
, 0, dp
->p
, dp
->q
);
145 dp
->g
= pgen("g", MP_NEW
, MP_NEW
, event
, ectx
, 0, prim_step
, &i
,
147 mpmont_destroy(&p
.mm
);
153 /* --- Tidy up --- */
165 /*----- That's all, folks -------------------------------------------------*/