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

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