Shift and Substitution

Alice: Okay, Hanne, let’s start our discussion of some cryptographic algorithms.

Hanne: Yippee!

Alice: To give you some appreciation of the evolution of cryptography, we’ll first discuss a few ancient cryptographic algorithms before progressing towards some more modern ones. Let’s begin with the “Caesar cipher”—one of the oldest and simplest ciphers. This cipher is called “Caesar” since it is believed to have been used by Julius Caesar, a Roman military and political leader who lived around 50 B.C. To encrypt a message using the Caesar cipher, we simply shift each letter of the plaintext three places to the right. That is, ‘a’ becomes ‘d’, ‘b’ becomes ‘e’, and so on. Letters at the end of the alphabet wrap around to the beginning, so ‘x’ becomes ‘a’, ‘y’ becomes ‘b’, and ‘z’ becomes ‘c’.

Hanne: Oh, okay. So to encrypt, it is a simple shift of three to the right, and to decrypt, it will be a simple shift of three to the left.

Alice: Exactly. And notice that I used the Caesar cipher to encrypt the message I sent to Bob earlier:

Plaintext:Hello, Bob. I like your blue robe. It looks super comfy.

Ciphertext:Khoor, Ere. L olnh brxu eoxh ureh. Lw orrnv vxshu frpib.

Hanne: Neat.

Bob: Now, the Caesar cipher belongs to the broader class of ciphers known as “shift ciphers”. And as the name suggests, these ciphers are constructed by shifting each letter a certain number of positions in the alphabet.

Hanne: I see. The Caesar cipher is a shift cipher with a shift value of 3, and there are 26 different shift ciphers since there are 26 letters in the English alphabet.

Bob: Well, technically, there are only 25 different shift ciphers, ranging from a shift of 1 to a shift of 25. A shift of 26 will give us back the original letter we started with.

Hanne: Oh, right.

Bob: In shift ciphers, the key is the shift value. However, as we just discovered, there are only 25 possible shift values—that is, 25 possible keys! This is nowhere close to the number of possible keys that a cryptosystem should have in order to achieve security. A computer can quickly try all 25 possible shift values and discover the key. This technique of trying all possibilities is known as a “brute-force attack”, and it is effective in cases where the keyspace is small.

Hanne: Wait, I don’t fully understand how we can figure out the key in a shift cipher using a brute-force attack.

Bob: So, given a ciphertext, we try shifting it by all the values from 1 to 25. Then, we pick the result that makes the most sense.

Hanne: But what if, after trying all the shift values from 1 to 25, we find that multiple results make sense?

Bob: So, this can only happen for very short messages—short meaning messages that are only a few letters long. For instance, take the ciphertext “zsllw”. With a shift of 7, it decrypts to “sleep”, and with a shift of 24, it decrypts to “bunny”. In a case like this, we’ll have to use contextual clues to figure out the correct plaintext.

Hanne: Oh.

Bob: However, in practice, we typically deal with much longer ciphertexts, and in these cases, only one shift will produce a meaningful result.

Hanne: Why is that?

Bob: It essentially boils down to the structure of our language—the longer the ciphertext is, the less likely that two or more different shifts will decrypt to something sensible. But this is something that will only become clear after some practice brute forcing shift ciphers.

Hanne: Fair enough.

(Hanne thinks.)

Hanne: So… you said that shift ciphers are not secure since computers can quickly brute force the possibilities and discover the key. However, given that there are only 25 possible keys, wouldn’t a human also be able to brute force them in a reasonable time?

Alice: That’s correct.

Hanne: Well, wouldn’t this mean that a shift cipher would have been insecure even in Julius Caesar’s time?

Alice: Oh, I see what you’re getting at. Using that logic, yes—shift ciphers would have been insecure even around 50 B.C. If an adversary knew that Caesar was using a shift cipher, they could have easily figured out that the shift value was 3 and would have been able to decrypt all his communications. However, that said, it’s worth noting that we do not know how effective the Caesar cipher was during its time. Perhaps it offered no security at all. Or maybe it did, and Julius Caesar relied on his adversaries not figuring out that he was using a shift cipher. The field of cryptography was far less developed back then than it is today, so he probably could have gotten away with this—but we can only speculate.

