Cryptanalysis of RSA Using Algebraic and Lattice Methods

Faisal Amir  Harahap; Yusfrizal Yusfrizal; Mutiara Sovina; Ivi Lazuly

doi:10.59934/jaiea.v3i3.507

Authors

Faisal Amir Harahap Universitas Potensi Utama
Yusfrizal Yusfrizal Universitas Potensi Utama
Mutiara Sovina Universitas Potensi Utama
Ivi Lazuly Universitas Potensi Utama

DOI:

https://doi.org/10.59934/jaiea.v3i3.507

Keywords:

Algebraic Techniques, Cryptosystems, Lattices, RSA

Abstract

This paper applies tools from the geometry of numbers to solve several problems in cryptanalysis. We use algebraic techniques to cryptanalyze several public key cryptosystems. This paper focuses on RSA and RSA-like schemes, and use tools from the theory of integer lattices to get our results. We believe that this field is still underexplored, and that much more work can be done utilizing connections between lattices and cryptography. This paper studies the security of the RSA public key cryptosystem under partial key exposure. We show that for short public exponent RSA, given a quarter of the bits of the private key an adversary can recover the entire private key. Similar results (though not as strong) are obtained for larger values of the public exponent e. Our results point out the danger of partial key exposure in the RSA public key cryptosystem. This paper shows that if the secret exponent d used in the RSA public key cryptosystem is less than N0.292, then the system is insecure. This is the first improvement over an old result of Wiener showing that when d is less than N0.25 the RSA system is insecure.

Downloads

Download data is not yet available.

References

M. F. Brown, “Encryption Systems Resilient against Quantum Cracking.” Utica College, 2019.

P. Kestner, “Codes and Secret Messages: From the Ancient Origins of Steganography and Cryptography and their Relevance to Today,” in The Art of Cyber Warfare: Strategic and Tactical Approaches for Attack and Defense in the Digital Age, Springer, 2024, pp. 59–111.

E. Göransson, G. V. M. Haverling, S. O’Sullivan, O. Merisalo, I. Ventura, and P. A. Stokes, “Textual traditions.” De Gruyter, 2020.

A. A. Mohammed and H. A. Anwer, “A New Method Encryption and Decryption.,” Webology, vol. 18, no. 1, 2021.

F. Rubin, Secret Key Cryptography: Ciphers, from Simple to Unbreakable. Simon and Schuster, 2022.

D. D. Kumar, J. D. Mukharzee, C. V. D. Reddy, and S. M. Rajagopal, “Safe and Secure Communication Using SSL/TLS,” in 2024 International Conference on Emerging Smart Computing and Informatics (ESCI), 2024, pp. 1–6.

O. A. Alzubi, J. A. Alzubi, O. Dorgham, and M. Alsayyed, “Cryptosystem design based on Hermitian curves for IoT security,” J. Supercomput., vol. 76, no. 11, pp. 8566–8589, 2020.

A. Bakhtiyor, K. Zarif, A. Orif, and B. Ilkhom, “Algebraic Cryptanalysis of O’zDSt 1105: 2009 Encryption Algorithm,” in 2020 International Conference on Information Science and Communications Technologies (ICISCT), 2020, pp. 1–7.

C. Lee, A. Pellet-Mary, D. Stehlé, and A. Wallet, “An LLL algorithm for module lattices,” in International Conference on the Theory and Application of Cryptology and Information Security, 2019, pp. 59–90.

D. R. Hancock, B. Algozzine, and J. H. Lim, “Doing case study research: A practical guide for beginning researchers,” 2021.

M. Mumtaz and L. Ping, “Forty years of attacks on the RSA cryptosystem: A brief survey,” J. Discret. Math. Sci. Cryptogr., vol. 22, no. 1, pp. 9–29, 2019.

V. K. Chauhan, K. Dahiya, and A. Sharma, “Problem formulations and solvers in linear SVM: a review,” Artif. Intell. Rev., vol. 52, no. 2, pp. 803–855, 2019.

A. May, “Lattice-based integer factorisation: an introduction to coppersmith’s method,” Comput. Cryptogr. Algorithmic Asp. Cryptol., pp. 78–105, 2021.

Z. K. Abdalrdha, I. H. Al-Qinani, and F. N. Abbas, “Subject review: key generation in different cryptography algorithm,” Int J Sci Res Sci Eng Technol, vol. 6, no. 5, pp. 230–240, 2019.

G.-C. Kim, S.-C. Li, and H.-C. Hwang, “Fast rebalanced RSA signature scheme with typical prime generation,” Theor. Comput. Sci., vol. 830, pp. 1–19, 2020.

S. Varghese and S. M. C. Vigila, “A Novel Method for Mapping Plaintext Characters to Elliptic Curve Affine points over Prime Field and Pseudorandom Number Generation,” Int. J. Comput. Inf. Syst. Ind. Manag. Appl., vol. 12, p. 8, 2020.

J. M. Almira, Norbert Wiener: A Mathematician Among Engineers. World Scientific, 2022.