- Forum
- General C++ Programming
- Encryption using Genetic Algoritms
Encryption using Genetic Algoritms
I've been working on a program to read strings of bytes from a file and use "crossover" to swap bits between the strings and then write them to a new file. The length of the read strings and the intersections where they are spliced are defined by the user, which forms the encryption key. In theory the encrypted file would be unreadable since the crossover points and section sizes could be any number of combinations, much like an XOR encryption key. My only problem is that the encrypted files seem to still retain some patterns of bytes similar to the original file. For example I made a very small text file to test the strength of the algorithm containing these bytes:
0D 0A FF FF FF FF 00 00 00 00
And the resulting file looked like this:
FF FF C7 38 00 00 C7 38 C7 38
Obviously some 'bits' should remain unchanged because they are swapped or crossed, but I still didn't expect to see such an obvious pattern in the resulting output. I have improved the speed of the encryption program by buffering the file stream and using some assembly to perform the bit swapping, so my first idea was to perform multiple passes through the file to, in effect, jumble up the data more and more, but this would take up a lot more processing time to complete.
I'm not intending this to be any improvement on contemporary encryption algorithms, its just part of my university project on Genetic Algorithms and seemed quite an interesting programming challenge.
Does anyone else have any ideas how this concept could be improved, preferably without using up more processing time.
Leon ^^
0D 0A FF FF FF FF 00 00 00 00
And the resulting file looked like this:
FF FF C7 38 00 00 C7 38 C7 38
Obviously some 'bits' should remain unchanged because they are swapped or crossed, but I still didn't expect to see such an obvious pattern in the resulting output. I have improved the speed of the encryption program by buffering the file stream and using some assembly to perform the bit swapping, so my first idea was to perform multiple passes through the file to, in effect, jumble up the data more and more, but this would take up a lot more processing time to complete.
I'm not intending this to be any improvement on contemporary encryption algorithms, its just part of my university project on Genetic Algorithms and seemed quite an interesting programming challenge.
Does anyone else have any ideas how this concept could be improved, preferably without using up more processing time.
Leon ^^
I would guess from your above example that the distance between intersections was somewhat large. You probably want the distance to
be very small (less than 16 bits, maybe less than 8).
But your encrypter is so simple compared to DES, Triple DES, Blowfish, et al in terms of computation time that speed would be my last concern.
be very small (less than 16 bits, maybe less than 8).
But your encrypter is so simple compared to DES, Triple DES, Blowfish, et al in terms of computation time that speed would be my last concern.
You're right that its a very simple algorithm, I wouldn't call myself a world-class programmer yet LoL. I'm considering using the same key to perform crossover at both a byte level and a bit level to further "mutate" it, as they say in Genetics. I've read a few articles about Genetic Algorithms being used to encrypt multimedia files more quickly than XOR encryption to be sent over a network, such as internet radio designated only for users who subscribe etc. Which is why speed would be so essential for an algorithm of this type. But like I said I doubt it would be very useful in the end, just an interesting weekend project.
Leon
Leon
Keep in mind that encryption algorithms don't fall out of the sky. The design of DES (for example) took a lot of study and experimentation to get rid of all the obvious patterns.
Of course I agree, no second year student is gonna come up with a new algorithm that can beat DES as a weekend project.
I have implemented two levels to the algorithm now though. It first uses the input key to randomise the 'bytes' and thus try to remove any repeating patterns. Then it crosses the 'bits' of the byte strings to create a mutated file on two levels.
After the 'byte' pass the file just looks like the hexadecimal version of a word jumble, but any repeating patterns I have deliberately entered are lost. After the 'bit' pass I couldn't distinguish anything similar to the original and there were no repetitions. However, running through these two stages multiple times would further degrade/mutate the code still.
Hopefully when I submit the work I'll get extra credit for using up my weekend on this LoL.
Leon
I have implemented two levels to the algorithm now though. It first uses the input key to randomise the 'bytes' and thus try to remove any repeating patterns. Then it crosses the 'bits' of the byte strings to create a mutated file on two levels.
After the 'byte' pass the file just looks like the hexadecimal version of a word jumble, but any repeating patterns I have deliberately entered are lost. After the 'bit' pass I couldn't distinguish anything similar to the original and there were no repetitions. However, running through these two stages multiple times would further degrade/mutate the code still.
Hopefully when I submit the work I'll get extra credit for using up my weekend on this LoL.
Leon
Perhaps I missed something here. I am familiar with a couple of Encryption techniques (Priv Key, TripleDES, Vernam Cipher etc) and I am familiar with path-finding and minimization algorithms.
But I fail to see the relevance of a genetic algorithm to encrypting a file. Genetic algorithms build new generations from previous using a random selection from the existing population to create a new member. Unless your Seed and random number generator was identical on both systems the genetic algorithm would run differently. Not only that, but there is essentially no benefit in using something like a genetic algorithm to encrypt. It's highly inefficient.
If you want a nice fast, fairly secure encryption then using something like the Vernam cipher. It's a 1time key cipher that cannot be reversed cracked. The only method of de-ciphering the ciphertext is by using the 1time key.
http://www.pro-technix.com/information/crypto/pages/vernam_base.html
http://en.wikipedia.org/wiki/One-time_pad
But I fail to see the relevance of a genetic algorithm to encrypting a file. Genetic algorithms build new generations from previous using a random selection from the existing population to create a new member. Unless your Seed and random number generator was identical on both systems the genetic algorithm would run differently. Not only that, but there is essentially no benefit in using something like a genetic algorithm to encrypt. It's highly inefficient.
If you want a nice fast, fairly secure encryption then using something like the Vernam cipher. It's a 1time key cipher that cannot be reversed cracked. The only method of de-ciphering the ciphertext is by using the 1time key.
http://www.pro-technix.com/information/crypto/pages/vernam_base.html
http://en.wikipedia.org/wiki/One-time_pad
Last edited on
Using a random number generator was only a passing idea. I agree that it wouldn't make the algorithm more secure and would be different on different systems.
Perhaps I should be more specific and say the algorithm uses Genetic Crossover to perform the encryption, not a full Genetic Algorithm that is used to find solutions in a best-fit scenario.
Essentially using Genetic Crossover means splitting the file into sections (strands, DNA, Chromosomes, etc) and then using Genetic Crossover to mix up the data. The the user-defined key (Encryption key) is used to define the crossover points of the file sections. Therefore theoretically you couldn't read the data in the file without knowing the original key to cross the parts back into their original positions.
The only advantage I can see to using Genetic Crossover in file encryption is that it removes repeating patterns quite proficiently; something that can be a security risk when using conventional encryption methods. Current ciphers and algorithms (as far as I know) have to process the files using considerable overhead to remove those repeating patterns, which might make Genetic Crossover faster in that respect. Even using Genetic Crossover before a standard cipher might make the code more secure and reduce overhead.
As far as Genetic Crossover being slower or inefficient I can't comment on that yet. I still have to finish the program and test it against another encryption program to see how it compares in terms of encryption time. But the files I've run through it so far seem to encrypt very quickly. All of the actual crossing of data is done using bitwise operations and assembly code, so hopefully this might work to speed things up.
Leon
Perhaps I should be more specific and say the algorithm uses Genetic Crossover to perform the encryption, not a full Genetic Algorithm that is used to find solutions in a best-fit scenario.
Essentially using Genetic Crossover means splitting the file into sections (strands, DNA, Chromosomes, etc) and then using Genetic Crossover to mix up the data. The the user-defined key (Encryption key) is used to define the crossover points of the file sections. Therefore theoretically you couldn't read the data in the file without knowing the original key to cross the parts back into their original positions.
The only advantage I can see to using Genetic Crossover in file encryption is that it removes repeating patterns quite proficiently; something that can be a security risk when using conventional encryption methods. Current ciphers and algorithms (as far as I know) have to process the files using considerable overhead to remove those repeating patterns, which might make Genetic Crossover faster in that respect. Even using Genetic Crossover before a standard cipher might make the code more secure and reduce overhead.
As far as Genetic Crossover being slower or inefficient I can't comment on that yet. I still have to finish the program and test it against another encryption program to see how it compares in terms of encryption time. But the files I've run through it so far seem to encrypt very quickly. All of the actual crossing of data is done using bitwise operations and assembly code, so hopefully this might work to speed things up.
Leon
closed account (z05DSL3A)
There was a paper published in the Information Technology Journal on this subject.
Title: Image Encryption Using Genetic Algorithm
Author(s): Mohammed A.F. Al-Husainy
Journal: Information Technology Journal
Year: 2006
Abstract: The security of digital images attracts much attention recently, especially when these digital images are stored in some types of memory or send through the communication networks. Many different image encryption methods have been proposed to keep the security of these images. Image encryption techniques tries to convert an image to another image that is hard to understand. In this proposed method, Genetic Algorithm (GA) is used to produce a new encryption method by exploitation the powerful features of the Crossover and Mutation operations of (GA). The proposed encryption method, in this study , has been tested on some known images and good results are recorded.
www.scialert.net/qredirect.php?doi=itj.2006.516.519&linkid=pdf
Title: Image Encryption Using Genetic Algorithm
Author(s): Mohammed A.F. Al-Husainy
Journal: Information Technology Journal
Year: 2006
Abstract: The security of digital images attracts much attention recently, especially when these digital images are stored in some types of memory or send through the communication networks. Many different image encryption methods have been proposed to keep the security of these images. Image encryption techniques tries to convert an image to another image that is hard to understand. In this proposed method, Genetic Algorithm (GA) is used to produce a new encryption method by exploitation the powerful features of the Crossover and Mutation operations of (GA). The proposed encryption method, in this study , has been tested on some known images and good results are recorded.
www.scialert.net/qredirect.php?doi=itj.2006.516.519&linkid=pdf
I found that paper when I was looking for some help LoL. I got stuck trying to figure out the right sequence of bitwise operations and was hoping someone else may have uploaded their source code. In it they don't mention any kind of encryption key, but I did notice they used the image itself to hide some of the decryption values. Not a good idea. Also I noticed they used both Genetic Crossover and Genetic Mutation.
From what I can tell from Al-Husainy's paper they split the image data into vectors (the same method I used with byte strings) and applied 'bit' crossover and Genetic Mutation to the vectors before reconstituting the file with the encrypted vectors. Although I would warn against their method of storing any data used to encrypt the file 'inside' the file itself.
I don't see the point in using Genetic Mutation however, it doesn't mix up the bytes into a new order, it only multiplies them (using bit shift and wrap-around) into new values. If they had performed crossover on a byte level like I had, and not just a bit level, I would think the mutation aspect of the algorithm would only add extra overhead when the file itself is already resistant to cryptographic analysis. The only way to make the file more secure from that point onwards is to extend the encryption key and create a larger solution space.
Leon
From what I can tell from Al-Husainy's paper they split the image data into vectors (the same method I used with byte strings) and applied 'bit' crossover and Genetic Mutation to the vectors before reconstituting the file with the encrypted vectors. Although I would warn against their method of storing any data used to encrypt the file 'inside' the file itself.
I don't see the point in using Genetic Mutation however, it doesn't mix up the bytes into a new order, it only multiplies them (using bit shift and wrap-around) into new values. If they had performed crossover on a byte level like I had, and not just a bit level, I would think the mutation aspect of the algorithm would only add extra overhead when the file itself is already resistant to cryptographic analysis. The only way to make the file more secure from that point onwards is to extend the encryption key and create a larger solution space.
Leon
Topic archived. No new replies allowed.