From bb2e2fd89f5577ebbaaf6b721a48dea9f27ea4cd Mon Sep 17 00:00:00 2001 From: mdw Date: Sat, 17 Jun 2000 12:05:15 +0000 Subject: [PATCH] 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. --- rsa-gen.c | 123 ++++++++++++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 100 insertions(+), 23 deletions(-) diff --git a/rsa-gen.c b/rsa-gen.c index 056d245..159357f 100644 --- 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); } -- 2.11.0