cipher is a secret way of writing in which plaintext is converted into a scrambled (encrypted) version of the original message (ciphertext) by using a key. Those who know the key can easily decrypt the ciphertext back into the plaintext. Cryptanalysis is the study of breaking ciphers that is finding the key or converting the ciphertext into the plaintext without knowing the key. Many cryptographic systems have a finite key space and, hence, are vulnerable to an exhaustive key search attack. Yet, these systems remain secure from such an attack because the size of the key space is such that the time and resources for a search are not available. Optimization techniques have got a significant importance in determining efficient solutions of different complex problems. One such problem is to break S-DES. This paper considers cryptanalysis of S-DES. In the brute force attack, the attacker tries each and every possible key on the part of cipher text until desired plaintext is obtained. A brute force approach may take so much time to guess the real key which is used to generate a cipher text, so the difficulty of breaking the cipher is directly proportional to the number of keys. On the other hand optimization technique can be used for the same purpose. Genetic algorithm is an evolutionary algorithm that works well and takes less time to break cipher as compared to Brute force attack.

The remaining paper is organized as follows: Section II discusses the earlier works done in this field. Section III presents overview of S-DES and Section IV gives the overview of Genetic Algorithm. Experimental results are discussed in Section V.Conclusion are presented in section VI At last References are given.

In the last few years, so many papers have been published in the field of cryptanalysis. R.Spillman etc. showed that Knapsack cipher [4] and substitution ciphers [5] could be attacked using genetic algorithm. In the recent years Garg[1,2] presented the use of memetic algorithm and genetic algorithm to break a simplified data encryption standard algorithm. Nalini [3] used efficient heuristics to attack S-DES. In 2006 Nalini used GA, Tabu search and Simulated Annealing techniques to break S-DES. Matusi [7] showed the first experimental cryptanalysis of DES using an linear cryptanalysis technique. Clark [6] also presented important analysis on how different optimization techniques can be used in the field of cryptanalysis. Vimalathithan [9] also used GA to attack Simplified-DES. In this paper, a Genetic Algorithm with improved parameters is used to break S-DES.A population of keys is generated and their fitness is calculated by using efficient fitness function. At the end, we will find the key in less time.

In this section we will provide the overview of S-DES Algorithm. Simplified DES, developed by Professor Edward Schaefer of Santa Clara University is an educational rather than a secure encryption algorithm. The S-DES [8,10] encryption algorithm takes an 8-bit block of plaintext and a 10-bit key as input and produces an 8-bit block of ciphertext as output. The S-DES decryption algorithm takes an 8-bit block of ciphertext and the same 10-bit key used to produce that ciphertext as input and produces the original 8-bit block of plaintext. The encryption algorithm involves five functions: an initial permutation (IP); a complex function labeled f K , which involves both permutation and substitution operations and depends on a key input; a simple permutation function that switches (SW) the two halves of the data; the function f K again; and finally a permutation function that is the inverse of the initial permutation (IP -1 ).

The function f K takes as input not only the data passing through the encryption algorithm, but also an 8bit key. S-DES uses a 10-bit key from which two 8-bit subkeys are generated. In this, the key is first subjected to a permutation (P10). Then a shift operation is performed. The output of the shift operation then passes through a permutation function that produces an 8-bit output (P8) for the first subkey (K 1 ). The output of the shift operation also feeds into another shift and another instance of P8 to produce the second subkey (K 2 ).  The S-boxes operate as follows:

The first and fourth input bits are treated as 2-bit numbers that specify a row of the S-box and the second and third input bits specify a column of the Sbox. The entry in that row and column in base 2 is the 2-bit output.


# The Switch Function

The function f K only alters the leftmost 4 bits of the input. The switch function (SW) interchanges the left and right 4 bits so that the second instance of f K operates on a different 4 bits. In this second instance, the E/P, S0, S1, and P4 functions are the same. The key input is K2.

The genetic algorithm [13,20] is a search algorithm based on the natural selection and on "survival of the fittest", the main idea is that in order for a population of individuals to adapt to some environment, it should behave like a natural system. This means that survival and reproduction of an individual is promoted by the elimination of useless traits and by rewarding useful behavior. The genetic algorithm belongs to the family of evolutionary algorithms. An evolutionary algorithm maintains a population of solutions for the problem at hand. The population is then evolved by the iterative application of a set of stochastic operators. The simplest form of genetic algorithm involves three types of operators: selection, crossover and mutation. A selection operator is applied first.  In this paper, we are using Ring crossover operator [11].In ring crossover two parents such as parent1 and parent2 are considered for the crossover process, and then combined in the form of ring, as shown in fig. 4 decided in any point of ring. The children are created with a random number generated in any point of ring according to the length of the combined two parental chromosomes. With reference to the cutting point, while one of the children is created in the clockwise direction, the other one is created in direction of the anticlockwise, as shown in fig. 4(c). Then swapping and reversing process is performed in the Ring Crossover operator, as shown in fig. 4(d).

