Correcting Errors in RSA Private Keys 12:10 Mon 23 Apr 12 :: 5.57 Ingkarni Wardli :: Mr Wilko Henecka :: University of Adelaide
Let pk=(N,e) be an RSA public key with corresponding secret key sk=(d,p,q,...). Assume that we obtain partial error-free information of sk, e.g., assume that we obtain half of the most significant bits of p. Then there are well-known algorithms to recover the full secret key. As opposed to these algorithms that allow for correcting erasures of the key sk, we present for the first time a heuristic probabilistic algorithm that is capable of correcting errors in sk provided that e is small. That is, on input of a full but error-prone secret key sk' we reconstruct the original sk by correcting the faults.
More precisely, consider an error rate of d in [0,1), where we flip each bit in sk with probability d resulting in an erroneous key sk'. Our Las-Vegas type algorithm allows to recover sk from sk' in expected time polynomial in logN with success probability close to 1, provided that d is strictly less than 0.237. We also obtain a polynomial time Las-Vegas factorization algorithm for recovering the factorization (p,q) from an erroneous version with error rate d strictly less than 0.084.