CRYPTANALYSIS APPROACH BASED ON EVOLUTIONARY COMPUTATION

Abstract

This study explores the feasibility of applying evolutionary computation in cryptanalysis, specifically the use of genetic algorithms (GA) to solve the integer factorization problem. The relevance of this research is driven by the fact that the security of the RSA cryptosystem relies heavily on the computational complexity of the factorization problem. Since modern classical subexponential algorithms (e.g., GNFS, QS) face critical difficulties when processing large-scale numbers, there is a need for alternative heuristic approaches. The primary objective of this work is to practically verify the capability of GA in solving the factorization problem. The research methodology is based on formalizing the factorization problem as a combinatorial optimization problem, where the search for divisors is reduced to minimizing an objective error function (two variants of which are considered). The selection of GA as the research tool is justified by its mathematical properties, support for discrete representation, and successful prior application to other cryptanalysis tasks. To validate the method’s effectiveness, the algorithm was preliminarily tested on the frequency cryptanalysis of a simple substitution cipher, demonstrating high decryption accuracy for ciphertexts exceeding 200 characters in length. The results of practical factorization using GA are presented and compared with the classical trial division method. For small numbers (up to 106), the GA operates stably, although it is slower than the classical method. For larger numbers (up to 109), the algorithm demonstrates competitiveness, outperforming trial division in 8 % of cases; however, it exhibits instability. For even larger numbers (up to 1018), the algorithm produced incorrect results due to the precision limitations of the standard float data type. Implementing higher precision (decimal) in the Python environment prevented premature algorithm termination but did not enable the GA to find a solution within an acceptable time limit. Consequently, the genetic algorithm cannot currently be considered a full-fledged replacement for subexponential algorithms when factoring cryptographically significant numbers. However, its application as an auxiliary heuristic tool is entirely viable. The preliminary use of GA can potentially narrow the search space prior to the application of powerful subexponential algorithms, such as GNFS, QS, or ECM.