# 16.2: Substitution Ciphers - Mathematics

One simple encryption method is called a substitution cipher.

Substitution Cipher

A substitution cipher replaces each letter in the message with a different letter, following some established mapping.

A simple example of a substitution cipher is called the Caesar cipher, sometimes called a shift cipher. In this approach, each letter is replaced with a letter some fixed number of positions later in the alphabet. For example, if we use a shift of 3, then the letter A would be replaced with D, the letter 3 positions later in the alphabet. The entire mapping would look like: [1]

Original: (mathrm{ABCDEFGHIJKLMNOPQRSTUVWXYZ})

Maps to: (mathrm{DEFGHIJKLMNOPQRSTUVWXYZABC})

Example 1

Use the Caesar cipher with shift of 3 to encrypt the message: “We ride at noon”

Solution

We use the mapping above to replace each letter. W gets replaced with Z, and so forth, giving the encrypted message: ZH ULGH DW QRRQ.

Notice that the length of the words could give an important clue to the cipher shift used. If we saw a single letter in the encrypted message, we would assume it must be an encrypted A or I, since those are the only single letters than form valid English words.

To obscure the message, the letters are often rearranged into equal sized blocks. The message ZH ULGH DW QRRQ could be written in blocks of three characters as

ZHU LGH DWQ RRQ.

Example 2

Decrypt the message GZD KNK YDX MFW JXA if it was encrypted using a shift cipher with shift of 5.

Solution

We start by writing out the character mapping by shifting the alphabet, with A mapping to F, five characters later in the alphabet.

Original: (mathrm{ABCDEFGHIJKLMNOPQRSTUVWXYZ})

Maps to: (mathrm{FGHIJKLMNOPQRSTUVWXYZABCDE})

We now work backwards to decrypt the message. The first letter G is mapped to by B, so B is the first character of the original message. Continuing, our decrypted message is

Removing spaces we get BUYFIFTYSHARESA. In this case, it appears an extra character was added to the end to make the groups of three come out even, and that the original message was “Buy fifty shares.”

Try it Now 1

Decrypt the message BNW MVX WNH if it was encrypted using a shift cipher with shift 9 (mapping A to J).

SEND MONEY

Notice that in both the ciphers above, the extra part of the alphabet wraps around to the beginning. Because of this, a handy version of the shift cipher is a cipher disc, such as the Alberti cipher disk shown here[2] from the 1400s. In a cipher disc, the inner wheel could be turned to change the cipher shift. This same approach is used for “secret decoder rings.”

The security of a cryptographic method is very important to the person relying on their message being kept secret. The security depends on two factors:

1. The security of the method being used
2. The security of the encryption key used

In the case of a shift cipher, the method is “a shift cipher is used.” The encryption key is the specific amount of shift used.

Suppose an army is using a shift cipher to send their messages, and one of their officers is captured by their enemy. It is likely the method and encryption key could become compromised. It is relatively hard to change encryption methods, but relatively easy to change encryption keys.

During World War II, the Germans’ Enigma encryption machines were captured, but having details on the encryption method only slightly helped the Allies, since the encryption keys were still unknown and hard to discover. Ultimately, the security of a message cannot rely on the method being kept secret; it needs to rely on the key being kept secret.

Encryption Security

The security of any encryption method should depend only on the encryption key being difficult to discover. It is not safe to rely on the encryption method (algorithm) being kept secret.

With that in mind, let’s analyze the security of the Caesar cipher.

Example 3

Suppose you intercept a message, and you know the sender is using a Caesar cipher, but do not know the shift being used. The message begins EQZP. How hard would it be to decrypt this message?

Solution

Since there are only 25 possible shifts, we would only have to try 25 different possibilities to see which one produces results that make sense. While that would be tedious, one person could easily do this by hand in a few minutes. A modern computer could try all possibilities in under a second.

(egin{array}{|l|l|l|l|l|l|l|l|}
hline extbf { Shift } & extbf { Message } & extbf { Shift } & extbf { Message } & extbf { Shift } & extbf { Message } & extbf { Shift } & extbf { Message }
hline 1 & ext { DPYO } & 7 & ext { XJSI } & 13 & ext { RDMC } & 19 & ext { LXGW }
hline 2 & ext { COXN } & 8 & ext { WIRH } & 14 & ext { QCLB } & 20 & ext { KWFV }
hline 3 & ext { BNWM } & 9 & ext { VHQG } & 15 & ext { PBKA } & 21 & ext { JVEU }
hline 4 & ext { AMVL } & 10 & ext { UGPF } & 16 & ext { OAJZ } & 22 & ext { IUDT }
hline 5 & ext { ZLUK } & 11 & ext { TFOE } & 17 & ext { NZIY } & 23 & ext { HTCS }
hline 6 & ext { YKTJ } & mathbf{1 2} & extbf { SEND } & 18 & ext { MYHX } & 24 & ext { GSBR }
hline & & & & & & 25 & ext { FRAQ }
hline
end{array})

In this case, a shift of 12 (A mapping to M) decrypts EQZP to SEND. Because of this ease of trying all possible encryption keys, the Caesar cipher is not a very secure encryption method.

Brute Force Attack

A brute force attack is a method for breaking encryption by trying all possible encryption keys.

To make a brute force attack harder, we could make a more complex substitution cipher by using something other than a shift of the alphabet. By choosing a random mapping, we could get a more secure cipher, with the tradeoff that the encryption key is harder to describe; the key would now be the entire mapping, rather than just the shift amount.

Example 4

Use the substitution mapping below to encrypt the message “March 12 0300”

Original: (mathrm{ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789})

Maps to: (mathrm{2BQF5WRTD8IJ6HLCOSUVK3A0X9YZN1G4ME7P})

Solution

Using the mapping, the message would encrypt to 62SQT ZN Y1YY

Try it Now 2

Use the substitution mapping from Example 4 to decrypt the message C2SVX2VP

PARTY AT 9

While there were only 25 possible shift cipher keys (35 if we had included numbers), there are about 1040 possible substitution ciphers[3]. That’s much more than a trillion trillions. It would be essentially impossible, even with supercomputers, to try every possible combination. Having a huge number of possible encryption keys is one important part of key security.

Unfortunately, this cipher is still not secure, because of a technique called frequency analysis, discovered by Arab mathematician Al-Kindi in the 9th century. English and other languages have certain letters than show up more often in writing than others.[4] For example, the letter E shows up the most frequently in English. The chart to the right shows the typical distribution of characters.

Example 5

The chart to the right shows the frequency of different characters in some encrypted text. What can you deduce about the mapping?

Solution

Because of the high frequency of the letter S in the encrypted text, it is very likely that the substitution maps E to S. Since W is the second most frequent character, it likely that T or A maps to W. Because C, A, D, and J show up rarely in the encrypted text, it is likely they are mapped to from J, Q, X, and Z.

In addition to looking at individual letters, certain pairs of letters show up more frequently, such as the pair “th.” By analyzing how often different letters and letter pairs show up an encrypted message, the substitution mapping used can be deduced[5].

[1] en.Wikipedia.org/w/index.php?title=File:Caesar3.svg&page=1. PD

[2] en.Wikipedia.org/wiki/File:Alberti_cipher_disk.JPG

[3] There are 35 choices for what A maps to, then 34 choices for what B maps to, and so on, so the total number of possibilities is 35*34*33*…*2*1 = 35! = about 1040

[4] en.Wikipedia.org/w/index.php?title=File:English_letter_frequency_(alphabetic).svg&page=1 PD

[5] For an example of how this is done, see en.Wikipedia.org/wiki/Frequency_analysis

In cryptography, a cipher (or cypher) is a method for protecting data through encryption and decryption. Most ciphers require a specific key for encryption and decryption, but some ciphers like the ROT13 or Atbash ciphers have fixed keys. Many of the ciphers listed here were for military or other significant use during an earlier time, but today mostly are used only by puzzle makers.

Modern encryption methods can be divided by the key type and their operation on input data. Symmetric key algorithms use the same key for encryption and decryption (private key cryptography). Asymmetric key algorithms use different keys for encryption and decryption (public key cryptography). With symmetric keys, the sender and receiver must have agreed upon a key in advance, while with asymmetric keys anyone can send messages to the receiver. Also depending on their operation, ciphers are either block ciphers (encrypting a fixed block size) or stream ciphers (encrypting a continuous stream of data).

## Caesar Shift (Substitution Cipher)

A Caesar Shift cipher is a type of mono-alphabetic substitution cipher where each letter of the plain text is shifted a fixed number of places down the alphabet. For example, with a shift of 1, letter A would be replaced by letter B, letter B would be replaced by letter C, and so on. This type of substitution Cipher is named after Julius Caesar, who used it to communicate with his generals.

Key +5
Plain text alphabet: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
/>
Cipher text alphabet: F G H I J K L M N O P Q R S T U V W X Y Z A B C D E

This type of cipher is a form of symmetric encryption as the same key can be used to both encrypt and decrypt a message. (e.g. If a message is encrypted with a key of +5, it can be decrypted with a key of -5).

You can generate your own encryption keys and encrypt your own messages using our online Caesar Shift substitution engine:

#### Frequency Analysis

SPAASL KVLZ SBRL RUVD AOHA AOL NHSHJAPJ LTWPYL OHZ ZLJYLASF ILNBU JVUZAYBJAPVU VU H ULD HYTVYLK ZWHJL ZAHAPVU LCLU TVYL WVDLYMBS AOHU AOL MPYZA KYLHKLK KLHAO ZAHY.

DOLU JVTWSLALK, AOPZ BSAPTHAL DLHWVU DPSS ZWLSS JLYAHPU KVVT MVY AOL ZTHSS IHUK VM YLILSZ ZAYBNNSPUN AV YLZAVYL MYLLKVT AV AOL NHSHEF…”

## Substitution cipher decoder

The calculator below automatically decodes the text enciphered with the simple substitution cipher without knowing the key. The calculator logic is explained below the calculator.

#### Substitution cipher breaker

In cryptography, a substitution cipher is a method of encrypting by which units of plaintext are replaced with ciphertext, according to a fixed system the "units" may be single letters (the most common), pairs of letters, triplets of letters, mixtures of the above, and so forth. The receiver deciphers the text by performing the inverse substitution. Substitution of single letters separately — simple substitution — can be demonstrated by writing out the alphabet in some order to represent the substitution. It is a cipher key, and it is also called a substitution alphabet. 1

For a simple substitution cipher, the set of all possible keys is the set of all possible permutations. Thus, for the English alphabet, the number of keys is 26! (factorial of 26), which is about . Because of this, if you want to decipher the text without knowing the key, the brute force approach is out of the question.

However, the simple substitution cipher is considered a weak cipher because it is vulnerable to cryptoanalysis. First of all, substitution does not change the letters' frequencies, so if you have a decent amount of enciphered text and you know the language it was written in, you can try frequency analysis. For example, the most common letter in the English language is E, so, most common letter in the encrypted text is probable the E substitution. The analyst also looks for bigrams and trigrams frequencies because some unigram frequencies are too close to each other to rely on them. Using frequencies, analysts can create trial keys and test them to see if they reveal some words and phrases in the encrypted text.

But this manual approach is time-consuming, so the goal of an automated solution is to exclude humans from the process of breaking the cipher. And it is possible due to another simple substitution cipher vulnerability, known as Utility of Partial Solution.

In other words, if there are many pairs of keys in the keyspace where the decryption of the ciphertext by the key more similar to the correct key more closely resembles the plaintext than the decryption of the ciphertext by the other key, the cipher has Utility of Partial Solutions. If there is a correlation between the degree to which a key resembles the correct key and the degree to which that key's decryption of the ciphertext resembles the plaintext, it should be possible to search the keyspace efficiently by quickly discarding keys that are "worse" than whatever key is the closest match at any moment, climbing ever closer to the optimal key without knowing it initially. These keyspaces can be searched via Stochastic Optimization Algorithms. 2

The tricky part here is how you can measure if one key is "worse" than another. We need text fitness to address this, which gives us some score on how the given text looks like typical English text. There are different approaches, and I've tried this and that, but one which worked for me is outlined here: Text fitness (version 3). In short, it uses the sum of log probabilities of quadgrams and compares the sum with the sum for the "normal" English text (created as the sum of log probabilities of the most often English quadgrams). Here I'd like to thank Jens Guballa (site), author of another substitution solver, who kindly gives me a hint that text fitness function should be "normalized."

The implementation below uses a genetic algorithm to search for the correct key. If it fails, you can repeat a couple of times (each time it starts from a set of random keys as an initial generation) or tweak the settings, for example, increase the number of generations. Just click the Details to reveal additional settings. In this mode, the calculator also displays the best key in each generation, which is quite curious to watch.

If you see that the found key is close to the correct one but misses a couple of letters, you may use Substitution cipher tool to manually test the keys.

The Bifid cipher was invented by the French amateur cryptographer Félix Delastelle around 1901, and is considered an important invention in cryptology. It uses a combination of a Polybius square and transposition of fractionated letters to encrypt messages.

The two-square cipher is also called "double Playfair". It is stronger than an ordinary Playfair cipher, but still easier to use than the four-square cipher. Depending on the orientation of the squares, horizontal or vertical, the cipher behaves slightly different.

## The Germans and the Russians: Real Codes Decrypted

Let’s try running our code on a test message:

In addition to being correct, most of the attempts were very close as well, giving the first few letters such decodings as “coroti” or “gorothy”. Let’s try a harder one. This message was sent by Baron August Schluga, a German spy in WWI (source):

Here’s a code sent by Aldrich Ames, the most notorious CIA mole to have ever been caught. It was a portion of a message sent in 1992 that was found on his person when he was arrested:

This is a bit more disheartening because it’s obviously close to correct, but not quite there. A human can quickly fix the errors, switching p with m, and z and k. That being said, perhaps by slightly increasing the number of steps we could find our way to the right decryption.

Here’s another, from the same source above, sent by Confederate General J.E. Johnston during the Siege of Vicksburg, May 25, 1863 during the U.S. Civil War. It was intercepted and then deciphered by Lincoln’s three-man team of cryptanalysts:

Again, we are close but not quite there. In fact, this time the decryption even fails to segment the last block, even when there are useful pieces inside it. This is a side-effect of our zealous segmentation model that punishes unknown words exponentially in their length.

Unfortunately, our program seems to fail more often than succeed. Indeed, the algorithm is not all that good. One might hope the following function is usually the identity on any given message, but it rarely is:

In fact I have yet to see one example of this function returning sensible output for any input.

That last one was close, but still rather far off. What’s more, for random small inputs the function seems to generate sensible output!

Disregarding the fun we could have decrypting random message, we cry, “What gives?!” It seems that there’s some sort of measure of entropy that comes into play here, and messages with less entropy have a larger number of interpretations. Here entropy could mean the number of letters used in the message, the number of distinct letters used in the message, or some combination of both.

The last obvious annoyance is that thee program is really slow. If we watch the intermediate computations, we note that it will sometimes approach the correct solution, and then stray away. And what’s more, the number of steps per run is fixed. Why couldn’t it be based on the amount of progress it has made so far, pushing those close solutions a bit further to the correct key, perhaps by spending more time just on those successful decryptions.

Next time, we’ll spend our time trying to improve the steepest ascent algorithm. We’ll try to make it more quickly abandon crappy starting positions, and squeeze the most out of successful runs. We’ll further do some additional processing in our search for neighboring keys, and potentially involve letter 2-, 3-, 4-, and even 5-grams.

But all in all, this worked out pretty well. We often emphasize the deficiencies of our algorithms, but here we have surprisingly many benefits. For one, we actually decoded real-life messages! With this program in hand even as few as twenty years ago, we would have had a valuable tool for uncovering nefarious secrets encoded via substitution.

Even more, by virtue of our data-driven solution, we inherently bolster our algorithm with additional security. It’s stable, in the sense that minor data corruption (perhaps a typo, or nefarious message obfuscation) is handled well: our segmentation algorithm allows for typos, and a message with one or two typos still had a high letter trigram score in our probabilistic model. Hence we trivially bypass any sort of message obfuscation: if the average human can make sense of the decrypted message, so could our program.

And as with word segmentation, it’s extensible: simply by swapping out the data sets and making minor alphabet changes, we can make our program handle encrypted messages in any language. This exponentially increases the usefulness of our approach, because data sets are cheap, while sophisticated algorithms are expensive (at least, good ones can be sophisticated).

So look forward to next time when we improve the accuracy and speed of the steepest-ascent algorithm.

## Source code

