X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/01898d8eb947e922eb289589cd7b1f016e2ada06..f0c52873e4c1e3a16bb2d5a086df2526f698e4ac:/rsa-recover.c

diff --git a/rsa-recover.c b/rsa-recover.c
index c125aef..4546cc3 100644
--- a/rsa-recover.c
+++ b/rsa-recover.c
@@ -1,13 +1,13 @@
 /* -*-c-*-
  *
- * $Id: rsa-recover.c,v 1.1 1999/12/22 15:50:45 mdw Exp $
+ * $Id: rsa-recover.c,v 1.7 2004/04/08 01:36:15 mdw Exp $
  *
  * Recover RSA parameters
  *
  * (c) 1999 Straylight/Edgeware
  */
 
-/*----- Licensing notice --------------------------------------------------* 
+/*----- Licensing notice --------------------------------------------------*
  *
  * This file is part of Catacomb.
  *
@@ -15,26 +15,18 @@
  * 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.1  1999/12/22 15:50:45  mdw
- * Initial RSA support.
- *
- */
-
 /*----- Header files ------------------------------------------------------*/
 
 #include "mp.h"
@@ -45,7 +37,7 @@
 
 /* --- @rsa_recover@ --- *
  *
- * Arguments:	@rsa_param *rp@ = pointer to parameter block
+ * Arguments:	@rsa_priv *rp@ = pointer to parameter block
  *
  * Returns:	Zero if all went well, nonzero if the parameters make no
  *		sense.
@@ -53,7 +45,7 @@
  * Use:		Derives the full set of RSA parameters given a minimal set.
  */
 
-int rsa_recover(rsa_param *rp)
+int rsa_recover(rsa_priv *rp)
 {
   /* --- If there is no modulus, calculate it --- */
 
@@ -75,7 +67,7 @@ int rsa_recover(rsa_param *rp)
 	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)) {
+      if (!MP_EQ(r, MP_ZERO)) {
 	mp_drop(r);
 	return (-1);
       }
@@ -84,10 +76,11 @@ int rsa_recover(rsa_param *rp)
 
     /* --- Otherwise use the public and private moduli --- */
 
-    else if (rp->e && rp->d) {
+    else if (!rp->e || !rp->d)
+      return (-1);
+    else {
       mp *t;
-      unsigned s;
-      mpscan ms;
+      size_t s;
       mp a; mpw aw;
       mp *m1;
       mpmont mm;
@@ -102,15 +95,7 @@ int rsa_recover(rsa_param *rp)
 
       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);
+      t = mp_odd(t, t, &s);
 
       /* --- Set up for the exponentiation --- */
 
@@ -134,8 +119,9 @@ int rsa_recover(rsa_param *rp)
 	 */
 
 	aw = primetab[i++];
-	z = mpmont_expr(&mm, z, &a, t);
-	if (MP_CMP(z, ==, mm.r) || MP_CMP(z, ==, m1))
+	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 --- *
@@ -149,10 +135,10 @@ int rsa_recover(rsa_param *rp)
 	for (;;) {
 	  mp *zz = mp_sqr(MP_NEW, z);
 	  zz = mpmont_reduce(&mm, zz, zz);
-	  if (MP_CMP(zz, ==, mm.r)) {
+	  if (MP_EQ(zz, mm.r)) {
 	    mp_drop(zz);
 	    goto done;
-	  } else if (MP_CMP(zz, ==, m1)) {
+	  } else if (MP_EQ(zz, m1)) {
 	    mp_drop(zz);
 	    goto again;
 	  }
@@ -182,6 +168,11 @@ int rsa_recover(rsa_param *rp)
       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);
     }
   }
@@ -191,12 +182,19 @@ int rsa_recover(rsa_param *rp)
   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 --- */
 
@@ -206,11 +204,12 @@ int rsa_recover(rsa_param *rp)
       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)) {
+    if (!MP_EQ(g, MP_ONE)) {
       mp_drop(g);
       return (-1);
     }