Genetic algorithm for cryptanalysis on the Vigenere cipher.

摘要

Cryptology encompasses cryptography and cryptanalysis. Cryptography is the process of protecting information by encrypting it into an unreadable format. Cryptanalysis is the process of obtaining the original message from an encrypted message without knowledge of the key. A genetic algorithm (GA) is a search method based on natural selection and genetic inheritance. This study investigate how the use of genetic algorithms may lead to efficient cryptanalysis of a poly-alphabetic substitution cipher, the Vigenere cipher. Frequency analysis is used to measure the performance of each key generated by the genetic algorithm. For the frequency analysis to work, it is important to incorporate different types of texts into the file used to calculate the expected frequencies. Different parameters and techniques for the population size, crossover, mutation and selection were explored. Higher values for the population size, crossover rate, mutation rate, and crossover type may help to improve the accuracy of the genetic algorithm, but may also add computational time and complexity. It is important to maintain a balance between these combination of parameters, which depend on each others. Overall, the population size of 20 was the most efficient, providing good accuracy and time performance, and a mutation rate of 0.01 proved to be the best choice. The crossover rate of 1 provided better performances, but the crossover rates of 0.6 and 0.8 were also efficient. The elitist strategy improves significantly the overall performance of the genetic algorithm. In general, the GA-based approach could lead to faster and automated cryptanalysis techniques, given that a suitable fitness function can be implemented.