Figure 4 : Ring Crossover Procedure [11] The primary goals of this work are to produce a performance comparison between traditional Brute force search algorithm and genetic algorithm with improved parameters based method, and to determine the use of typical GA-based methods in the field of cryptanalysis.

The procedure to carry out the cryptanalysis using GA in order to break the key is as follows 1. Input: ciphertext, and the language statistics. 2. Randomly generate an initial pool of solutions (keys). 
C K = (i Ã) |K (i) u -D(i) u | + (i, j Ã) | K (i, j) b -D (i, j) b | + (i,j,k Ã)|K(i,j,k) t -D(i,j,k) t | (!)
Our objective in this paper is to compare the results obtained from Brute Force search algorithm with the Genetic Algorithms with improved parameters. The experiments were conducted on Core chromosome, the more times it is likely to be selected to reproduce. Crossover : Crossover selects genes from is parent chromosomes and creates a new offspring. The simplest way to do this is to choose randomly some crossover point and everything before this point is copied from the first parent and then, everything after a crossover point copied from the second parent. Mutation : After a crossover, mutation is performed. This is to prevent falling all solutions in population into a local optimum of solved problem. Mutation changes randomly the new offspring. In binary GA we can switch a few randomly chosen bits from 1 to 0 or from 0 to 1.  From the above table, it is found that both GA works better than Brute force algorithm in terms of time taken as well as obtaining number of key bits.  In this paper, we have used a Genetic algorithm with Ring crossover and other operators for the cryptanalysis of Simplified Data Encryption Standard. We found that Genetic Algorithm is far better than Brute Force search algorithm for cryptanalysis of S-DES. Although S-DES is a simple encryption algorithm, GA with Ring Crossover method can be adopted to handle other complex block ciphers like DES and AES. 
1![Figure 1: Simplified Data Encryption Algorithm a) Initial and Final Permutations The input to the algorithm is an 8-bit block of plaintext, which we first permute using the IP function IP= [2 6 3 1 4 8 5 7].This retains all 8-bits of the plaintext but mixes them up. At the end of the algorithm, the inverse permutation is applied; the inverse permutation is done by applying, IP -1 = [4 1 3 5 7 2 8 6] where we have IP -1 (IP(X)) =X. b) The Function f K The function f k , which is the complex component of S-DES, consists of a combination of permutation and substitution functions. The functions are given as follows. Let L, R be the left 4-bits and right 4-bits of the input, then, f K (L, R) = (L XOR f(R, key), R) Where XOR is the exclusive-OR operation and key is a sub -key. Computation of f(R, key) is done as follows.](image-2.png "Figure 1 :")
2![Figure 2 : Working of S-box](image-3.png "Figure 2 :")
![Journal of Computer Science and Technology Volume XII Issue V Version I 2012 March c) Selection : This selection operator selects chromosomes in the population for reproduction. The better the](image-4.png "Global")
3![Figure 3 : Flow chart of Genetic Algorithm [19]](image-5.png "Figure 3 :")
3![Calculate the fitness value of each of the solutions in the pool using equation (1). 4. Create a new population by repeating following steps until the new population is complete a. Select parent (keys) from a current population according to their fitness value (the better fitness, the bigger chance to be selected). Here Tournament selection is used. b. With a crossover probability cross over the parents to form new offspring (childrens). In our genetic algorithm we are using Ring Crossover Operator c. For each of the children, perform a mutation operation with some mutation probability to generate new children. d. Place new children in the new population 5. Use new generated population for a further run of the algorithm 6. If the end condition is satisfied, stop, and return the best solution in current population a) Cost Function Equation (1) is a general fitness function used to determine the suitability of a assumed key (k). Here, A denotes the language alphabet (i.e., for English, [A... Z, _ ], where _ represents the space symbol), K and D denote known language statistics and decrypted message statistics, respectively, and the u, b, and t denote the unigram, digram and trigram statistics respectively; , and are the weights assigning different weights to each of the three statistics where + + = 1. In view of the computational complexity of trigram, only unigram and digram statistics are used.](image-6.png "3 .")
2![Duo system. There are a variety of cost functions used by other researchers in the past. The most common cost function uses gram statistics. Some use a large amount of grams © 2012 Global Journals Inc. (US) Global Journal of Computer Science and Technology Volume XII Issue V Version I 57 2012 March (b). Later, a random cutting point is](image-7.png "2")
5![Figure 5 : comparison of Genetic algorithm and Brute Force Search algorithm](image-8.png "Figure 5 :")
6![Figure 6 : The running time comparison of Genetic Algorithm and Brute Force Search Algorithm](image-9.png "Figure 6 :")
![1. G Poonam, Memetic Algorithm Attack on Simplified Data Encryption Standard algorithm, proceeding of International Conference on Data Management, February 2008, pg 1097-1108 Computer Science and Technology Volume XII Issue V Version I](image-10.png "")
GA ParametersThe following are the GA parameters usedduring the experimentation:Population Size: 100Selection : Tournament Selection operatorCrossover Ring CrossoverCrossover: .85Mutation: .02No. of Generation: 50GeneticAlgorithmBrute ForceSearchAlgorithm
1Force Search Algorithm.S.AmountNo. ofNo. ofTimeTimeNoofbitsbitsTakenTakenCiphermatchedmatcheby GAbyTextusingd using(M)BruteGABruteForceForcesearchsearch(M)1.200554.724.32.400432.124.73.600761.923.64.800873.124.15.1000972.625.16.1200982.125.5
			© 2012 Global Journals Inc. (US) Global Journal of Computer Science and Technology Volume XII Issue V Version I
			© 2012 Global Journals Inc. (US)
		
		
			

				


