Generic interface.

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

/* -*-c-*-
 *
 * $Id: bbs-gen.c,v 1.1 1999/12/10 23:14:59 mdw Exp $
 *
 * Generate Blum integers
 *
 * (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: bbs-gen.c,v $
 * Revision 1.1  1999/12/10 23:14:59  mdw
 * Blum-Blum-Shub generator, and Blum-Goldwasser encryption.
 *
 */

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

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

#include "bbs.h"
#include "fibrand.h"
#include "mp.h"
#include "mprand.h"
#include "pgen.h"
#include "rabin.h"

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

/* --- @bbs_gen@ --- *
 *
 * Arguments:	@bbs_params *bp@ = pointer to parameter block
 *		@mp *p, *q@ = initial numbers to search from
 *		@size_t n@ = number of attempts to make
 *		@void (*proc)(int ev, mp *m, void *p)@ = event handler
 *		@void *arg@ = argument for event handler
 *
 * Returns:	Zero if all went well, otherwise an event code which explains
 *		the problem.
 *
 * Use:		Finds two prime numbers %$p'$% and %$q'$% such that both are
 *		congruent to %$3 \bmod 4$%, and  $(p - 1)/2$% and
 *		%$(q - 1)/2$% have no common factors.  The product %$n = pq$%
 *		is eminently suitable for use as a modulus in a Blum-Blum-
 *		Shub pseudorandom bit generator.
 */

int bbs_gen(bbs_params *bp, mp *p, mp *q, size_t n,
	    int (*proc)(int /*ev*/, mp */*m*/, void */*p*/), void *arg)
{
  pgen px, py;
  mp *pp;
  mp *g = MP_NEW;
  grand *gr = fibrand_create(0);
  int rcx, rcy;
  int fail = BBSEV_OK;
  size_t sz;

  /* --- Initialize @p@ and @q@ --- *
   *
   * Divide both by two, and make the results odd.
   */

  p = mp_lsr(MP_NEW, p, 1); p->v[0] |= 1;
  q = mp_lsr(MP_NEW, q, 1); q->v[0] |= 1;

  /* --- Set up the search for @p@ --- *
   *
   * I want a prime %$p$% such that %$(p - 1)/2$% has no small factors.
   */

  rcx = pgen_create(&px, p); mp_drop(p);
  rcy = pgen_muladd(&py, &px, 2, 1);

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

  sz = mp_bits(py.m);
  for (;;) {
    if (rcx != PGEN_COMPOSITE && rcy != PGEN_COMPOSITE) {
      if (rcy != PGEN_PRIME) {
	rabin r;
	int i;

	if (proc && (fail = proc(BBSEV_TRYP, py.m, arg)) != 0)
	  break;
	rabin_create(&r, py.m);	
	for (i = 0; i < 5; i++) {
	  g = mprand(g, sz, gr, 1);
	  if ((rcy = rabin_test(&r, g)) == PGEN_COMPOSITE)
	    break;
	  if (proc && (fail = proc(BBSEV_PASSP, py.m, arg)) != 0)
	    break;
	}
	rabin_destroy(&r);
	if (fail)
	  goto fail_0;
	if (i < 5) {
	  if (proc && (fail = proc(BBSEV_FAILP, py.m, arg)) != 0)
	    goto fail_0;
	  if (n) {
	    n--;
	    if (!n) {
	      fail = BBSEV_FAILP;
	      goto fail_0;
	    }
	  }
	}
      }

      if (rcy != PGEN_COMPOSITE)
	break;
    }
    rcx = pgen_step(&px, 2);
    rcy = pgen_step(&py, 4);
  }

  if (proc && (fail = proc(BBSEV_GOODP, py.m, arg)) != 0)
    goto fail_0;

  /* --- I now have a @p@ (and a %$(p - 1)/2$%) --- */

  pp = MP_COPY(px.m); pgen_destroy(&px);
  p = MP_COPY(py.m); pgen_destroy(&py);

  /* --- Next trick is to generate @q@ --- *
   *
   * I don't care about small factors of %$(q - 1)/2$%, just that it's
   * relatively prime to %$(p - 1)/2$%.
   */

  {
    mp *m = mp_lsl(MP_NEW, q, 1);
    m->v[0] |= 1;
    rcx = pgen_create(&px, m);
    mp_drop(m);
  }

  if (proc && (fail = proc(BBSEV_FINDQ, 0, arg)) != 0)
    goto fail_1;

  for (;;) {
    if (rcx != PGEN_COMPOSITE) {
      int ok;

      /* --- Ensure that %$(p - 1)/2$% and %$(q - 1)/2$% are coprime --- */

      mp_gcd(&g, 0, 0, pp, q);
      ok = MP_CMP(g, ==, MP_ONE);

      if (ok && rcx != PGEN_PRIME) {
	rabin r;
	int i;

	if (proc && (fail = proc(BBSEV_TRYQ, px.m, arg)) != 0)
	  break;
	rabin_create(&r, px.m);
	for (i = 0; i < 5; i++) {
	  g = mprand(g, sz, gr, 1);
	  if ((rcx = rabin_test(&r, g)) == PGEN_COMPOSITE)
	    break;
	  if (proc && (fail = proc(BBSEV_PASSQ, px.m, arg)) != 0)
	    break;
	}
	rabin_destroy(&r);
	if (fail)
	  goto fail_1;
	if (i < 5) {
	  if (proc && (fail = proc(BBSEV_FAILQ, px.m, arg)) != 0)
	    goto fail_1;
	  if (n) {
	    n--;
	    if (!n) {
	      fail = BBSEV_FAILQ;
	      goto fail_1;
	    }
	  }
	}
      }

      if (ok && rcx != PGEN_COMPOSITE)
	break;
    }

    q = mp_add(q, q, MP_TWO);
    rcx = pgen_step(&px, 4);
  }

  if (proc && (fail = proc(BBSEV_GOODQ, px.m, arg)) != 0)
    goto fail_1;

  /* --- Done --- */

  mp_drop(g);
  mp_drop(q);
  mp_drop(pp);
  q = MP_COPY(px.m);
  bp->p = p;
  bp->q = q;
  pgen_destroy(&px);
  bp->n = mp_mul(MP_NEW, p, q);
  gr->ops->destroy(gr);
  return (0);

  /* --- Failed --- */

fail_1:
  pgen_destroy(&px);
  mp_drop(p);
  mp_drop(pp);
  mp_drop(g);
  gr->ops->destroy(gr);
  return (fail);

fail_0:
  if (g)
    mp_drop(g);
  pgen_destroy(&px);
  pgen_destroy(&py);
  mp_drop(q);
  gr->ops->destroy(gr);
  return (fail);
}

/*----- That's all, folks -------------------------------------------------*/