0
$\begingroup$

As a little pet project I'm writing some code to do a little cryptanalysis. Starting with something simple I have created a hill climbing algorithm for solving a simple substitution cipher.

So I start by generating a parent key by shuffling letters A-Z randomly. For the first iteration I am generating a child key by randomly swapping 2 characters from the parent key, and in each subsequent iteration I am shuffling two characters from the previous iteration's key.

While this approach works, it seems very inefficient, as the randomness seems to generate the same key over and over again on each attempt at a solution.

So my question is, is there a better solution for generating child keys than random? A few things I have considered but not tried:

  • memorizing previous keys and checking a new random key has not already been tried
  • Some other means of shuffling characters, such as swap 1-2, 1-3, 1-4 .... 2-3,2-4... etc (This feels much too much like brute force)

But both of these strike me as making the algorithm less efficient not more (ie, the overhead in doing each outweighs the gain made by using random chance).

Any particular thoughts?


Edit: As the comments have quite rightfully pointed out perhaps the problem I'm facing is not actually how to generate better child keys, but how to avoid a local maximum. Other relevant details of my algorithm are as follows:

  • I am scoring based on the Sum of the Log10 probability of Quadgrams
  • I am running my algorithm until 1000 iterations have not provided a better score
  • I am running the entire thing until 20 tries have not produced a better score
$\endgroup$
  • 1
    $\begingroup$ What is the scoring function you are using? One problem you might be running into is that you fall into a local maximum, where any single step you can make the score wrose, and so your mechanism doesn't want to do anything. You need to consider your scoring mechanism when selecting a mutation method (and, in particular, so that your mutation method as a decent probability of finding it's way out of a local maximum) $\endgroup$ – poncho Oct 2 '14 at 18:27
  • $\begingroup$ Are you only generating one child each iteration? $\endgroup$ – mikeazo Oct 2 '14 at 18:31
  • $\begingroup$ @poncho - Scoring function is sum of Log10 probability of quadgrams (hope that makes sense) $\endgroup$ – Jamiec Oct 2 '14 at 18:56
  • $\begingroup$ @mikeazo - No, im generating new child keys until such time 1000 iterations have passed with no improvement to score - but therein lies the problem, on many of those iterations the same child key has been created as has been tried before. $\endgroup$ – Jamiec Oct 2 '14 at 18:57
  • $\begingroup$ That makes sense -- however, it strikes me that the combination of that scoring function and a single letter swap is likely to be prone to local maximum. Consider the case where it guesses a common quadrigram is "tion" (which gets a great score), but the actual decryption is "ould"(which is also quite common); it's hard to see how the system would move from "tion" to "ould" without having a bad intermediate score. $\endgroup$ – poncho Oct 2 '14 at 19:09
1
$\begingroup$

My experience is that hill climbing is very efficient for solving substitution ciphers. As I understand there are two topics now.

  1. How to generate the child keys
    Swapping characters of the key randomly (stochastic hill climbing) as well as trying all possible swap combinations is reasonable. But for solving a substitution cipher I believe trying all possible character swaps per parent is more efficient. First, trying the same key more than once is avoided (at least for one parent), secondly it provides a clear condition when to stop the hill climbing: If none of the childs provide a better result than the parent. Using the stochastic hill climbing and keeping track of the tried keys would be overkill, and I think effectively it turns this into trying all possible key swaps.

  2. How to avoid a local maximum
    One option is to use the Random-restart hill climbing (or Shotgun hill climbing, see http://en.wikipedia.org/wiki/Hill_climbing#Variants). It simply repeats the hill climbing using different random initial conditions and it works very well for breaking substitution ciphers.

Resources:

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer and the resources, I will go and give these a try. I think I must have already tried point 2, as I put in my answer Im retrying with a new initial parent key 20 times looking for a better result than the previous attempts $\endgroup$ – Jamiec Oct 3 '14 at 15:21
  • $\begingroup$ Using a fixed number of new initial parent keys has a disadvantage. The 20 initial keys probably work well for very long ciphers (where even a much smaller value might be sufficient), but for short ciphers most probably much more different initial keys must be used. The implementation I provided in the reference is using the following approach: If the "best result" is reached 3 times, the Random-restart hill climbing stops. Each time a new "best result" is found, counting starts from the beginning. $\endgroup$ – Jagu Oct 5 '14 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.