* 
	
		Genetic algorithm Attack on Simplified Data Encryption Standard Algorithm
		
			GargPoonam
		
	
	
		International journal Research in Computing Science
		
			
			2006
		
	




* 
	
		Cryptanalysis of S-DES via Optimization heuristics
		
			Nalini
		
	
	
		International Journal of Computer Sciences and network security
		
			6
			1B
			Jan 2006
		
	




* 
	
		Cryptanalysis of Knapsack Ciphers Using Genetic Algorithms
		
			RSpillman
		
	
	
		Cryptologia XVII
		
			4
			
			1993
		
	




* 
	
		Use of A Genetic Algorithm in the Cryptanalysis of simple substitution Ciphers
		
			RSpillman
		
		
			MJanssen
		
		
			BNelson
		
		
			MKepner
		
	
	
		Cryptologia XVII
		
			1
			
			1993
		
	




* 
	
		Optimisation Heuristics for the Automated Cryptanalysis of Classical Ciphers
		
			ClarkA
		
		
			DawsonEd
		
	
	
		Journal of Combinatorial Mathematics and Combinatorial Computing
		
			28
			
			1998
		
	




* 
	
		Linear cryptanalysis method for DES cipher
		
			MMatsui
		
	
	
		Lect. Notes Comput. Sci
		
			765
			
			1994
		
	




* 
	
		Cryptography and Network Security Principles and Practices, Third Edition
		
			WilliamStallings
		
		
			2003
			Pearson Education Inc
		
	




* 
	
		Cryptanalysis of SDES Using Genetic Algorithm
		
			MR LVimalathithan
		
		
			Valarmathi
		
	
	
		International Journal of Recent Trends in Engineering
		
			2
			4
			
			November 2009
		
	




* 
	
		A Simplified Data Encryption Standard Algorithm
		
			ESchaefer
		
	
	
		Cryptologia
		
			20
			1
			
			1996
		
	




* 
	
		A Novel Crossover Operator for Genetic Algorithms: Ring Crossover
		
			Y?lmazKaya
		
		
			MuratUyar
		
		
			RamazanTekdn
		
		
	




* 
	
		Handbook of Genetic Algorithm
		
			LDavis
		
		
			1991
			Van Nostrand Reinhold
			New York
		
	




* 
	
		Genetic algorithms in search. Optimization and Machine Learning
		
			DEGoldberg
		
		Reading. M.A. addison -Wesley
		
			1989
		
	




* 
	
		Evolutionary optimization of constrained problems
		
			A
		
		
			Michalewiez
		
		
			NAttia
		
	
	
		InProc.3rd annu. Conf. on Evolutionary Programming
				
			1994
			
		
	




* 
	
		Genetic algorithms+ Data structures = Evolution programs
		
			ZMichalewicz
		
		
			1996
			springer
			New York
		
	
	3rd ed




* 
	
		A Course on number theory and cryptography
		
			NKoblitz
		
		
			1994
			Springer-Verlag New York,Inc
		
	




* 
	
		
		
			JAlfred
		
		
			Menezes
		
		
			Menezes
		
	
	
		Alfred J. Handbook of Applied Cryptography
		
			1997
			CRC
		
	




* 
	
		Breaking Transposition Cipher with Genetic Algorithhm Electronics and Electrical Engineering
		
			RToemeh
		
		
			SArumugam
		
		
			2007
		
	




* 
	
		Multi-objective Optimization using Evolutionary Algorithms
		
			KalyanmoyDeb
		
		
			2001
			John Wiley and Sons
		
	




* 
	
		Studying chaos via 1-Dmaps-atutorial
		
			CWWu
		
		
			NFRulkov
		
	
	
		IEEE Trans. on Circuits and Systems I: Fundamental Theory and Applications
		
			40
			10
			
			1993