Time Complexity Analysis of Attacking RSA Using Probabilistic Factorization Algorithm in Python
Soraya Triutami Dewi, Richy Vernando Yolandito, Faisal Faisal · 2024
This paper analyzes the time complexity of attacks on the RSA cryptosystem by focusing on the factoring of the modulus n. The RSA algorithm is widely used for secure data transmission, and its security relies on the computational difficulty of factoring large integers. This study delves into the mathematical foundations of these attacks, specifically the probabilistic algorithm for factoring$n$as outlined by Stein. The paper presents a mathematical model of factoring n attack, focusing on its time complexity analysis. The paper also provides a Python implementation of this cryptanalytic attack and evaluates its performance for different bit keys. The results highlight the efficiency of the algorithm to perform cryptanalytic attacks with different key sizes and the importance of using sufficiently large key lengths to maintain security against such attacks.