Abstract
Let N = pq be RSA modulus where primes p and q are of the same bit-length. If \(|\rho q - p| = N^{\frac{1}{4}+\gamma}\) where ρ is a known constant satisfying 1 ≤ ρ ≤ 2 and the constant γ satisfies \(0< \gamma< \frac{1}{4}\), we show the factorization attack on N and weak key attack against RSA modulus N. We present algorithms to find the factorization of N in time O(N γ + ε) by some square root attacks, such as the baby-step giant-step method and a more sophisticated square root attack. Using similar techniques of Blömer and May (PKC 2004), we present a weak key attack and find new weak keys over the work of Maitra and Sarkar (ISC 2008).
This research is partially supported by Project 973 (no: 2007CB807902) and the science and technology foundation of the ministry of education (no. 210123) and the natural science foundation in Shandong province (no: Y2008A22) in China.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blömer, J., May, A.: A generalized wiener attack on RSA. In: Bao, F., Deng, R., Zhou, J. (eds.) PKC 2004. LNCS, vol. 2947, pp. 1–13. Springer, Heidelberg (2004)
Coppersmith, D.: Small solutions to polynomial equations and low exponent RSA vulnerabilities. Journal of Cryptology 10(4), 223–260 (1997)
Crandall, R., Pomerance, C.: Prime Numbers, 2nd edn. Springer, Heidelberg (2005)
von zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 2nd edn. Cambridge University Press, Cambridge (2003)
Han, L.D., Xu, G.W.: Generalization of Some Attacks on RSA with Small Prime Combination and Small Private Exponent. In: 2009 Asia-Pacific Conference on Information Processing, vol. 1, pp. 445–449 (2009)
Lang, S.: Introduction to diophantine approximations. Addison-Wesley Pub. Co., Reading (1966)
Lewis, D.J. (ed.): Number Theory Institute 1969. Proceedings of Symposia in Pure Mathematics, vol. 20. American Mathematical Society, Providence RI (1971)
Maitra, S., Sarkar, S.: Revisiting Wiener’s attack - new weak keys in RSA. In: Wu, T.-C., Lei, C.-L., Rijmen, V., Lee, D.-T. (eds.) ISC 2008. LNCS, vol. 5222, pp. 228–243. Springer, Heidelberg (2008)
Maitra, S., Sarkar, S.: Revisiting Wiener’s attack - new weak keys in RSA, http://eprint.iacr.org/2008/228.pdf
Nguyen, P.Q.: Recent Trends in Cryptography. In: Luengo, I. (ed.) Public-Key Cryptanalysis. Contemporary Mathematics series, vol. 477, AMS-RSME (2009)
Pollard, J.M.: Monte Carlo methods for index computation \(\pmod p\). Math. Comp. 32, 918–924 (1978)
Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. of the ACM 21, 120–126 (1978)
Shanks, D.: Class number, a theory of factorization and genera. In: Lewis [7], pp. 415–440 (1971)
de Weger, B.: Cryptanalysis of RSA with small prime difference. Applicable Algebra in Engineering, Communication and Computing 13, 17–28 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Meng, X. (2011). Cryptanalysis of RSA with Small Prime Combination. In: Rhee, KH., Nyang, D. (eds) Information Security and Cryptology - ICISC 2010. ICISC 2010. Lecture Notes in Computer Science, vol 6829. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24209-0_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-24209-0_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24208-3
Online ISBN: 978-3-642-24209-0
eBook Packages: Computer ScienceComputer Science (R0)