/* -*-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
*
/*----- 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.
*
#include "grand.h"
#include "mp.h"
+#include "mpint.h"
#include "pgen.h"
#include "rsa.h"
#include "strongprime.h"
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 --- */
/* --- 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);
/* --- 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);
fail_q:
mp_drop(rp->p);
fail_p:
+ mp_drop(rp->e);
+ if (rp->d)
+ mp_drop(rp->d);
return (-1);
}