[u/mdw/catacomb] / dsa-gen.c

/* -*-c-*-
 *
 * $Id: dsa-gen.c,v 1.3 1999/12/10 23:18:38 mdw Exp $
 *
 * Generate DSA shared parameters
 *
 * (c) 1999 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 * 
 * Catacomb is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: dsa-gen.c,v $
 * Revision 1.3  1999/12/10 23:18:38  mdw
 * Change interface for suggested destinations.
 *
 * Revision 1.2  1999/11/20 22:23:48  mdw
 * Allow event handler to abort the search process.
 *
 * Revision 1.1  1999/11/19 19:28:00  mdw
 * Implementation of the Digital Signature Algorithm.
 *
 */

/*----- Header files ------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>

#include "dsa.h"
#include "fibrand.h"
#include "mp.h"
#include "mprand.h"
#include "pgen.h"
#include "rabin.h"
#include "sha.h"

/*----- Main code ---------------------------------------------------------*/

/* --- @dsa_seed@ --- *
 *
 * Arguments:	@dsa_param *dp@ = where to store parameters
 *		@unsigned l@ = bitlength of @p@ in bits
 *		@const void *k@ = pointer to key material
 *		@size_t sz@ = size of key material
 *		@int (*proc)(int ev, mp *m, void *p)@ = event procedure
 *
 * Returns:	Zero if all went well, nonzero if key material was
 *		unsuitable (one of the @DSAEV@ codes).
 *
 * Use:		Generates the DSA shared parameters from a given seed value.
 *		This can take quite a long time.  The size of @p@ in bits is
 *		%$l = 512 + 64l'$%.  The DSA standard, FIPS 186, only allows
 *		%$0 \le l' \le 8$%.  This implementation has no such limit,
 *		although @l@ must be a multiple of 8.
 *
 *		The event procedure is informed of various happenings during
 *		generation.  It is passed an event code describing what
 *		happened, and a multiprecision number which pertains to the
 *		event code.  It may abort the search at any time by returning
 *		a nonzero value, which is returned as the result of the
 *		function.
 */

