math/, pub/: Generate primes with exactly the right size.

[catacomb] / pub / rsa-gen.c

diff --git a/pub/rsa-gen.c b/pub/rsa-gen.c
index a7a2ca4ef4955c2357e6de50d0747f916c221593..0653d1c3b2dafaf1bd2ca1b9eaadf0282e518790 100644 (file)
--- a/pub/rsa-gen.c
+++ b/pub/rsa-gen.c
@@ -77,20 +77,30 @@ again:
   if ((rp->p = strongprime("p", MP_NEWSEC, nbits/2, r, n, event, ectx)) == 0)
     goto fail_p;
 
-  /* --- Do painful fiddling with GCD steppers --- */
+  /* --- Do painful fiddling with GCD steppers --- *
+   *
+   * Also, arrange that %$q \ge \lceil 2^{N-1}/p \rceil$%, so that %$p q$%
+   * has the right length.
+   */
 
   {
     mp *q;
+    mp *t = MP_NEW, *u = MP_NEW;
     rabin rb;
 
     if ((q = strongprime_setup("q", MP_NEWSEC, &g.jp, nbits / 2,
                               r, n, event, ectx)) == 0)
       goto fail_q;
+    t = mp_lsl(t, MP_ONE, nbits - 1);
+    mp_div(&t, &u, t, rp->p);
+    if (!MP_ZEROP(u)) t = mp_add(t, t, MP_ONE);
+    if (MP_CMP(q, <, t)) q = mp_leastcongruent(q, t, q, g.jp.m);
+
     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);
+            rabin_iters(nbits/2), pgen_test, &rb);
     pfilt_destroy(&g.jp);
     mp_drop(g.r);
     if (!q) {