Skip to main content

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
    madness
    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”.

    XDAFGGDDAAFDADGADDFFAAAGFXAADDGDGDDDDDAFDFXFDXAFDDADAGFXADXDGADGAFDAFADGGFFXFAXD
    DDDGDFDDFAAAGAFADXFFXADFGGFDDFAFXAAFXXAFXFFAGDAGADAADFXAGADGXXDAAFFDXXFXDFXDGFXA
    GFGADXGDADDDAFAFXAFDXDDDAAFAAAFFXFAAAFAGGXDXXAAFFXXFDFXDAFFADXDFGXDFXFFFGFGFDXDA
    FDDDAXXAXAFGFDDDGGFFXDDGFDDDDAXGFGADXFDGFXFXGDDFXDXGAFXXDAFFFXFGGDGAGGFAFFFAAFAX
    DFDDXADDDDFFXGAFDAGFFXAAADDXGGXXAADADXGAGXDDAXGGDAGDFAAAAGXADGAXXAFFXFGDAFDFDXFD
    FAAAAFXFDAAAXFAFAGDAXDADFAADGDFFXGFFDFGXAAXADAFFGXFXAFXXADAFADXXXGXXAFXDADGXXFDD
    DAAFDGGAAAFAAXAGDXDAGDFADDFDXDFDFDADAFAAAAFFFXADGFXAAGAAAXFAFDXFFDGFXAGADXFDAAFD
    DAXXGADAAFADAFFFXFADXDAXFFDXAFAXADDFXDFDADDDAAFAAGADGDAFDXAFDDAFDFDXFDGXFFAAGDXD
    XXGXXAFADFXGADGGGGDDGAAFAADDDDDGFXFAADFFXAGXGAAFADDAXDDGFDXXAGAGDFDGADFAAXDDADDD
    XDADDFADGAADGGXDDDDDFFXFDDADFFAFGAXFXFAAXGDGADAGDDXGXAXFDXDDFAAGDGGXGXXDDFGAFFAA
    DDGFAFDFDAAXFFAAADGGFDFADGAFFDXDFFFADDGGDDADXDDDXXAGDDGDDAGAFFXAFFAGGFDAGADADDFX
    DXDFGADGDAFDDAFDAAAADDGFFAXFFAXXADDFADDXFFDGAFAFGXGAGFGGGGFXDXDGGADFXFXXFXDADGAX
    FDFXFFFADGDGGADAADDFFFDXADAGDDGFADAXFXADFADFGXGAADADDDGFFFDDAFDDXDDGXXDAAFFFXFFA
    FGFGXDGFFDFFFDGFXXAGGDGDADGGGXXDDXGDDGAAXGFDFFXAFFGADADFFFXFFDXFAXFXFFADAFFDAFAF
    DGGFGXGFGFFAGGDGFFFGAXDDXGDDADAXFFGFDAFDDFFFGAFAGGGDDDDFFGDDGFXDDFAGADAFDADFFAXX
    GFXGFFDFDGFXGFGGXFDDFDXXXXADDFDFDGFGFXAFAFGADDAGDDDAAFXFGFGDFDGDADDXFDAGFFFDFFDG
    GAFXGADXDDFGGFGFXFDADXGDDAFGDDAFDFFFFGXDDAFDDDGFAFFDGXDFXFADGXFFXDDFFFXAGGDADXGX
    ADDXXDXFDDXADDDADGFGXAFFGFFGDAFAFFDDFDXGDXFAADXDFDDXGDDGDGGAAAGFFDGGAXXXAXDFFXFA
    GGAXFGDDDAFXXDDDDXDGDADAGFDFDDFFDFAGGGFDADDAFDXDDFDFGGFFGGDGGGDGDDAFDAFFGGXGXDGX
    GDFFFDFDDFXAGFDGDXXFXFDGGGFXDDGGFDXXFAXXDFFDFDDDGGFXADDGDGAGFDDFAXXFGXGDGDDAFADD
    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
    sinkrad
    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
    madness
    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
    madness
    Participant

    The Vigenere cipher is so easy to break because it is highly constrained. Furthermore, a text that is doubly encrypted, where the second encryption is a Vigenere, can usually be broken. This is the fatal flaw of the Quagmire I cipher, which is equivalent to a monoalphabetic substitution followed by a Vigenere.

Viewing 8 posts - 1 through 8 (of 8 total)
  • You must be logged in to reply to this topic.
Report a problem