pub/rsa-recover.c: Gather cleanup to the end of the function.

[catacomb] / pub / rsa-recover.c

/* -*-c-*-
 *
 * Recover RSA 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.
 */

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

#include "mp.h"
#include "mpmont.h"
#include "rsa.h"

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

/* --- @rsa_recover@ --- *
 *
 * Arguments:	@rsa_priv *rp@ = pointer to parameter block
 *
 * Returns:	Zero if all went well, nonzero if the parameters make no
 *		sense.
 *
 * Use:		Derives the full set of RSA parameters given a minimal set.
 *
 *		On failure, the parameter block might be partially filled in,
 *		but the @rsa_privfree@ function will be able to free it
 *		successfully.
 */

int rsa_recover(rsa_priv *rp)
{
  int rc = -1;
  int i;
  size_t s;
  mpmont mm;
  mp a; mpw aw;
  mp *g = MP_NEW, *r = MP_NEW, *t = MP_NEW, *zt;
  mp *m1 = MP_NEW, *z = MP_NEW, *zz = MP_NEW;
  mp *phi = MP_NEW, *p1 = MP_NEW, *q1 = MP_NEW;

  mm.r = 0;

  /* --- If there is no modulus, calculate it --- */

  if (!rp->n) {
    if (!rp->p || !rp->q) goto out;
    rp->n = mp_mul(MP_NEW, rp->p, rp->q);
  }

  /* --- If there are no factors, compute them --- */

  else if (!rp->p || !rp->q) {

    /* --- If one is missing, use simple division to recover the other --- */

    if (rp->p || rp->q) {
      if (rp->p) mp_div(&rp->q, &r, rp->n, rp->p);
      else mp_div(&rp->p, &r, rp->n, rp->q);
      if (!MP_EQ(r, MP_ZERO)) goto out;
    }

    /* --- Otherwise use the public and private moduli --- */

    else if (!rp->e || !rp->d)
      goto out;
    else {

      /* --- Work out the appropriate exponent --- *
       *
       * I need to compute %$s$% and %$t$% such that %$2^s t = e d - 1$%, and
       * %$t$% is odd.
       */

      t = mp_mul(t, rp->e, rp->d);
      t = mp_sub(t, t, MP_ONE);
      t = mp_odd(t, t, &s);

      /* --- Set up for the exponentiation --- */

      mpmont_create(&mm, rp->n);
      m1 = mp_sub(m1, rp->n, mm.r);

      /* --- Now for the main loop --- *
       *
       * Choose candidate integers and attempt to factor the modulus.
       */

      mp_build(&a, &aw, &aw + 1);
      i = 0;

    again:

      /* --- Choose a random %$a$% and calculate %$z = a^t \bmod n$% --- *
       *
       * If %$z \equiv 1$% or %$z \equiv -1 \pmod n$% then this iteration
       * is a failure.
       */

      aw = primetab[i++];
      z = mpmont_mul(&mm, z, &a, mm.r2);
      z = mpmont_expr(&mm, z, z, t);
      if (MP_EQ(z, mm.r) || MP_EQ(z, m1)) goto again;

      /* --- Now square until something interesting happens --- *
       *
       * Compute %$z^{2i} \bmod n$%.  Eventually, I'll either get %$-1$% or
       * %$1$%.  If the former, the number is uninteresting, and I need to
       * restart.  If the latter, the previous number minus 1 has a common
       * factor with %$n$%.
       */

      for (;;) {
	zz = mp_sqr(zz, z);
	zz = mpmont_reduce(&mm, zz, zz);
	if (MP_EQ(zz, mm.r)) goto done;
	else if (MP_EQ(zz, m1)) goto again;
	zt = z; z = zz; zz = zt;
      }

      /* --- Do the factoring --- *
       *
       * Here's how it actually works.  I've found an interesting square
       * root of %$1 \pmod n$%.  Any square root of 1 must be congruent to
       * %$\pm 1$% modulo both %$p$% and %$q$%.  Both congruent to %$1$% is
       * boring, as is both congruent to %$-1$%.  Subtracting one from the
       * result makes it congruent to %$0$% modulo %$p$% or %$q$% (and
       * nobody cares which), and hence can be extracted by a GCD
       * operation.
       */

    done:
      z = mpmont_reduce(&mm, z, z);
      z = mp_sub(z, z, MP_ONE);
      mp_gcd(&rp->p, 0, 0, rp->n, z);
      mp_div(&rp->q, 0, rp->n, rp->p);
      if (MP_CMP(rp->p, <, rp->q))
	{ zt = rp->p; rp->p = rp->q; rp->q = zt; }
    }
  }

  /* --- If %$e$% or %$d$% is missing, recalculate it --- */

  if (!rp->e || !rp->d) {

    /* --- Compute %$\varphi(n)$% --- */

    phi = mp_sub(phi, rp->n, rp->p);
    phi = mp_sub(phi, phi, rp->q);
    phi = mp_add(phi, phi, MP_ONE);
    p1 = mp_sub(p1, rp->p, MP_ONE);
    q1 = mp_sub(q1, rp->q, MP_ONE);
    mp_gcd(&g, 0, 0, p1, q1);
    mp_div(&phi, 0, phi, g);

    /* --- Recover the other exponent --- */

    if (rp->e) mp_gcd(&g, 0, &rp->d, phi, rp->e);
    else if (rp->d) mp_gcd(&g, 0, &rp->e, phi, rp->d);
    else goto out;
    if (!MP_EQ(g, MP_ONE)) goto out;
  }

  /* --- Compute %$q^{-1} \bmod p$% --- */

  if (!rp->q_inv) {
    mp_gcd(&g, 0, &rp->q_inv, rp->p, rp->q);
    if (!MP_EQ(g, MP_ONE)) goto out;
  }

  /* --- Compute %$d \bmod (p - 1)$% and %$d \bmod (q - 1)$% --- */

  if (!rp->dp) {
    p1 = mp_sub(p1, rp->p, MP_ONE);
    mp_div(0, &rp->dp, rp->d, p1);
  }
  if (!rp->dq) {
    q1 = mp_sub(q1, rp->q, MP_ONE);
    mp_div(0, &rp->dq, rp->d, q1);
  }

  /* --- Done --- */

  rc = 0;
out:
  mp_drop(g); mp_drop(r); mp_drop(t);
  mp_drop(m1); mp_drop(z); mp_drop(zz);
  mp_drop(phi); mp_drop(p1); mp_drop(q1);
  if (mm.r) mpmont_destroy(&mm);
  return (rc);
}

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