Substitution cipher was broken using frequency analysis already in the 9th century. By using more ciphertext symbols the frequency distribution is flattened which makes cracking more difficult. This cipher is named homophonic substitution cipher. It is not possible to break it using only pencil and paper. In this thesis, the problem of breaking the homophonic substitution cipher is presented as an optimization problem, which is then successfully solved by a combination of two heuristic algorithms. We compare simulated annealing and Tabu search with each other and inspect the impact of the use of bigrams and trigrams on cracking. Performance is mainly influenced by the length of the ciphertext and the complexity of the cipher key. Our implementation broke as many as 57% of the most difficult test cases and 98% of the easiest ones.
|