Hanne: Ah, I see.

Alice: Awesome. So that’s the gist of shift ciphers. To encrypt, shift each letter in the text by a fixed number of places to the right, and to decrypt, simply reverse the process by shifting each letter the same number of places to the left.

Hanne: Got it.

Alice, Bob, and Hanne entered a room adorned with marble sculptures of Julius Caesar and other Roman figures. Paintings of ancient Roman events lined the walls, and a large ceiling mosaic depicting two armies locked in a grand battle loomed above them. Various artefacts—like scrolls, coins, and daggers—were also scattered throughout the room, completing the setting’s historical immersion.

In the midst of it all, Hanne noticed three sets of ciphertext—one written across the walls, one on the ceiling, and one on the floor. Alice and Bob explained that the ciphertexts were encrypted with different shift ciphers and that she could try to decrypt them at her leisure. But for the time being, they would continue their discussion of cryptography and their exploration of the castle.

Hanne saw written on the walls:

Rdlpgsh sxt bpcn ixbth qtudgt iwtxg stpiwh; iwt kpaxpci ctktg iphit du stpiw qji dcrt.

On the ceiling:

L fdph, L vdz, L frqtxhuhg.

And on the floor:

Vlr qll, zefia?

She then exited the room and continued her adventure with Alice and Bob—but she was eager to return to decrypt the ciphertexts and unlock their secrets.

Alice: So, Hanne, now you know about the Caesar cipher as well as shift ciphers.

Hanne: Yes, but I am thinking about how we can improve upon this class of ciphers. In shift ciphers, we shift each letter by the same value. What if… we instead shift each letter by a different value? In this way, rather than the key being a single shift value, the key can be a table of letters and their corresponding shift values.

Alice: But there are 26 letters and only 25 different shift values.

Hanne: Well, one letter would have a shift of 0—that is, it wouldn’t change.

Alice: Interesting. So, the key will be a table of letters and their corresponding shift values, ranging from 0 to 25.

Hanne: Exactly. And there will be much more than 25 possibilities for the key since we will need to consider all the configurations of the table.

Alice: How many configurations of the table would there be?

Hanne: Hmm… I don’t know.

Alice: Well, it is important that we figure this out since we need to understand the size of our keyspace before we can consider using this cryptosystem in practice. The naïve way of finding the total number of table configurations would be to construct all possible tables and count how many we get. But this is a long and arduous process. We need a more efficient approach to figure out how many possible configurations there are.

Bob: Right. Usually, when we are faced with counting problems like these, it is best to start with smaller examples in the hope of discovering any patterns that can be extended to bigger instances of the problem. What is our problem? We have 26 letters and 26 different shift values—0 to 25. We want to figure out how many ways there are to construct a table where each letter has a different shift value. Tough stuff.

Hanne: Tough stuff indeed.

Bob: Let’s assume that there was only 1 letter—say ‘a’—and therefore, only 1 shift value—0. How many ways are there to construct a table where each letter has a different shift value?

Hanne: One way:

(The tables appeared before them.)

Letter	Shift Value
\[a\]	\[0\]

Bob: Lovely. What about in the case with 2 letters and in the case with 3 letters?

Hanne: There are two ways to construct the table in the case with 2 letters:

Letter	Shift Value
\[a\]	\[0\]
\[b\]	\[1\]

Letter	Shift Value
\[a\]	\[1\]
\[b\]	\[0\]

And six ways in the case with 3 letters:

Bob: Beautiful. So, with 1, 2, and 3 letters, we have 1, 2, and 6 configurations of the table, respectively. We would not ask you for any cases with more letters, but I can tell you that with 4, 5, and 6 letters, there will be 24, 120, and 720 configurations of the table, respectively.

Hanne: Wow.

Alice: Given this data, we can try to spot if there are any patterns emerging:

Number of letters	Number of configurations
\[1\]	\[1\]
\[2\]	\[2\]
\[3\]	\[6\]
\[4\]	\[24\]
\[5\]	\[120\]
\[6\]	\[720\]

After some analysis, you may notice that, except for the first term, each term is formed by multiplying the number of letters by the number of configurations of the previous term. For instance, the fourth term, 24, is found by multiplying 4 by 6; the fifth term, 120, is found by multiplying 5 by 24, and so on.

Hanne: Okay, interesting observation. But why does it happen, and how can we be certain that it will continue for larger values?

Alice: To understand why, let’s analyse the case with 3 letters a little more closely. Recall how the six tables for this case were presented to you—three rows of two tables. Observe the shift value for ‘a’ in each row.

(Hanne analyses the case with 3 letters.)

Hanne: In the first row of tables, ‘a’ is 0; in the second row, ‘a’ is 1; and in the third row, ‘a’ is 2.

Alice: Good. And think about why the shift value for ‘a’ is broken up like this—into three groups of two, as opposed to any other combination.

Hanne: Well, with three letters, there are three possible shift values for ‘a’—0, 1, or 2. That’s why it is broken up into three groups. The reason these three groups each have a size of two is because, after the shift value for ‘a’ is chosen, there are two ways to arrange the remaining shift values between ‘b’ and ‘c’.

Alice: Great. And the total number of configurations of the table in this case is:

\[3 \times 2 = 6\]

Bob: And observe that we can apply a similar logic to the case with 4 letters as well. There will be 4 groups since there are 4 different shift values—0 to 3—and, in each group, after a shift value for ‘a’ is chosen, we need to find the number of ways to arrange the remaining three shift values. But we know this information from the previous case—there are six ways! Thus, we will end up with four groups of six, and the total number of configurations in this case is:

\[4 \times 6 = 24\]

Hanne: Oh, okay. And I see how this logic can be extended to cases with more letters.

Alice: Lovely. This is why the pattern that each term is formed by multiplying the number of letters by the number of configurations of the previous term works:

Number of letters	Number of configurations
\[1\]	\(1\)
\[2\]	\(2 = 2 \times 1\)
\[3\]	\(6 = 3 \times 2\)
\[4\]	\(24 = 4 \times 6\)
\[5\]	\(120 = 5 \times 24\)
\[6\]	\(720 = 6 \times 120\)

Hanne: Okay, so to find the number of configurations for 26 letters, we basically build up this table until we get to 26.

Alice: We could do that. However, notice that because every term, except for the first, is related to the previous term, the multiplicative expressions can be broken down into a descending sequence. That is, we can substitute “2 = 2 × 1” into “6 = 3 × 2” to get:

\[6 = 3 \times 2 \times 1\]

Similarly, we can substitute “6 = 3 × 2 × 1” into “24 = 4 × 6” to get:

\[24 = 4 \times 3 \times 2 \times 1\]

Continuing along these lines, we will get:

Number of letters	Number of configurations
\[1\]	\(1\)
\[2\]	\(2 = 2 \times 1\)
\[3\]	\(6 = 3 \times 2 \times 1\)
\[4\]	\(24 = 4 \times 3 \times 2 \times 1\)
\[5\]	\(120 = 5 \times 4 \times 3 \times 2 \times 1\)
\[6\]	\(720 = 6 \times 5 \times 4 \times 3 \times 2 \times 1\)

Thus, with 26 letters, there will be:

\[26 \times 25 \times 24 \times \ \ldots\ \times 3 \times 2 \times 1 = \ 403,291,461,126,605,635,584,000,000\]

total configurations of the table.

Hanne: Wow! That’s a large keyspace.

Alice: Indeed.

Bob: And when dealing with large numbers, we often use something called “scientific notation” to represent them. The concept of scientific notation dates back to the ancient mathematician and inventor Archimedes, who lived around 250 B.C., but it has evolved over time through contributions from various individuals. Scientific notation uses a shorter number, multiplied by a power of 10, to represent very large or very small numbers. So, instead of saying:

\[403,291,461,126,605,635,584,000,000\]

every time, we could instead say:

\[4.03 \times 10^{26}\]

This notation means that we move the decimal point in 4.03 twenty-six places to the right and fill in zeros for the missing numbers. That is:

\[403,000,000,000,000,000,000,000,000\]

While it is not the same number, it is a reasonably close approximation. We use the squiggly symbol, “≈”, to indicate that something is an approximation. So, we can say that for 26 letters there will be:

\[26 \times 25 \times 24 \times \ \ldots\ \times 3 \times 2 \times 1 \approx 4.03 \times 10^{26}\]

total configurations of the table.

Hanne: Got it.

Bob: Great.

Alice: So, before we analyse this cryptosystem further, let’s briefly comment on these descending products that we found. In mathematics, this kind of expression is called a “factorial”. To understand its definition, we must first be familiar with the set of integers. The set of integers refers to the positive whole numbers, their negative counterparts, and the number zero. We use the symbol “\(\mathbb{Z}\)” to refer to the set of integers. So,

\[\mathbb{Z =}\left\{ \ldots - 3,\ - 2,\ - 1,\ 0,\ 1,\ 2,\ 3,\ \ldots \right\}\]

Hanne: I see.

Alice: Now, the factorial of a positive integer, \(n\), is defined as the product of all positive integers up to and including \(n\). It is denoted by an exclamation mark after the integer \(n\)—that is, \(n!\)—and it is referred to as “\(n\) factorial”. So:

\[n! = n \times (n - 1) \times (n - 2) \times \ldots \times 3 \times 2 \times 1\]

And it follows that:

\[n! = n \times (n - 1)!\]

This expression describes the property that we found in the table configurations, where each term was formed by multiplying the number of letters by the number of configurations of the previous term.

Bob: And another way to think of the factorial is as the number of permutations—or arrangements—of \(n\) objects. That is, there are \(n!\) ways to arrange \(n\) objects. For instance, if you have 3 objects and 3 slots to place these objects in, then for the first slot, you can put any of the 3 objects in; for the second slot, you can put any of the 2 remaining objects in; and for the last slot, you put the 1 remaining object in. Multiplying the three numbers in this sequence gives:

\[3 \times 2 \times 1 = 6\]

This is the total number of ways to arrange 3 objects.

Alice: Right. So, when we were analysing the number of configurations of the table for the different numbers of letters, this was equivalent to finding the number of ways to order those letters.

Hanne: I see. And there are \(3!\) ways to arrange 3 letters and \(26!\) ways to arrange 26 letters.

Bob: Exactly.

(Hanne reflects on the definition of a factorial: The factorial of a positive integer, \(n\), is defined as the product of all positive integers up to and including \(n\).)

Hanne: I notice that factorials are only defined for positive integers. What is the factorial of a negative integer?

Bob: The concept of a negative factorial is not defined in standard mathematics.

Hanne: Why not?

Bob: The factorial is based on the notion of counting or arranging objects. Extending the factorial function to negative integers does not have a meaningful interpretation.

Hanne: I see. What about \(0!\)?

Bob: For the special case of 0, we define \(0!\) to be equal to 1.

Hanne: Why?

Bob: There are several reasons why this convention was adopted. Some reasons, such as for mathematical convenience or for allowing complex formulae to be presented in a simpler form, may not be immediately clear to you now. However, one explanation that you might grasp is the combinatorial interpretation: there is one permutation of zero objects, one way to arrange zero objects—do nothing. This is consistent with other areas of mathematics. For example, when determining the number of ways to choose items from a set, choosing zero items is considered one way, and it is called the “empty set”.

Hanne: Okay. One way to arrange zero objects—do nothing—I can work with that. Who created the factorial?

Bob: Factorials were independently discovered and used by different ancient cultures. The way that we define and use them today has been shaped by the contributions of numerous mathematicians throughout history.

Hanne: Fair enough. … But getting back to my proposed cryptosystem, we found that there were \(26! \approx 4.03 \times 10^{26}\) different possible configurations of the table. I assume that an adversary wouldn’t be able to brute force all these possibilities within a reasonable time—even with the help of a computer.