int dsa_seed(dsa_param *dp, unsigned l, const void *k, size_t sz,
	     int (*proc)(int /*ev*/, mp */*m*/, void */*p*/), void *arg)
{
  mp *q, *p, *g;
  mp *s = mp_loadb(MP_NEW, k, sz);
  octet *sbuf = xmalloc(sz);
  grand *gr;
  int fail = 0;

  l /= 8;
  gr = fibrand_create(LOAD32(k));

  /* --- Generate @q@ --- */

  {
    octet xbuf[SHA_HASHSZ], ybuf[SHA_HASHSZ];
    sha_ctx c;
    int i;

    sha_init(&c);
    sha_hash(&c, k, sz);
    sha_done(&c, xbuf);

    mpx_uaddn(s->v, s->vl, 1);
    mp_storeb(s, sbuf, sz);
    sha_init(&c);
    sha_hash(&c, sbuf, sz);
    sha_done(&c, ybuf);
    
    for (i = 0; i < sizeof(xbuf); i++)
      xbuf[i] ^= ybuf[i];
    xbuf[0] |= 0x80;
    xbuf[SHA_HASHSZ - 1] |= 0x01;
    q = mp_loadb(MP_NEW, xbuf, sizeof(xbuf));
  }

  /* --- Quick primality check --- */

  if (proc && (fail = proc(DSAEV_FINDQ, 0, arg)) != 0)
    goto fail_0;

  {
    pgen pg;
    int rc = pgen_create(&pg, q);
    pgen_destroy(&pg);
    if (rc == PGEN_COMPOSITE) {
      if (proc)
	fail = proc(DSAEV_FAILQ, q, arg);
      if (!fail)
	fail = DSAEV_FAILQ;
      goto fail_0;
    }
  }

  /* --- Ensure that @q@ is prime --- *
   *
   * This requires 18 iterations, because the DSA spec is paranoid.
   * Fortunately, it doesn't actually take very long.
   */

  {
    rabin r;
    int i;
    mp *g = MP_NEW;

    rabin_create(&r, q);
    for (i = 0; i < 18; i++) {
      g = mprand(g, 8 * SHA_HASHSZ, gr, 1);
      if (rabin_test(&r, g) == PGEN_COMPOSITE)
	break;
      if (proc && (fail = proc(DSAEV_PASSQ, q, arg)) != 0)
	break;
    }
    mp_drop(g);
    rabin_destroy(&r);
    if (fail)
      goto fail_0;
    if (i < 18) {
      if (proc)
	fail = proc(DSAEV_FAILQ, q, arg);
      if (!fail)
	fail = DSAEV_FAILQ;
      goto fail_0;
    }
    if (proc && (fail = proc(DSAEV_GOODQ, q, arg)) != 0)
      goto fail_0;
    if (proc && (fail = proc(DSAEV_FINDP, 0, arg)) != 0)
      goto fail_0;
  }

  /* --- Now generate @p@ --- *
   *
   * This is, unfortunately, rather more messy and complicated.
   */

  {
    mp *q2 = mp_lsl(MP_NEW, q, 1);
    mp *ll = mp_lsl(MP_NEW, MP_ONE, l * 8 - 1);
    unsigned n = l / SHA_HASHSZ, b = l % SHA_HASHSZ;
    size_t psz = SHA_HASHSZ * (n + 1);
    octet *pbuf = xmalloc(psz);
    sha_ctx c;
    unsigned i, j;

    /* --- Fiddle with the leftover bytes count --- */

    b = SHA_HASHSZ - b;

    /* --- Go round 4096 times trying different @p@ values --- */

    p = MP_NEW;
    for (j = 0; j < 4096; j++) {

      /* --- Build a prospective value of @p@ --- */

      {
	octet *pp = pbuf + SHA_HASHSZ * n;

	for (i = 0; i <= n; i++) {
	  mpx_uaddn(s->v, s->vl, 1);
	  mp_storeb(s, sbuf, sz);
	  sha_init(&c);
	  sha_hash(&c, sbuf, sz);
	  sha_done(&c, pp);
	  pp -= SHA_HASHSZ;
	}

	pbuf[b] &= 0x7f;
	p = mp_loadb(p, pbuf + b, psz - b);
	p = mp_add(p, p, ll);
      }

      /* --- Adjust @p@ so that %$p \bmod 2q = 1$% --- */

      {
	mp *c = MP_NEW;
	mp_div(0, &c, p, q2);
	c = mp_sub(c, c, MP_ONE);
	p = mp_sub(p, p, c);
	mp_drop(c);
      }

      /* --- Check that @p@ is large enough --- */

      if (MP_CMP(p, <, ll))
	continue;

      /* --- Run a simple primality test --- */

      {
	pgen pg;
	int rc = pgen_create(&pg, p);
	pgen_destroy(&pg);
	if (rc == PGEN_COMPOSITE)
	  continue;
      }

      /* --- Run the Rabin-Miller test --- */

      {
	rabin r;
	mp *g = MP_NEW;

	rabin_create(&r, p);
	if (proc && (fail = proc(DSAEV_TRYP, p, arg)) != 0)
	  break;
	for (i = 0; i < 5; i++) {
	  g = mprand(g, 8 * (psz - b), gr, 1);
	  if (rabin_test(&r, g) == PGEN_COMPOSITE)
	    break;
	  if (proc && (fail = proc(DSAEV_PASSP, p, arg)) != 0)
	    break;
	}
	mp_drop(g);
	rabin_destroy(&r);
	if (fail)
	  break;
	if (i < 5) {
	  if (proc && (fail = proc(DSAEV_FAILP, p, arg)) != 0)
	    break;
	  continue;
	}
      }

      /* --- It worked! --- */

      if (proc)
	fail = proc(DSAEV_GOODP, p, arg);
      if (proc && !fail)
	fail = proc(DSAEV_FINDG, 0, arg);
      break;
    }

    free(pbuf);
    mp_drop(q2);
    mp_drop(ll);
    if (j >= 4096 || fail)
      goto fail_1;
  }

  /* --- Choose a generator of an order-%$q$% subgroup of %$Z^*_p$% --- */

  {
    mp *pp = MP_NEW;
    mpw hw;
    mp h;
    unsigned i;
    mpmont mm;

    /* --- Calculate %$p' = (p - 1)/q$% --- */

    pp = mp_sub(MP_NEW, p, MP_ONE);
    mp_div(&pp, 0, pp, q);

    /* --- Now find %$h$% where %$g = h^{p'} \bmod p \ne 1$% --- */

    mp_build(&h, &hw, &hw + 1);
    mpmont_create(&mm, p);
    for (i = 0; i < NPRIME; i++) {
      hw = ptab[i];
      if (proc && (fail = proc(DSAEV_TRYH, &h, arg)) != 0)
	break;
      g = mpmont_exp(&mm, MP_NEW, &h, pp);
      if (MP_CMP(g, !=, MP_ONE))
	break;
      mp_drop(g);
      if (proc && (fail = proc(DSAEV_FAILH, &h, arg)) != 0)
	break;
    }
    mp_drop(pp);
    mpmont_destroy(&mm);
    if (fail)
      goto fail_1;
    if (i >= NPRIME) {
      fail = DSAEV_FAILH;
      goto fail_1;
    }
  }
  if (proc && (fail = proc(DSAEV_GOODG, g, arg) != 0))
    goto fail_2;

  /* --- Return the important information that I succeeded --- */

  dp->g = g;
  dp->p = p;
  dp->q = q;
  mp_drop(s);
  free(sbuf);
  gr->ops->destroy(gr);
  return (0);

  /* --- Tidy up after failure --- */

fail_2:
  mp_drop(g);
fail_1:
  mp_drop(p);
fail_0:
  mp_drop(q);
  mp_drop(s);
  free(sbuf);
  gr->ops->destroy(gr);
  return (-1);
}

/*----- Test rig ----------------------------------------------------------*/

#ifdef TEST_RIG

static char baton[] = "/-\\|";
static char *b = baton;

static int event(int ev, mp *m, void *p)
{
  if (ev == DSAEV_TRYP || ev == DSAEV_PASSP) {
    fputc(*b++, stdout);
    fputc('\b', stdout);
    fflush(stdout);
    if (!*b)
      b = baton;
  }
  return (0);
}

static int verify(dstr *v)
{
  mp *q = *(mp **)v[2].buf;
  mp *p = *(mp **)v[3].buf;
  mp *g = *(mp **)v[4].buf;
  dsa_param dp;
  unsigned l = *(unsigned *)v[1].buf;
  int ok = 1;
  int rc;

  rc = dsa_seed(&dp, l, v[0].buf, v[0].len, event, 0);
  if (rc || MP_CMP(q, !=, dp.q) ||
      MP_CMP(p, !=, dp.p) || MP_CMP(g, !=, dp.g)) {
    fputs("\n*** gen failed", stderr);
    fputs("\nseed = ", stderr); type_hex.dump(&v[0], stderr);
    fprintf(stderr, "\nl = %u", l);
    fputs("\n   q = ", stderr); mp_writefile(q, stderr, 16);
    fputs("\n   p = ", stderr); mp_writefile(q, stderr, 16);
    fputs("\n   g = ", stderr); mp_writefile(g, stderr, 16);
    if (!rc) {
      fputs("\ndp.q = ", stderr); mp_writefile(dp.q, stderr, 16);
      fputs("\ndp.p = ", stderr); mp_writefile(dp.p, stderr, 16);
      fputs("\ndp.g = ", stderr); mp_writefile(dp.g, stderr, 16);
    }
    fputc('\n', stderr);
    ok = 0;
  }

  mp_drop(q); mp_drop(p); mp_drop(g);
  if (!rc) {
    mp_drop(dp.q); mp_drop(dp.p); mp_drop(dp.g);
  }
  assert(mparena_count(MPARENA_GLOBAL) == 0);
  return (ok);
}

static test_chunk tests[] = {
  { "gen", verify,
    { &type_hex, &type_int, &type_mp, &type_mp, &type_mp, 0 }  },
  { 0, 0, { 0 } }
};

int main(int argc, char *argv[])
{
  sub_init();
  test_run(argc, argv, tests, SRCDIR "/tests/dsa");
  return (0);
}

#endif

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
8b810a45	1	/* --c--
8b810a45	2	*
ef5f4810	3	* $Id: dsa-gen.c,v 1.3 1999/12/10 23:18:38 mdw Exp $
8b810a45	4	*
	5	* Generate DSA shared parameters
	6	*
	7	* (c) 1999 Straylight/Edgeware
	8	*/
	9
	10	/----- Licensing notice --------------------------------------------------
	11	*
	12	* This file is part of Catacomb.
	13	*
	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.
	18	*
	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.
	23	*
	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,
	27	* MA 02111-1307, USA.
	28	*/
	29
	30	/----- Revision history --------------------------------------------------
	31	*
	32	* $Log: dsa-gen.c,v $
ef5f4810	33	* Revision 1.3 1999/12/10 23:18:38 mdw
	34	* Change interface for suggested destinations.
	35	*
