Computer cipher solving – Lesson 1: Hillclimbing

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.