From 7acba5f3a6ff10f1424c309d0d34d2b713233019 Mon Sep 17 00:00:00 2001 From: Wouter Bolsterlee Date: Fri, 20 Jun 2014 22:07:46 +0200 Subject: Increase attempts for recovering RSA (p,q) from (n,e,d) Bump the maximum number of iterations to recover (p,q) given (n,e,d) to increase the chance that the algorithm succeeds. The algorithm used is a probabilistic one with a 1/2 chance of finding the right value in each iteration, so it's likely that only a few iterations are needed. However, in some extreme cases this may still fail. Bumping the maximum number allow the algorithm to correctly find the right values for these cases. This changes bumps the number of iterations from 50 to 500 (the value 'a' is increased by 2 in each step), and hence reduces the chance of failure from 2**-50 to 2**-500. Note that this change does *not* result in a performance degradation. --- src/_fastmath.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src') diff --git a/src/_fastmath.c b/src/_fastmath.c index c331557..e369f5a 100644 --- a/src/_fastmath.c +++ b/src/_fastmath.c @@ -616,7 +616,7 @@ static int factorize_N_from_D(rsaKey *key) cnt = mpz_scan1(t, 0); mpz_fdiv_q_2exp(t,t,cnt); mpz_set_ui(a, 2); - for (spotted=0; (!spotted) && (mpz_cmp_ui(a,100)<0); mpz_add_ui(a,a,2)) { + for (spotted=0; (!spotted) && (mpz_cmp_ui(a,1000)<0); mpz_add_ui(a,a,2)) { mpz_set(k, t); for (; (mpz_cmp(k,ktot)<0); mpz_mul_ui(k,k,2)) { mpz_powm(cand,a,k,key->n); -- cgit v1.2.1