Factorization Algorithm for Semi-primes and the Cryptanalysis of Rivest-Shamir-Adleman (RSA) Cryptography

Richard Omollo *

Department of Computer Science and Software Engineering, School of Informatics and Innovative Systems, Kenya and Jaramogi Oginga Odinga University of Science and Technology, Box 210-40601, Bondo, Kenya.

Arnold Okoth

Department of Computer Science and Software Engineering, School of Informatics and Innovative Systems, Kenya and Jaramogi Oginga Odinga University of Science and Technology, Box 210-40601, Bondo, Kenya.

*Author to whom correspondence should be addressed.


Abstract

This paper introduces a new factoring algorithm called Anorld’s Factorization Algorithm that utilizes semi-prime numbers and their implications for the cryptanalysis of the Rivest-Shamir-Adleman (RSA) cryptosystem. While using the concepts of number theory and algorithmic design, we advance a novel approach that notably enhances the efficiency of factoring large semi-prime numbers compared to other algorithms that have been developed earlier. In our approach, we propose a three-step algorithm that factorizes relatively large semi-primes in polynomial time. We have introduced factorization up to 12-digit semi-prime using Wolfram|Alpha, a mathematical software suitable for exploring polynomials. Additionally, we have discussed the implications of the new algorithm for the security of RSA-based cryptosystems. In conclusion, our research work emphasizes the important role of factoring algorithms in the cryptanalysis of RSA cryptosystems and proposes a novel approach that bolsters the efficiency and effectiveness of semi-prime factorization, thereby informing the development of more powerful cryptographic protocols.

Keywords: Arnold’s Factorization Algorithm (A.F.A.), modular factorial, euclidean algorithm, RSA cryptography


How to Cite

Omollo, R., & Okoth , A. (2024). Factorization Algorithm for Semi-primes and the Cryptanalysis of Rivest-Shamir-Adleman (RSA) Cryptography. Asian Journal of Research in Computer Science, 17(6), 85–95. https://doi.org/10.9734/ajrcos/2024/v17i6458

Downloads

Download data is not yet available.

References

Sattar J Aboud, Mohammad A AL-Fayoumi, Mustafa Al-Fayoumi, Haidar S Jabbar. An efficient RSA public key encryption scheme. Fifth international conference on information technology: New generations. IEEE Computer Society; 2008.

Michael NJ, Ogoegbulem O, Obukohwo V, Egbogho HE. Number Theory in RSA Encryption Systems. GPH – International Journal of Mathematics. 2023;6:11.

Richard Omollo, Arnold Okoth. Large Semi Primes Factorization with Its Implications to RSA Cryptosystems. BOHR International Journal of Smart Computing and Information Technology. 2022;3(1):1–8.

Douglas R, Stinson, Maura B. Paterson. Cryptography Theory and Practice 4th Edition. CRC Press; 2019.

Dirk B, Artur E, Anton Z. The Physics of Quantum Information. XIV – 315, Springer; 2000.

Matthew H. Quantum Computing and Shor’s Algorithm. 2015;1-7.

Adjie Wahyu Wicaksono, Arya Wicaksana. Implementation of Shor’s quantum factoring algorithm using project Q framework. International Journal of Engineering and Advanced Technology (IJEAT) ISSN: 2249-8958 (Online). 2019; 8(6S3).

Arun Bhalla, Kenneth Eguro, Matthew Hayward. Quantum Computing, Shor’s Algorithm, and Parallelism; 2015.

Gil Kalai, Yosef Rinott, Tomer Shoham. Google’s 2019 Quantum Supremacy Claims: Data Documentation, and Discussion; 2022 Available:https://www.arxiv.org

Jeffrey Shallit. Origins of the Analysis of the Euclidean Algorithm. Historia Mathematica. 1994;21:401-419.

Carlos M Falcon Rodriguez, Maria A. Garcia Cruz, Claudia Falcon. Full Euclidean Algorithm by Means of a Steady Walk. Applied Mathematics. 2021;12: 269-279

Anton Iliev, Nikolay Kyurkchiev, Asen Rahnev. A New Improvement Euclidean Algorithm for Greatest Common Divisor. I. Neural, Parallel, and Scientific Computations. 2018;26(3):355-362.

ISSN: 1061-5369

Franz Lemmermeyer. The Euclidean Algorithm in Algebraic Number Fields. Mathematics Subject Classification; 2004.

Wan Nur Shaziayani Wan Mohd Rosly, Sharifah Sarimah Syed Abdullah, Fuziatul Norsyiha Ahmad Shukri. The uses of Wolfram Alpha in Mathematics. Articles of Teaching and Learning in Higher Education. 2020;1:96 – 103.

