Abstract
At Eurocrypt’99, Boneh and Durfee presented a new short secret exponent attack which improves Wiener’s bound (d < N 0.25) up to d < N 0.292. In this paper we show that it is possible to use a short secret exponent which is below these bounds while not compromising with the security of RSA provided that p and q are differing in size and are large enough to combat factoring algorithms. As an example, the RSA system with d of 192 bits, p of 256 bits, and q of 768 bits is secure against all the existing short secret exponent attacks. Besides, in order to balance and minimize the overall computations between encryption and decryption, we propose a variant of RSA such that both e and d are of the same size, e.g., log2 e ≈ log2 d ≈ 568 for a 1024-bit RSA modulus. Moreover, a generalization of this variant is presented to design the RSA system with log2 e + log2 d ≈ log2 N + l k where l k is a predetermined constant, e.g., 112. As an example, we can construct a secure RSA system with p of 256 bits, q of 768 bits, d of 256 bits, and e of 880 bits.
This wok was supported in part by the National Science Council, Taiwan, under contract NSC-88-2213-E-324-007 and NSC88-2213-E-006-025.
Chapter PDF
Similar content being viewed by others
References
Boneh, D., Durfee, G.: Cryptanalysis of RSA with private exponent d < N0.292. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 1–23. Springer, Heidelberg (1999)
Coppersmith, D.: Finding a small root of a univariate modular equation. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 155–165. Springer, Heidelberg (1996)
Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology 10, 233–260 (1997)
Coppersmith, D., Franklin, M., Patarin, J., Reiter, M.: Low-exponent RSA with related messages. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 1–9. Springer, Heidelberg (1996)
Cavallar, S., Lioen, W., te Riele, H., Dodson, B., Lenstra, A., Leyland, P., Montgomery, P.L., Murphy, B., Zimmermann, P.: Factorization of RSA-140 using the Number Field Sieve. In: Proc. of ASIACRYPT 1999. Springer, Heidelberg (1999)
ECMNET Project, http://www.loria.fr/~zimmerma/records/ecmnet.html
Gilbert, H., Gupta, D., Odlyzko, A., Quisquater, J.J.: Attacks on Shamir’s RSA for paranoids. Information Processing Letters 68, 197–199 (1998)
Hastad, J.: On using RSA with low exponent in a public key network. In: Proc. of CRYPTO 1985. LNCS, pp. 403–408. Springer, Heidelberg (1986)
Hastad, J.: Solving simultaneous modular equations of low degree. SIAM J. of Computing 17, 336–341 (1988)
Herstein, I.N.: Topics in Algebra, Xerox Corporation (1975)
Hühnlein, D., Jacobson, M.J., Paulus, S., Takagi, T.: A cryptosystem based on nonmaximal imaginary quadratic orders with fast decryption. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 294–307. Springer, Heidelberg (1998)
Joye, M., Quisquater, J.J., Yen, S.M., Yung, M.: Security paradoxes: how improving a cryptosystem may weaken it. In: Proceedings of the Ninth National Conference on Information Security, Taiwan, May 14-15, pp. 27–32 (1999)
Lenstra, A.: Generating RSA moduli with a predetermined portion. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 1–10. Springer, Heidelberg (1998)
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)
Pinch, R.: Extending the Wiener attack to RSA-type cryptosystems. Electronics Letters 31(20), 1736–1738 (1995)
Rivest, R., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Communication of the ACM 21, 120–126 (1978)
Rivest, R., Silverman, R.D.: Are strong primes needed for RSA? The 1997 RSA Laboratories Seminar series. Seminar Proceedings (1997)
Sakai, R., Morii, M., Kasahara, M.: New key generation algorithm for RSA cryptosystem. IEICE Trans. Fundamentals E77-A(1), 89–97 (1994)
Shamir, A.: RSA for paranoids. CryptoBytes 1(3), 1, 3–4 (1995)
Shamir, A.: Factoring large numbers with the TWINKLE device. In: Eurocrypt 1999 (1999) (presented at)
Silverman, R.D.: Fast generation of random, strong RSA primes. CryptoBytes 3(1), 9–13 (1997)
Silverman, R.D.: The requirement for strong primes in RSA, RSA Laboratories Technical Note, May 17 (1997)
Takagi, T.: Fast RSA-type cryptosystem modulo p2q. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 318–326. Springer, Heidelberg (1998)
Vanstone, S.A., Zuccherato, R.J.: Short RSA keys and their generation. Journal of Cryptology 8, 101–114 (1995)
Verheul, E., van Tilborg, H.: Cryptanalysis of less short RSA secret exponents. In: Applicable Algebra in Engineering, Communication and Computing, vol. 8, pp. 425–435. Springer, Heidelberg (1997)
Wiener, M.: Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory 36(3), 553–558 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sun, HM., Yang, WC., Laih, CS. (1999). On the Design of RSA with Short Secret Exponent. In: Lam, KY., Okamoto, E., Xing, C. (eds) Advances in Cryptology - ASIACRYPT’99. ASIACRYPT 1999. Lecture Notes in Computer Science, vol 1716. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-48000-6_13
Download citation
DOI: https://doi.org/10.1007/978-3-540-48000-6_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66666-0
Online ISBN: 978-3-540-48000-6
eBook Packages: Springer Book Archive