Lots of changes:

  * Apply limits on %$\gcd(p - 1, q - 1)$% to reduce the space of
    equivalent decryption exponents.

  * Force %$e = F_4 = 2^{16} + 1$% to avoid small-encryption-exponent
    attacks.

  * Ensure that %$p > q$% and that %$p - q$% is large to deter
    square-root-based factoring methods.

  * Use %$e d \equiv 1 \pmod{\lambda(n)}$%, where %$\lambda(n)$% is
    %$\lcm(p - 1, q - 1)$%, as recommended in PKCS#1, rather than the
    more usual %$\varphi(n) = (p - 1)(q - 1)$%.

  * Handle aborts from pgen_jump.

diff --git a/rsa-gen.c b/rsa-gen.c
index 056d245..159357f 100644 (file)
--- a/rsa-gen.c
+++ b/rsa-gen.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: rsa-gen.c,v 1.1 1999/12/22 15:50:45 mdw Exp $
+ * $Id: rsa-gen.c,v 1.2 2000/06/17 12:05:15 mdw Exp $
  *
  * RSA parameter generation
  *
@@ -30,6 +30,24 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: rsa-gen.c,v $
+ * Revision 1.2  2000/06/17 12:05:15  mdw
+ * Lots of changes:
+ *
+ *   * Apply limits on %$\gcd(p - 1, q - 1)$% to reduce the space of
+ *     equivalent decryption exponents.
+ *
+ *   * Force %$e = F_4 = 2^{16} + 1$% to avoid small-encryption-exponent
+ *     attacks.
+ *
+ *   * Ensure that %$p > q$% and that %$p - q$% is large to deter
+ *     square-root-based factoring methods.
+ *
+ *   * Use %$e d \equiv 1 \pmod{\lambda(n)}$%, where %$\lambda(n)$% is
+ *     %$\lcm(p - 1, q - 1)$%, as recommended in PKCS#1, rather than the
+ *     more usual %$\varphi(n) = (p - 1)(q - 1)$%.
+ *
+ *   * Handle aborts from pgen_jump.
+ *
  * Revision 1.1  1999/12/22 15:50:45  mdw
  * Initial RSA support.
  *
@@ -41,6 +59,7 @@
 
 #include "grand.h"
 #include "mp.h"
+#include "mpint.h"
 #include "pgen.h"
 #include "rsa.h"
 #include "strongprime.h"