Hiyam, Bataineh, Ali Zoubi, Abdalla Khataybeh. Utilizing MATHEMATICA Software to Improve Students’ Problem Solving Skills of Derivative and its Applications. International Journal of Education and Research. 2019;7(11): 57– 70.

Mohammed Muniru Iddrisu, Kodjoe Isaac Tetteh. The Gamma Function and Its Analytical Applications”. Journal of Advances in Mathematics and Computer Science. 2017;23(3):1-16.

Yingpu Deng and Yanbin Pan. An Algorithm for Factoring Integers. CiteSeerX; 2018.

Peter L. Montgomery. A Survey of Modern Integer Factorization Algorithms. CWI Quarterly. 1994;7(4):337 – 365.

David CW Muir. Factoring Integers using Geometry; 2022.

Seema Kute, Chitra Desai, Mukti Jadhav. Analysis of factoring algorithms for number factorization. International Journal of Creative Research Thoughts. 2023;11(3): 735 – 740.

Abdelmajid Hassan Mansour. Analysis of RSA Digital Signature Key Generation using Strong Prime. International Journal of Computer (IJC). 2017;24(1):28-36.

Venkateswara Rao Pallipamu, Thammi Reddy K, Suresh Varma P. Design of RSA Digital Signature Scheme Using A Novel Cryptographic Hash Algorithm. International Journal of Emerging Technology and Advanced Engineering. June 2014;4(6).

Farah Jihan Aufa; Endroyono, Achmad Affandi. Security System Analysis in Combination Method: RSA Encryption and Digital Signature Algorithm. 4th International Conference on Science and Technology (ICST); 2018.

Om Pal and Bashir Alam. Diffie-Hellman Key Exchange Protocol with Entities Authentication. International Journal of Engineering and Computer Science. April 2017;6(4):20831-20839

Chiradeep Gupta, Subba Reddy NV. Enhancement of security of Diffie-hellman key exchange protocol using RSA Cryptography. Journal of Physics: Conference Series; 2021.

Shahid Mubeen, Abdur Rehman. (n, k)-FACTORIALS. Journal of Inequalities and Special Functions 2014;5(3):14-20. URL: http://www.ilirias.com ISSN: 2217-4303

Babu G. Properties of Combination Using Double Factorial. International Journal of Science and Research (IJSR); 2016.

Bo Xiong, Yimin Huang, Steffen Staab, Zhenguo Li. MOFA: Modular Factorial Design for Hyper-Parameter Optimization; 2020 Available:https://www.arxiv.org

Man-Hong Yung. Quantum supremacy: Some fundamental concepts. Oxford University Press; 2017.

Neetu Settia. Cryptanalysis of modern cryptographic algorithms. International Journal of Computer Science and Technology. 2010;1(2):166 – 169.

Ibrahim Marouf, Mohammed Mosab Asad, Qasem Abu Al-Haija. Comparative Study of Efficient Modular Exponentiation Algorithms. COMPUSOFT. An International Journal of Advanced Computer Technology. August 2017;6(8): 2381– 2389.

Anthony Overmars, Sitalakshmi Venkatraman. A New Method for Factorizing Semi-Primes Using Simple Polynomials. 3rd International Conference on Research in Applied Science. 2020;25 – 30.

Anthony Overmars, Sitalakshmi Venkatraman. A fast factorisation of semi-primes using sum of squares. Mathematical and Computational Application; 2019.

Anthony Overmars, Sitalakshmi Venkatraman. New Semi-Prime Factoriza-tion and Application in Large RSA Key Attacks. Journal of Cybersecurity and Privacy; 2021.

A Fast Factorization of Semi Primes Using Sum of Squares. 2019;11-12.

Adeniyi Abidemi Emmanuel, Okeyinka Aderemi E, Adebiyi Marion O, Asani Emmanuel O. A Note on Time and Space Complexity of RSA and El Gamal Cryptographic Algorithms. IJACSA) International Journal of Advanced Computer Science and Applications. 2021;12(7).

Keita Emura, Atsuko Miyaji, Kazumasa Omote, Akito Nomura, Masakazu Soshi. A Ciphertext-Policy Attribute-Based Encryption Scheme with Constant Ciphertext Length. Conference Paper in International Journal of Applied Cryptography· November 2009. Japan Advanced Institute of Science and Technology; 2009.

Zhengping Jay Luo, Ruowen Liu, Aarav Mehta. Understanding the RSA algorithm”. ACM Vol. 1, No. 1, Article. Publication date: August 2023; 2023.

Robert Erra, Christophe Grenier. The Fermat factorization method revisited; 2009 Available:https://eprint.iacr.org/2009/318.pdf