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].

94A60 Cryptography
Full Text: DOI