Codebreaking

On substitution ciphers

Graham A. Niblo

These notes form a brief introduction to substitution ciphers, to accompany the lesson plans provided with the University of Southampton National Cipher Challenge, 2005. We would like to thank Hugh Evans of Sholing City Technology College for his assistance in the design of these teaching materials.

Caesar shift ciphers

 The easiest method of enciphering a text message is to replace each character by another using a fixed rule, so for example every letter a may be replaced by D, and every letter b by the letter E and so on.

 Applying this rule to the previous paragraph produces the text

WKH HDVLHVW PHWKRG RI HQFLSKHULQJ D WHAW PHVVDJH LV WR UHSODFH HDFK FKDUDFWHU EB DQRWKHU XVLQJ D ILAHG UXOH, VR IRU HADPSOH HYHUB OHWWHU D PDB EH UHSODFHG EB G, DQG HYHUB OHWWHU E EB WKH OHWWHU H DQG VR RQ.

 (Note the convention in these notes that ciphertext is written in capital letters, while plaintext is usually lowercase.)

 Such a cipher is known as a shift cipher since the letters of the alphabet are shifted round by a fixed amount, and as a Caesar shift since such ciphers were used by Julius Caesar. To decode a Caesar shift it is enough to work out the amount of shift, which can be done, for example, by discovering which character has replaced the letter e. In the example above we might guess that the three-letter word starting the sentence is the and therefore that the letter e has been replaced by H. A quick check shows that the Caesar shift by 3 does indeed encode the word the as WKH, and it is easy to complete the decryption.

 In fact there are only 26 Caesar shift ciphers (and one of them does nothing to the text) so it is not too hard to decipher the text by brute force. We can try each of the shifts in turn on the first word of the cipher text until we discover the correct shift. This process can be simplified by using a cipher wheel, a simple mechanical device that allows one to generate each of the Caesar shift ciphers, and to encode or decode messages using it. At the front of this pack you will find a sheet, which can be photocopied onto thin card in order to make a cipher wheel. Cut out the two discs, and fasten through their centres with a paper fastener to make the wheel. Use the convention that you read plaintext on the outer rim of the wheel and cipher text from the smaller wheel.

Keyword substitution ciphers

To increase the difficulty of deciphering the text we need a richer family of ciphers. A good example is furnished by the keyword cipher. In this we design an encryption table by choosing a keyword or phrase, which is used to jumble the alphabet as follows:

Write down the phrase, with no spaces between the letters, and omitting any repeated character. So if the phrase is “The Simpsons” we write down THESIMPON. Now we continue to go round the alphabet until every letter appears exactly once, and write the list under the standard alphabet:

abcdefghijklmnopqrstuvwxyz

THESIMPONQRUVWXYZABCDFGJKL

Of course if the key phrase is carefully chosen (for example “The quick brown fox jumps over the lazy dog”) we may not need to complete the list as above, but such a choice is not necessary. The number of such ciphers is 26!, or approximately 1027, and brute force cannot be used to attack the problem. However an attack is possible.

Consider the text

VEP HYXHLVHTP MO AWFJYFLT H RFNEPS HJNEHAPV FL VEFU ZHC FU VEHV FV FU PHUC VM KPKMSFUP VEP IPCZMSY MS IPCNESHUP, HLY EPLRP VEP RFNEPS HJNEHAPV. VEFU FU FKNMSVHLV, APRHWUP FO VEP UPLYPS EHU VM IPPN VEP RFNEPS HJNEHAPV ML H NFPRP MO NHNPS, VEP PLPKC RHL RHNVWSP VEP NHNPS, YFURMXPS VEP IPC, HLY SPHY HLC RMKKWLFRHVFMLU VEHV EHXP APPL PLRSCNVPY ZFVE FV. EMZPXPS FO VEP IPC RHL AP RMKKFVVPY VM KPKMSC FV FU JPUU JFIPJC VM OHJJ FLVM PLPKC EHLYU.

