# zbMATH — the first resource for mathematics

Correcting errors in RSA private keys. (English) Zbl 1283.94067
Rabin, Tal (ed.), Advances in cryptology - CRYPTO 2010. 30th annual cryptology conference, Santa Barbara, CA, USA, August 15–19, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-14622-0/pbk). Lecture Notes in Computer Science 6223, 351-369 (2010).
Summary: Let $$pk= (N,e)$$ be an RSA public key with corresponding secret key ${\mathsf sk}=(p,q,d,d_p,d_q, q_p^{-1}).$ 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 $$\widetilde{\mathsf sk}$$ we reconstruct the original sk by correcting the faults.
More precisely, consider an error rate of $$\delta \in [0,\frac 1 2)$$, where we flip each bit in sk with probability $$\delta$$ resulting in an erroneous key $$\widetilde{\mathsf sk}$$. Our Las-Vegas type algorithm allows to recover sk from $$\widetilde{\mathsf sk}$$ in expected time polynomial in $$\log N$$ with success probability close to 1, provided that $$\delta < 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 $$\delta < 0.084$$.
For the entire collection see [Zbl 1194.94022].

##### MSC:
 94A60 Cryptography
##### Keywords:
RSA; error correction; statistical cryptanalysis
Full Text: