Abstract
We consider RSA-type schemes with modulus N=p r q for r ≥ 2. We present two new attacks for small secret exponent d. Both approaches are applications of Coppersmith’s method for solving modular univariate polynomial equations [5]. From these new attacks we directly derive partial key exposure attacks, i.e. attacks when the secret exponent is not necessarily small but when a fraction of the secret key bits is known to the attacker. Interestingly, all of these attacks work for public exponents e of arbitrary size. Additionally, we present partial key exposure attacks for the value d p = d mod p − 1 which is used in CRT-variants like Takagi’s scheme [11]. Our results show that RSA-type schemes that use moduli of the form N=p r q are more susceptible to attacks that leak bits of the secret key than the original RSA scheme.
Chapter PDF
Similar content being viewed by others
References
Boneh, D., Durfee, G.: Cryptanalysis of RSA with private key d less than N0.292. IEEE Trans. on Information Theory 46(4) (2000)
Boneh, D., Durfee, G., Frankel, Y.: An attack on RSA given a small fraction of the private key bits. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 25–34. Springer, Heidelberg (1998)
Boneh, D., Durfee, G., Howgrave-Graham, N.: Factoring N = p rq for large r. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 326–337. Springer, Heidelberg (1999)
Blömer, J., May, A.: New Partial Key Exposure Attacks on RSA. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 27–43. Springer, Heidelberg (2003)
Coppersmith, D.: Small solutions to polynomial equations and low exponent vulnerabilities. Journal of Cryptology 10(4), 223–260 (1997)
Fujioka, A., Okamoto, T., Miyaguchi, S.: ESIGN: An Efficient Digital Signature Implementation for Smartcards. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 446–457. Springer, Heidelberg (1991)
Kocher, P.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996)
Kocher, P., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999)
Stinson, D.: Cryptography Theory and Practice, 2nd edn. CRC Press, Boca Raton (2002)
Okamoto, T., Uchiyama, S.: A new public key cryptosystem as secure as factoring. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 308–318. Springer, Heidelberg (1998)
Takagi, T.: Fast RSA-type cryptosystem modulo pkq. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 318–326. Springer, Heidelberg (1998)
Wiener, M.: Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory 36, 553–558 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
May, A. (2004). Secret Exponent Attacks on RSA-type Schemes with Moduli N=p r q . In: Bao, F., Deng, R., Zhou, J. (eds) Public Key Cryptography – PKC 2004. PKC 2004. Lecture Notes in Computer Science, vol 2947. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24632-9_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-24632-9_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21018-4
Online ISBN: 978-3-540-24632-9
eBook Packages: Springer Book Archive