RSA Cryptanalysis: A Novel Acceleration for Euler-Based Fermat Factorization Algorithm

Abstract

The Rivest-Shamir-Adleman (RSA) cryptosystem is an efficient and secure method for transmitting data over the Internet. Breaking this system primarily relies on the integer factorization problem, which involves factoring a composite odd number, n, into two prime factors, p and q. Euler-based Fermat Factorization (EFF) is one of the factoring methods based on the modular multiplication operation and is efficient when δ = p − q ≤ n^0.25. However, the execution times of the EFF algorithm increase significantly with large values of n and δ > n^0.25. In this paper, we propose a novel technique for optimizing the number of modular multiplication operations required to find the two factors. The method can factor a large odd number in a fast time, even when δ > n^0.25. For different values of the length of the primes and δ, the experimental results indicate that the proposed algorithm is, on average, 85.5% faster than the previous improvements on the Fermat factorization method.