987bb691	36	* Revision 1.2 1999/11/20 22:23:48 mdw
	37	* Allow event handler to abort the search process.
	38	*
8b810a45	39	* Revision 1.1 1999/11/19 19:28:00 mdw
	40	* Implementation of the Digital Signature Algorithm.
	41	*
	42	*/
	43
	44	/----- Header files ------------------------------------------------------/
	45
	46	#include <stdio.h>
	47	#include <stdlib.h>
	48
	49	#include "dsa.h"
ef5f4810	50	#include "fibrand.h"
8b810a45	51	#include "mp.h"
ef5f4810	52	#include "mprand.h"
8b810a45	53	#include "pgen.h"
8b810a45	54	#include "rabin.h"
8b810a45	55	#include "sha.h"
	56
	57	/----- Main code ---------------------------------------------------------/
	58
	59	/* --- @dsa_seed@ --- *
	60	*
	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
8b810a45	64	* @size_t sz@ = size of key material
ef5f4810	65	* @int (proc)(int ev, mp m, void *p)@ = event procedure
8b810a45	66	*
	67	* Returns: Zero if all went well, nonzero if key material was
	68	* unsuitable (one of the @DSAEV@ codes).
	69	*
	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.
	75	*
	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
987bb691	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
	81	* function.
8b810a45	82	*/
	83
	84	int dsa_seed(dsa_param dp, unsigned l, const void k, size_t sz,
987bb691	85	int (proc)(int /ev/, mp /m/, void /p/), void arg)
8b810a45	86	{
	87	mp q, p, *g;
	88	mp *s = mp_loadb(MP_NEW, k, sz);
	89	octet *sbuf = xmalloc(sz);
ef5f4810	90	grand *gr;
987bb691	91	int fail = 0;
8b810a45	92
8b810a45	93	l /= 8;
ef5f4810	94	gr = fibrand_create(LOAD32(k));
8b810a45	95
	96	/* --- Generate @q@ --- */
	97
	98	{
	99	octet xbuf[SHA_HASHSZ], ybuf[SHA_HASHSZ];
	100	sha_ctx c;
	101	int i;
	102
	103	sha_init(&c);
	104	sha_hash(&c, k, sz);
	105	sha_done(&c, xbuf);
	106
987bb691	107	mpx_uaddn(s->v, s->vl, 1);
8b810a45	108	mp_storeb(s, sbuf, sz);
	109	sha_init(&c);
	110	sha_hash(&c, sbuf, sz);
	111	sha_done(&c, ybuf);
	112
	113	for (i = 0; i < sizeof(xbuf); i++)
	114	xbuf[i] ^= ybuf[i];
	115	xbuf[0] \|= 0x80;
	116	xbuf[SHA_HASHSZ - 1] \|= 0x01;
	117	q = mp_loadb(MP_NEW, xbuf, sizeof(xbuf));
	118	}
	119
	120	/* --- Quick primality check --- */
	121
ef5f4810	122	if (proc && (fail = proc(DSAEV_FINDQ, 0, arg)) != 0)
	123	goto fail_0;
	124
8b810a45	125	{
	126	pgen pg;
	127	int rc = pgen_create(&pg, q);
	128	pgen_destroy(&pg);
	129	if (rc == PGEN_COMPOSITE) {
	130	if (proc)
987bb691	131	fail = proc(DSAEV_FAILQ, q, arg);
	132	if (!fail)
	133	fail = DSAEV_FAILQ;
8b810a45	134	goto fail_0;
	135	}
	136	}
	137
	138	/* --- Ensure that @q@ is prime --- *
	139	*
	140	* This requires 18 iterations, because the DSA spec is paranoid.
	141	* Fortunately, it doesn't actually take very long.
	142	*/
	143
	144	{
	145	rabin r;
	146	int i;
	147	mp *g = MP_NEW;
8b810a45	148
	149	rabin_create(&r, q);
	150	for (i = 0; i < 18; i++) {
ef5f4810	151	g = mprand(g, 8 * SHA_HASHSZ, gr, 1);
8b810a45	152	if (rabin_test(&r, g) == PGEN_COMPOSITE)
8b810a45	153	break;
987bb691	154	if (proc && (fail = proc(DSAEV_PASSQ, q, arg)) != 0)
987bb691	155	break;
8b810a45	156	}
	157	mp_drop(g);
	158	rabin_destroy(&r);
987bb691	159	if (fail)
987bb691	160	goto fail_0;
8b810a45	161	if (i < 18) {
8b810a45	162	if (proc)
987bb691	163	fail = proc(DSAEV_FAILQ, q, arg);
ef5f4810	164	if (!fail)
987bb691	165	fail = DSAEV_FAILQ;
8b810a45	166	goto fail_0;
8b810a45	167	}
987bb691	168	if (proc && (fail = proc(DSAEV_GOODQ, q, arg)) != 0)
987bb691	169	goto fail_0;
ef5f4810	170	if (proc && (fail = proc(DSAEV_FINDP, 0, arg)) != 0)
ef5f4810	171	goto fail_0;
8b810a45	172	}
	173
	174	/* --- Now generate @p@ --- *
	175	*
	176	* This is, unfortunately, rather more messy and complicated.
	177	*/
	178
	179	{
	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);
	185	sha_ctx c;
	186	unsigned i, j;
	187
	188	/* --- Fiddle with the leftover bytes count --- */
	189
	190	b = SHA_HASHSZ - b;
	191
	192	/* --- Go round 4096 times trying different @p@ values --- */
	193
	194	p = MP_NEW;
	195	for (j = 0; j < 4096; j++) {
	196
	197	/* --- Build a prospective value of @p@ --- */
	198
	199	{
	200	octet pp = pbuf + SHA_HASHSZ n;
	201
	202	for (i = 0; i <= n; i++) {
987bb691	203	mpx_uaddn(s->v, s->vl, 1);
8b810a45	204	mp_storeb(s, sbuf, sz);
	205	sha_init(&c);
	206	sha_hash(&c, sbuf, sz);
	207	sha_done(&c, pp);
	208	pp -= SHA_HASHSZ;
	209	}
	210
	211	pbuf[b] &= 0x7f;
	212	p = mp_loadb(p, pbuf + b, psz - b);
	213	p = mp_add(p, p, ll);
	214	}
	215
	216	/* --- Adjust @p@ so that %$p \bmod 2q = 1$% --- */
	217
	218	{
	219	mp *c = MP_NEW;
	220	mp_div(0, &c, p, q2);
	221	c = mp_sub(c, c, MP_ONE);
	222	p = mp_sub(p, p, c);
	223	mp_drop(c);
	224	}
	225
	226	/* --- Check that @p@ is large enough --- */
	227
	228	if (MP_CMP(p, <, ll))
	229	continue;
	230
	231	/* --- Run a simple primality test --- */
	232
	233	{
	234	pgen pg;
	235	int rc = pgen_create(&pg, p);
	236	pgen_destroy(&pg);
	237	if (rc == PGEN_COMPOSITE)
	238	continue;
	239	}
	240
	241	/* --- Run the Rabin-Miller test --- */
	242
	243	{
	244	rabin r;
	245	mp *g = MP_NEW;
	246
8b810a45	247	rabin_create(&r, p);
987bb691	248	if (proc && (fail = proc(DSAEV_TRYP, p, arg)) != 0)
987bb691	249	break;
8b810a45	250	for (i = 0; i < 5; i++) {
ef5f4810	251	g = mprand(g, 8 * (psz - b), gr, 1);
8b810a45	252	if (rabin_test(&r, g) == PGEN_COMPOSITE)
8b810a45	253	break;
987bb691	254	if (proc && (fail = proc(DSAEV_PASSP, p, arg)) != 0)
987bb691	255	break;
8b810a45	256	}
	257	mp_drop(g);
	258	rabin_destroy(&r);
987bb691	259	if (fail)
987bb691	260	break;
8b810a45	261	if (i < 5) {
987bb691	262	if (proc && (fail = proc(DSAEV_FAILP, p, arg)) != 0)
987bb691	263	break;
8b810a45	264	continue;
	265	}
	266	}
	267
	268	/* --- It worked! --- */
	269
	270	if (proc)
987bb691	271	fail = proc(DSAEV_GOODP, p, arg);
ef5f4810	272	if (proc && !fail)
ef5f4810	273	fail = proc(DSAEV_FINDG, 0, arg);
8b810a45	274	break;
	275	}
	276
	277	free(pbuf);
	278	mp_drop(q2);
	279	mp_drop(ll);
987bb691	280	if (j >= 4096 \|\| fail)
8b810a45	281	goto fail_1;
	282	}
	283
	284	/* --- Choose a generator of an order-%$q$% subgroup of %$Z^_p$% --- /
	285
	286	{
	287	mp *pp = MP_NEW;
	288	mpw hw;
	289	mp h;
	290	unsigned i;
	291	mpmont mm;
	292
	293	/* --- Calculate %$p' = (p - 1)/q$% --- */
	294
