A Comparison between Single and Multi- Crossover Pointsto Break Hill Cipher Using Heuristic Search: MA & GA

Abstract

Hill cipher is a classical cipher which is based on linear algebra. In this method, matrices and matrix multiplication have been used to combine the plaintext.Heuristic search is a search techniques. The methods of HS are: (GA, SE, EP, MA, TS). Genetic algorithms are one of Heuristic search, it is search techniques which is used natural selection. GAs select optimal solution through three operations, they are : selection, crossover and mutation. The parameters are kept in memory and the best values of fitness have been selected to represent next generation.Memetic Algorithm is one of Heuristic search , a memetic algorithm is an extension of the traditional genetic algorithm. It uses a local search technique to reduce the likelihood of the convergence, to reach the best solution. This paper focuses on using MA and GA to find optimal solution to cryptanalyse Hill cipher. Then comparing two methods of crossover to see which one has best solution, and comparing between GA and MA to see which one has best solution.MATLAB is used as M-FILE.Theresults ofcryptanalysis cleared as following:- 1- Without genetic algorithms: The number of correct letters for the key was 1 out of 9. 2- Using genetic algorithms: two methods are used, and they have been compared of crossover, they are single and multi- crossover points randomly. After (250) generation, the number of correct letters was 4 out of 9 when single crossover point is used. The number of correct letters was 8 out of 9 when multi crossover point are used. So multi crossover point have best solution. Genetic algorithms are applied successfully.3- Using Memetic Algorithms. After (100) generation, the number of correct letters was 8 out of 9. So MA is better than Genetic algorithms.4- the number of correct letter was 9 out of 9 when the MA is used.