As before we notice that the first word has three letters and, since it occurs several times, may well be the word the. This gives a strong hint that the letter e is enciphered as the letter P in the keyphrase cipher. Of course other three letter words are possible, e.g., and or but. Nonetheless a quick check shows us that the letter P is the most common letter in the enciphered text, just as e is the most common letter in English so it is reasonable to assume that the correct decryption translates P to e. This also suggests that V stands for t and E for h, allowing us to begin to decipher the text. We will use the convention that uppercase letters denote enciphered letters and lowercase denotes plaintext characters:

the HYXHLtHTe MO AWFJYFLT H RFNheS HJNhHAet FL thFU ZHC FU thHt Ft FU eHUC tM KeKMSFUe the IeCZMSY MS IeCNhSHUe, HLY heLRe the RFNheS HJNhHAet. thFU FU FKNMStHLt, AeRHWUe FO the UeLYeS hHU tM IeeN the RFNheS HJNhHAet ML H NFeRe MO NHNeS, the eLeKC RHL RHNtWSe the NHNeS, YFURMXeS the IeC, HLY SeHY HLC RMKKWLFRHtFMLU thHt hHXe AeeL eLRSCNteY ZFth Ft. hMZeXeS FO the IeC RHL Ae RMKKFtteY tM KeKMSC Ft FU JeUU JFIeJC tM OHJJ FLtM eLeKC hHLYU.

Reading carefully we see the single letter word H, and the four letter word thHt in the first line, and guess that H enciphers the letter a. Making that replacement we get:

the aYXaLtaTe MO AWFJYFLT a RFNheS aJNhaAet FL thFU ZaC FU that Ft FU eaUC tM KeKMSFUe the IeCZMSY MS IeCNhSaUe, aLY heLRe the RFNheS aJNhaAet. thFU FU FKNMStaLt, AeRaWUe FO the UeLYeS haU tM IeeN the RFNheS aJNhaAet ML a NFeRe MO NaNeS, the eLeKC RaL RaNtWSe the NaNeS, YFURMXeS the IeC, aLY SeaY aLC RMKKWLFRatFMLU that haXe AeeL eLRSCNteY ZFth Ft. hMZeXeS FO the IeC RaL Ae RMKKFtteY tM KeKMSC Ft FU JeUU JFIeJC tM OaJJ FLtM eLeKC haLYU.

Now the two  2 letter words Ft FU are probably “it is” meaning that F enciphers “i” and U enciphers “s”. Hence we get:

the aYXaLtaTe MO AWiJYiLT a RiNheS aJNhaAet iL this ZaC is that it is easC tM KeKMSise the IeCZMSY MS IeCNhSase, aLY heLRe the RiNheS aJNhaAet. this is iKNMStaLt, AeRaWse iO the seLYeS has tM IeeN the RiNheS aJNhaAet ML a NieRe MO NaNeS, the eLeKC RaL RaNtWSe teh NaNeS, YisRMXeS the IeC, aLY SeaY aLC RMKKWLiRatiMLs that haXe AeeL eLRSCNteY Zith it. hMZeXeS iO the IeC RaL Ae RMKKitteY tM KeKMSC it is Jess JiIeJC tM OaJJ iLtM eLeKC haLYs.

Continuing with appropriate guesses (haXe = have, easC = easy and so on) we decipher the text to get the following extract from Simon Singh’s excellent history of codes and ciphers, The Code Book:

“The advantage of building a cipher alphabet in this way is that it is easy to memorise the keyword or keyphrase, and hence the cipher alphabet. This is important, because if the sender has to keep the cipher alphabet on a piece of paper, the enemy can capture the paper, discover the key, and read any communications that have been encrypted with it. However if the key can be committed to memory it is less likely to fall into enemy hands."

Frequency analysis

 A more methodical attack is frequency analysis. One counts the number of occurrences of each character in the cipher text and compares it with an expected frequency for the standard English alphabet. In the cipher text above a character count gives us the following table of occurrences:

Compare this to a table of expected frequencies, taken from Simon Singh’s “The Code Book”:

