3 * $Id: dsa-gen.c,v 1.3 1999/12/10 23:18:38 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.3 1999/12/10 23:18:38 mdw
34 * Change interface for suggested destinations.
36 * Revision 1.2 1999/11/20 22:23:48 mdw
37 * Allow event handler to abort the search process.
39 * Revision 1.1 1999/11/19 19:28:00 mdw
40 * Implementation of the Digital Signature Algorithm.
44 /*----- Header files ------------------------------------------------------*/
57 /*----- Main code ---------------------------------------------------------*/
59 /* --- @dsa_seed@ --- *
61 * Arguments: @dsa_param *dp@ = where to store parameters
62 * @unsigned l@ = bitlength of @p@ in bits
63 * @const void *k@ = pointer to key material
64 * @size_t sz@ = size of key material
65 * @int (*proc)(int ev, mp *m, void *p)@ = event procedure
67 * Returns: Zero if all went well, nonzero if key material was
68 * unsuitable (one of the @DSAEV@ codes).
70 * Use: Generates the DSA shared parameters from a given seed value.
71 * This can take quite a long time. The size of @p@ in bits is
72 * %$l = 512 + 64l'$%. The DSA standard, FIPS 186, only allows
73 * %$0 \le l' \le 8$%. This implementation has no such limit,
74 * although @l@ must be a multiple of 8.
76 * The event procedure is informed of various happenings during
77 * generation. It is passed an event code describing what
78 * happened, and a multiprecision number which pertains to the
79 * event code. It may abort the search at any time by returning
80 * a nonzero value, which is returned as the result of the
84 int dsa_seed(dsa_param
*dp
, unsigned l
, const void *k
, size_t sz
,
85 int (*proc
)(int /*ev*/, mp */
*m*/
, void */
*p*/
), void *arg
)
88 mp
*s
= mp_loadb(MP_NEW
, k
, sz
);
89 octet
*sbuf
= xmalloc(sz
);
94 gr
= fibrand_create(LOAD32(k
));
96 /* --- Generate @q@ --- */
99 octet xbuf
[SHA_HASHSZ
], ybuf
[SHA_HASHSZ
];
107 mpx_uaddn(s
->v
, s
->vl
, 1);
108 mp_storeb(s
, sbuf
, sz
);
110 sha_hash(&c
, sbuf
, sz
);
113 for (i
= 0; i
< sizeof(xbuf
); i
++)
116 xbuf
[SHA_HASHSZ
- 1] |= 0x01;
117 q
= mp_loadb(MP_NEW
, xbuf
, sizeof(xbuf
));
120 /* --- Quick primality check --- */
122 if (proc
&& (fail
= proc(DSAEV_FINDQ
, 0, arg
)) != 0)
127 int rc
= pgen_create(&pg
, q
);
129 if (rc
== PGEN_COMPOSITE
) {
131 fail
= proc(DSAEV_FAILQ
, q
, arg
);
138 /* --- Ensure that @q@ is prime --- *
140 * This requires 18 iterations, because the DSA spec is paranoid.
141 * Fortunately, it doesn't actually take very long.
150 for (i
= 0; i
< 18; i
++) {
151 g
= mprand(g
, 8 * SHA_HASHSZ
, gr
, 1);
152 if (rabin_test(&r
, g
) == PGEN_COMPOSITE
)
154 if (proc
&& (fail
= proc(DSAEV_PASSQ
, q
, arg
)) != 0)
163 fail
= proc(DSAEV_FAILQ
, q
, arg
);
168 if (proc
&& (fail
= proc(DSAEV_GOODQ
, q
, arg
)) != 0)
170 if (proc
&& (fail
= proc(DSAEV_FINDP
, 0, arg
)) != 0)
174 /* --- Now generate @p@ --- *
176 * This is, unfortunately, rather more messy and complicated.
180 mp
*q2
= mp_lsl(MP_NEW
, q
, 1);
181 mp
*ll
= mp_lsl(MP_NEW
, MP_ONE
, l
* 8 - 1);
182 unsigned n
= l
/ SHA_HASHSZ
, b
= l
% SHA_HASHSZ
;
183 size_t psz
= SHA_HASHSZ
* (n
+ 1);
184 octet
*pbuf
= xmalloc(psz
);
188 /* --- Fiddle with the leftover bytes count --- */
192 /* --- Go round 4096 times trying different @p@ values --- */
195 for (j
= 0; j
< 4096; j
++) {
197 /* --- Build a prospective value of @p@ --- */
200 octet
*pp
= pbuf
+ SHA_HASHSZ
* n
;
202 for (i
= 0; i
<= n
; i
++) {
203 mpx_uaddn(s
->v
, s
->vl
, 1);
204 mp_storeb(s
, sbuf
, sz
);
206 sha_hash(&c
, sbuf
, sz
);
212 p
= mp_loadb(p
, pbuf
+ b
, psz
- b
);
213 p
= mp_add(p
, p
, ll
);
216 /* --- Adjust @p@ so that %$p \bmod 2q = 1$% --- */
220 mp_div(0, &c
, p
, q2
);
221 c
= mp_sub(c
, c
, MP_ONE
);
226 /* --- Check that @p@ is large enough --- */
228 if (MP_CMP(p
, <, ll
))
231 /* --- Run a simple primality test --- */
235 int rc
= pgen_create(&pg
, p
);
237 if (rc
== PGEN_COMPOSITE
)
241 /* --- Run the Rabin-Miller test --- */
248 if (proc
&& (fail
= proc(DSAEV_TRYP
, p
, arg
)) != 0)
250 for (i
= 0; i
< 5; i
++) {
251 g
= mprand(g
, 8 * (psz
- b
), gr
, 1);
252 if (rabin_test(&r
, g
) == PGEN_COMPOSITE
)
254 if (proc
&& (fail
= proc(DSAEV_PASSP
, p
, arg
)) != 0)
262 if (proc
&& (fail
= proc(DSAEV_FAILP
, p
, arg
)) != 0)
268 /* --- It worked! --- */
271 fail
= proc(DSAEV_GOODP
, p
, arg
);
273 fail
= proc(DSAEV_FINDG
, 0, arg
);
280 if (j
>= 4096 || fail
)
284 /* --- Choose a generator of an order-%$q$% subgroup of %$Z^*_p$% --- */
293 /* --- Calculate %$p' = (p - 1)/q$% --- */
295 pp
= mp_sub(MP_NEW
, p
, MP_ONE
);
296 mp_div(&pp
, 0, pp
, q
);
298 /* --- Now find %$h$% where %$g = h^{p'} \bmod p \ne 1$% --- */
300 mp_build(&h
, &hw
, &hw
+ 1);
301 mpmont_create(&mm
, p
);
302 for (i
= 0; i
< NPRIME
; i
++) {
304 if (proc
&& (fail
= proc(DSAEV_TRYH
, &h
, arg
)) != 0)
306 g
= mpmont_exp(&mm
, MP_NEW
, &h
, pp
);
307 if (MP_CMP(g
, !=, MP_ONE
))
310 if (proc
&& (fail
= proc(DSAEV_FAILH
, &h
, arg
)) != 0)
322 if (proc
&& (fail
= proc(DSAEV_GOODG
, g
, arg
) != 0))
325 /* --- Return the important information that I succeeded --- */
332 gr
->ops
->destroy(gr
);
335 /* --- Tidy up after failure --- */
345 gr
->ops
->destroy(gr
);
349 /*----- Test rig ----------------------------------------------------------*/
353 static char baton
[] = "/-\\|";
354 static char *b
= baton
;
356 static int event(int ev
, mp
*m
, void *p
)
358 if (ev
== DSAEV_TRYP
|| ev
== DSAEV_PASSP
) {
368 static int verify(dstr
*v
)
370 mp
*q
= *(mp
**)v
[2].buf
;
371 mp
*p
= *(mp
**)v
[3].buf
;
372 mp
*g
= *(mp
**)v
[4].buf
;
374 unsigned l
= *(unsigned *)v
[1].buf
;
378 rc
= dsa_seed(&dp
, l
, v
[0].buf
, v
[0].len
, event
, 0);
379 if (rc
|| MP_CMP(q
, !=, dp
.q
) ||
380 MP_CMP(p
, !=, dp
.p
) || MP_CMP(g
, !=, dp
.g
)) {
381 fputs("\n*** gen failed", stderr
);
382 fputs("\nseed = ", stderr
); type_hex
.dump(&v
[0], stderr
);
383 fprintf(stderr
, "\nl = %u", l
);
384 fputs("\n q = ", stderr
); mp_writefile(q
, stderr
, 16);
385 fputs("\n p = ", stderr
); mp_writefile(q
, stderr
, 16);
386 fputs("\n g = ", stderr
); mp_writefile(g
, stderr
, 16);
388 fputs("\ndp.q = ", stderr
); mp_writefile(dp
.q
, stderr
, 16);
389 fputs("\ndp.p = ", stderr
); mp_writefile(dp
.p
, stderr
, 16);
390 fputs("\ndp.g = ", stderr
); mp_writefile(dp
.g
, stderr
, 16);
396 mp_drop(q
); mp_drop(p
); mp_drop(g
);
398 mp_drop(dp
.q
); mp_drop(dp
.p
); mp_drop(dp
.g
);
400 assert(mparena_count(MPARENA_GLOBAL
) == 0);
404 static test_chunk tests
[] = {
406 { &type_hex
, &type_int
, &type_mp
, &type_mp
, &type_mp
, 0 } },
410 int main(int argc
, char *argv
[])
413 test_run(argc
, argv
, tests
, SRCDIR
"/tests/dsa");
419 /*----- That's all, folks -------------------------------------------------*/