3 * $Id: dsa-gen.c,v 1.7 2000/08/15 21:45:05 mdw Exp $
5 * Generate DSA shared 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.7 2000/08/15 21:45:05 mdw
34 * Use the new trial division equipment in pfilt. This gives a 10%
35 * performance improvement in dsa-gen.t.
37 * Revision 1.6 2000/07/29 10:00:14 mdw
38 * Rename `dsa_seed' to `dsa_gen' for consistency with other parameter-
39 * generation interfaces.
41 * Revision 1.5 2000/02/12 18:21:02 mdw
42 * Overhaul of key management (again).
44 * Revision 1.4 1999/12/22 15:52:44 mdw
45 * Reworking for new prime-search system.
47 * Revision 1.3 1999/12/10 23:18:38 mdw
48 * Change interface for suggested destinations.
50 * Revision 1.2 1999/11/20 22:23:48 mdw
51 * Allow event handler to abort the search process.
53 * Revision 1.1 1999/11/19 19:28:00 mdw
54 * Implementation of the Digital Signature Algorithm.
58 /*----- Header files ------------------------------------------------------*/
70 #include "primorial.h"
73 /*----- The DSA stepper ---------------------------------------------------*/
77 * Arguments: @pgen_event *ev@ = pointer to event block
78 * @dsa_stepctx *d@ = pointer to stepping context
80 * Returns: A @PGEN@ result code.
82 * Use: Steps the generator once, reads the result, and tests it.
85 static int next(pgen_event
*ev
, dsa_stepctx
*d
)
90 /* --- Load the new candidate --- */
92 m
= mprand(ev
->m
, d
->bits
, d
->r
, d
->or);
94 /* --- Force to be a multiple of @q@ --- */
98 mp_div(0, &r
, m
, d
->q
);
105 /* --- Do the trial division --- */
107 rc
= pfilt_smallfactor(m
);
109 /* --- Return the result --- */
114 /* --- @dsa_step@ --- */
116 int dsa_step(int rq
, pgen_event
*ev
, void *p
)
124 return (next(ev
, d
));
131 /*----- Glue code ---------------------------------------------------------*/
133 /* --- @dsa_gen@ --- *
135 * Arguments: @dsa_param *dp@ = where to store parameters
136 * @unsigned ql@ = length of @q@ in bits
137 * @unsigned pl@ = length of @p@ in bits
138 * @unsigned steps@ = number of steps to find @q@
139 * @const void *k@ = pointer to key material
140 * @size_t sz@ = size of key material
141 * @pgen_proc *event@ = event handler function
142 * @void *ectx@ = argument for event handler
144 * Returns: @PGEN_DONE@ if everything worked ok; @PGEN_ABORT@ otherwise.
146 * Use: Generates the DSA shared parameters from a given seed value.
148 * The parameters are a prime %$q$%, relatively small, and a
149 * large prime %$p = kq + 1$% for some %$k$%, together with a
150 * generator %$g$% of the cyclic subgroup of order %$q$%. These
151 * are actually the same as the Diffie-Hellman parameter set,
152 * but the generation algorithm is different.
154 * The algorithm used is a compatible extension of the method
155 * described in the DSA standard, FIPS 186. The standard
156 * requires that %$q$% be 160 bits in size (i.e., @ql == 160@)
157 * and that the length of %$p$% be %$L = 512 + 64l$% for some
158 * %$l$%. Neither limitation applies to this implementation.
161 int dsa_gen(dsa_param
*dp
, unsigned ql
, unsigned pl
, unsigned steps
,
162 const void *k
, size_t sz
, pgen_proc
*event
, void *ectx
)
170 /* --- Initialize the stepping context --- */
172 s
.r
= dsarand_create(k
, sz
);
175 /* --- Find @q@ --- */
178 s
.r
->ops
->misc(s
.r
, DSARAND_PASSES
, 2);
180 if ((dp
->q
= pgen("q", MP_NEW
, MP_NEW
, event
, ectx
, steps
, dsa_step
, &s
,
181 rabin_iters(ql
), pgen_test
, &r
)) == 0)
184 /* --- Find @p@ --- */
186 s
.q
= mp_lsl(MP_NEW
, dp
->q
, 1);
187 s
.r
->ops
->misc(s
.r
, DSARAND_PASSES
, 1);
189 if ((dp
->p
= pgen("p", MP_NEW
, MP_NEW
, event
, ectx
, 4096, dsa_step
, &s
,
190 rabin_iters(pl
), pgen_test
, &r
)) == 0)
194 /* --- Find @g@ --- *
196 * The division returns remainder 1. This doesn't matter.
199 mpmont_create(&p
.mm
, dp
->p
);
200 qc
= MP_NEW
; mp_div(&qc
, 0, dp
->p
, dp
->q
);
204 if ((dp
->g
= pgen("g", MP_NEW
, MP_NEW
, event
, ectx
, 0, prim_step
, &i
,
205 1, prim_test
, &p
)) == 0)
211 mpmont_destroy(&p
.mm
);
212 s
.r
->ops
->destroy(s
.r
);
215 /* --- Tidy up when things go wrong --- */
219 mpmont_destroy(&p
.mm
);
224 s
.r
->ops
->destroy(s
.r
);
228 /*----- Test rig ----------------------------------------------------------*/
232 static int verify(dstr
*v
)
234 mp
*q
= *(mp
**)v
[2].buf
;
235 mp
*p
= *(mp
**)v
[3].buf
;
236 mp
*g
= *(mp
**)v
[4].buf
;
238 unsigned l
= *(unsigned *)v
[1].buf
;
242 rc
= dsa_gen(&dp
, 160, l
, 1, v
[0].buf
, v
[0].len
, pgen_evspin
, 0);
243 if (rc
|| MP_CMP(q
, !=, dp
.q
) ||
244 MP_CMP(p
, !=, dp
.p
) || MP_CMP(g
, !=, dp
.g
)) {
245 fputs("\n*** gen failed", stderr
);
246 fputs("\nseed = ", stderr
); type_hex
.dump(&v
[0], stderr
);
247 fprintf(stderr
, "\nl = %u", l
);
248 fputs("\n q = ", stderr
); mp_writefile(q
, stderr
, 16);
249 fputs("\n p = ", stderr
); mp_writefile(p
, stderr
, 16);
250 fputs("\n g = ", stderr
); mp_writefile(g
, stderr
, 16);
252 fputs("\ndp.q = ", stderr
); mp_writefile(dp
.q
, stderr
, 16);
253 fputs("\ndp.p = ", stderr
); mp_writefile(dp
.p
, stderr
, 16);
254 fputs("\ndp.g = ", stderr
); mp_writefile(dp
.g
, stderr
, 16);
260 mp_drop(q
); mp_drop(p
); mp_drop(g
);
262 mp_drop(dp
.q
); mp_drop(dp
.p
); mp_drop(dp
.g
);
264 assert(mparena_count(MPARENA_GLOBAL
) == 0);
268 static test_chunk tests
[] = {
270 { &type_hex
, &type_int
, &type_mp
, &type_mp
, &type_mp
, 0 } },
274 int main(int argc
, char *argv
[])
277 test_run(argc
, argv
, tests
, SRCDIR
"/tests/dsa");
283 /*----- That's all, folks -------------------------------------------------*/