prime generation: Deploy the new Baillie--PSW testers.

[catacomb] / pub / rsa-gen.c

/* -*-c-*-
 *
 * RSA parameter generation
 *
 * (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.
 */

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

#include <mLib/dstr.h>

#include "grand.h"
#include "mp.h"
#include "mpint.h"
#include "pgen.h"
#include "rsa.h"
#include "strongprime.h"

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

/* --- @rsa_gen@, @rsa_gen_e --- *
 *
 * Arguments:	@rsa_priv *rp@ = pointer to block to be filled in
 *		@unsigned nbits@ = required modulus size in bits
 *		@mp *e@ = public exponent
 *		@grand *r@ = random number source
 *		@unsigned n@ = number of attempts to make
 *		@pgen_proc *event@ = event handler function
 *		@void *ectx@ = argument for the event handler
 *
 * Returns:	Zero if all went well, nonzero otherwise.
 *
 * Use:		Constructs a pair of strong RSA primes and other useful RSA
 *		parameters.  A small encryption exponent is chosen if
 *		possible.
 */

static int genprime(mp **pp, mp **dd, const char *name,
		    unsigned nbits, mp *e,
		    grand *r, unsigned nsteps, pgen_proc *event, void *ectx)
{
  pgen_jumpctx jctx; pfilt j;
  mp *p = MP_NEWSEC, *t = MP_NEW, *u = MP_NEW;
  mpw p3, j3, a;
  int rc = -1;

  j.m = MP_NEW;

  /* Find a start position for the search. */
  p = strongprime_setup(name, p, &j, nbits, r, nsteps, event, ectx);
  if (!p) goto end;

  /* Special handling for e = 3. */
  if (MP_EQ(e, MP_THREE)) {
    /* We must have p == 2 (mod 3): if p == 0 (mod 3) then p is not prime; if
     * p == 1 (mod 3) then e|(p - 1).  So fiddle the start position and jump
     * context to allow for this.
     */

    /* Figure out the residues of the start position and jump. */
    mp_div(0, &t, p, MP_THREE); p3 = t->v[0];
    mp_div(0, &u, j.m, MP_THREE); j3 = u->v[0];

    /* If the jump is a multiple of three already, then we're stuffed unless
     * the start position is 2 (mod 3).  This shouldn't happen, since the
     * jump should be twice a multiple of two large primes, which will be
     * nonzero (mod 3).
     *
     * Set a = (2 - p) j mod 3.  Then p' = p + a j == p (mod j), and p' ==
     * p + (2 - p) j^2 == 2 (mod 3).
     */
    assert(j3 != 0);
    a = ((2 - p3)*j3)%3;
    if (a == 1) p = mp_add(p, p, j.m);
    else if (a == 2) { t = mp_lsl(t, j.m, 1); p = mp_add(p, p, t); }

    /* Finally, multiply j by three to make sure it preserves this
     * congruence.
     */
    pfilt_muladd(&j, &j, 3, 0);
  }

  /* Set the search going. */
  jctx.j = &j;
  p = pgen(name, p, p, event, ectx,
	   nsteps, pgen_jump, &jctx,
	   PGEN_BAILLIEPSWNTESTS, pgen_bailliepswtest, 0);

  if (!p) goto end;

  /* Check the GCD constraint. */
  t = mp_sub(t, p, MP_ONE);
  mp_gcd(&t, &u, 0, e, t);
  if (!MP_EQ(t, MP_ONE)) goto end;

  /* All is good. */
  mp_drop(*pp); *pp = p; p = 0;
  mp_drop(*dd); *dd = u; u = 0;
  rc = 0;
end:
  mp_drop(p); mp_drop(t); mp_drop(u);
  mp_drop(j.m);
  return (rc);
}

int rsa_gen_e(rsa_priv *rp, unsigned nbits, mp *e,
	      grand *r, unsigned nsteps, pgen_proc *event, void *ectx)
{
  mp *p = MP_NEWSEC, *q = MP_NEWSEC, *n = MP_NEW;
  mp *dp = MP_NEWSEC, *dq = MP_NEWSEC;
  mp *t = MP_NEW, *u = MP_NEW, *v = MP_NEW;
  mp *tt;
  int rc = -1;

#define RETRY(what) \
  do { if (nsteps) goto fail; else goto retry_##what; } while (0)

  /* Find the first prime. */
retry_all:
retry_p:
  if (genprime(&p, &dp, "p", nbits/2, e, r, nsteps, event, ectx))
    RETRY(p);

  /* Find the second prime. */
retry_q:
  if (genprime(&q, &dq, "q", nbits/2, e, r, nsteps, event, ectx))
    RETRY(q);

  /* Check that gcd(p - 1, q - 1) is sufficiently large. */
  u = mp_sub(u, p, MP_ONE);
  v = mp_sub(v, q, MP_ONE);
  mp_gcd(&t, 0, 0, u, v);
  if (mp_bits(t) >= 8) RETRY(all);

  /* Arrange for p > q. */
  if (MP_CMP(p, <, q)) {
    tt = p;  p  = q;  q  = tt;
    tt = dp; dp = dq; dq = tt;
  }

  /* Check that the modulus is the right size. */
  n = mp_mul(n, p, q);
  if (mp_bits(n) != nbits) RETRY(all);

  /* Now we want to calculate d.  The unit-group exponent is λ = lcm(p - 1,
   * q - 1), so d == e^-1 (mod λ).
   */
  u = mp_mul(u, u, v);
  mp_div(&t, 0, u, t);
  rp->d = mp_modinv(MP_NEW, e, t);

  /* All done. */
  rp->e = MP_COPY(e);
  rp->q_inv = mp_modinv(MP_NEW, q, p);
  rp->p = p; p = 0; rp->dp = dp; dp = 0;
  rp->q = q; q = 0; rp->dq = dq; dq = 0;
  rp->n = n; n = 0;
  rc = 0;

fail:
  mp_drop(p); mp_drop(dp);
  mp_drop(q); mp_drop(dq);
  mp_drop(n);
  mp_drop(t); mp_drop(u); mp_drop(v);
  return (rc);
}

int rsa_gen(rsa_priv *rp, unsigned nbits,
	    grand *r, unsigned nsteps, pgen_proc *event, void *ectx)
{
  mp *f4 = mp_fromulong(MP_NEW, 65537);
  int rc = rsa_gen_e(rp, nbits, f4, r, nsteps, event, ectx);
  mp_drop(f4); return (rc);
}

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