Alice: That’s right. With current computational capabilities, it is infeasible to try all these possibilities within a reasonable time.

Hanne: Yay! So, is this cryptosystem used in practice?

Alice: Nope.

Hanne: Aww. Why not?

Alice: Well, there is an issue with it. For instance, observe that in the case with two letters:

Letter	Shift Value
\[a\]	\[0\]
\[b\]	\[1\]

Letter	Shift Value
\[a\]	\[1\]
\[b\]	\[0\]

neither scenario is practical. In the first table, if we shift ‘a’ by 0 and ‘b’ by 1, then both ‘a’ and ‘b’ get encrypted to ‘a’. This is a problem. When we see an ‘a’ in the ciphertext, we would not know whether to decrypt it to ‘a’ or to ‘b’—even if we have the key!

Hanne: Ohhh. And a similar argument can be made for the second table, where we shift ‘a’ by 1 and ‘b’ by 0.

Bob: That’s right. In the case with two letters, all possible configurations of the table are not practical. However, in the case with three letters, some configurations may be valid. For example, in:

Letter	Shift Value
\[a\]	\[0\]
\[b\]	\[1\]
\[c\]	\[2\]

‘a’ is encrypted to ‘a’, ‘b’ is encrypted to ‘c’, and ‘c’ is encrypted to ‘b’. Every letter in the plaintext is encrypted to a unique letter in the ciphertext. This configuration is good. However, other configurations may not work:

Letter	Shift Value
\[a\]	\[0\]
\[b\]	\[2\]
\[c\]	\[1\]

Here, ‘a’, ‘b’, and ‘c’ are all encrypted to ‘a’. When we see an ‘a’ in the ciphertext, we would not know what to decrypt it to.

Hanne: I see.

Alice: And notice that we did not need to worry about valid configurations when we were exploring shift ciphers. This is because, in shift ciphers, each letter is shifted by the same amount, so we naturally achieve a unique mapping between the plaintext and ciphertext. However, now that we are assigning a different shift value to each letter, we introduce the possibility of two or more plaintext letters mapping to the same ciphertext letter.

Hanne: Ah… right. So, we have some more analysis to do. We need to figure out how many valid configurations exist for the case with 26 letters.

Alice: Yes. And again, we start with smaller instances of the problem. Some rough calculations give:

Number of letters	Number of configurations	Number of valid configurations
\[1\]	\[1\]	\[1\]
\[2\]	\[2\]	\[0\]
\[3\]	\[6\]	\[3\]
\[4\]	\[24\]	\[0\]
\[5\]	\[120\]	\[15\]
\[6\]	\[720\]	\[0\]
\[7\]	\[5,040\]	\[133\]
\[8\]	\[40,320\]	\[0\]
\[9\]	\[362,880\]	\[2,025\]
\[10\]	\[3,628,800\]	\[0\]
\[11\]	\[39,916,800\]	\[37,851\]
\[12\]	\[479,001,600\]	\[0\]
\[13\]	\[6,227,020,800\]	\[1,030,367\]

Bob: The emerging pattern suggests that if the number of letters is odd—odd meaning that the number is not divisible by 2—then there will exist at least one valid configuration. However, if the number of letters is even—even meaning that the number is divisible by 2—then there will be no valid configurations. And since 26 is an even number, it seems to be the case that there will be no valid table configurations out of the \(26!\) total possible configurations.

Hanne: Oof.

Alice: However, we should mention that it is in situations like these where mathematical proofs are extremely helpful. While we gave you the results up to the case with 13 letters, there is no guarantee that the observed pattern will continue through to the case with 26 letters. One option would be to continue the calculations until we reach the case with 26 letters. But as you can see, the number of table configurations increases very quickly, and testing each configuration to determine whether it is valid would take a long time—a very long time. Instead, what we would like to do is show how the property of evenness results in there being no valid configurations. If we can do this, it would imply that there will be no valid configurations for the case with 26 letters. We would not need to hope that the pattern continues for larger numbers; we would have proven it!

