International Journal of Research in Computer Science

eISSN 2249-8265 Volume 2 Issue 3 (2012) pp. 7-10

© White Globe Publications
www.ijorcs.org

A NOVEL APPROACH TO GENETIC ALGORITHM

BASED CRYPTOGRAPHY
Farhat Ullah Khan1, Surbhi Bhatia2
1
Assiatant Professor, Amity University
Email: fukhan@amity.edu
2
Student M. Tech, Amity University
Email: surbhibhatia1988@yahoo.com

Abstract: Cryptography is immensely essential binary. Standard Genetic operators like mutation and
ingredient of network security. Public Key crossover have been applied to the population to
Cryptography, one of the most important forms of improve the quality of the sample. The technique
cryptography, requires the key to be unique and non- proposed has been explained in the following section
repeating. There are two ways of producing the key. and results have been explicated. The work produces a
One is rigorous mathematically strong algorithmic decent sample satisfying most of the test. In the future
approach like AES and the other is the approach that we intend to check the strength of key generated by
mimics nature. The work presented explores various exposing the cipher text to various attacks.
attempts that have been made in this direction and
suggests a new technique using Genetic Algorithms. II. CRYPTOGRAPHY
The technique has been implemented and analyzed. The application of Genetic Algorithm and
The results obtained are encouraging. The samples cryptography has been discussed in some of the works
satisfy most of the tests including gap test, frequency [1], [2]. In most of the cases GA approach has been
test etc thus strengthening the belief that the algorithm applied to decrypt simple ciphers. In the security
is as strong, if not better than any of the analysis cipher attacked included monoalphabetic
mathematically strong approach. substitution cipher, transposition, permutation, vernam
Keywords: Cryptography, Genetic Algorithms, One cipher etc.
Time Pad, Vernam Cipher. Monoalphabetic Substitution Cipher: A key consist
of all the possible permutation of an alphabet which
I. INTRODUCTION when replaced may lead to the deciphering of the text.
Genetic Algorithms (GAs) being optimization To handle the problems of monoalphabetic
algorithms unite ‘survival of the fittest’ and a substitution, other methods like polyalphabetic
simplified version of Genetic course [1]. A thorough substitution and permutation, transposition cipher are
study on the success of GAs in cryptography was used. The permutation cipher is applied to a block of
carried out by Benthany Delman [2]. The work takes ciphers while columns transposition is applied to the
GA as base for generating the key and proposes a entire text at once.
novel technique to produce a key which can substitute Vernam Cipher- It is a stream cipher in which a binary
One Time Pad (OTP) in the Vernam Cipher. The key key string of the same length to produce a cipher text
produced is non-repeating and thus making the cipher such that
almost unbreakable. GAs in spite of being random c[i] = p[i] + k[i]
have the ability to make the population converge to the Where c[i] = ith character of the cipher text, k[i] = ith
desired point using a fitness function [1].The technique character of the key, P[i] = ith character of the
has been implemented and the randomness of the plaintext.
population generated was calculated. The experiments
carried out recognized the ability of GAs to produce a In the work proposed, the intention is to create a
good quality random sample. If the key of the Vernam key as strong if not stronger than the vernam cipher. If
Cipher is selected from that sample then it is found to the key is randomly chosen and never used again, the
be better as compared to existing PRNG. Many cipher is called one time pad [1], [2]. The one time pad
attempts have been made to accomplish the above task is theoretically unbreakable [1], [2], [3]. The
using GAs. Some of them open the door for further cryptanalysis can at maximum guess the key in which
exploration in the field. The work carries forward one case a very large number of guesses for the key to be
such attempt [1] and analyses the effect of the changes correct can ensure the near unbreakability of the cipher
proposed. The initial population taken in the work is [4].

