[u/mdw/catacomb] / rsa-recover.c

/* -*-c-*-
 *
 * $Id: rsa-recover.c,v 1.6 2001/06/16 12:56:38 mdw Exp $
 *
 * 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.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: rsa-recover.c,v $
 * Revision 1.6  2001/06/16 12:56:38  mdw
 * Fixes for interface change to @mpmont_expr@ and @mpmont_mexpr@.
 *
 * Revision 1.5  2000/10/08 12:11:22  mdw
 * Use @MP_EQ@ instead of @MP_CMP@.
 *
 * Revision 1.4  2000/07/01 11:22:22  mdw
 * Remove bad type name `rsa_param'.
 *
 * Revision 1.3  2000/06/22 19:03:14  mdw
 * Use the new @mp_odd@ function.
 *
 * Revision 1.2  2000/06/17 12:07:19  mdw
 * Fix a bug in argument validation.  Force %$p > q$% in output.  Use
 * %$\lambda(n) = \lcm(p - 1, q - 1)$% rather than the more traditional
 * %$\phi(n) = (p - 1)(q - 1)$% when computing the decryption exponent.
 *
 * Revision 1.1  1999/12/22 15:50:45  mdw
 * Initial RSA support.
 *
 */

/*----- 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.
 */

int rsa_recover(rsa_priv *rp)
{
  /* --- If there is no modulus, calculate it --- */

  if (!rp->n) {
    if (!rp->p || !rp->q)
      return (-1);
    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) {
      mp *r = MP_NEW;
      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)) {
	mp_drop(r);
	return (-1);
      }
      mp_drop(r);
    }

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

    else if (!rp->e || !rp->d)
      return (-1);
    else {
      mp *t;
      size_t s;
      mp a; mpw aw;
      mp *m1;
      mpmont mm;
      int i;
      mp *z = MP_NEW;

      /* --- 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(MP_NEW, 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(MP_NEW, 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;
      for (;;) {
      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))
	  continue;

	/* --- 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 (;;) {
	  mp *zz = mp_sqr(MP_NEW, z);
	  zz = mpmont_reduce(&mm, zz, zz);
	  if (MP_EQ(zz, mm.r)) {
	    mp_drop(zz);
	    goto done;
	  } else if (MP_EQ(zz, m1)) {
	    mp_drop(zz);
	    goto again;
	  }
	  mp_drop(z);
	  z = zz;
	}
      }

      /* --- 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);
      rp->p = MP_NEW;
      mp_gcd(&rp->p, 0, 0, rp->n, z);
      rp->q = MP_NEW;
      mp_div(&rp->q, 0, rp->n, rp->p);
      mp_drop(z);
      mp_drop(t);
      mp_drop(m1);
      if (MP_CMP(rp->p, <, rp->q)) {
	z = rp->p;
	rp->p = rp->q;
	rp->q = z;
      }
      mpmont_destroy(&mm);
    }
  }

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

  if (!rp->e || !rp->d) {
    mp *phi;
    mp *g = MP_NEW;
    mp *p1, *q1;

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

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

    /* --- 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 {
      mp_drop(phi);
      mp_drop(g);
      return (-1);
    }

    mp_drop(phi);
    if (!MP_EQ(g, MP_ONE)) {
      mp_drop(g);
      return (-1);
    }
    mp_drop(g);
  }

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

  if (!rp->q_inv)
    mp_gcd(0, 0, &rp->q_inv, rp->p, rp->q);

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

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

  /* --- Done --- */

  return (0);
}

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
01898d8e	1	/* --c--
01898d8e	2	*
b0b682aa	3	* $Id: rsa-recover.c,v 1.6 2001/06/16 12:56:38 mdw Exp $
01898d8e	4	*
	5	* Recover RSA 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: rsa-recover.c,v $
b0b682aa	33	* Revision 1.6 2001/06/16 12:56:38 mdw
	34	* Fixes for interface change to @mpmont_expr@ and @mpmont_mexpr@.
	35	*
22bab86c	36	* Revision 1.5 2000/10/08 12:11:22 mdw
	37	* Use @MP_EQ@ instead of @MP_CMP@.
	38	*
b82ec4e8	39	* Revision 1.4 2000/07/01 11:22:22 mdw
	40	* Remove bad type name `rsa_param'.
	41	*
31cb4e2e	42	* Revision 1.3 2000/06/22 19:03:14 mdw
	43	* Use the new @mp_odd@ function.
	44	*
f3099c16	45	* Revision 1.2 2000/06/17 12:07:19 mdw
	46	* Fix a bug in argument validation. Force %$p > q$% in output. Use
	47	* %$\lambda(n) = \lcm(p - 1, q - 1)$% rather than the more traditional
	48	* %$\phi(n) = (p - 1)(q - 1)$% when computing the decryption exponent.
	49	*
01898d8e	50	* Revision 1.1 1999/12/22 15:50:45 mdw
	51	* Initial RSA support.
	52	*
	53	*/
	54
	55	/----- Header files ------------------------------------------------------/
	56
	57	#include "mp.h"
	58	#include "mpmont.h"
	59	#include "rsa.h"
	60
	61	/----- Main code ---------------------------------------------------------/
	62
	63	/* --- @rsa_recover@ --- *
	64	*
b82ec4e8	65	* Arguments: @rsa_priv *rp@ = pointer to parameter block
01898d8e	66	*
	67	* Returns: Zero if all went well, nonzero if the parameters make no
	68	* sense.
	69	*
	70	* Use: Derives the full set of RSA parameters given a minimal set.
	71	*/
	72
