We use lattice basis reduction for ciphertext-only attack on RSA. Our attack is applicable in the conditions when known attacks are not applicable, and, contrary to known attacks, it does not require prior knowledge of a part of a message or key, small encryption key, ⥌, or message broadcasting. Our attack is successful when a vector, comprised of a message and its exponent, is likely to be the shortest in the lattice, and meets Minkowski's Second Theorem bound. We have conducted experiments for message, keys, and encryption/decryption keys with sizes from 40 to 8193 bits, with dozens of thousands of successful RSA cracks. It took about 45 seconds for cracking 2001 messages of 2050 bits and for large public key values related with Euler’s totient function, and the same order private keys. Based on our findings, for RSA not to be susceptible to the proposed attack, it is recommended avoiding RSA public key form used in our experiments.

[1] Ali H. and Al-Salami M., “Timing Attack Prospect for RSA Cryptanalysis Using Genetic Algorithm Technique,” The International Arab Journal of Information Technology, vol. 1, no. 1, pp. 80-85, 2004.

[2] Alimorad R. and Arkian H., “Integer Factorization Implementations,” ICTACT Journal on Communication Technolgy, vol. 7, no. 2, pp. 1310-1314, 2016.

[3] Belhaj S. and Kahla H., “on the Complexity of Computing the GCD of two Polynomials via Hankel Matrices,” ACM Communications in Computer Algebra, vol. 46, no. 3/4, pp. 74-75, 2013.

[4] Berkovits S., “Factoring Via Superencryption,” Cryptologia, vol. 6, no. 3, pp. 229-237, 182.

[5] Biswas S. and Tiwari N., “Attacks and Threats on RSA,” in Proceedings of Emerging Technologies in Data Mining and Information Security, pp. 737-747, 2018.

[6] Bleichenbacher D., “On the Security of the KMOV Public Key Cryptosystem,” in Proceedingsof Annual International Cryptology 246 The International Arab Journal of Information Technology, Vol. 18, No. 2, March 2021 Conference Lecture Notes in Computer Science, Santa Barbara, pp. 235-248, 1997.

[7] Boneh D., “Twenty Years of Attacks on the RSA Cryptosystem,” Notices of the AMS, vol. 46, no. 2, pp. 203-213, 1999.

[8] Boneh D. and Durfee G., “Cryptanalysis of RSA with Private Key d Less than N^0:292,” in Proceedings of Eurocrypt'99 Proceedings of the 17th International Conference on Theory and Application of Cryptographic Techniques, Berlin, pp. 1-11, 1999.

[9] Boneh D. and Durfee G., “Cryptanalysis of RSA with Private Key d Less Than N0.292,” IEEE Transactions on Information Theory, vol. 46, no. 4, pp. 1339-1349, 2006.

[10] Boneh D., Durfee G., and Frankel Y., “An Attack on RSA Given A Small Fraction of The Private Key Bits,” in Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Beijing, pp. 25-34, 1998.

[11] Boneh D., Joux A., and Nguyen P., “Why Textbook Elgamal and RSA Encryption Are Insecure,” in Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Kyoto, pp. 30-43, 2000.

[12] Bunder M., Nitaj A., Susilo W., and Tonien J., “A Generalized Attack on RSA Type Cryptosystems,” Theoretical Computer Science, vol. 704, pp. 74-81, 2017.

[13] Coppersmith D., “Finding A Small Root of A Bivariate Integer Equation, Factoring with High Bits Known,” in Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques, Lecture Notes in Computer Science, Saragossa, pp. 178-189, 1996.

[14] Coppersmith D., “Finding a Small Root of a Univariate Modular Equation,” in Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques, Saint-Malo, pp. 155-165, 1996.

[15] Coppersmith D., Franklin M., Patarin J., and Reiter M., “Low Exponent RSA With Related Messages,” in Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques, Lecture Notes in Computer Science, Saragossa, pp. 1-91, 996.

[16] DeLaurentis J., “A Further Weakness in the Common Modulus Protocol for the RSA Cryptoalgorithm,” Cryptologia, vol. 8, no. 3, p. 253-259, 1984.

[17] Ghafar A., Ariffin M., and Asbullah M., “A New LSB Attack on Special-Structured RSA Primes,” Symmetry, vol. 12, no. 5, pp. 1-13, 2020.

[18] Gradshteyn I., Ryzhik I., Jeffrey A., and Zwillinger D., Table of Integrals, Series, and Products, Sixth Edition 6th Edition, Academic Press, 2000.

[19] Hastad J., “On using RSA with Low Exponent in A Public Key Network,” in Proceedings of Conference on the Theory and Application of Cryptographic Techniques, Lecture Notes in Computer Science, Santa Barbara, pp. 403-408, 1985.

[20] Hastad J., “Solving Simultaneous Modular Equations of Low Degree,” Society for Industrial and Applied Mathematics, vol. 17, no. 2, pp. 336- 341, 1988.

[21] Hoffstein J., Howgrave-Graham N., Pipher J., and Whyte W., The LLL Algorithm, Springer Link, 2009.

[22] Hoffstein J., Pipher J., and Silverman J., “NTRU: A Ring-Based Public Key Cryptosystem,” in Proceedings of International Algorithmic Number Theory Symposium, Portland, pp. 267- 288, 1988.