www.ijorcs.org
8 Farhat Ullah Khan, Surbhi Bhatia
III. SECURITY OF THE KEY 1) Reproduction Operator: Reproduction is done on
the basis of Rowlett Wheel selection .It selects
In the literature review, it was found that the
chromosomes from the initial population and enters
characteristics that determine the strength of the key
them into the mating procedure.
are not quantifiable but matrices might be used for
evaluating and comparing cryptographic algorithm [5]. 2) Crossover Operator: Crossover Rate (0 to 1)
The characteristics that are considered are determines the probability of producing a new
Type: Symmetric or Asymmetric; Functions: chromosome form the parents. For example, the strings
Integrity and authentication of message; Key size and 10000100 to 11111111 could be crossed over after the
rounds; and the complexity of the algorithm. The third locus in each to produce the two offspring
attacks that can be carried out so as to test the strength 10011111 to 11100100. The crossover operator
of the algorithm are brute force, factoring and roughly mimics biological recombination between two
differential cryptanalysis. The matrices that have been single-chromosomes (haploid) organisms.
used to judge the effect of these attacks are based on 3) Mutation Operator: It randomly changes its genetic
the key length and complexity of the algorithm. makeup. This operator randomly flips some of the bits
in a chromosome. For example, the string 00000100
IV. GENETIC ALGORITHMS might be mutated in its second position to yield
Genetic Algorithms are adaptive search procedures 01000100. Mutation can occur at each bit position in a
which are footed on Charles Darwin theory of the string with some probability, usually very small (e.g.,
survival of the fittest [6]. The concept behind these 0.001) [6], [7], [8].
algorithms was to imitate the randomness of the
nature. So, GAs follows nature to a great extent. GAs V. PROPOSED WORK
produce a population in such a way that the attribute The process of generating the key from the Genetic
which is trendy, that is, has higher fitness value is Population has the following steps
replicated more, as is done by the nature. This is also
the fundamental concept behind evolution. So, these In the first step a binary population is generated.
algorithms are also referred as the evolutionary Each cell is generated using the pseudo random
algorithms. number generator of the programming language. The
number generated is one if the PRNG generates a
Genetic Algorithms (GAs) are search procedures to number greater than 50 else it is 0. Each chromosome
converge to optimal solution based on the theory of contains 25 such cells and the number of chromosomes
survival of the fittest. The basic entity of GA is in the experiment was taken as 1000.
chromosome. Each chromosome symbolizes a solution
to the problem and is composed of a string of cells of Now for each chromosome we repeat the following
finite length. The binary alphabet {0, 1} is often used process:
to represent these cells but integers can be used Divide the chromosome into 5 groups.
depending on the application. The fitness value is a Calculate the number of ones in each group.
function or rationale against which chromosome is If the number of one’s is greater than 2 then
tested for its suitability to the problem in hand. the new array will have 1 as its cell otherwise 0.
A. Steps In Genetic Algorithms The above step converts the population of
chromosomes having 25 cells as one having 5 cells.
A brief overview of the steps involved in Genetic Now we have a 5X 1000 array with us.
Algorithms is as follows.
The array is then read vertically 25 cells at the time.
Step 1. A population having P individuals are randomly The first column followed by the second and so on.
generated by pseudo random generators whose
individuals may represent a feasible solution. The above step gives us an array of 25 X 200
This is a representation of solution vector in a which serves as the population now. This is followed
solution space and is called initial solution. This by crossover and mutation operators being applied to
guarantees the search to be unbiased, as it starts the sample.
from wide range of points in the solution space.
Now each cell is multiplied by 2(12-i) where ’I’ is the
Step 2. Individual members of the population are
cell number. This generates a sample of 200 numbers.
evaluated to find the objective function value.
Step 3. In the third step, the objective function is Each number is then converted into an integer. The
mapped into a fitness function that computes a process is repeated 5 times. The coefficient of auto
fitness value for each member of the population. correlation is then calculated. If the result is favorable
This is followed by the application of GA then the population is accepted else the whole process
operators. is repeated.

