RSA Cryptanalysis: An Elitist Genetic Algorithm for Integer Factorization

The problem of Integer Factorization deals with the disintegration of an integer into prime factors. This has direct applications in cryptanalysis, particularly in breaking the RSA. Lately, scientists have investigated the scope of employing metaheuristic approaches to perform integer factorization in bounded time. This paper improves the state-of-the-art by incorporating the concept of elitism, removal of redundancy, as well as diminishing the effect of exploitation in a genetic algorithm (GA) model. This enabled us to factor integers up to 22 decimal digits (≈ 70 bits) with a higher rate of success and quicker convergence on a standard desktop, thereby breaking the bottleneck of existing metaheuristic approaches. By design, the proposed metaheuristic approach is population based and can process the intermediate steps by means of independent calculations. Hence, it can be easily parallelized and scaled up for factorizing larger integers.