An Improved Genetic Algorithm and A New Discrete Cuckoo Algorithm for Solving the Classical Substitution Cipher

Introduction

Cryptology has two divisions’ cryptography and cryptanalysis that are not completely disjoint. Cryptography is related to developing ciphers, while cryptanalysis is related to finding flaws or oversights in the ciphers. For communicating confidential information over the insecure public channel encryption algorithm is used. The encryption algorithm is an important component of the cipher that uses a secret key to transform the given plaintext (the message or information) into a ciphertext, i.e., in a code which is very difficult to decode (or detect) without knowing the secret key. In fact, detecting secret key is a challenging NP-complete problem in theoretical computer science (Menezes et al., 1996; Stinson, 2005; Castro and Viñuela, 2005; Danziger and Henriques, 2012; Awad and El-Alfy, 2015; Holden, 2017). The brute-force strategy can be used to search secret key of the cipher in the keyspace. However, in the worst case, the entire keyspace will be traversed by the brute-force strategy. For instance, if the key size of a substitution cipher is 27, then there are 27! = 1.088 × 10²⁸ keys. If a supercomputer is available that could verify a billion-billion '27-tuple' keys per second, would require about 345 years. Hence, these ciphers are secure from brute-force attacks, since the keyspace dimension is so large, the resources and time are not available for searching the key. On the other hand, metaheuristics are capable to the search secret key of ciphers in a considerable time by mounting automated cryptanalytic attacks (Castro and Viñuela, 2005; Danziger and Henriques, 2012; Bhateja et al., 2015; Jain and Chaudhari, 2015a). Automated attacks are run without time-consuming interaction of humans with a search process and finish when the secret key is determined (Bhateja et al., 2015; Jain and Chaudhari, 2015a). Due to this advantage of automated attacks, a large number of cryptanalysts are interested to develop such attacks. The research in the area of application of metaheuristics in automated attacks was first reported in 1993 (Matthews, 1993; Spillman et al., 1993; Forsyth and Naini 1993), and the results have proven that metaheuristics are highly effective for this purpose.

For determining secret key, the automated attack strategy may use just the known ciphertexts (i.e., encrypted plaintexts), some plaintexts, and intelligent algorithms. If the attacker (or cryptanalyst) recover the secret key by using the “known ciphertexts” only, then this kind of attack is referred as a ciphertext-only attack (Menezes et al., 1996; Stinson, 2005; Holden, 2017). This type of attack is most demanding and challenging, therefore, in this work, we demonstrate such attacks using metaheuristic techniques. For a systematic demonstration of automated attacks, the well-known classical substitution cipher is considered. One can ask why modern ciphers are not considered to demonstrate metaheuristic attacks. The fact is that metaheuristics cannot be applied to attack modern ciphers such as DES (data encryption standard), AES (advanced encryption standard), and RSA (Rivest–Shamir–Adleman), because unsuitability in designing the fitness function for modern ciphers (Castro and Viñuela, 2005; Danziger and Henriques, 2012; Awad and El-Alfy, 2015). However, cryptanalysis of classical ciphers (an NP-complete problem) can be carried out using metaheuristics because the fitness function can be well-designed by using expected and observed n-gram statistics of the language (Castro and Viñuela, 2005; Danziger and Henriques, 2012; Awad and El-Alfy, 2015). For solving NP-complete permutation problems, this paper proposes an enhanced genetic algorithm and a new discrete cuckoo search strategy. As an application, we employ the proposed algorithms to solve the classical substitution cipher.