Using this and information about common one, two and three letter words we have enough to begin to tackle the cipher.

Disguising the word structure

 The chink in the armour of our ciphers so far has been the preservation of word structure. This allows one to spot common words. In order to avoid such weakness cryptographers usually remove punctuation and block the characters together in groups of four or five, so our previous cipher text looks like

VEPHY XHLVH TPMOA WFJYF LTHRF NEPSH JNEHA PVFLV EFUZH CFUVE HVFVF UPHUC VMKPK MSFUP VEPIP CZMSY MSIPC NESHU PHLYE PLRPV EPRFN EPSHJ NEHAP VVEFU FUFKN MSVHL VAPRH WUPFO VEPUP LYPSE HUVMI PPNVE PRFNE PSHJN EHAPV MLHNF PRPMO NHNPS VEPPL PKCRH LRHNV WSPVE PNHNP SYFUR MXPSV EPIPC HLYSP HYHLC RMKKW LFRHV FMLUV EHVEH XPAPP LPLRS CNVPY ZFVEF VEMZP XPSFO VEPIP CRHLA PRMKK FVVPY VMKPK MSCFV FUJPU UJFIP JCVMO HJJFL VMPLP KCEHL YU

Usually the length of the text groups doesn’t matter, however, in analysing a Vigenère cipher (see below) a carelessly chosen block length may make the length of the keyword more apparent, since it can reveal the repetitions more easily.

To attack cipher text that has been grouped in this way we have to work with letters not words. To do so we use the frequency analysis described above, together with a little judgement (or luck!). The process can be hard, but wars have been won or lost on the back of it, and so have fortunes.

“It was hard going, but Jericho didn’t mind. He was taking action, that was the point. It was the same as code-breaking. However hopeless the situation, the rule was always to do something. No cryptogram, Alan Turing used to say, was ever solved by simply staring at it.” From Enigma, by Robert Harris.

Affine shift ciphers

Despite the advantages for an agent in using keyword substitution ciphers most modern ciphers are automated and rely on a mathematical encryption algorithm. Indeed the Caesar shift cipher can be viewed as just such a cipher:

We start by encoding each letter by its numerical position in the alphabet:

Next we shift the alphabet by adding 3 to each position:

Of course 24+3 = 27 ≠ 1, but here we are carrying out modular arithmetic, familiar as clock arithmetic, so that when we reach 26 we continue from 1.

Finally we replace the numbers with the letters they stand for:

This recovers the cipher table constructed in lesson plan 1 for the Caesar shift by 3.

There is a convenient shorthand for the Caesar shift by n, given by xà x+n. It is confusing since here we are using x to stand for the position of a letter, and n to stand for the shift amount, i.e., x and n are each one of the values 1 … 26.  It is clear that since the shift is defined by the integer n there are only 26 Caesar shift ciphers.

There is a bigger class of shift ciphers which can be written in these terms known as the affine shift ciphers, and they exploit the fact that we can multiply as well as add integers in modular arithmetic. It is slightly complicated to set up formally but rather easy to do in practice so we will work through an example.

The affine shift x -> 3x+5

We start as before with the position table, but this time instead of replacing a position x with the number x+3 we will replace it by the number 3x+5, where this number is interpreted appropriately. So for example 2 à 3.2+5 = 11, while 8 à 3.8+5 = 29 which is interpreted as 3 (29=26+3). Whenever the result of the computation is larger than 26 we keep subtracting 26 until it becomes smaller. More formally we compute 3x+5 and then take the remainder after division by 26. This yields the table:

And from this we recover the encryption table as given on the handout for lesson 3:

The affine shift ciphers can also be written in a shorthand form x à ax+b and the Caesar shift ciphers are special cases of the affine shift ciphers with a=1.

Now notice that in both the Caesar shift x -> x+3 and the affine shift x à 3x+5 the letter y is enciphered as B, since 25+3 = 28 = 26+2, and 3.25+5 = 80  = 3.26+2. It follows that two different affine shift ciphers can encrypt a letter in the same way, so it is no longer sufficient to discover the letter substituting for e in order to decipher the message. Since there are two degrees of freedom in our choice of cipher we might hope that deciphering two letters is sufficient, and it is, since, if we know two values of the expression ax+b we can solve the two corresponding simultaneous equations to find a and b.

