3 * Generate DSA shared 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 ------------------------------------------------------*/
42 /*----- The DSA stepper ---------------------------------------------------*/
46 * Arguments: @pgen_event *ev@ = pointer to event block
47 * @dsa_stepctx *d@ = pointer to stepping context
49 * Returns: A @PGEN@ result code.
51 * Use: Steps the generator once, reads the result, and tests it.
54 static int next(pgen_event
*ev
, dsa_stepctx
*d
)
59 /* --- Load the new candidate --- */
62 d
->r
->ops
->misc(d
->r
, DSARAND_GETSEED
, d
->seedbuf
);
63 m
= mprand(ev
->m
, d
->bits
, d
->r
, 0);
65 /* --- Force to be a multiple of @q@ --- */
69 mp_div(0, &r
, m
, d
->q
);
76 /* --- Do the trial division --- */
78 rc
= pfilt_smallfactor(m
);
81 /* --- Return the result --- */
86 /* --- @dsa_step@ --- */
88 int dsa_step(int rq
, pgen_event
*ev
, void *p
)
102 /*----- Glue code ---------------------------------------------------------*/
104 /* --- @dsa_gen@ --- *
106 * Arguments: @dsa_param *dp@ = where to store parameters
107 * @unsigned ql@ = length of @q@ in bits
108 * @unsigned pl@ = length of @p@ in bits
109 * @unsigned steps@ = number of steps to find @q@
110 * @const void *k@ = pointer to key material
111 * @size_t sz@ = size of key material
112 * @dsa_seed *ds@ = optional pointer for output seed information
113 * @pgen_proc *event@ = event handler function
114 * @void *ectx@ = argument for event handler
116 * Returns: @PGEN_DONE@ if everything worked ok; @PGEN_ABORT@ otherwise.
118 * Use: Generates the DSA shared parameters from a given seed value.
120 * The parameters are a prime %$q$%, relatively small, and a
121 * large prime %$p = kq + 1$% for some %$k$%, together with a
122 * generator %$g$% of the cyclic subgroup of order %$q$%. These
123 * are actually the same as the Diffie-Hellman parameter set,
124 * but the generation algorithm is different.
126 * The algorithm used is a compatible extension of the method
127 * described in the DSA standard, FIPS 186. The standard
128 * requires that %$q$% be 160 bits in size (i.e., @ql == 160@)
129 * and that the length of %$p$% be %$L = 512 + 64l$% for some
130 * %$l$%. Neither limitation applies to this implementation.
133 int dsa_gen(dsa_param
*dp
, unsigned ql
, unsigned pl
, unsigned steps
,
134 const void *k
, size_t sz
, dsa_seed
*ds
,
135 pgen_proc
*event
, void *ectx
)
143 /* --- Initialize the stepping context --- */
145 s
.r
= dsarand_create(k
, sz
);
147 /* --- Find @q@ --- */
150 s
.r
->ops
->misc(s
.r
, DSARAND_PASSES
, 2);
158 ds
->p
= s
.seedbuf
= xmalloc(sz
);
160 if ((dp
->q
= pgen("q", MP_NEW
, MP_NEW
, event
, ectx
, steps
, dsa_step
, &s
,
161 rabin_iters(ql
), pgen_test
, &r
)) == 0)
164 /* --- Find @p@ --- */
167 s
.q
= mp_lsl(MP_NEW
, dp
->q
, 1);
168 s
.r
->ops
->misc(s
.r
, DSARAND_PASSES
, 1);
171 if ((dp
->p
= pgen("p", MP_NEW
, MP_NEW
, event
, ectx
, 4096, dsa_step
, &s
,
172 rabin_iters(pl
), pgen_test
, &r
)) == 0)
178 /* --- Find @g@ --- *
180 * The division returns remainder 1. This doesn't matter.
183 mpmont_create(&p
.mm
, dp
->p
);
184 qc
= MP_NEW
; mp_div(&qc
, 0, dp
->p
, dp
->q
);
188 if ((dp
->g
= pgen("g", MP_NEW
, MP_NEW
, event
, ectx
, 0, prim_step
, &i
,
189 1, prim_test
, &p
)) == 0)
195 mpmont_destroy(&p
.mm
);
196 s
.r
->ops
->destroy(s
.r
);
199 /* --- Tidy up when things go wrong --- */
203 mpmont_destroy(&p
.mm
);
208 s
.r
->ops
->destroy(s
.r
);
214 /*----- Test rig ----------------------------------------------------------*/
218 static int verify(dstr
*v
)
220 mp
*q
= *(mp
**)v
[4].buf
;
221 mp
*p
= *(mp
**)v
[5].buf
;
222 mp
*g
= *(mp
**)v
[6].buf
;
225 unsigned long l
= *(unsigned long *)v
[1].buf
;
226 unsigned long n
= *(unsigned long *)v
[3].buf
;
230 keycheck_reportctx kcr
;
232 rc
= dsa_gen(&dp
, 160, l
, 16, v
[0].buf
, v
[0].len
, &ds
, pgen_evspin
, 0);
233 if (rc
|| ds
.count
!= n
|| ds
.sz
!= v
[2].len
||
234 memcmp(ds
.p
, v
[2].buf
, v
[2].len
) != 0 ||
235 !MP_EQ(q
, dp
.q
) || !MP_EQ(p
, dp
.p
) || !MP_EQ(g
, dp
.g
)) {
236 fputs("\n*** gen failed", stderr
);
237 fputs("\nseed_in = ", stderr
); type_hex
.dump(&v
[0], stderr
);
238 fprintf(stderr
, "\nl = %lu", l
);
239 fputs("\nseed_out = ", stderr
); type_hex
.dump(&v
[2], stderr
);
240 fprintf(stderr
, "\ncount = %lu", n
);
241 fputs("\n q = ", stderr
); mp_writefile(q
, stderr
, 16);
242 fputs("\n p = ", stderr
); mp_writefile(p
, stderr
, 16);
243 fputs("\n g = ", stderr
); mp_writefile(g
, stderr
, 16);
246 d
.buf
= ds
.p
; d
.len
= ds
.sz
;
247 fputs("\nds.seed = ", stderr
); type_hex
.dump(&d
, stderr
);
248 fprintf(stderr
, "\nds.count = %u", ds
.count
);
249 fputs("\ndp.q = ", stderr
); mp_writefile(dp
.q
, stderr
, 16);
250 fputs("\ndp.p = ", stderr
); mp_writefile(dp
.p
, stderr
, 16);
251 fputs("\ndp.g = ", stderr
); mp_writefile(dp
.g
, stderr
, 16);
259 keycheck_init(&kc
, keycheck_stdreport
, &kcr
);
261 dsa_checkparam(&kc
, &dp
, &ds
);
262 if (!keycheck_allclear(&kc
, KCSEV_ERR
)) {
263 fputs("\n*** gen failed check", stderr
);
264 fputs("\nseed_in = ", stderr
); type_hex
.dump(&v
[0], stderr
);
265 fprintf(stderr
, "\nl = %lu", l
);
266 fputs("\nseed_out = ", stderr
); type_hex
.dump(&v
[2], stderr
);
267 fprintf(stderr
, "\ncount = %lu", n
);
268 fputs("\n q = ", stderr
); mp_writefile(q
, stderr
, 16);
269 fputs("\n p = ", stderr
); mp_writefile(p
, stderr
, 16);
270 fputs("\n g = ", stderr
); mp_writefile(g
, stderr
, 16);
275 mp_drop(q
); mp_drop(p
); mp_drop(g
);
277 mp_drop(dp
.q
); mp_drop(dp
.p
); mp_drop(dp
.g
); xfree(ds
.p
);
279 assert(mparena_count(MPARENA_GLOBAL
) == 0);
283 static test_chunk tests
[] = {
285 { &type_hex
, &type_ulong
, &type_hex
, &type_ulong
,
286 &type_mp
, &type_mp
, &type_mp
, 0 } },
290 int main(int argc
, char *argv
[])
293 test_run(argc
, argv
, tests
, SRCDIR
"/t/dsa");
299 /*----- That's all, folks -------------------------------------------------*/