b82ec4e8	73	int rsa_recover(rsa_priv *rp)
01898d8e	74	{
	75	/* --- If there is no modulus, calculate it --- */
	76
	77	if (!rp->n) {
	78	if (!rp->p \|\| !rp->q)
	79	return (-1);
	80	rp->n = mp_mul(MP_NEW, rp->p, rp->q);
	81	}
	82
	83	/* --- If there are no factors, compute them --- */
	84
	85	else if (!rp->p \|\| !rp->q) {
	86
	87	/* --- If one is missing, use simple division to recover the other --- */
	88
	89	if (rp->p \|\| rp->q) {
	90	mp *r = MP_NEW;
	91	if (rp->p)
	92	mp_div(&rp->q, &r, rp->n, rp->p);
	93	else
	94	mp_div(&rp->p, &r, rp->n, rp->q);
22bab86c	95	if (!MP_EQ(r, MP_ZERO)) {
01898d8e	96	mp_drop(r);
	97	return (-1);
	98	}
	99	mp_drop(r);
	100	}
	101
	102	/* --- Otherwise use the public and private moduli --- */
	103
f3099c16	104	else if (!rp->e \|\| !rp->d)
	105	return (-1);
	106	else {
01898d8e	107	mp *t;
31cb4e2e	108	size_t s;
01898d8e	109	mp a; mpw aw;
	110	mp *m1;
	111	mpmont mm;
	112	int i;
	113	mp *z = MP_NEW;
	114
	115	/* --- Work out the appropriate exponent --- *
	116	*
	117	* I need to compute %$s$% and %$t$% such that %$2^s t = e d - 1$%, and
	118	* %$t$% is odd.
	119	*/
	120
	121	t = mp_mul(MP_NEW, rp->e, rp->d);
	122	t = mp_sub(t, t, MP_ONE);
31cb4e2e	123	t = mp_odd(t, t, &s);
01898d8e	124
	125	/* --- Set up for the exponentiation --- */
	126
	127	mpmont_create(&mm, rp->n);
	128	m1 = mp_sub(MP_NEW, rp->n, mm.r);
	129
	130	/* --- Now for the main loop --- *
	131	*
	132	* Choose candidate integers and attempt to factor the modulus.
	133	*/
	134
	135	mp_build(&a, &aw, &aw + 1);
	136	i = 0;
	137	for (;;) {
	138	again:
	139
	140	/* --- Choose a random %$a$% and calculate %$z = a^t \bmod n$% --- *
	141	*
	142	* If %$z \equiv 1$% or %$z \equiv -1 \pmod n$% then this iteration
	143	* is a failure.
	144	*/
	145
	146	aw = primetab[i++];
b0b682aa	147	z = mpmont_mul(&mm, z, &a, mm.r2);
b0b682aa	148	z = mpmont_expr(&mm, z, z, t);
22bab86c	149	if (MP_EQ(z, mm.r) \|\| MP_EQ(z, m1))
01898d8e	150	continue;
	151
	152	/* --- Now square until something interesting happens --- *
	153	*
	154	* Compute %$z^{2i} \bmod n$%. Eventually, I'll either get %$-1$% or
	155	* %$1$%. If the former, the number is uninteresting, and I need to
	156	* restart. If the latter, the previous number minus 1 has a common
	157	* factor with %$n$%.
	158	*/
	159
	160	for (;;) {
	161	mp *zz = mp_sqr(MP_NEW, z);
	162	zz = mpmont_reduce(&mm, zz, zz);
22bab86c	163	if (MP_EQ(zz, mm.r)) {
01898d8e	164	mp_drop(zz);
01898d8e	165	goto done;
22bab86c	166	} else if (MP_EQ(zz, m1)) {
01898d8e	167	mp_drop(zz);
	168	goto again;
	169	}
	170	mp_drop(z);
	171	z = zz;
	172	}
	173	}
	174
	175	/* --- Do the factoring --- *
	176	*
	177	* Here's how it actually works. I've found an interesting square
	178	* root of %$1 \pmod n$%. Any square root of 1 must be congruent to
	179	* %$\pm 1$% modulo both %$p$% and %$q$%. Both congruent to %$1$% is
	180	* boring, as is both congruent to %$-1$%. Subtracting one from the
	181	* result makes it congruent to %$0$% modulo %$p$% or %$q$% (and
	182	* nobody cares which), and hence can be extracted by a GCD
	183	* operation.
	184	*/
	185
	186	done:
	187	z = mpmont_reduce(&mm, z, z);
	188	z = mp_sub(z, z, MP_ONE);
	189	rp->p = MP_NEW;
	190	mp_gcd(&rp->p, 0, 0, rp->n, z);
	191	rp->q = MP_NEW;
	192	mp_div(&rp->q, 0, rp->n, rp->p);
	193	mp_drop(z);
	194	mp_drop(t);
	195	mp_drop(m1);
f3099c16	196	if (MP_CMP(rp->p, <, rp->q)) {
	197	z = rp->p;
	198	rp->p = rp->q;
	199	rp->q = z;
	200	}
01898d8e	201	mpmont_destroy(&mm);
	202	}
	203	}
	204
	205	/* --- If %$e$% or %$d$% is missing, recalculate it --- */
	206
	207	if (!rp->e \|\| !rp->d) {
	208	mp *phi;
	209	mp *g = MP_NEW;
f3099c16	210	mp p1, q1;
01898d8e	211
	212	/* --- Compute %$\varphi(n)$% --- */
	213
	214	phi = mp_sub(MP_NEW, rp->n, rp->p);
	215	phi = mp_sub(phi, phi, rp->q);
	216	phi = mp_add(phi, phi, MP_ONE);
f3099c16	217	p1 = mp_sub(MP_NEW, rp->p, MP_ONE);
	218	q1 = mp_sub(MP_NEW, rp->q, MP_ONE);
	219	mp_gcd(&g, 0, 0, p1, q1);
	220	mp_div(&phi, 0, phi, g);
	221	mp_drop(p1);
	222	mp_drop(q1);
01898d8e	223
	224	/* --- Recover the other exponent --- */
	225
	226	if (rp->e)
	227	mp_gcd(&g, 0, &rp->d, phi, rp->e);
	228	else if (rp->d)
	229	mp_gcd(&g, 0, &rp->e, phi, rp->d);
	230	else {
	231	mp_drop(phi);
f3099c16	232	mp_drop(g);
01898d8e	233	return (-1);
	234	}
	235
	236	mp_drop(phi);
22bab86c	237	if (!MP_EQ(g, MP_ONE)) {
01898d8e	238	mp_drop(g);
	239	return (-1);
	240	}
	241	mp_drop(g);
	242	}
	243
	244	/* --- Compute %$q^{-1} \bmod p$% --- */
	245
	246	if (!rp->q_inv)
	247	mp_gcd(0, 0, &rp->q_inv, rp->p, rp->q);
	248
	249	/* --- Compute %$d \bmod (p - 1)$% and %$d \bmod (q - 1)$% --- */
	250
	251	if (!rp->dp) {
	252	mp *p1 = mp_sub(MP_NEW, rp->p, MP_ONE);
	253	mp_div(0, &rp->dp, rp->d, p1);
	254	mp_drop(p1);
	255	}
	256	if (!rp->dq) {
	257	mp *q1 = mp_sub(MP_NEW, rp->q, MP_ONE);
	258	mp_div(0, &rp->dq, rp->d, q1);
	259	mp_drop(q1);
	260	}
	261
	262	/* --- Done --- */
	263
	264	return (0);
	265	}
	266
	267	/----- That's all, folks -------------------------------------------------/