www.ijorcs.org
A Novel Approach to Genetic Algorithm Based Cryptography 9
VI. EXAMPLE If the Coefficient of Correlation is satisfactory, then
random chromosome is selected which is taken as key
If the original population was a 5*5 population
otherwise, the process is repeated.
where the cells are generated randomly.
10010 VII. RESULTS AND CONCLUSIONS
10101
The work has been implemented and analyzed. The
11101
implementation has been done in C#. Samples have
00101 been collected and analyzed in Microsoft Excel,
01011 Various tests have been applied on the sample and
most of them give satisfactory results.
The above population is read vertically. New array
would be Since, around a 400 values were analyzed and no
11100 repetition was obtained therefore frequency test was
00101 not applied. The coefficient of autocorrelation was
01110 calculated for k = 1 to k = 10. The result for k = 1 was
10001 0.03, thus indicating a good random sample. Karl
Pearson Coefficient of correlation has been calculated,
01111
also giving satisfactory data.
Any two random numbers are generated from 0 to
In the analysis of data, a correlogram is an image of
5, say, 2nd and 4th chromosome.
correlation statistics. In time series analysis, a
One point crossover is performed as shown below: correlogram, also known as an autocorrelation plot, is
a plot of the sample autocorrelations versus (the
00101
time lags). The correlogram is a commonly used tool
10001 for checking randomness in a data set. This
Taking the crossover point, COP= 2. The chromosome randomness is ascertained by computing
becomes autocorrelations for data values at varying time lags. If
00001 random, such autocorrelations should be near zero for
any and all time-lag separations. If non-random, then
After crossover has been performed, then mutation one or more of the autocorrelations will be
is done by selecting a random chromosome and significantly non-zero.
flipping from amongst those chromosomes.
The majority was calculated by taking a group of
11110 10 cells. If more samples are needed then a set of 5
cells can also be taken. The whole process needs to be
The number of times the crossover is to be
enhanced, analyzed and put to more stringent tests.
performed is given by the formula: Number of
Moreover it was also observed that the sample
crossovers = Number of cells in each chromosome*
obtained distribute almost equally between data
Number of chromosomes* Crossover Rate/ 100
samples.
The number of times the mutation is to be
performed is given by the formula: Number of
Mutations = Number of cells in each chromosome*
Number of chromosomes* Mutation Rate/ 100
Once the task is accomplished, then Coefficient of
Correlation of the above is calculated by taking k=1, 2,
and 3.
The coefficient of autocorrelation is defined as
follows.
Given measurements, Y1, Y2, ..., YN at time X1, X2,
..., XN, the lag k autocorrelation function is defined as

∑𝑁−𝑘 � �
𝑖=1 (𝑌𝑖 −𝑌)(𝑌𝑖+𝑘 −𝑌)
𝑟𝑘 = 𝑁
∑ (𝑌𝑖 −𝑌�)2
[11] Figure 1: Scatter Diagram of Samples Obtained
𝑖=1

www.ijorcs.org
10 Farhat Ullah Khan, Surbhi Bhatia
IX. REFERENCES
[1] Harsh Bhasin, Nakul Arora, Reliability Infocom
Technology and Optimization 2010, Conference
Proceedings pages 226- 230.
[2] Bethany Delman, Genetic Algorithms in Cryptography,
MS Thesis 2004.
[3] ABDELSALAM ALMARIMI et al, A NEW
APPROACH FOR DATA ENCRYPTION USING
GENETIC ALGORITHMS, Published in: · Proceeding
CERMA '10 Proceedings of the 2010 IEEE Electronics,
Robotics and Automotive Mechanics Conference
[4] Menezes, A., van Oorschot, P., & Vanstone, S. (1997).
Handbook of Applied Cryptography Boca Raton: CRC
Figure 2: Sample division Press
[5] Norman D. Jorstad, CRYPTOGRAPHIC ALGORITHM
VIII. FUTURE SCOPE METRICS, January 1997
The task has been accomplished and tested. The [6] Harsh Bhasin, Surbhi Bhatia, Use of Genetic Algorithms
tests are done using the Coefficient of autocorrelation for Finding Roots of Algebraic Equations, IJCSIT,
as the principle factor in determining the randomness Volume 2, Issue 4, Pages 1693-1696
of the sample. Since, it is a process based on heuristic [7] Harsh Bhasin, Supreet Singh, GA-Correlation Based
selection; its strength can be compared with the Rule Generation for Expert Systems, IJCSIT, Volume 3,
Issue 2, Pages 3733-3736
contemporary mechanism of producing keys based on
Cellular Automata, Corpuscular theory and ACO. [8] Harsh Bhasin, Surbhi Bhatia, Application of Genetic
Random Number Generation via Cellular Automata Algorithms in Machine learning, IJCSIT, Volume 2,
Issue 5, Pages 2412-2415
[9] has been proposed in some paper. The task
therefore is to implement those works and compare the [9] Stephen Wolfram, Cellular Automata And Complexity:
Collected Papers, 1994, ISBN 0-201-62716-7.
above work with a Cellular Random Number
Generator. Corpuscular theory [10] is a relatively new [10] Thomson, J. J. (Joseph John), 7 Mar 2010, The
one. Its results are being asked for and when available corpuscular theory of matter .
will be compared with the above work. PRNG is using [11] Raymond Kan, Xiaulo Wang (November 2008), On the
ACO will be developed in the next phase. Distribution of the sample Autocorrelation Coefficients.

How to cite
Farhat Ullah Khan, Surbhi Bhatia, "A Novel Approach to Genetic Algorithm based Cryptography". International
Journal of Research in Computer Science, 2 (3): pp. 7-10, April 2012. doi:10.7815/ijorcs.23.2012.022

www.ijorcs.org