/* -*-c-*-
*
- * $Id: rsa-gen.c,v 1.1 1999/12/22 15:50:45 mdw Exp $
+ * $Id$
*
* RSA parameter generation
*
* MA 02111-1307, USA.
*/
-/*----- Revision history --------------------------------------------------*
- *
- * $Log: rsa-gen.c,v $
- * Revision 1.1 1999/12/22 15:50:45 mdw
- * Initial RSA support.
- *
- */
-
/*----- Header files ------------------------------------------------------*/
#include <mLib/dstr.h>
#include "grand.h"
#include "mp.h"
+#include "mpint.h"
#include "pgen.h"
#include "rsa.h"
#include "strongprime.h"
/* --- @rsa_gen@ --- *
*
- * Arguments: @rsa_param *rp@ = pointer to block to be filled in
+ * Arguments: @rsa_priv *rp@ = pointer to block to be filled in
* @unsigned nbits@ = required modulus size in bits
* @grand *r@ = random number source
* @unsigned n@ = number of attempts to make
* possible.
*/
-int rsa_gen(rsa_param *rp, unsigned nbits, grand *r, unsigned n,
+int rsa_gen(rsa_priv *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;
+
+ /* --- Bits of initialization --- */
- /* --- Generate strong primes %$p$% and %$q$% --- */
+ rp->e = mp_fromulong(MP_NEW, 0x10001);
+ rp->d = MP_NEW;
- if ((rp->p = strongprime("p", MP_NEW, nbits/2, r, n, event, ectx)) == 0)
+ /* --- 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.
+ */
+
+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 (MP_NEGP(phi)) {
+ mp *z = rp->p;
+ rp->p = rp->q;
+ rp->q = z;
+ }
/* --- Work out the modulus and the CRT coefficient --- */
rp->n = mp_mul(MP_NEW, rp->p, rp->q);
- rp->q_inv = MP_NEW; mp_gcd(0, 0, &rp->q_inv, rp->p, rp->q);
+ rp->q_inv = mp_modinv(MP_NEW, rp->q, rp->p);
/* --- 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_EQ(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);
}