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

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

Ashish Jain (Indian Institute of Technology Indore, Indore, India & Manipal University Jaipur, Jaipur, India) and Narendra S. Chaudhari (Indian Institute of Technology Indore, Indore, India)
Copyright: © 2019 |Pages: 22
DOI: 10.4018/IJAMC.2019040105

Abstract

Searching secret key of classical ciphers in the keyspace is a challenging NP-complete problem that can be successfully solved using metaheuristic techniques. This article proposes two metaheuristic techniques: improved genetic algorithm (IGA) and a new discrete cuckoo search (CS) algorithm for solving a classical substitution cipher. The efficiency and effectiveness of the proposed techniques are compared to the existing tabu search (TS) and genetic algorithm (GA) techniques using three criteria: (a) average number of key elements correctly detected, (b) average number of keys examined before determining the required key, and (c) the mean performance time. As per the results obtained, the improved GA is comparatively better than the existing GA for criteria (a) and (c), while the proposed CS strategy is significantly better than rest of the algorithms (i.e., GA, IGA, and TS) for all three criteria. The obtained results indicate that the proposed CS technique can be an efficient and effective option for solving other similar NP-complete combinatorial problems also.
Article Preview
Top

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 × 1028 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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2020): 3 Released, 1 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing