Attacks on Shamir’s ‘RSA for paranoids’. (English) Zbl 1339.94044

Summary: In order to allow for efficient use of extremely large moduli, A. Shamir has proposed a variant of RSA in which one of the two prime factors is much smaller than the other [“RSA for paranoids”, CryptoBytes (The Technical Newsletter of RSA Laboratories) (1995), http://www.rsa.com/rsalabs/cryptobytes/]. This note points out that unless special precautions are taken, simple implementations of Shamir’s idea are subject to protocol attacks that recover the secret keys.


94A60 Cryptography
Full Text: DOI Link


[1] Hastad, J., On using RSA with low exponent in a public key network, (Williams, H. C., Advances in Cryptology—CRYPTO ’85. Advances in Cryptology—CRYPTO ’85, Lecture Notes in Computer Sci., Vol. 218 (1986), Springer: Springer Berlin), 403-408 · Zbl 0635.94008
[2] Joye, M.; Quisquater, J.-J., On the importance of securing your bins: The garbage-man-in-the-middle attack, (Matsumoto, T., 4th ACM Conf. Computer Comm. Security (1997), ACM Press), 135-141
[3] Odlyzko, A. M., The future of integer factorization, CryptoBytes (The Technical Newsletter of RSA Laboratories), 1, 2, 5-12 (1995), and at
[4] Shamir, A., RSA for paranoids, CryptoBytes (The Technical Newsletter of RSA Laboratories), 1, 3, 4 (1995), Available at
[5] Stinson, D. R., Cryptography: Theory and Practice (1995), CRC Press · Zbl 0855.94001
[6] Wiener, M. J., Cryptanalysis of short RSA secret exponents, IEEE Trans. Inform. Theory, 36, 553-558 (1990) · Zbl 0703.94004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.