ef5f4810	295	pp = mp_sub(MP_NEW, p, MP_ONE);
ef5f4810	296	mp_div(&pp, 0, pp, q);
8b810a45	297
	298	/* --- Now find %$h$% where %$g = h^{p'} \bmod p \ne 1$% --- */
	299
	300	mp_build(&h, &hw, &hw + 1);
	301	mpmont_create(&mm, p);
	302	for (i = 0; i < NPRIME; i++) {
	303	hw = ptab[i];
987bb691	304	if (proc && (fail = proc(DSAEV_TRYH, &h, arg)) != 0)
987bb691	305	break;
ef5f4810	306	g = mpmont_exp(&mm, MP_NEW, &h, pp);
8b810a45	307	if (MP_CMP(g, !=, MP_ONE))
8b810a45	308	break;
8b810a45	309	mp_drop(g);
987bb691	310	if (proc && (fail = proc(DSAEV_FAILH, &h, arg)) != 0)
987bb691	311	break;
8b810a45	312	}
8b810a45	313	mp_drop(pp);
ef5f4810	314	mpmont_destroy(&mm);
987bb691	315	if (fail)
987bb691	316	goto fail_1;
8b810a45	317	if (i >= NPRIME) {
	318	fail = DSAEV_FAILH;
	319	goto fail_1;
	320	}
	321	}
