Study of the Vulnerabilities of the RSA Algorithm Through Factorization Attacks Implemented with Quantum Computing Techniques
Abstract
Purpose: to investigate the risks to information security posed by quantum attacks, in particular, using the Shor algorithm for factorizing large numbers using the Qiskit library.
Method: theoretical analysis of the literature and practical modeling based on quantum programming in Qiskit; implementation of simulation of Shor's algorithm for factorization of a composite number.
Findings: The Shor algorithm for factorizing small composite numbers was simulated in the Qiskit environment. The resources required to crack RSA-2048 with quantum computers were estimated. The modern standards of post-quantum cryptography (CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON, SPHINCS+) are investigated. It is shown that the introduction of post-quantum algorithms is critical for maintaining data security in the future.
Theoretical implications: deepening the understanding of the impact of quantum computing on traditional cryptography; analysis of the fundamental principles of quantum factorization and their importance for cryptanalytics.
Practical implications: Companies can use the results to plan the transition to post-quantum cryptographic standards, which will reduce the risks of “Harvest Now, Decrypt Later” attacks and strengthen the long-term security of critical data.
Value: The work demonstrates that the active integration of quantum-resistant security methods is a prerequisite for maintaining data security in the transition period of quantum technologies.
Future research: analysis of the effectiveness of new post-quantum algorithms in various security protocols, optimization of key size and signing speed under real-world loads, development of hybrid models of classical and quantum-secure cryptography.
Paper type: empirical study.
Purpose: to investigate the risks to information security posed by quantum attacks, in particular, using the Shor algorithm for factorizing large numbers using the Qiskit library.
Method: theoretical analysis of the literature and practical modeling based on quantum programming in Qiskit; implementation of simulation of Shor's algorithm for factorization of a composite number.
Findings: The Shor algorithm for factorizing small composite numbers was simulated in the Qiskit environment. The resources required to crack RSA-2048 with quantum computers were estimated. The modern standards of post-quantum cryptography (CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON, SPHINCS+) are investigated. It is shown that the introduction of post-quantum algorithms is critical for maintaining data security in the future.
Theoretical implications: deepening the understanding of the impact of quantum computing on traditional cryptography; analysis of the fundamental principles of quantum factorization and their importance for cryptanalytics.
Practical implications: Companies can use the results to plan the transition to post-quantum cryptographic standards, which will reduce the risks of “Harvest Now, Decrypt Later” attacks and strengthen the long-term security of critical data.
Value: The work demonstrates that the active integration of quantum-resistant security methods is a prerequisite for maintaining data security in the transition period of quantum technologies.
Future research: analysis of the effectiveness of new post-quantum algorithms in various security protocols, optimization of key size and signing speed under real-world loads, development of hybrid models of classical and quantum-secure cryptography.
Paper type: empirical study.
Downloads
References
Chuang, I.L., Gershenfeld, N., Kubinec, M. (1998). Experimental Implementation of Fast Quantum Searching. Physical Review Letters, 80(15), pp. 3408–3411. https://doi.org/10.1103/PhysRevLett.80.3408.
Whyte, S. (2024). QUANTUM CRYPTOGRAPHY AND ITS IMPLICATIONS IN CYBERSECURITY: SECURING COMMUNICATION IN THE QUANTUM ERA. International Journal of Computer Science and Information Technology.
Sharma, M. та ін. (2021). Leveraging the power of quantum computing for breaking RSA encryption. Cyber-Physical Systems, 7, pp. 73–92.
Boutin, C. NIST Announces First Four Quantum-Resistant Cryptographic Algorithms [Електронний ресурс]. Available from: https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms. Accessed: April 27, 2025.
Beauregard, S. (2002). Circuit for Shor’s Algorithm Using 2n+3 Qubits.
Shor, P.W. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 26(5), pp. 1484–1509. https://doi.org/10.1137/S0097539795293172.
DiVincenzo, D.P., Shor, P.W. (1996). Fault-Tolerant Error Correction with Efficient Quantum Codes. Physical Review Letters, 77(15), pp. 3260–3263. https://doi.org/10.1103/PhysRevLett.77.3260.
García-Martín, D., Sierra, G. (2018). Five Experimental Tests on the 5-Qubit IBM Quantum Computer. Journal of Applied Mathematics and Physics, 6, pp. 1460–1475.
Fouque, P.-A., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., Prest, T., Ricosset, T., Seiler, G., Whyte, W., Zhang, Z. (2020). Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU. Specification v1.2. [Електронний ресурс]. Available from: https://falcon-sign.info/falcon.pdf. Accessed: April 27, 2025.
Boutin, C. NIST Releases First 3 Finalized Post-Quantum Encryption Standards [Електронний ресурс]. Available from: https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards. Accessed: April 27, 2025.
Schaumann, J. (2024). Post-Quantum Cryptography in January 2024 [Електронний ресурс]. Available from: https://www.netmeister.org/blog/pqc-2024-01.html. Accessed: November 27, 2024.
Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., Stehlé, D. (2017). CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme. IACR Cryptology ePrint Archive, 2017/633. [Електронний ресурс]. Available from: https://eprint.iacr.org/2017/633.pdf. Accessed: April 27, 2025.
Derevianko, Ya.A., Gorbenko, I.D. (2022). FALCON signature vulnerability to special attacks and its protection. Radiotekhnika, 210, pp. 37–52. https://doi.org/10.30837/rt.2022.3.210.03.
Pathum, U. (2024). CRYSTALS Kyber: The Key to Post-Quantum Encryption [Електронний ресурс]. Available from: https://medium.com/@hwupathum/crystals-kyber-the-key-to-post-quantum-encryption-3154b305e7bd. Accessed: November 26, 2024.
Bernstein, D.J., Hülsing, A., Cybercrypt, S.K., Niederhagen, R., Rijneveld, J., Schwabe, P. (2019). The SPHINCS+ Signature Framework.
Deig, J. (2024). New Standards to Head Off Quantum Cyberthreats. Cisco Newsroom. [Електронний ресурс]. Available from: https://newsroom.cisco.com/c/r/newsroom/en/us/a/y2024/m07/new-standards-to-head-off-quantum-cyberthreats.html. Accessed: April 27, 2025.
Kasirajan, V. (2021). Fundamentals of Quantum Computing. Cham: Springer International Publishing. https://doi.org/10.1007/978-3-030-63689-0.
Gidney, C., Ekerå, M. (2021). How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum, 5, p. 433. https://doi.org/10.22331/q-2021-04-15-433.
Abstract views: 8 PDF Downloads: 11
Copyright (c) 2025 Roman Shkliarskyy, Danyil Zhuravchak
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors agree with the following conditions:
1. Authors retain copyright and grant the journal right of first publication (Download agreement) with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
2. Authors have the right to complete individual additional agreements for the non-exclusive spreading of the journal’s published version of the work (for example, to post work in the electronic repository of the institution or to publish it as part of a monograph), with the reference to the first publication of the work in this journal.
3. Journal’s politics allows and encourages the placement on the Internet (for example, in the repositories of institutions, personal websites, SSRN, ResearchGate, MPRA, SSOAR, etc.) manuscript of the work by the authors, before and during the process of viewing it by this journal, because it can lead to a productive research discussion and positively affect the efficiency and dynamics of citing the published work (see The Effect of Open Access).