Bob: Right. We won’t delve into the proof in this case, but it is an area that you can revisit after gaining some experience with mathematical proofs. For the time being, we will assume that the pattern continues for larger numbers, implying that there will be no valid configurations for the case with 26 letters.

Hanne: Okay. So, in the end, I guess my cryptosystem was not that great after all.

Bob: So it seems. But it can be easily fixed. Plus, the thinking that got us to this point was incredibly valuable. It would have been a shame to miss out on this exploration.

Hanne: Oh! What’s the fix?

Bob: Rather than have a table where each letter is shifted by a different value, construct the table where each letter is mapped to a different letter. With this construction, some letters may be shifted by the same value, but that’s okay. At least we will have valid table configurations to work with.

Hanne: Okay. So something like:

Plaintext	Ciphertext
\[a\]	\[f\]
\[b\]	\[u\]
\[c\]	\[n\]
…	…

Bob: Exactly.

Hanne: And we have 26 slots for the ciphertext and 26 letters to use. For the first slot, we can use any of the 26 letters; for the second slot, any of the remaining 25; and so on. This is 26 factorial! So there are \(26! \approx 4.03 \times 10^{26}\) table configurations—only this time each configuration is valid!

Bob: Yay! It makes sense that we will also get \(26!\) possible configurations, since the first time around we were considering 26 shift values—0 to 25—and this time, we are considering 26 letters—‘a’ to ‘z’.

Hanne: Indeed. So, we found a working cryptosystem.

Bob: Correct. This cryptosystem is called a “simple substitution cipher”, since each letter is being substituted for another. In fact, if you think about it, shift ciphers are a type of simple substitution cipher, with the additional property that each letter is shifted by a fixed number.

Hanne: Right.

(Hanne thinks.)

Hanne: Also, I just realised that for a simple substitution cipher, there are technically \(26! - 1\ \)possible configurations since we should exclude the case where each letter gets mapped to itself.

Bob: Ha! The ciphertext is the plaintext—misdirection.

Alice: That’s right, Hanne. We don’t want the possibility of the ciphertext being identical to the plaintext. And continuing along this line of thinking, you’ll notice that there are other special cases that we’d like to avoid. For instance, consider the case where ‘a’ is encrypted to ‘b’, ‘b’ is encrypted to ‘a’, and all other letters are encrypted to themselves. Here, the ciphertext would closely resemble the plaintext, and decryption would be easy for an adversary.

Hanne: Right. We’ll need to do some further analysis to determine which table configurations to exclude.

Alice: Correct. However, even if we were to assume that all \(26!\) possibilities are valid, a simple substitution cipher would still not be secure enough.

Hanne: What! But the keyspace is so large—\(4.03 \times 10^{26}\) possibilities.

Alice: Yes. But the size of the keyspace is just one factor to consider. We also need to ensure that our cryptosystem does not leak any information; only then would the size of the keyspace come into play. However, if our cryptosystem leaks information, it can give an adversary insights into what our key might be. They will be able to narrow down the possibilities for the key and have a better chance of discovering it compared to a brute-force attack.

Bob: This process of analysing a cryptosystem to find weaknesses in it is known as “cryptanalysis”, and it is a major part of cryptography. It turns out that simple substitution ciphers leak information, and this greatly compromises their security.

Hanne: How do simple substitution ciphers leak information?

Bob: Repeated letters in the ciphertext correspond to repeated letters in the plaintext. Think about it. Regardless of how “cool secret” is encrypted, the two ‘o’s in “cool” and the two ‘e’s in “secret” will always get mapped to the same letter. For example, it may be encrypted to “kggn oikdim”. An adversary would notice the two ‘g’s and the two ‘i’s in the ciphertext. This gives information away that can help narrow down the possible keys.

Alice: In addition to repeated letters, there is also the issue of repeated words. Common words like “the” and “and” are likely to be repeated in the plaintext and would therefore show up as repeated groupings in the ciphertext. An adversary can analyse these repetitions and make educated guesses about the corresponding letters in the plaintext.

Hanne: Ohhh… I see.