We may be more familiar with this exercise when solving the equations over the real numbers, but the same method works for modular arithmetic, with the caveat that in general we cannot divide. This caveat has an interpretation in cryptography. In order for the rule x -> ax+b to define a cipher it had better be the case that each of the numbers 1 … 26 appears exactly once in the list of numbers ax+b as x ranges from 1 to 26. If we choose a carelessly (so that we can’t divide by a mod 26) this might not be the case.

For example the rule x -> 2x tries to encipher both m and z as Z, since 2.13=26 and 2.26 = 52 both of which are equal to 26 modulo 26. Such an encryption cannot easily be deciphered since the recipient of the message is unable to determine whether the sender intended Z to be read as m or z.

From a mathematician’s point of view the enciphering rule defines a function from the alphabet to itself, and this needs an inverse if the cipher is to be decipherable in a deterministic way. In other words the number theory function x -> ax+b needs to have an inverse in mod 26 arithmetic. It is a fact from elementary number theory that it will have such an inverse if and only if a is coprime to 26, that is, their only common divisor is 1.

There are 12 numbers less than 26 and coprime to it (those odd numbers not divisible by 13) so we have 12 possible choices of the number a, and 26 choices for the number b, yielding 312 affine shift ciphers. This makes a brute force attack, without frequency analysis, less practical than the much simpler situation for Caesar shift ciphers.

Polyalphabetic ciphers

The main weakness allowing us to tackle a substitution cipher is the irregularity in the distribution of letters in English text. Other languages demonstrate similar (though language specific) irregularities and you can find frequency tables for them on the web.

In order to remove this weakness from a cipher it is necessary to disguise the frequencies of letters in the plaintext and the easiest way to do this is by using a polyalphabetic cipher. In such a cipher each plaintext letter may be encoded in more than one way so that, for example, the letter e may be enciphered as both X and G within the ciphertext. One problem with this approach is that if X and G both encode for e we don’t have enough letters left to encode the other 25 letters. One elegant solution to this problem is the famous French cipher known as the Vigenère cipher.

In a Vigenère cipher ANY letter might be encoded by any other; a given Vigenère cipher uses a subset of the 26 possible Caesar shift ciphers. Of course for a genuine recipient to have any hope of deciphering the message there has to be a way to determine for each cipher character which of the shifts has been used. The answer to this tricky problem is to choose a sequence of them known to both parties but to no-one else.

So the two parties might agree to use shifts of 22, 9, 7, 5, 14, 5 18, and 5 in that order and to continue repeating the pattern for the entire text: 22, 9, 7, 5, 14, 5 18, 5, 22, 9, 7, 5, 14, 5 18, 5, 22, 9 etc..

In order to decode the cipher text the recipient shifts the first cipher character back by 22, the second back by 9 and so on to recover the cipher text. Of course the question remains how one can memorise the correct sequence, but here we borrow an idea from the keyword cipher. The shift numbers 1, …, 26 are taken to stand for the alphabet a, …, z, and then the pattern 22, 9, 7, 5, 14, 5 18, 5 spells the word vigenere.

To set up a Vigenère cipher the two parties agree in advance to use the shift pattern encoded by some agreed keyword or phrase; in our previous Golden Jubilee Cipher challenge we used a Vigenère cipher based on the keyword GOLD, so characters were shifted in turn by 7, 15, 12, 4. Such a cipher is very hard to crack.

The method we recommend is due to Babbage and Kasiski who independently discovered it, and is based on the regularity of the repetition. An  analysis of repeated strings of letters is used to try to determine the length of the keyword, and once this is done a standard frequency analysis is applied to each part of the ciphertext encoded by a single cipher. A very good account of Babbage-Kasiski deciphering can be read in chapter 2 of Simon Singh’s  The Code Book.