dCode retains ownership of the online 'Mono-alphabetic Substitution' tool source code. Except explicit open source licence (indicated CC / Creative Commons / free), any 'Mono-alphabetic Substitution' algorithm, applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any 'Mono-alphabetic Substitution' function (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and no data download, script, copy-paste, or API access for 'Mono-alphabetic Substitution' will be for free, same for offline use on PC, tablet, iPhone or Android ! dCode is free and online.

## Substitution cipher tool

A tool to encrypt/decrypt messages with a simple substitution cipher given as the key. It is also useful for manual cryptanalysis of a substitution cipher - when you have a message written in the English alphabet partially decrypted with an automatic tool and want to tweak the key.

This simple tool allows you to encode and decode messages with a simple substitution cipher. For a cipher breaker, see Substitution cipher breaker. You can read a cipher description and some considerations regarding the strength of a cipher below the calculator.

#### Substitution Cipher Tool

According to Wikipedia, in cryptography, a substitution cipher is a method of encrypting by which units of plaintext are replaced with ciphertext, according to a fixed system the "units" may be single letters (the most common), pairs of letters, triplets of letters, mixtures of the above, and so forth. The receiver deciphers the text by performing the inverse substitution.

A simple substitution is the substitution of single letters separately. The substitution key is usually represented by writing out the alphabet in some order. The Caesar cipher is a form of a simple substitution cipher. For example, its ROT2 key can be presented as CDEFGHIJKLMNOPQRSTUVWXYZAB. This means that A is replaced with C, B with D, and so on.

The number of all possible keys for a simple substitution cipher is a factorial of 26 (26!). However, you can break it if you have enough ciphered text by using frequency analysis or the stochastic optimization algorithm (check out our Substitution cipher breaker). The cipher does not change language letter frequencies (it is said to be monoalphabetic), unlike, for example, the polyalphabetic Vigenère cipher, so it is considered to be rather weak.

Paste text into the field, fill the key, choose "encode" if you have pasted clear text or "decode" if you have pasted ciphered text, and press "Calculate". Traditionally, punctuation and spaces are removed to disguise word boundaries and text is written in blocks of letters, usually five. This option is supported for encoding as well.

## 16.2: Substitution Ciphers - Mathematics

In cryptography we encrypt messages that contains letters, but substitution ciphers are based on arithmetic operations on integers. Therefore, we have to convert the letters into integers before we apply the cryptosystem on the message. Because we use the English alphabet with 26 letters we have the following conversion between letters and integers:

 a b c d e f g h i j k l m 0 1 2 3 4 5 6 7 8 9 10 11 12
 n o p q r s t u v w x y z 13 14 15 16 17 18 19 20 21 22 23 24 25
E.g. the letter "a" is converted into the integer "0", the letter "b" into "1" and so on.

#### Modulo computation

You already use modulo computation when you look at the clock and e.g. needs to figure out what time it's 3 hours after 11 o'clock, which is 2 o'clock. In math we write that as:

where 12 is the modulus because we want the time as an integer between 0 and 11 (12 o'clock is in this case denoted by 0). In words we say 11 plus 3 modulo 12 is equal 2. The result of a modulo computation is an integer between 0 and the modulus minus 1. E.g. with the modulus 3 we have that:

• ( 1 : mod : 3 = 1 )
• ( 2 : mod : 3 = 2 )
• ( 3 : mod : 3 = 0 )
• ( 4 : mod : 3 = 1 )
• ( 5 : mod : 3 = 2 )
• ( 6 : mod : 3 = 0 )
• etc.

If we e.g. look at ( 27 : mod : 5 ) then modulo computes the number of times 5 divides 27 and then returns the remainder of the result which is 2 in this case, i.e. ( 27 : mod : 5 = 2 ). But how did we get this result?

First we compute the number of times it's possible to multiply 5 with the number ( x ) such that we get an integer as close as possible to 27 without exceeding it, i.e. we have to find the maximun value of ( x ) such that ( 5 cdot x leq 27 ). In this case we have that ( x = 5 ) because ( 5 cdot 5 = 25 leq 27 ). Then by subtracting 27 with 25 we get the answer ( 27 - 25 = 2).

If the integer is negative e.g. ( -27 : mod : 5 ) we have to do it slightly different and the answer is ( -27 : mod : 5 = 3 ). In this case the integer ( x ) is negative and should be the closest integer that exceed -27, i.e. we have to find the minimum value of ( -x ) such that ( 5 cdot -x geq -27 ). Now we have that ( -x = -6 ) because ( 5 cdot -6 = -30 geq -27 ). Then by subtracting -27 with -30 we get the answer ( -27 - (-30) = -27 + 30 = 3).

It's important that ( x ) or ( -x ) is an integer such as ( -14, 3, 17 ) etc. and NOT a fraction or float such as ( frac<1><4>, frac<-3><7>, 2.5, 5.1 ) etc.

If two integers ( a ) and ( b ) modulo the same modulus ( c ) returns the same remainder ( r ), then we say that ( a ) and ( b ) are congruent modulo ( c ). I.e. if ( a : mod : c = r ) and ( b : mod : c = r ) then ( a equiv b : (mod : c) ). Also, notice that if the modulus ( c ) is greater than the integer ( a ), i.e. ( c > a ), the result will always be equal ( a : mod : c = a ).

#### Greatest common divisor

Before we describe what the greatest common divisor of two integers are, we first define what we mean by a divisor. In this context is a divisor of an integer ( x ) some integer that divides ( x ) evenly, i.e. the result must not be a float. E.g. if you try to divide ( x=12 ) with 5 it returns the float ( frac<12> <5>= 2.4 ) and 5 is therefore not a divisor of ( x=12 ). For ( x=12 ) we have the divisors 1, 2, 3, 4, 6 and 12 because ( frac<12> <1>= 12 ), ( frac<12> <2>= 6 ), ( frac<12> <3>= 4 ), ( frac<12> <4>= 3 ), ( frac<12> <6>= 2 ) and ( frac<12> <12>= 1 ).

Likewise the divisors of 16 is 1, 2, 4, 8 and 16 because ( frac<16> <1>= 16 ), ( frac<16> <2>= 8 ), ( frac<16> <4>= 4 ), ( frac<16> <8>= 2 ) and ( frac<16><16>=1 ).

The greatest common divisor of 12 and 16 is therefore 4, because it is the largest integer of the common divisors. In math we write that as ( gcd(12, 16) = 4 ).

Two integers with greatest common divisor 1 are called relatively prime numbers or co-primes. E.g. 15 and 28 are relatively prime numbers because ( gcd(15, 28) = 1 ) (notice that 28 is not a prime number).

If one of the two integers is a prime number the greatest common divisor will always be 1, i.e. ( gcd(a, p) = 1 ) where ( a ) is an integer (either a prime number or a composite number) and ( p ) is a prime number.

One method to compute the greatest common divisor of two integers is by using the Euclidean algorithm developed by the famous Greek mathematician Euclid. See "The extended Euclidean algorithm" for more information about how to compute the greatest common divisor of two integer.

#### The extended Euclidean algorithm

The extended Euclidean algorithm is an extended version of the Euclidean algorithm, which only returns the greatest common divisor of two integers. Given two integers ( a ) and ( b ) the extended Euclidean algorithm returns the integers ( a ), ( b ), ( lambda ) and ( mu ) such that:

( a cdot lambda + b cdot mu = gcd(a, b) )

where ( lambda ) and ( mu ) are called the Bézout coefficients for ( a ) and ( b ). Only if ( a ) and ( b ) are relatively prime numbers, i.e. ( gcd(a, b) = 1 ), then:

( a cdot lambda + b cdot mu = 1 )

and ( lambda mod b ) is the inverse of ( a ), denoted ( a^ <-1>= lambda mod b ), and ( mu : mod : a ) is the inverse of ( b ), denoted ( b^ <-1>= mu : mod : a ) (see "Modulo computation" for more information about the ( mod ) operator). One useful property of an integer and its inverse is that ( a cdot a^ <-1> mod b = 1 ) and ( b cdot b^ <-1> mod a = 1 ).

You can easily compute ( gcd(a, b) ), ( lambda ) and ( mu ) for e.g. ( a=5 ) and ( b=39 ) with a simple table. So, let us first create a table with 3 columns (we do not yet know how many rows there will be in the table). Let us denote the entry in the first row and first column for [1,1], the entry in the first row and second column for [1,2], the entry in the second row and first column for [2,1] and so on.

Next we write ( b=39 ) in entry [1,1] and ( a=5 ) in entry [2,1]. Then we try to find the biggest integer ( q_ <1>), such that ( q_ <1>cdot a leq b ). We have that ( q_<1>=7 ), which we write in entry [2,2], because ( 7 cdot 5 = 35 leq 39 ) and a remainder of ( r_<1>=4 ), which we write in entry [3,1].

Again we try to find the biggest integer ( q_ <2>), such that ( q_ <2>cdot r_ <1>leq a ). We have that ( q_<2>=1 ), which we write in entry [3,2], because ( 1 cdot 4 = 4 leq 5 ) and a remainder of ( r_<2>=1 ) that we write in entry [4,1]. Notice that we just computed the same as before, just with integers in a lower row.

The next computation returns a remainder of ( r_ <3>= 0 ) because ( q_ <3>cdot r_ <2>= 4 cdot 1 = 4 leq 4 = r_ <1>). We have now computed ( gcd(5, 39)=r_<2>=1 ) since ( r_ <3>= 0 ). And because 5 and 39 are relatively prime numbers, we know that ( lambda ) and ( mu ) exists and we can then start using the last column.

First we write ( x_<1>=0 ) in entry [4,3] and ( x_<2>=1 ) in entry [3,3]. Then we write ( x_<3>=q_ <2>cdot x_ <2>+ x_ <1>= 1 cdot 1 + 0 = 1 ) in entry [2,3]. For entry [1,3] we compute the same as before, just with integers from the row above, i.e. ( x_<4>=q_ <1>cdot x_ <3>+ x_ <2>= 7 cdot 1 + 1 = 8 ).

Finally we have that ( a cdot x_ <4>pm b cdot x_ <3>= r_ <2>), where we need to decide whether it should be plus or minus between the two terms. Because ( a cdot x_ <4>= 5 cdot 8 = 40 ), ( b cdot x_ <3>= 39 cdot 1) and ( 40 geq 39 ) we have that ( 5 cdot 8 - 39 cdot 1 = 1 ) (which is the same as ( 5 cdot 8 + 39 cdot (-1) = 1 )) and the Bézout coefficients are ( lambda=8 ) and ( mu=-1 ). Notice that ( a^ <-1>= lambda mod b = 8 mod 39 = 8) and ( b^ <-1>= mu mod a = -1 : mod : 5 = 4) where ( a cdot a^ <-1> mod b = 5 cdot 8 mod 39 = 1 ) and ( b cdot b^ <-1> mod a = 39 cdot 4 mod 5 = 1 ).

The table for computing ( 5 cdot lambda + 39 cdot mu = gcd(5, 39) ) is:

 ( b=39 ) ( x_<4>=8 ) ( a=5 ) ( q_<1>=7 ) ( x_<3>=1 ) ( r_<1>=4 ) ( q_<2>=1 ) ( x_<2>=1 ) ( r_<2>=1 ) ( q_<3>=4 ) ( x_<1>=0 ) ( r_<3>=0 )

#### The Caesar cipher explained

The Caesar cipher, also known as the shift cipher, is named after the Roman general Julius Caesar who used it to communicate with his officers during wars about the year of 50 BC. It's a simple substitution cipher where each letter in the alphabet is substituted with another letter by shifting it ( s ) times. It's said that Julius Caesar used the shift value ( s = 3 ).

Assume Alice wants to send a message ( m ) (also called the plaintext) to her friend Bob using the Caesar cipher. First they in advance agree on a shift value ( s ) and then Alice encrypts the message by shifting each letter in the message ( s ) times to the right which produces the ciphertext ( c ). She then sends the ciphertext to Bob who decrypts it by shifting each letters in the ciphertext ( s ) times to the left.

In the case with the shift value ( s = 3 ) the letter "a" in the plaintext becomes "D" in the ciphertext, "b" becomes "E", "c" becomes "F" etc. You may wonder what happens with the last letters in the alphabet because there is no letter appearing three letters after "x", "y" and "z". The answer is simple: we just use the same approach as modulo computation, i.e. "x" becomes "A", "y" becomes "B" and "z" becomes "C". The encryption table for ( s = 3 ) is illustrated in the following table where the plaintext letters are in lowercase and the ciphertext letters are in uppercase:

Encryption table for ( s = 3 )
a b c d e f g h i j k l m
D E F G H I J K L M N O P
n o p q r s t u v w x y z
Q R S T U V W X Y Z A B C

If we convert the letters into integers such that "a" is converted into "0", "b" is converted into "1", "c" is converted into "2" etc. then the encryption of the letter ( m_ ) in the message ( m ) is defined as ( c_ = (m_ + s) : mod : 26 ) and decryption is defined as ( m_' = (c_ - s) : mod : 26 ). The modulus is 26 because there is 26 letters in the English alphabet. It's easy to verify that ( m_' = m_ ) because:

##### The protocol
 Key exchange Alice and Bob agree on the shift value ( s ). Encryption Alice: Uses the shift value to compute the ciphertexts ( c_ = (m_ + s) : mod : 26 ) for ( i = 1, 2, dots n ) where ( n = |m| ) (the length of the plaintext ( m )). Alice sends the ciphertext ( c = (c_<1>, c_<2>, dots, c_) ) to Bob. Decryption Bob: Uses the shift value to decrypt the ciphertexts ( m_ = (c_ - s) : mod : 26 ) for ( i = 1, 2, dots n ) where ( n = |c| ) (the length of the ciphertext ( c )).
##### Example

Alice wants to send the message ( m = mbox <"meet me at the secret location">) to Bob. First they agree on the shift value ( s = 3 ) and then Alice converts the letters in ( m ) into the integers ( m_ <1>= 12, m_ <2>= 4, dots, m_ <25>= 13 ), which she encrypts:

( eqalign < c_<1>&= (m_ <1>+ s) : mod : 26 = (12 + 3) : mod : 26 = 15 c_ <2>&= (m_ <2>+ s) : mod : 26 = (4 + 3) : mod : 26 = 7 &vdots c_ <25>&= (m_ <25>+ s) : mod : 26 = (13 + 3) : mod : 26 = 16 > )

She then converts the ciphertexts ( c_ <1>= 15, c_ <2>= 7, dots, c_ <25>= 16 ) into letters and sends the ciphertext ( c = mbox <"PHHW PH DW WKH VHFUHW ORFDWLRQ">) to Bob.

Bob decrypts the received ciphertext almost just like Alice encrypted the message. First he converts the letters in the ciphertext ( c ) into the integers ( c_<1>, c_<2>, dots, c_ <25>) and then he decrypts them:

( eqalign < m_<1>&= (c_ <1>- s) : mod : 26 = (15 - 3) : mod : 26 = 12 m_ <2>&= (c_ <2>- s) : mod : 26 = (7 - 3) : mod : 26 = 4 &vdots m_ <25>&= (c_ <25>- s) : mod : 26 = (16 - 3) : mod : 26 = 13 > )

Finally he converts the plaintexts ( m_<1>, m_<2>, dots, m_ <25>) back into letters which result in the message ( m = mbox <"meet me at the secret location">).

#### The Affine cipher explained

The affine cipher is a combination of the Caesar cipher and a multiplication cipher: First Alice and Bob agrees on the two integers ( a ) and ( b ) between 0 and 25 such that ( gcd(a, 26) = 1 ) because during decryption her friend Bob needs the inverse ( a^ <-1>) of ( a ) which only exists when ( gcd(a, 26) = 1 ).

Alice then encrypts the message ( m ) by first converting each letter into integers where the letter "a" is converted into the integer "0", "b" is converted into "1", "c" is converted into "2" etc. Then for each integer ( m_ ) she computes ( c_ = (a cdot m_ + b) : mod : 26 ) (notice that if ( a=1 ) the affine cipher corresponds to the Caesar cipher with the sift value ( b )), converts each ( c_ ) back into letters and sends the ciphertext ( c ) to Bob. The modulus is 26 because there is 26 letters in the English alphabet.

Bob decrypts the ciphertext in a similar way as Alice encrypted the message. First he computes the inverse ( a^ <-1>) of ( a ) with the extended Euclidean algorithm, which gives him the equation ( a cdot lambda + 26 cdot mu = gcd(a, 26) ) where ( a^ <-1>= lambda mod 26 ) and ( a cdot a^ <-1>: mod : 26 = 1 ) (remember that ( a^ <-1>) only exists because ( gcd(a, 26) = 1 )). Then he converts each letter in ( c ) into integers ( c_ ), computes ( m_' = a^ <-1>cdot (c_ - b) : mod : 26 ) and finally he converts the integers ( m_' ) back into letters, which result in the message ( m ). We see that ( m_' = m_ ) because:

( eqalign< m_' &= a^ <-1>cdot (c_ - b) : mod : 26 &&(c_ = (a cdot m_ + b)) &= a^ <-1>cdot ((a cdot m_ + b) - b) : mod : 26 &=a^ <-1>cdot (a cdot m_) : mod : 26 &&(a cdot a^ <-1>: mod : 26 = 1) &= m_ : mod : 26 > )

##### The protocol
 Key exchange Alice and Bob agree on the values ( a ) and ( b ) such that ( gcd(a, 26) = 1 ). Encryption Alice: Uses the values ( a ) and ( b ) to compute the ciphertexts ( c_ = (a cdot m_ + b) : mod : 26 ) for ( i = 1, 2, dots n ) where ( n = |m| ) (the length of the plaintext ( m )). Alice sends the ciphertext ( c = (c_<1>, c_<2>, dots, c_) ) to Bob. Decryption Bob: Computes the inverse ( a^ <-1>) of ( a ) with the extended Euclidean algorithm. Uses ( b ) and ( a^ <-1>) to decrypt the ciphertexts ( m_ = a^ <-1>cdot (c_ - b) : mod : 26 ) for ( i = 1, 2, dots n ) where ( n = |c| ) (the length of the ciphertext ( c )).
##### Example

Alice wants to send the message ( m = mbox <"it begins at midnight">) to Bob. First they agree on the integers ( a = 15 ) and ( b = 9 ) where ( gcd(a, 26) = gcd(15, 26) = 1 ). Then Alice converts the letters in ( m ) into the integers ( m_ <1>= 8, m_ <2>= 19, dots, m_ <18>= 19 ), which she encrypts:

( eqalign < c_<1>&= (a cdot m_ <1>+ b) : mod : 26 = (15 cdot 8 + 9) : mod : 26 = 25 c_ <2>&= (a cdot m_ <2>+ b) : mod : 26 = (15 cdot 18 + 9) : mod : 26 = 19 &vdots c_ <18>&= (a cdot m_ <18>+ b) : mod : 26 = (15 cdot 19 + 9) : mod : 26 = 8 > )

She then converts ( c_ <1>= 15, c_ <2>= 7, dots, c_ <18>= 16) back into letters and sends the ciphertext ( c = mbox <"ZI YRVZWT JI HZCWZVKI">) to Bob.

When Bob receives the ciphertext he first computes the inverse ( a^ <-1>) of ( a = 15 ) with the extended Euclidean algorithm. The extended Euclidean algorithm gives him the equation ( gcd(a, 26) = a cdot lambda + 26 cdot mu = 15 cdot 7 + 26 cdot (-4) = 1 ) where ( a^ <-1>= lambda mod 26 = 7 mod 26 = 7 ). Then he converts the letters in ( c ) into the integers ( c_ <1>, c_<2>, dots, c_ <18>) and decrypts them:

( eqalign < m_<1>&= a^ <-1>cdot (c_ <1>- b) : mod : 26 = 7 cdot (15 - 9) : mod : 26 = 8 m_ <2>&= a^ <-1>cdot (c_ <2>- b) : mod : 26 = 7 cdot (7 - 9) : mod : 26 = 18 &vdots m_ <18>&= a^ <-1>cdot (c_ <18>- b) : mod : 26 = 7 cdot (16 - 9) : mod : 26 = 19 > )

Finally he converts ( m_ <1>, m_<2>, dots, m_ <18>) back into letters which result in the message ( m = mbox <"it begins at midnight">).

#### The Vigenére cipher explained

The Caesar and affine cipher are both monoalphabetic ciphers because once a key is chosen each letter is mapped uniquely to another letter. As cryptanalytic methods became more sophisticated in the 16th century more sophisticated ciphers were invented and one of them was the Vigenére cipher, which was invented by Blaise de Vigenére in the 16th century. The Vigenére cipher is a polyalphabetic cipher because each letter is encrypted and decrypted with different keys, i.e. the same letter can be mapped to multiple different letters.

##### Example

Alice wants to send the message ( m = mbox <"it is hidden at the bridge">) to Bob where ( n = |m| = 21). First they agree on the keyword ( K = mbox <"THEORY">) of length ( t = 6 ). Because ( t Try the cipher

The one-time pad described by Gilbert Vernam in 1917 is a perfectly secure cryptosystem when the used key is completely random and only used to encrypt a single message. Perfectly secure means that if Alice and Bob's common adversary Eve with infinity computing power intercept a ciphertext she learns nothing whatsoever about the message or the key.

Encryption and decryption in the one-time pad are almost identical to the one used in the Vigenére cipher which makes it very attractive because they are simple operations, but unfortunately the used key must have the same length as the message. If we could encrypt multiple messages with the same key this would not be a problem, but the key must only be used once to keep the one-time pad perfectly secure.

In the one-time pad Alice and Bob first agrees on a random key ( K ) of length ( n ) where ( n = |m| ) (the length of the message ( m )). Alice then encrypts the message ( m ) using the key ( K ) just like she did in the Vigenére cipher: She first converts the letters in the key ( K ) and the message ( m ) into the integers ( k_<1>, k_<2>, dots, k_ ) and ( m_<1>, m_<2>, dots, m_ ) respectively. Then she encrypts each letter by computing ( c_ = (m_ + k_) : mod : 26 ) where the modulus is 26 because the English alphabet has 26 letters. Finally she converts the integers ( c_<1>, c_<2>, dots, c_ ) into letters and sends the ciphertext ( c ) to Bob.

Bob decrypts the received ciphertext ( c ) in a similar way: he converts the key ( K ) and the ciphertext ( c ) into the integers ( k_<1>, k_<2>, dots, k_ ) and ( c_<1>, c_<2>, dots, c_ ) respectively and computes ( m_' = (c_ - k_) : mod : 26 ). Finally he converts the integers ( m_<1>', m_<2>', dots, m_' ) into letters, which result in the message ( m ). We have that ( m_' = m_ ) because:

##### The protocol
 Key exchange Alice and Bob agree on the key ( K = (k_<1>, k_<2>, dots, k_) ) where ( n = |m| ) (the length of the message ( m )). Encryption Alice: Uses the key ( k_ ) to compute the ciphertext ( c_ = (m_ + k_) : mod : 26 ) for ( i = 1, 2, dots, n ). Alice sends the ciphertext ( c = (c_<1>, c_<2>, dots, c_) ) to Bob. Decryption Bob: Uses the key ( k_ ) to decrypt the ciphertext ( m_ = (c_ - k_) : mod : 26 ) for ( i = 1, 2, dots, n ).
##### Example

Alice wants to send the message ( m = mbox <"meet me tomorrow morning">) to Bob where ( n = |m| = 21 ). First they agree on a random key with the same length as the message: ( K = mbox <"WVJLQCOEUTYJNNUGDROVS">) . She then converts the letters in ( K ) and ( m ) into the integers ( k_ <1>= 22, k_ <2>= 21, dots, k_ <21>= 18 ) and ( m_ <1>= 12, m_ <2>= 4, dots, m_ <21>= 6 ) respectively and computes:

( eqalign < c_<1>&= (m_ <1>+ k_<1>) : mod : 26 = (12 + 22) : mod : 26 = 8 c_ <2>&= (m_ <2>+ k_<2>) : mod : 26 = (4 + 21) : mod : 26 = 25 &vdots c_ <21>&= (m_ <21>+ k_<18>) : mod : 26 = (6 + 18) : mod : 26 = 24 > )

She then converts ( c_ <1>= 8, c_ <2>= 25, dots, c_ <21>= 24 ) back into letters and sends the ciphertext ( c = mbox <"IZNE CG HSGHPABJ GUUEWIY">) to Bob.

When Bob receives the ciphertext he converts the letters in ( K ) and ( c ) into the integers ( k_ <1>, k_<2>, dots, k_ <21>) and ( c_ <1>, c_<2>, dots, c_ <21>) respectively and computes:

( eqalign < m_<1>&= (c_ <1>- k_<1>) : mod : 26 = (8 - 22) : mod : 26 = 12 m_ <2>&= (c_ <2>- k_<2>) : mod : 26 = (25 - 21) : mod : 26 = 4 &vdots m_ <21>&= (c_ <21>- k_<18>) : mod : 26 = (24 - 18) : mod : 26 = 6 > )

Finally he converts ( m_ <1>, m_<2>, dots, m_ <21>) back into letters, which result in the message ( m = mbox <"meet me tomorrow morning">).

## Substitution Cipher

This problem offers a statistical activity that has immediate practical application. We have offered a spreadsheet toolkit so that students can concentrate on the analysis of the data without needing to waste time on computation.

### Possible approach

"Which letters do you think appear most often in the English language?"
"How could you find out?"

Allow some time for students to think about and share their answers. If they have books with them, perhaps suggest that they take a look to see which letters seem most common at first glance.

If a computer room is available, introduce students to the toolkit and give them time to perform a frequency analysis on some English text (Wikipedia articles are a great source for this). Share results from the frequency analysis. Does everybody find the same letters come out top, and bottom? There is opportunity here for some discussion about the benefits of using longer sample texts.

Then present students with the ciphertext in the problem (available as a text file here).

If a computer room is not available, the ciphertext is available as a worksheet here. Here is a second version of the worksheet with the ciphertext faint so that students can write over it as they go deciphering the message.

### Key questions

Are there any short words? What might they be?

### Possible support

Students could be encouraged to work collaboratively on this problem. There are lots of suggestions to help them get started in the hint.

### Possible extension

Students could investigate the frequency of digraphs (pairs of letters such as th or sh) in the English language and consider whether this speeds up the deciphering process.

The Secondary Cipher Challenge and Substitution Transposed offer challenging extensions for students who have worked on this problem and the problem Transposition Cipher.

## The Black Chamber

The monoalphabetic substitution cipher seemed uncrackable, because of the huge number of possible keys. There was, however, a shortcut that would undermine its security. This section tells the story of how this code breaking technique was invented, explains how it works and provides you with a tool that will help you to crack ciphers.

The cracking of the substitution cipher marks the birth of cryptanalysis (code breaking). This occurred during the golden age of the Islamic civilization, when many ancient foreign manuscripts were being brought to Baghdad to be added to the great Arab libraries. Some of these manuscripts were encrypted, which motivated the code breakers to crack the ciphers and reveal the secrets within. The picture shows the first page of al-Kindi's manuscript "On Deciphering Cryptographic Messages", containing the oldest known description of cryptanalysis by frequency analysis.

The letters "a" and "I" are the most common in Arabic. In English, E, then T, then A are the most common letters.

If a message is enciphered so that every letter is substituted for a different letter, then the new letter will take on all the attributes of the old letter, including how common it is.

So if the most common letter in an encoded English message is W, then W probably represents E. If there are lots of Gs, then G might represent T. And so on.

The letters "a" and "I" are the most common in Arabic. In English, E, then T, then A are the most common letters.

Although it is not known who first realized that the variation in the frequencies of letters could be exploited in order to break ciphers, the earliest known description of the technique is by the 9th century scientist Abu Yusuf Ya 'qub ibn Is-haq ibn as-Sabbah ibn 'omran ibn Ismail al-Kindi. Known as the philosopher of the Arabs', al-Kindi was the author of 290 books on medicine, astronomy, mathematics, linguistics and music, but his greatest treatise, which was only rediscovered in 1987 in the Sulaimaniyyah Ottoman Archive in Istanbul, is entitled "A Manuscript on Deciphering Cryptographic Messages."