A Challengers Handbook

by

Caesum

Advanced Ciphers

When I talk about advanved ciphers I am talking about simple ciphers that could potentially be solved with pen and paper. We have already talked about the simple commonplace ciphers like substitution. Lets just mention some more.

First of all a note about transposition ciphers. Most transposition ciphers on challenge sites tend to be columnar transpositions. This is where we may have a piece of text and be told that it is a column transposition or a simple transposition. Sometimes you will be able to solve these by sight, reading words like apssowdr=password (a two column transposition cipher). There are two stages to solving this kind of cipher. The first stage is guessing the column width. The second stage is finding the ordering. Here is problem 16 from Gaines:

OEEHE ATFLS VASYC IOAED QOHDF MCMTC POGEO
REUGM IEFUO GCYWG DQUUI ALSIE RNORN RRATO AQ

We have 72 letters which immediately suggests several grid sizes. However we might try near square sizes first, say 8*9 and 9*8. Each is shown below:

OEEHEATF
LSVASYCI
OAEDQOHD
FMCMTCPO
GEOREUGM
IEFUOGCY
WGDQUUIA
LSIERNOR
NRRATOAQ

OEEHEATFL
SVASYCIOA
EDQOHDFMC
MTCPOGEOR
EUGMIEFUO
GCYWGDQUU
IALSIERNO
RNRRATOAQ

The first thing to notice about the above is several occurences of the letter Q, which is almost always followed by U. The second grid has a Q towards the top left which is in a column and row with no U. Now it could appear at the end of a column or row but the first grid feels most possible due to U appearing in the same column. We would expect 40% vowels in each column, so 3 or 4 vowels in each column and only one column is outside this with 5 vowels, so this is great evidence that we are on the right track. So first lets look at the first grid, and lets move those rows to the top:

OAEDQOHD
WGDQUUIA
IEFUOGCY

OEEHEATF
LSVASYCI
FMCMTCPO
GEOREUGM
LSIERNOR
NRRATOAQ

You will notice that I have also lined up a third row on this same basis as well. However the real thing to notice is the set of digraphs formed from row 1 and row 2 and from row 2 and row 3 - we have OW, AG, ED, DQ, QU, OU, HI, DA in the first two rows and this is the strongest evidence we have for the correct positioning of these rows - DQ could be end/start of words and the rest are very likely combinations of letters. From the remaining rows look for a row to go at the start, the second one fits nicely giving nice combinations and also the word YOU in one column:

LSVASYCI
OAEDQOHD
WGDQUUIA
IEFUOGCY

OEEHEATF
FMCMTCPO
GEOREUGM
LSIERNOR
NRRATOAQ

Now if you look at whats left we have one row - FMCMTCPO which has a lot of consonants and it would be nice to pair it with some good combinations and vowels. The first row fits this description well:

LSVASYCI
OAEDQOHD
WGDQUUIA
IEFUOGCY

FMCMTCPO
OEEHEATF

GEOREUGM
LSIERNOR
NRRATOAQ

Now comparing our two almost complete blocks it is easy to see 'MESSAGE' appearingin the second column:

FMCMTCPO
OEEHEATF
LSIERNOR
LSVASYCI
OAEDQOHD
WGDQUUIA
IEFUOGCY

GEOREUGM
NRRATOAQ

And finally we have FOLLOWING in the first column:

FMCMTCPO
OEEHEATF
LSIERNOR
LSVASYCI
OAEDQOHD
WGDQUUIA
IEFUOGCY
NRRATOAQ
GEOREUGM

FOLLOWING MESSAGE RECEIVED FROM HEADQUARTERS:
QUOTE CAN YOU GO UP TO CHICAGO FRIDAY - QM

The important things to note in transpositions are that number of vowels vs consonants are favourable (see the grid that we did not use it has 4-3-2-1-5-3-3-5-4 vowels). When putting together rows or columns always look for a good set of digrams - common pairings like er/re/th/es etc and do not put together too many uncommon pairs. Look for rows with a number of low frequency letters in it as this will generally be harder to pair well with anything (see the first row above). Gaines goes on to consider many types of transposition ciphers.

The next cipher I want to talk briefly about is Vigenere (and its variants). This is basically a Polyalphabetic cipher, which is to say that it uses multiple alphabets. These alphabets are all basically Caesar shifts and it is done with a key. So for a key of 'KEY' every third letter is encrypted using the Caesar alphabet starting with K, and every third letter (starting with the second letter) by E, and so on. There is a very good program for analysing the possible keylength and trying to guess the key, called Vigsolve. The principle is that if you consider frequency analysis of say every third letter then it would have the same characteristics as English if the keylength was 3. Hence we can guess the keylength. Vigsolve then attempts to line up the frequency analysis with the English alphabet and so guess the key. Suffice it to say that this works very well.

I would also like to mention Playfair, a well known cipher that enciphers letters in pairs, and uses a grid to work this out easily. There is a very good solver for playfair ciphers that you can get here. Of course this is for a 5*5 playfair grid, but is easy to change for other (say 4*6) variants since it comes with source code.

There are many other ciphers that could be used in challenges most of which have never appeared. Few challenges use anything more than simple caesars, substitutions and encoding schemes like morse, semaphore, braille, bacon ciphers. It is worth knowing the names of some of them so that should they be used then any clue would be immediately obvious to you. The ACA describe many different ciphers here and give their rules as to what they would expect in a problem submitted to them for their puzzlers to be able to solve. Faced with such problems a reference like Gaines (which I keep citing because it really opened my eyes and because it is very cheap) is useful because it discusses so many cipher solving techniques and makes you think about what the weaknesses are in any new cipher that you are presented with.

Should a challenge ask you to solve anything as advanced as Enigma then you will want to use Cryptool. I have seen rotor ciphers in challenges, and they actually shouldn't be too difficult to solve given enough information on their workings, by writing a brute force program to attack them using probable words.

Back to Encryption