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 -------------------------------------------------*/