Since I’m going to the ACA convention in a few days, cryptography is on my mind. I thought I’d depart from my regular book reviews and give a few brief lessons on computer solving of ciphers. I only apply these methods to simple ACA ciphers like cryptograms, Playfair, etc., but the principles and general techniques apply to many sophisticated encryption methods. I’ll only use pseudocode since programmers use many different languages, and I only know a bit of some older types (BASIC, Pascal, Delphi). First, I’ll discuss a common method of attack: hillclimbing.
Before I describe how to do it, you’ll understand it better if you know why it’s called hillclimbing. Imagine you’re a paratrooper who is dropping onto an enemy’s mountain range. Your mission is to get to the top of the mountain to disable his radar station and anti-aircraft guns. You parachute down in the dead of night. It’s foggy and pitch black. You can’t turn on a light and can’t see exactly where you are or which direction the mountaintop is. Your only tool is a very sensitive altimeter with a lighted screen. You decide just to go up. You measure your altitude and then take a step, then look at it again. If you’re higher, you repeat the process from there. If you’re lower or the same altitude, you step back to where you were and step a different direction. By always going higher you will eventually reach the top. But the top of what? You may be on a foothill or ridge or side bluff or even the wrong mountain. After all, the mountain isn’t a smooth cone rising from a smooth plain. However, you aren’t the only paratrooper. If hundreds of your fellow paratroopers land all over the area, scattered widely, one or more is bound to land close enough to the top so that this method of always climbing will get him to the radar station. That’s the principle behind hillclimbing. Take a random shot at a solution, and improve it gradually until you can’t improve it any more. Do that many times until one of the attempts produces a solution.
I’m assuming you know what type of cipher you are attacking, or at least think you know, have a cipher to decrypt, and have a decryption engine for it. All you need is the right key. Hillclimbing code will:
- Pick a random key
- Decrypt using that key
- Measure how good the decryption is ( a future lesson will discuss how to do this)
- Make a small change in the key (e.g. swap two letters)
- Repeat steps 2 and 3
- If the new key produces a better decryption, keep it, otherwise keep the first one
- Repeat from step 4 until you get no more improvement
- Go back to step 1 and repeat the whole process
The process is a looping procedure that ends only when you stop it or it meets some test or limit you have programmed into it. If you’re lucky, or good, you stop because you have found a solution. That’s it for today. You now understand the idea behind hillclimbing.
Thanks for share your método. I really want to learning to solve a puzzle.
Interesting first blog on ciphers…I look forward to reading more as these are things that drive me crazy at times. 🙂 Can I make a suggestion though? You had made a comment that you assumed that we know what cipher we are dealing with. What if we don’t though? Can you do a blog that outlines how to best figure out what kind of cipher you are dealing with?
Darrell, I do have a program that diagnoses (or tries to) the cipher type. There is no easy approach to this problem, though, so it is not something I can explain how to do in a short post. Perhaps the most practical advice I can give is to use available Internet resources like this one from BION: http://bionsgadgets.appspot.com/gadget_forms/refscore_extended.html.
I use my own program, but it is probably the most complex program I’ve ever written and can’t be reduced to pseudocode. It tests for dozens of cipher types and most of those tests are specific to one cipher. Still, there are things you can do easily with a computer program such as count how many different letters and compute the index of coincidence. If there’s 25 different letters and the J is missing then it’s probably a polybius-square based cipher. If it shows periodicity it’s likely to be in the Vigenere family, etc. The author of the cipher may even help you out by formatting it in a way that provides a hint. For example, if the ciphertext is written in pairs, it’s likely to be a Playfair, or other digraph-based cipher. If in 7-letter blocks it’s probably a periodic type and 7 is the period. There are too many kinds of tests and ciphers to describe them all.