@@ -66,16 +85,74 @@
 int rsa_gen(rsa_param *rp, unsigned nbits, grand *r, unsigned n,
            pgen_proc *event, void *ectx)
 {
-  mp *phi;
-  int i;
-  mp *g;
+  pgen_gcdstepctx g;
+  mp *phi = MP_NEW;
 
-  /* --- Generate strong primes %$p$% and %$q$% --- */
+  /* --- Bits of initialization --- */
+
+  rp->e = mp_fromulong(MP_NEW, 0x10001);
+  rp->d = MP_NEW;
+
+  /* --- Generate strong primes %$p$% and %$q$% --- *
+   *
+   * Constrain the GCD of @q@ to ensure that overly small private exponents
+   * are impossible.  Current results suggest that if %$d < n^{0.29}$% then
+   * it can be guessed fairly easily.  This implementation is rather more
+   * conservative about that sort of thing.
+   */
 
-  if ((rp->p = strongprime("p", MP_NEW, nbits/2, r, n, event, ectx)) == 0)
+again:
+  if ((rp->p = strongprime("p", MP_NEWSEC, nbits/2, r, n, event, ectx)) == 0)
     goto fail_p;
-  if ((rp->q = strongprime("q", MP_NEW, nbits/2, r, n, event, ectx)) == 0)
-    goto fail_q;
+
+  /* --- Do painful fiddling with GCD steppers --- */
+
+  {
+    mp *q;
+    rabin rb;
+
+    if ((q = strongprime_setup("q", MP_NEWSEC, &g.jp, nbits / 2,
+                              r, n, event, ectx)) == 0)
+      goto fail_q;
+    g.r = mp_lsr(MP_NEW, rp->p, 1);
+    g.g = MP_NEW;
+    g.max = MP_256;
+    q = pgen("q", q, q, event, ectx, n, pgen_gcdstep, &g,
+                rabin_iters(nbits/2), pgen_test, &rb);
+    pfilt_destroy(&g.jp);
+    mp_drop(g.r);
+    if (!q) {
+      mp_drop(g.g);
+      if (n)
+       goto fail_q;
+      mp_drop(rp->p);
+      goto again;
+    }
+    rp->q = q;
+  }
+
+  /* --- Ensure that %$p > q$% --- *
+   *
+   * Also ensure that %$p$% and %$q$% are sufficiently different to deter
+   * square-root-based factoring methods.
+   */
+
+  phi = mp_sub(phi, rp->p, rp->q);
+  if (MP_LEN(phi) * 4 < MP_LEN(rp->p) * 3 ||
+      MP_LEN(phi) * 4 < MP_LEN(rp->q) * 3) {
+    mp_drop(rp->p);
+    mp_drop(g.g);
+    if (n)
+      goto fail_q;
+    mp_drop(rp->q);
+    goto again;
+  }
+
+  if (phi->f & MP_NEG) {
+    mp *z = rp->p;
+    rp->p = rp->q;
+    rp->q = z;
+  }
 
   /* --- Work out the modulus and the CRT coefficient --- */
 
@@ -85,32 +162,29 @@ int rsa_gen(rsa_param *rp, unsigned nbits, grand *r, unsigned n,
   /* --- Work out %$\varphi(n) = (p - 1)(q - 1)$% --- *
    *
    * Save on further multiplications by noting that %$n = pq$% is known and
-   * that %$(p - 1)(q - 1) = pq - p - q + 1$%.
+   * that %$(p - 1)(q - 1) = pq - p - q + 1$%.  To minimize the size of @d@
+   * (useful for performance reasons, although not very because an overly
+   * small @d@ will be rejected for security reasons) this is then divided by
+   * %$\gcd(p - 1, q - 1)$%.
    */
 
-  phi = mp_sub(MP_NEW, rp->n, rp->p);
+  phi = mp_sub(phi, rp->n, rp->p);
   phi = mp_sub(phi, phi, rp->q);
   phi = mp_add(phi, phi, MP_ONE);
+  phi = mp_lsr(phi, phi, 1);
+  mp_div(&phi, 0, phi, g.g);
 
   /* --- Decide on a public exponent --- *
    *
    * Simultaneously compute the private exponent.
    */
 
-  rp->e = mp_create(1);
-  rp->d = MP_NEW;
-  g = MP_NEW;
-  for (i = 1; i < NPRIME; i++) {
-    rp->e->v[0] = primetab[i];
-    mp_gcd(&g, 0, &rp->d, phi, rp->e);
-    if (MP_CMP(g, ==, MP_ONE))
-      goto good_e;
-  }
-  goto fail_e;
+  mp_gcd(&g.g, 0, &rp->d, phi, rp->e);
+  if (MP_CMP(g.g, !=, MP_ONE) && MP_LEN(rp->d) * 4 > MP_LEN(rp->n) * 3)
+    goto fail_e;
 
   /* --- Work out exponent residues --- */
 
-good_e:
   rp->dp = MP_NEW; phi = mp_sub(phi, rp->p, MP_ONE);
   mp_div(0, &rp->dp, rp->d, phi);
 
@@ -120,13 +194,13 @@ good_e:
   /* --- Done --- */
 
   mp_drop(phi);
-  mp_drop(g);
+  mp_drop(g.g);
   return (0);
 
   /* --- Tidy up when something goes wrong --- */
 
 fail_e:
-  mp_drop(g);
+  mp_drop(g.g);
   mp_drop(phi);
   mp_drop(rp->n);
   mp_drop(rp->q_inv);
@@ -134,6 +208,9 @@ fail_e:
 fail_q:
   mp_drop(rp->p);
 fail_p:
+  mp_drop(rp->e);
+  if (rp->d)
+    mp_drop(rp->d);
   return (-1);
 }