987bb691	322	if (proc && (fail = proc(DSAEV_GOODG, g, arg) != 0))
987bb691	323	goto fail_2;
8b810a45	324
	325	/* --- Return the important information that I succeeded --- */
	326
987bb691	327	dp->g = g;
8b810a45	328	dp->p = p;
8b810a45	329	dp->q = q;
987bb691	330	mp_drop(s);
8b810a45	331	free(sbuf);
ef5f4810	332	gr->ops->destroy(gr);
8b810a45	333	return (0);
	334
	335	/* --- Tidy up after failure --- */
	336
987bb691	337	fail_2:
987bb691	338	mp_drop(g);
8b810a45	339	fail_1:
	340	mp_drop(p);
	341	fail_0:
	342	mp_drop(q);
	343	mp_drop(s);
	344	free(sbuf);
ef5f4810	345	gr->ops->destroy(gr);
8b810a45	346	return (-1);
	347	}
	348
	349	/----- Test rig ----------------------------------------------------------/
	350
	351	#ifdef TEST_RIG
	352
	353	static char baton[] = "/-\\\|";
	354	static char *b = baton;
	355
987bb691	356	static int event(int ev, mp m, void p)
8b810a45	357	{
	358	if (ev == DSAEV_TRYP \|\| ev == DSAEV_PASSP) {
	359	fputc(*b++, stdout);
	360	fputc('\b', stdout);
	361	fflush(stdout);
	362	if (!*b)
	363	b = baton;
	364	}
987bb691	365	return (0);
8b810a45	366	}
	367
	368	static int verify(dstr *v)
	369	{
	370	mp q = (mp **)v[2].buf;
	371	mp p = (mp **)v[3].buf;
	372	mp g = (mp **)v[4].buf;
	373	dsa_param dp;
	374	unsigned l = (unsigned )v[1].buf;
	375	int ok = 1;
	376	int rc;
	377
	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);
	387	if (!rc) {
	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);
	391	}
	392	fputc('\n', stderr);
	393	ok = 0;
	394	}
	395
	396	mp_drop(q); mp_drop(p); mp_drop(g);
	397	if (!rc) {
	398	mp_drop(dp.q); mp_drop(dp.p); mp_drop(dp.g);
	399	}
ef5f4810	400	assert(mparena_count(MPARENA_GLOBAL) == 0);
8b810a45	401	return (ok);
	402	}
	403
	404	static test_chunk tests[] = {
	405	{ "gen", verify,
	406	{ &type_hex, &type_int, &type_mp, &type_mp, &type_mp, 0 } },
	407	{ 0, 0, { 0 } }
	408	};
	409
	410	int main(int argc, char *argv[])
	411	{
	412	sub_init();
	413	test_run(argc, argv, tests, SRCDIR "/tests/dsa");
	414	return (0);
	415	}
	416
	417	#endif
	418
	419	/----- That's all, folks -------------------------------------------------/