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: 848 PDF Downloads: 597
Copyright (c) 2025 Roman Shkliarskyy, Danyil Zhuravchak
This work is licensed under a Creative Commons Attribution 4.0 International License.
