pub/dh-kcdsa.c: Retry or fail if we don't get the target sizes.

Following the usual convention, we retry unless the caller gave us a
bounded number of steps, and otherwise fail.

I think failure is fairly unlikely now.  To find an N-bit prime, we
expect to take about 4 N steps (see analysis in `math/strongprime.c').
But we're trying to find two primes simultaneously, one of N bits, and
one of M bits, so this will take about 16 M N steps in total.  We start
with v < 2^{N-M-1}, and choose 2^{M-1} <= q_0 < 2^M such that 2^{N-1} <
p_0 = 2 q_0 v + 1 < 2^N (nearly true).  We'll fail if 2^M - q_0 < 16 M N,
which seems unlikely, or if 2^N - p_0 < 32 M N v, i.e., 2^M - p_0/(2 v) <
16 M N, which is basically the same condition.

diff --git a/pub/dh-kcdsa.c b/pub/dh-kcdsa.c
index f4d0390..d27bc7d 100644 (file)
--- a/pub/dh-kcdsa.c
+++ b/pub/dh-kcdsa.c
@@ -70,6 +70,7 @@ int dh_kcdsagen(dh_param *dp, unsigned ql, unsigned pl,
 
   /* --- First trick: find %$v$% --- */
 
+retry:
   pf.step = 2;
   x = mprand(x, pl - ql - 1, r, 1);
   x = pgen("v", x, x, ev, ec,
@@ -95,6 +96,12 @@ int dh_kcdsagen(dh_param *dp, unsigned ql, unsigned pl,
   dp->p = sp[1].u.x;
   if (!dp->q)
     goto fail_1;
+  if (mp_bits(dp->q) != ql || mp_bits(dp->p) != pl) {
+    if (steps) goto fail_1;
+    MP_DROP(dp->p);
+    MP_DROP(dp->q);
+    goto retry;
+  }
 
   /* --- Third trick: find a generator --- */