How did you solve 6B?
Home › Forums › The Sixteenth National Cipher Challenge: The Lost Legion › How did you solve 6B?
- This topic has 7 replies, 8 voices, and was last updated 4 years, 7 months ago by Anonymous.
30 Nov 17 at 3:21 am #33189AnonymousInactive
I’m interested to learn how others tackled 6b.
The letter frequencies and the IoC suggested a vigenère cipher, key length 15 from the start.
Based on Maryam’s decoded note, I spent time trying to find substitution alphabets for the tabula recta that would make sense, but unsuccessfully, without the vigenère key. I tried sorting into relative frequency order (ETAOIN…), crib attacks and any manner of variations of slicing, dicing and reversing the letters.
Later, knowing the vigenère key yeilded a familiar letter frequency distribution that was straightforward to solve by affine or mono-substitution using the usual methods.
The “what a fine mess” clue was less cryptic than I thought; I went down the Laurel and Hardy route, thinking that it referred to the dual cipher nature of 6b. Bah! humbug.
To get the plaintext, an Affine shift (15,0) or substitution key APETIXMBQFUJYNCRGVKZODSHWL can be applied after the vigenère decode, alternatively, the same substitution key used (progressively shifted) in the tabula recta to output plaintext directly from a vigenère decoder:
The decoding Affine shift (15,0) or substitution alphabet AHOVCJQXELSZGNUBIPWDKRYFMT, is the inverse of shift (7,0) that was used to encode it.
Interestingly, when I took the 6b ciphertext message and passed it through my affine decoder first, then my vigenère decoder (per the encoding sequence), it suggested the correct plaintext solution immediately! With this sequence, the affine shift was (15,24) equivalent to a substitution alphabet of YNCRGVKZODSHWLAPETIXMBQFUJ then the subsequent vigenère key was YKTOCAHYGWATXGW.
I had not expected it to suggest any sensible results as my plaintext fitness measure is a chi squared comparison with english letter frequencies. This must be serendipity as there were other affine shifts which gave a cluster of close chi squared results and the best result was itself too high to be considered a close match. Further investigation showed that if the Affine shift was done first, all 26 possible (a,b) decodes with a=15; b=0,1,2,3,4,5,6…25 give solvable text with a vigenère decode.
On reflection, I could adapt my vigenère decoder to interface with some Threshold Acceptance code (similar to Simulated Annealing or Hill Climbing mentioned by others) to optimise the alphabets in the (virtual) tabula recta.
Question: Are there any analytical techniques to get the vigenère key, knowing the IoC=15, as cribs/n-grams cannot be used because the result is not plaintext and the letter frequency distribution is not the same as English? (I expect a sorted letter relative frequency correlation coefficient of some flavour could be used as a fitness measure for mono alphabetic encrypted plaintext, but what if the plaintext is scrambled by polyalphabetic ecryption or more…?). I shall be interested to hear other’s views/experience.30 Nov 17 at 12:58 pm #33193AnonymousInactive
I used the shotgun hill climbing method. Deciding that there was probably a vigènere involved, I realised after running it through my auto-vignère cracker that there must be some other cipher involved. Presuming it was probably some form of monoalphabetic substitution, I modified my Shotgun Hill Climbing program to instead guess at a Vigènere key, and to use the IOC to determine how good it was.
I’m a pretty awful coder so my program takes a while to run because it’s far more complexly written than it has to be, but after a lot of cycles I got a key that looked something very similar to the correct one – and see my small knowledge of Latin to go from there.
I actually was never one for using affine shift or keyword decryption – especially when word structure is preserved, I tend to just operate on letter frequency and guessing words – and it didn’t take very long to solve from there.
Obviously i did quite a lot of guessing – the ciphers used and that the key would be an actual phrase, so I’m interested to see how otthers did it!01 Dec 17 at 2:47 am #33233AnonymousInactive
The frequency distribution, and the clue from part A, suggested a polyalphabetic cipher, perhaps Vignère based. Trying different splits and the index of coincidence suggested a Vigenère key length of 15.
I tried doing a standard Vigenère break with length 15, but that didn’t work. Then, using the clue from part A, I tried affine ciphers on each split-out sub text, and that worked.
What’s confusing me is the key. Affine ciphers have two components, yet the keyword presented has only one letter for each part of the key. How do you get the second part of each key for the affine ciphers?01 Dec 17 at 2:48 am #33234AnonymousInactive
I took each affine shift from the monoalphabetic strain of the whole polyalphabetic thing to see what was the most likely alphabet (i.e. value for a assuming the affine shift is (a*x+b)mod 26). I then used the values for b to get an alphabet of GNUBIPWDKRYFMTAHOVCJQXELSZ and a key of AGRICOLAEMOLTE (or something simular) to get a weird substitution cipher. I then used standard monoalphabetic cracker to get a weird plaintext, that wasn’t quite the real thing but close enough for me to deduce the rest. This time lost me the deadline by 13 minutes. ARGHHHHHHHH!01 Dec 17 at 11:33 am #33256AnonymousInactive
I began with the vigenere first. Essentially I just grabbed a frequency distribution for all the letters encoded with the same letter. By looking at the pattern you can try to line up a feature of the distribution (in my case I just found the shift that had the least square distance from the average of the letters already seen). This may leave it with a caesar shift but caesar shift and substitution is no different to substitution so after that I just put it in my solver which used a hill climb to crack it01 Dec 17 at 11:33 am #33257AnonymousInactive
it was AGRICOLAEMORTEM01 Dec 17 at 2:58 pm #33267AnonymousInactive
By hand as it were, just with Excel 🙂 Established the repeat length of fifteen easily enough, then constructed a grid for the fifteen alphabets making no assumption as to their nature at all; I took them to be fifteen entirely independent random jumbles until late in the piece. Substituted in likely plaintext for the single letter words as “a” , letter after apostrophe as “s” and the common threes as “the”, then started looking for additional possible words based on capitalisation and spacing. Established ?the? as “other” and trial and error with words such as “Emperor’s”, then “?? the Emperor’s ???????” as “on the Emperor’s command”; essentially after this various other likely words showed up quickly. Only realised very late in the solving process that the fifteen cipher alphabets were the same apart from a Caesar shift, and never spotted the affine structure within the alphabet until it was pointed out on the forum, nor any idea of a key word to set the alphabets.
Must have made hard work of it missing all the extra information, but on the other hand the method didn’t need any potentially false assumptions about the nature of the alphabets used.04 Jan 18 at 3:06 pm #34110AnonymousInactive
I did something very similar but a bit more slowly, it was the only one I didn’t get in time…felt really silly when I saw it was affine, the day after the deadline.
- You must be logged in to reply to this topic.