Bob: And the more general attack that simple substitution ciphers are susceptible to is known as “frequency analysis”. In this attack, a cryptanalyst analyses the frequency of letters in the ciphertext and matches them to the frequency of letters in the English language. For example, in English plaintext, the letters ‘z’, ‘q’, and ‘j’ are rarely used, while the letters ‘e’, ‘t’, and ‘a’ are used quite often. To exploit this variability in letter frequency, an adversary can start by mapping the most frequent letters in the ciphertext to the most frequent letters in English text. Although they may not get the correct mapping from plaintext to ciphertext for all letters, they are likely to identify a few correctly. From there, they can refine their guesses based on the context and additional patterns that they observe.

Hanne: Okay. So, because simple substitution ciphers do not hide letter frequency, it allows adversaries to make educated guesses, making it easier for them to decrypt the ciphertext.

Bob: Precisely. We say that attacking simple substitution ciphers using frequency analysis relies heavily on “heuristics”. A heuristic is a problem-solving approach that is governed by loosely defined rules, often involving trial and error and making educated guesses. And while this may sound time-consuming, heuristics are significantly faster than brute-force attacks—and become even more effective with access to larger amounts of ciphertext.

Hanne: I see.

Alice: So, that was a brief introduction to a few cryptographic algorithms. To recap, we covered the Caesar cipher, shift ciphers, and simple substitution ciphers, and we also learnt about heuristics and how frequency analysis can be used to break simple substitution ciphers.

Hanne: Fascinating stuff!

Alice, Bob, and Hanne entered a room with a boxing ring at its centre. They climbed into the ring, and Hanne noticed moving illustrations across the floor. The illustrations were constantly changing and depicted people engaged in various activities—painting, sculpting, writing, and athletic events.

After a while, the illustrations faded and made way for something new. The floor of the ring was now covered with a sprawling ciphertext:

Ky kr hby ywe ickyki owb ibphyr; hby ywe nsh owb abkhyr bpy wbo ywe rycbhd nsh rypnmuer, bc owece ywe lbec bv leelr ibpul wste lbhe ywen meyyec. Ywe icelky meubhdr yb ywe nsh owb kr siypsuug kh ywe scehs, owbre vsie kr nsccel mg lpry shl roesy shl mubbl; owb ryckter tsukshyug; owb eccr, owb ibner rwbcy sdskh shl sdskh, meispre ywece kr hb evvbcy okywbpy eccbc shl rwbcyibnkhd; mpy owb lber siypsuug ryckte yb lb ywe leelr; owb fhbor ywe dcesy ehywprksrnr, ywe dcesy letbykbhr; owb raehlr wknreuv kh s obcywg ispre; owb sy ywe mery fhbor kh ywe ehl ywe yckpnaw bv wkdw siwketenehy, shl owb sy ywe obcry, kv we vskur, sy uesry vskur owkue lsckhd dcesyug, rb ywsy wkr ausie rwsuu hetec me okyw ywbre ibul shl yknkl rbpur owb hekywec fhbo tkiybcg hbc levesy.

Alice and Bob explained that the ciphertext was encrypted using a simple substitution and quickly reiterated the approach a cryptanalyst would use to break it. They said the cryptanalyst would first find the frequency of all the letters in the ciphertext and rank them from most frequent to least frequent. They would then compare this distribution to the frequency of letters in standard English text—which can be found in letter frequency tables online—and use this mapping as the first guess for the substitution table. They are likely to get a few letter mappings correct, and from there they would use contextual clues to figure out the rest—specifically, they will focus heavily on all the two-letter and three-letter groupings in the ciphertext, since there are only so many two-letter and three-letter words in English.

Hanne was also given a hint that the letter ‘e’ was encrypted to itself. She quickly scanned the ciphertext and saw many three-letter groupings ending with ‘e’ and felt she had a good idea of what those groupings might decrypt to.

Alice and Bob again told Hanne that they were going to continue their exploration of the castle, but she could return to decrypt the ciphertext at her leisure. The three then exited the room and continued their cryptographic adventure.