×

A generalized Wiener attack on RSA. (English) Zbl 1198.94082

Bao, Feng (ed.) et al., Public key cryptography – PKC 2004. 7th international workshop on theory and practice in public key cryptography, Singapore, March 1–4, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21018-0/pbk). Lecture Notes in Computer Science 2947, 1-13 (2004).
Summary: We present an extension of Wiener’s attack on small RSA secret decryption exponents [M. J. Wiener, “Cryptanalysis of short RSA secret exponents”, IEEE Trans. Inf. Theory 36, No. 3, 553–558 (1990; Zbl 0703.94004)]. Wiener showed that every RSA public key tuple (\(N,e\)) with \(e \in {\mathbb{Z}}_{\phi(N)}^*\) that satisfies \(ed-1=0\,\mod\, \phi(N)\) for some \(d<\frac 1 3 N^{\frac 1 4}\) yields the factorization of \(N=pq\). Our new method finds \(p\) and \(q\) in polynomial time for every (\(N,e)\) satisfying \(ex+y = 0\,\mod\, \phi(N)\) with \[ x < \frac 1 3 N^{\frac 1 4} \quad \text{and} \quad |y| = {\mathcal O}(N^{- \frac 3 4}ex). \] In other words, the generalization works for all secret keys \(d= - x y ^{-1}\), where \(x\), \(y\) are suitably small. We show that the number of these weak keys is at least \(N^{\frac 3 4-\epsilon}\) and that the number increases with decreasing prime difference \(p-q\). As an application of our new attack, we present the cryptanalysis of an RSA-type scheme presented by S.-M. Yen, S. Kim, S. Lim and S. Moon [“RSA speedup with residue number system immune against hardware fault cryptanalysis”, Lect. Notes Comput. Sci. 2288, 397–413 (2002; Zbl 0999.94539)]. Our results point out again the warning for crypto-designers to be careful when using the RSA key generation process with special parameters.
For the entire collection see [Zbl 1049.94003].

MSC:

94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI