# Breaking the more complex ciphers

Viewing 8 posts - 1 through 8 (of 8 total)
• Author
Posts
• #68167
Break_The_Cipher
Participant

In trying to get a head start on the difficult ciphers before they come, I’ve reached a wall mostly in two-step encryption ciphers. I do think that I should also eventually make a script for the solitaire cipher because that could easily come up later, but it looked too confusing to make a decrypt script for.

I’m not really sure how to get past the substitution cipher encrypted with columnar transposition without waiting through an unreasonable amount of iterations. I’ve tried to create a substitution key through matching letter frequencies with the standard frequencies and then use tetragram fitness to decrypt the transposition, but the substitution key always seems to be greatly inaccurate. Does anyone know a way to break this? The ADFGVX cipher also has a similar problem, where I can use fitness for both keys, but it takes too many iterations to find a key for the Polybius square and the transposition.

#68168
Participant

@Break_The_Cipher,
I dunno. I made a script to encipher and decipher in the solitaire cipher. The hard part is breaking it without knowing the key.

For a substitution + transposition, it is easy to do the substitution part first, IF you know in advance that the substitution is a Caesar or affine cipher. For a general monoalphabetic substitution, you better hope that the transposition has few enough keys that you can try them all, then try to break the substitution for each one. Another approach is to try to match frequencies, then try to break the transposition, then go back and try to fix the substitution. I remember saying such a thing last year. But it’s very likely to fail.

I break ADFGX and ADFGVX by maximizing the index of coincidence in order to find the transposition key. If I find the correct key, then all that remains is a monoalphabetic substitution, which is easy to break. 6B from last year was one of these; it had only 6 possible transposition keys, so it was easy.

Here is an ADFGX ciphertext for you to practice with. Let’s call it “madness-2021-5”.

DGFDFDGFGF

#68188
Break_The_Cipher
Participant

I think I have an effective enough script which can find the text given the transposition keylength. It struggles to find the right keylength for this ciphertext though, is there an effective way to quickly check which keylengths are going to work? Also I’m not sure if it’s just my script but it seems the ioc gets higher and higher when the keylength is larger

#68194
Break_The_Cipher
Participant

Ok it seems the script struggles to decrypt transposition with keylengths of around 20 or so, is there a way to make it more effective?

#68330
Break_The_Cipher
Participant

It seems that the script gives different keys every time I run it, which means it runs into local maxima a lot. I’ve tried making it go through lots of iterations but it seems that hill-climbing is not enough to find an accurate transposition key. Is there a better way to find the key and get it out of the local maxima? I think simulated annealing would do a better job at finding the key, but I’m not sure.

#68334
Participant

@Break_The_Cipher, it is expected that hill climbing will find local maxima when the keylength you are looking for differs from the actual keylength. When you are trying transpositions of the correct keylength it is unlikely you will get stuck in a local maximum.

For testing whether the text might be encrypted with keylength n, I start by trying the following transpositions:
(1, 2, 3, .., n)
(2, 1, 3, .., n)
(2, 3, 1, .., n)

(2, 3, 4, .., 1)
That is, I try placing the first column in any other position of the matrix. When the keylength is correct at least one of these transpositions should put two columns that are adjacent in the actual key next to one another, which will result in a higher index of coincidence (ioc) for that transposition. For each possible keylength n I then compute the highest ioc over these n transpositions and the lowest ioc. Values of n for which the highest and lowest value differ strongly are likely candidates for the keylength.

Applied to the example of madness and for (n = 1..14):
keylength: 3 – 0.00164
keylength: 4 – 0.00223
keylength: 5 – 0.00124
keylength: 6 – 0.00285
keylength: 7 – 0.00051
keylength: 8 – 0.00096
keylength: 9 – 0.00073
keylength: 10 – 0.00087
keylength: 11 – 0.00079
keylength: 12 – 0.0012
keylength: 13 – 0.00084
keylength: 14 – 0.00108

The largest improvements are found with keylength 6, 4, 3, 12 (in that order). For this data set 6 is indeed the correct keylength. 12 probably gets a good score since it is a multiple of six.

The difficulty here is that 6 is not a multiple of the text length and therefore additional steps are required when placing the text in a matrix. Possibly something went wrong in that step. The easiest way to debug your code is to encrypt a known text with a known key and see whether your algorithm is capable of retrieving that key. Best to start simple with a keylength that divides the length of your text and then advance to the harder case of a keylength that is not a divider of the text length.

#68344
Participant

The professionals have trouble with permutations > 15, so I doubt you are able to do 20.

Anyway, you have to find a way to deal with multiple maxima.

BTW, simulated annealing is just another approach to hill climbing. I prefer to use a constant temperature, since the maxima are generally very steep.

#68346