[23] Hoffstein J., Pipher J., and Silverman J., An Introduction to Mathematical Cryptography, Springer Link, 2014.

[24] Hoffstein J., Silverman J., and Whyte W., “Estimated Breaking Times for NTRU Lattices Updated 2003,” Technical Report, 1999.

[25] “IEEE Standard Specification for Public Key Cryptographic Techniques Based on Hard Problems Over Lattices,” 2009.

[26] Jamnig P., “Securing The RSA-Cryptosystem Against Cycling Attacks,” Cryptologia, vol. 12, no. 3, pp. 159-164, 1988.

[27] Kirchner P. and Fouque P., “Revisiting Lattice Attacks on Overstretched NTRU Parameters,” in Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, Part I, Lecture Notes in Computer Science, Paris, pp. 3-26, 2017.

[28] Kleinjung T., Aoki K., Franke J., Lenstra A., Thomé E., Bos J., Gaudry P., Kruppa A., Montgomery P., Osvik D., Riele H., Timofeev A., and Zimmermann P., “Factorization of A 768-Bit RSA Modulus,” in Proceedings of Annual Cryptology Conference, Santa Barbara, pp. 333-350, 2010.

[29] Lenstra A., Lenstra H., and Lovasz L., “Factoring Polynomials with Rational Coefficients,” Mathematische Annalen, vol. 261, no. 4, pp. 515- 534, 1982.

[30] Lenstra A. and Verheul E., “Selecting Cryptographic Key Sizes,” Journal of Cryptology, vol. 14, pp. 255-293, 2001.

[31] May A., in The LLL Algorithm-Survey and Applications, Springer Link, 2009.

[32] Micciancio D., “Shortest Vector Problem,” in Encyclopedia of Algorithms., pp. 1974-1977, 2016. Ciphertext-Only Attack on RSA Using Lattice Basis Reduction 247

[33] Moriarty J., Kaliski B., Jonsson J., and Rusch A., “PKCS# 1: RSA Cryptography Specifications Version 2.2.,” Technical Report 2016.

[34] Mumtaz M. and Ping L., “Forty Years of Attacks on the RSA Cryptosystem: A Brief Survey,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 22, no. 1, pp. 9-29, 2019.

[35] Nguyen P. and Valle B., The LLL Algorithm: Survey and Applications, Springer Link, 2009.

[36] Rabah K., “Review of Methods for Integer Factorization Applied to Cryptography,” Journal of Applied Sciences, vol. 6, no. 1, pp. 458-481, 2006.

[37] Rivest R., “Remarks on A Proposed Cryptanalytic Attack on The M.I.T. Public-Key Cryptosystem,” Cryptologia, vol. 2, no. 1, pp. 62- 65, 1978.

[38] Rivest R., Shamir A., and Adleman L., “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM, vol. 21, no. 2, pp. 120-126, 1978.

[39] Shoup V., NTL: A Library For Doing Number Theory. https://www.shoup.net/ntl/, Last Visited, 2020.

[40] Simmons G., “A “weak” Privacy Protocol Using The RSA Crypto Algorithm,” Cryptologia, vol. 7, no. 2, pp. 180-182, 1983.

[41] Simmons G. and Norris M., “Preliminary Comments on The M.I.T. Public Crypto- System,” Cryptologia, vol. 1, no. 4, pp. 406-414, 1977.

[42] Takayasu A. and Kunihiro N., “Partial Key Exposure Attacks on RSA: Achieving the Boneh- Durfee Bound,” in Proceedings of International Conference on Selected Areas in Cryptography, Montreal, pp. 345-362, 2014.

[43] Takayasu A. and Kunihiro N., “Partial Key Exposure Attacks on RSA: Achieving The Boneh-Durfee Bound,” Theoretical Computer Science, vol. 761, pp. 51-77, 2019.

[44] Thome E., LISTSERV. https://listserv.nodak.edu/cgibin/wa.exe?A2=NM BRTHRY;fd743373.1912&S, Last Vested, 2020.

[45] Weger B., “Cryptanalysis of RSA with Small Prime Difference,” Applicable Algebra in Engineering, Communication, and Computing, vol. 13, 2002.

[46] Wiener M., “Cryptanalysis of Short RSA Secret Exponents,” IEEE Transactions on Information Theory, vol. 36, no. 3, pp. 553-558, 1990.

[47] Wikipedia. https://en.wikipedia.org/wiki/RSA_Factoring_Ch allenge Last Vested 2020.

[48] Wu M., Chen C., Lin Y., and Sun H., “On the Improvement of Wiener Attack on RSA with Small Private Exponent,” The Scientific World Journal, pp. 1-9, 2014.

[49] Yan S., Cryptographic attacks on RSA, Springer Link, 2008.

[50] Yang Z., Fu S., Qu L., and Li C., “A Lower Dimension Lattice Attack on NTRU,” Science China Information Sciences, vol. 61, no. 5, p. 1- 9, 2018.

[51] Zimmermann P., https://lists.gforge.inria.fr/pipermail/cado-nfs- discuss/2020-February/001166.html, Last Visted, 2020.