From 591d081bf68095a6a329240b2caf0bea32219498 Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Wed, 23 Oct 2019 04:12:44 +0100 Subject: [PATCH] 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. --- pub/dh-kcdsa.c | 7 +++++++ 1 file changed, 7 insertions(+) diff --git a/pub/dh-kcdsa.c b/pub/dh-kcdsa.c index f4d0390d..d27bc7d8 100644 --- 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 --- */ -- 2.11.0