Alberti & Vigenère

Bob: Alrighty, Hanne. We learnt about shift ciphers and simple substitution ciphers, but shift ciphers have a very small keyspace, and simple substitution ciphers are susceptible to frequency analysis. Our hunt for a secure cryptosystem continues.

Hanne: Indeed. It seems that we are back to square one.

Bob: Ooooh… interesting phrase—“back to square one”. Yes and no.

(Bob thinks.)

Bob: To get a bit philosophical, our situation is similar to one that many who endeavour to achieve something worthwhile will inevitably encounter—failure. It is often said that failure is a great teacher, moving us one step closer to success. However, failure and learning from failure are two different processes, akin to having a book and reading it. One may fail but not learn anything if they do not analyse their failure and extract the lessons from it. As such, it is important to remember that learning from failure is not an automatic process; it requires thoughtful analysis and reflection to truly reap its benefits.

Hanne: I see.

Bob: So, as it relates to our hunt for a secure cryptosystem, in one sense, yes, we are back to square one—we haven't had any success yet. However, in another sense, we're not all the way back to the beginning; we have failed attempts that we can analyse and extract wisdom from. In this manner, we can gain a much stronger understanding of the task at hand compared to when we had first begun.

Hanne: Right.

Bob: So, let's do it! Let's analyse our failures! What makes simple substitution ciphers susceptible to frequency analysis?

(Hanne thinks.)

Hanne: It is the property that repeated letters and repeated groups of letters in the plaintext correspond to repeated letters and repeated groups of letters in the ciphertext.

Bob: Good. And this happens because there is a one-to-one mapping between letters in the plaintext and letters in the ciphertext. So, if “who” shows up 10 times in the plaintext, there will be a corresponding three-letter grouping that shows up 10 times in the ciphertext. This gives information away. But let's think—can we avoid this? Can we design a cryptosystem that does not have this weakness? A cryptosystem where “who” shows up 10 times in the plaintext, but there is no guarantee that a corresponding three-letter grouping will show up 10 times in the ciphertext?

Hanne: Hmm. But this would mean that “who” gets encrypted to different ciphertexts each time—or at least sometimes.

Bob: That's right. This is where the notion of “monoalphabetic” and “polyalphabetic” substitution ciphers comes into play. Monoalphabetic substitution ciphers, often referred to as “simple substitution ciphers”, use a single substitution alphabet, while polyalphabetic substitution ciphers, commonly shortened to “polyalphabetic ciphers”, make use of multiple substitution alphabets.

Hanne: A substitution alphabet?

Bob: Yes. A substitution alphabet is a rearrangement of the standard alphabet that defines how to substitute letters in a message. For instance, it could be a table showing how the letters of the plaintext map to the letters of the ciphertext.

Hanne: Oh, like the table of plaintext mapping to ciphertext that we talked about earlier!

Bob: Exactly. Simple substitution ciphers stick to one substitution alphabet for the entire message, while polyalphabetic ciphers switch between different alphabets every so often.

Hanne: I see. So because polyalphabetic ciphers constantly change the substitution alphabet, this means that “who” can show up 10 times in the plaintext, but there is no guarantee that a corresponding three-letter grouping will show up 10 times in the ciphertext.

Bob: Exactly. Polyalphabetic ciphers hide the plaintext letter frequencies, making them far more resistant to frequency analysis!

Hanne: Sweet!

(Hanne thinks.)

Hanne: Okay, but how exactly do polyalphabetic ciphers work? Like… how is the substitution alphabet constantly changed in a way that allows both the sender and receiver to know how and when to change it, while at the same time keeping this information hidden from an adversary?

Bob: Excellent question, Hanne! Unfortunately, we won't be able to give you a straightforward answer, since polyalphabetic ciphers come in many forms—each with its own method for securely changing the substitution alphabet. However, we can walk you through a couple of examples to give you a sense of how they can be designed.

Hanne: Sounds good.

Bob: We'll start with the first known polyalphabetic cipher—the “Alberti cipher”—and then discuss one of the more famous ones—the “Vigenère cipher”.

Alice: The Alberti cipher was developed in the 1400s by Leon Battista Alberti, and it used a cipher disk, known as the “Alberti cipher disk”, to obtain its substitution alphabet:

The cipher disk consisted of two concentric disks—an inner disk and an outer disk—each containing a set of characters. The mapping between the characters on the disks formed the substitution alphabet, and the inner disk could rotate to change the mapping. For this reason, the inner disk was called the “movable disk”, and the outer disk, the “stationary disk”. But we'll continue to use the terms “inner disk” and “outer disk” in our discussion.

Hanne: Okay.

Alice: Typically, the outer disk—with uppercase letters—was used to represent the plaintext, and the inner disk—with lowercase letters—the ciphertext. So, with the current disk configuration, the plaintext “ABC” would be encrypted to “gkl”.

Hanne: Right.

Alice: And it's also worth noting that each disk contains 24 characters. The inner disk has 23 letters and the '&' symbol—omitting the three letters 'j', 'u', and 'w'—while the outer disk has 20 letters and 4 numbers, omitting the six letters 'H', 'J', 'K', 'U', 'W', and 'Y'.

Hanne: Interesting. Why were these letters omitted?

Alice: It likely came down to a combination of historical, linguistic, and design factors. In the 1400s, when the Alberti cipher was invented, the Latin alphabet was widely used. This alphabet was almost identical to the modern English alphabet but had 23 letters, omitting 'J', 'U', and 'W'. That's why these letters were excluded from both disks.

Hanne: I see.

Alice: And as for the three additional letters omitted on the outer disk—'H', 'K', and 'Y'—we're not entirely sure why they were excluded. It's possible that Alberti anticipated that these letters would be less common in the texts his cipher would be used to encrypt, since they were also among the least used letters in Latin. Additionally, there seemed to be a desire to include numbers on the outer disk, which meant that some letters had to be sacrificed.

Hanne: Fair enough.

Bob: And just to mention, if one wanted to use this cipher disk with the modern English alphabet, they'd need to come up with a way to represent the six missing letters on the outer disk. One possible approach could be to use nearby letters and repeat them as a stand-in for the missing letters—though contextual clues would also need to be used. For example, the sender and receiver might agree on these substitutions for the missing letters:

Thus, any word in the plaintext containing one of these missing letters would need to be rewritten based on these substitutions. For instance, if the plaintext contained the word “THE”, the sender would first rewrite it as “TGGE” before encrypting it. Then, upon decrypting the ciphertext and uncovering “TGGE”, the receiver would need to recognise that “GG” represents 'H' and make the appropriate substitution.

Hanne: Right.

Bob: Of course, this isn't ideal, and it would've been better if the Alberti cipher disk included all 26 letters. But this is just to show how the cipher disk could be adapted for use with the modern English alphabet. For its time, though, it worked well with the Latin alphabet.

Hanne: Got it.

Bob: Splendid.

Alice: Now, let's talk about how the sender and receiver securely changed the substitution alphabet in the Alberti cipher. Several techniques were used, but we'll only discuss one of them. In this method, the sender and receiver would first agree on a character from the inner disk—essentially their secret key—and then use uppercase letters in the ciphertext to communicate how and when to rotate the inner disk. For instance, let's say that they chose 'k' for their secret key. The ciphertext would then look something like this:

Bittp rhhihhmCn gnvx&rm qx qrrn yAs&bbxkhvvi

The uppercase 'B' would tell the receiver to rotate the inner disk so that 'k' in the inner disk lines up with 'B' in the outer disk. The receiver would then start decrypting. When they encounter the next uppercase letter in the ciphertext—'C' in this case—they would rotate the inner disk again, this time lining up 'k' with 'C' before continuing to decrypt. And so on, until the entire ciphertext is decrypted.

Hanne: I see. So the key is a character in the inner disk, and the uppercase letters communicate which letter in the outer disk to line up the key with.

Alice: Precisely.

Hanne: Hmm… but hold on. Since the key is a character in the inner disk, this means there are only 24 possibilities for the key! An adversary could easily brute force this, and it shouldn't be too difficult for them to figure out the purpose of the uppercase letters in the ciphertext. They'd be able to easily decrypt any ciphertext produced by the Alberti cipher.

Alice: Good observation, Hanne. In the Alberti cipher, there are only 24 possible values for the key, and it's reasonable to assume that an adversary could figure out the purpose of the uppercase letters in the ciphertext. In fact, recall that we should assume the adversary knows the purpose of the uppercase letters in the ciphertext, as this is in line with Kerckhoffs' principle and Shannon's maxim—assume that the adversary knows everything about the system except the key.

Hanne: Right. So, in this light, although the Alberti cipher was the first polyalphabetic cipher, it wasn't very secure; its keyspace was too small.

Alice: Well, while that is true, it's worth noting that the security of the Alberti cipher could be improved—and indeed, was improved—over time. To enhance its security, one had to make the technique for switching the substitution alphabet more complex. For instance, instead of using uppercase letters to directly indicate how to rotate the inner disk, each uppercase letter could map to a different letter, indirectly signalling how to align the disks. In other words, the uppercase letters in the ciphertext would no longer be taken at face value but would instead map to another letter that the sender and receiver would have agreed on beforehand.

Bob: For example, again assuming that the secret key is 'k', an uppercase 'A' in the ciphertext wouldn't simply mean to line up 'k' with 'A'. Instead, the sender and receiver might have agreed beforehand that 'A' maps to 'S'. So, an uppercase 'A' in the ciphertext would mean to line up 'k' with 'S'.

Hanne: Oh.

Alice: Plus, we could take it a step further and make the mapping dynamic. That is, the first time an uppercase 'A' appears in the ciphertext, it might map to one value. The second time, it might map to another value, and so on for each subsequent appearance in the ciphertext.

Hanne: I see. And we do this for every uppercase letter.

Alice: That's right.

Hanne: Hmm… but it seems like a lot for the sender and receiver to remember.

Alice: Well, the sender and receiver wouldn't need to remember all the mappings. Instead, they would each have a secret codebook containing the necessary information.

Hanne: A codebook?

Alice: Yes. In cryptography, a codebook is a collection of some additional secret information that can be used to further secure a cryptosystem. It's not technically the key, but it functions as an extension of the key since it also needs to be kept secret. And just like the key, the codebook should be periodically updated to maintain security.

Hanne: Oh… okay. So, with the use of a codebook, the security of the Alberti cipher can be improved.

Alice: That's right. … So, to quickly recap: In the Alberti cipher, the key is a character in the inner disk, we insert uppercase letters in the ciphertext to indicate how and when to rotate the inner disk, and we use a codebook to enhance security. And while there are other techniques for changing the substitution alphabet in the Alberti cipher, they all essentially follow the same pattern: Start with some secret value, insert information into the ciphertext to indicate how and when to rotate the inner disk, and use a codebook to enhance security.

Hanne: Got it.

Alice: Finally, as a high-level overview, when it comes to breaking the Alberti cipher, it requires a combination of brute-force attacks, figuring out how the substitution alphabet is being changed—if not already known—and attempting to reconstruct the secret codebook based on information gained from breaking bits of the ciphertext from the brute-force attacks. … That's all we'll say about that. While for its time, the Alberti cipher was reasonably secure, with advancements in cryptanalysis, it wouldn't be suitable as a modern cryptosystem. Still, it was worth mentioning since it was the first known polyalphabetic cipher, and it gave us an example of how a cipher could be designed to allow both the sender and receiver to know how and when to change the substitution alphabet.

Hanne: Right.

Bob: Now, let's move on to one of the most popular polyalphabetic ciphers—the Vigenère cipher. The Vigenère cipher was developed about 100 years after the Alberti cipher, and it is much simpler to use. It does not require the sender and receiver to have a physical cipher disk, nor does it need a codebook to enhance its security. The Vigenère cipher simply uses a keyword or key phrase and repeats it to match the length of the plaintext. So continuing from our earlier example, if the plaintext is:

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

And the keyword is “alice”. Then, we repeat “alice” until it matches the length of the plaintext:

alice, ali. C eali ceal icea lice. Al iceal iceal iceal.

In the key, 'a' corresponds to a shift of 0, 'b' to a shift of 1, and so on, up to 'z', which corresponds to a shift of 25. So we line up the letters in the plaintext with the letters of the key, and we encrypt to get the ciphertext:

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

Key:alice, ali. c eali ceal icea lice. al iceal iceal iceal.

Ciphertext:Hptns, Bzj. K pivm asuc jnye cwdi. Ie tqskd awtec kqqfj.

That is, 'H' in the plaintext, shifted by 'a' in the key, gives 'H' in the ciphertext—since 'a' corresponds to a shift of 0. Likewise, 'e' in the plaintext, shifted by 'l' in the key, gives 'p' in the ciphertext—since 'l' corresponds to a shift of 11. And so on.

Hanne: Cool. And to decrypt, it would just be the reverse of this process—shifting to the left as opposed to the right.

Bob: Correct. And let's see how this ciphertext from the Vigenère cipher compares with that of the Caesar cipher:

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

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

Vigenère:Hptns, Bzj. K pivm asuc jnye cwdi. Ie tqskd awtec kqqfj.

Notice how the double 'l' in “Hello” shows up as a repeated grouping in the Caesar cipher but not in the Vigenère cipher. The same goes for the double 'o' in “looks”.

Hanne: Right. The Vigenère cipher hides repeated letters from the plaintext.

Bob: Exactly. And although there aren't any in this example, the Vigenère cipher would also hide repeated words from the plaintext.

Hanne: Right.

Bob: So, that's the essence of the Vigenère cipher. However, there are two additional points worth highlighting. Firstly, on the surface, it might not seem like a polyalphabetic cipher, since it isn't obvious that its substitution alphabet is being changed. In the Alberti cipher, this was straightforward: rotating the cipher disk changed the substitution alphabet. But how is this done in the Vigenère cipher?

Hanne: Hmm… yeah? How is the substitution alphabet changed in the Vigenère cipher?

Bob: Well, it essentially comes down to how the letters of the key align with the letters of the plaintext. The changing letters of the key effectively change the substitution alphabet. For example, consider again the “ll” in “Hello”. In the ciphertext, it became “tn”. Realise what this means: 'l' was first mapped to 't', and then, when it appeared again, it was mapped to 'n'. The mapping was changed! Thus, in the Vigenère cipher, the substitution alphabet changes with every character because of the changing letters of the key.

Hanne: Ohhh… got it.

Bob: Awesome. The second point to note has to do with something called the “tabula recta”. The tabula recta is a 26 × 26 square table of alphabets that provides us with a visual representation of the notion that 'a' corresponds to a shift of 0, 'b' to a shift of 1, and so on. Here's how it looks:

You can explore it more on your own if you want, but we'll quickly explain how it can be used for encryption and decryption with the Vigenère cipher. Recall our earlier example:

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

Key:alice, ali. c eali ceal icea lice. al iceal iceal iceal.

Ciphertext:Hptns, Bzj. K pivm asuc jnye cwdi. Ie tqskd awtec kqqfj.

During encryption, we'll have a letter from the plaintext and its corresponding letter from the key. Let's say the plaintext letter is 'I' and the key letter is 'C'. To find the corresponding letter in the ciphertext, we simply go to column 'I' and row 'C'.

Hanne: That gives 'K'.

Bob: Exactly. This is what we expect. 'C' corresponds to a shift of 2, and shifting 'I' to the right by 2 gives 'K'.

Hanne: Right.

Bob: Now, for decryption, we'll have a letter from the ciphertext and its corresponding letter from the key. Let's say the ciphertext letter is 'P' and the key letter is 'E'. To find the corresponding letter in the plaintext, we go to row 'E' and look for the column that has 'P'.

Hanne: Column 'L'.

Bob: Correct. This is also what we expect. 'E' corresponds to a shift of 4, and shifting 'P' to the left by 4 gives 'L'.

Hanne: I see.

Bob: So, that's the tabula recta. While it's not strictly necessary when using the Vigenère cipher, it's a handy tool that can be used to speed up encryption and decryption as opposed to calculating each shift manually.

Hanne: Understood.

Bob: Wonderful.

Alice: Now, let's analyse the size of the keyspace in the Vigenère cipher. In the Vigenère cipher, the key is a word or phrase. We will assume that the key cannot be of length 1, since this is equivalent to a shift cipher—all the letters in the plaintext would be shifted by the same amount. We will also assume that the key cannot be of length 2—mostly as a judgement call, as 2 seems too short to offer any meaningful security. Thus, we will consider 3 to be the minimum length for the key. So, Hanne, how many possible keys are there of length 3 in the Vigenère cipher?

Hanne: Well, I assume that letters cannot be repeated, since this may weaken the cipher. Under this assumption, we have 26 possibilities for the first letter, 25 for the second, and 24 for the third. So,

\[26 \times 25 \times 24 = 15{,}600\]

possible keys of length 3 in the Vigenère cipher.

Alice: Splendid! However, these are just the possible keys of length 3. The key could also be of length 4, or of length 5, and so on, until we use up all the letters.

Hanne: Right. To find the total number of keys in the Vigenère cipher, we'll need to sum the number of possible keys for each key length.

Alice: Exactly. This will result in an expression that looks like:

\[(26 \times 25 \times 24) + (26 \times 25 \times 24 \times 23) + \ldots + (26 \times 25 \times \ldots \times 1)\]

Hanne: Right.

Alice: And although it may not be immediately clear to you, if you were to spend some time analysing this expression, you might notice that we can simplify it as:

\[\frac{26!}{23!} + \frac{26!}{22!} + \ldots + \frac{26!}{0!}\]

Or, equivalently, as:

\[\frac{26!}{(26-3)!} + \frac{26!}{(26-4)!} + \ldots + \frac{26!}{(26-26)!}\]

In essence, we find the sum of this term for all the key lengths:

\[\frac{26!}{(26 - \text{key length})!}\ \ \ \ \ ,\ \text{where}\ 3 \leq \text{key length} \leq 26\]

And to express this more elegantly, we can use something called “summation notation”, which was introduced by the Swiss mathematician Leonhard Euler in 1755. With summation notation, the expression becomes:

\[\sum_{k=3}^{k=26}\frac{26!}{(26-k)!}\]

Hanne: Cool.

Alice: And we get:

\[\sum_{k=3}^{k=26}\frac{26!}{(26-k)!} \approx 1.09 \times 10^{27}\]

possible keys in the Vigenère cipher.

Hanne: That's a lot of possible keys.

Alice: Yes. And this is just a lower bound on the number of possible keys in the Vigenère cipher. This value that we obtained was under the assumption that letters cannot be repeated. However, while repeated letters may affect the security of the cipher when the key is short, allowing repeated letters is generally fine for longer keys.

Hanne: Oh! So, this means that there are upwards of \(1.09 \times 10^{27}\) possible keys in the Vigenère cipher!

Alice: That's right.

Hanne: Wow…wee!

Alice: Wow…wee, indeed! But let's not get ahead of ourselves. While understanding the size of the keyspace in a cryptosystem is important, it is just one area of concern.

Hanne: Right. We also need to ensure that the cryptosystem does not leak any information.

Alice: Exactly. So, do you see any weaknesses in the Vigenère cipher?

(Hanne thinks.)

Hanne: Hmm. Nothing comes to mind. The best attack seems to be trying to brute force the repeated keyword or key phrase.

Alice: Yes. Brute force does seem to be the best attack. And given the large number of possible keys, it is highly unlikely that an adversary would ever figure out the secret key.

Hanne: I see. So… is this it? Have we found it? The Vigenère cipher? A secure cryptosystem?

Alice: Maybe.

Hanne: Oh!

Bob: Well… to burst your bubble—no. The Vigenère cipher can indeed be broken.

Hanne: Awww.

Bob: But interestingly, although it was developed in the 1500s, a method for breaking it didn't emerge until the 1800s. And it was this long period of unbreakability that earned it the name “the indecipherable cipher”—a name it is still known by today, even though we now know how to break it.

Hanne: The indecipherable cipher… coool.

Alice: Now, we'll talk about how to break the Vigenère cipher in a bit, but first, let's take a step back and review the history of cryptography. This will help us see how everything fits together.

Bob: Ah, good idea, Alice. We did not delve into the history of cryptography earlier, Hanne—at least not step by step—since bombarding you with historical details about concepts you weren't yet familiar with wouldn't have been very effective. However, now that you have some insight into what the field of cryptography is all about, you should be better able to appreciate some of its historical developments.

Hanne: Right. I'm quite the experienced cryptographer now.

Bob: Ha! Yep… a true master in the making.

Alice: Before we begin, though, it is important to acknowledge that a challenge faced when analysing the history of cryptography—or any field for that matter—is dealing with possible and likely gaps in documentation. Many developments and uses may not have been recorded, or their records may have been lost over time.

Bob: Right. Although we credit certain individuals with first introducing specific concepts, it is possible that similar ideas were developed much earlier by others whose writings have been lost. Those whom we recognise as the inventors of certain techniques are simply those whose writings provide the earliest known descriptions of them. In some cases, they may have been the first inventors, whereas in other cases, they may not have been—and we may never know for sure.

Alice: And this uncertainty not only affects how we perceive the developments of a field but also how we view its origins. For instance, the earliest recorded use of cryptography dates back to ancient Egypt around 1900 BC. However, we have no idea to what extent it was used before then. We can't say for certain who invented cryptography or when it was first used; it likely evolved alongside language and modes of communication. So, when exploring history, it is crucial to recognise that surviving records do not provide a complete story. It is important to keep an open mind and approach history critically.

Hanne: Got it.

Bob: And while we're on the topic, we might as well mention a few other factors to consider when analysing history. One is interpretation: two historians may study the same material and draw different conclusions about its significance. Then, there is translation—where subtle variations in translation can alter a text's meaning or perceived meaning. And finally, there is the challenge of evaluating the credibility of historical sources.

Alice: Right. Evaluating the credibility of historical sources is important since historical accounts often contain biases and inaccuracies. One way to overcome these is to study historical accounts from different perspectives and examine the prevailing narrative. However, we don't always have access to these varied perspectives, and this can result in a narrative filled with inaccuracies. Additionally, for many ancient historical events, the surviving historical accounts were written by people born years after the events took place. In some cases, their writings are based on stories that were passed down orally, whereas, in other cases, their writings are based on documented knowledge that has since been lost. This makes it difficult to determine the credibility of these accounts. Nevertheless, we do the best we can with the resources available to us when evaluating the credibility of historical sources.

Hanne: I see.

Alice: So, hopefully these insights will encourage you to think more critically about history in whatever field you explore it in. And right now, that field is cryptography!

Hanne: Alrighty! Let's hear about the history of cryptography!

Alice: That's the spirit! It's going to be a lot in a short space of time, so take a deep breath, and here—we—go! The earliest recorded use of cryptography dates back to ancient Egypt around 1900 BC, where non-standard writing was found carved into the walls of a tomb. While it is widely believed that this writing was used for enhancement rather than secrecy, for many historians, the modification of plaintext qualified these writings as cryptographic, marking them as the first recorded use of cryptography.

Bob: From 1900 BC to around 50 BC, several ancient civilisations used cryptography in different ways. A notable example is clay tablets from Mesopotamia dated around 1500 BC, which are the first instance of cryptography being used to protect information—in this case, instructions for creating ceramic glazes. Another example is the “Scytale transposition cipher”, which was used by the Spartan military around 650 BC.

Alice: We did not talk about transposition ciphers, but essentially, they work by rearranging the order of the letters in the plaintext instead of substituting them. For example, the plaintext “SPARTANS” might be encrypted to the ciphertext “STPAANRS”.

Bob: Right. And specifically, in the Scytale cipher, the scytale was a wooden rod around which a strip of parchment was wrapped—“parchment” refers to material made from the skin of an animal that was used as a writing surface in ancient times. A message was written across the length of the parchment wrapped around the scytale, and when unwrapped, the text appeared scrambled. Then, to decrypt the message, the receiver would wrap the parchment around a rod of the same diameter. In this manner, the key in the Scytale cipher was a scytale of the correct diameter.

Hanne: Okay…

Alice: Admittedly, this can be a bit difficult to visualise, but you can imagine a thin, long piece of cloth wrapped around the trunk of a tree. The loops stack vertically on top of one another until much of the trunk is covered by the cloth. The message is then written vertically down the cloth, moving to the next column when the previous one is filled. Then, when the cloth is unwrapped, the message is still there, but the letters are scattered with no obvious order—that's the ciphertext. To decrypt, the receiver would have to wrap the cloth back around a tree trunk of the same thickness for the letters to line up correctly. This is essentially how the Scytale transposition cipher works.

Hanne: Ah… that clears things up a bit.

Alice: Excellent. Next, on to 50 BC, around the time when Julius Caesar used the shift cipher to secure his military communications. It's worth noting, though, that the oldest existing record claiming that Caesar used this cipher comes from Gaius Suetonius Tranquillus, a Roman historian born over a century after Caesar's death. Regardless, the Caesar cipher remains one of the most well-known ciphers, and it is often the first cipher that one is introduced to when learning about cryptography. This is perhaps due to a combination of its simplicity as well as Caesar's prominence in history.

Bob: Right. We encourage you, Hanne, to learn more about Julius Caesar and ancient Rome, as there are many fascinating insights to uncover. As a glimpse into Caesar's legacy, he played a key role in setting the stage for the transformation of the Roman Republic into the Roman Empire, paving the way for centuries of imperial rule. … On a lighter note, he also reformed the calendar, extending the length of a year from 355 days to 365 days and introducing leap years. This new calendar became known as the “Julian calendar”, and it remained in use for around 1600 years before being adjusted in 1582. The month of July is also named after Julius Caesar, and August is named after his successor, Augustus Caesar.

Hanne: Interesting. I will check out the life of Julius Caesar.

Bob: Lovely.

Alice: Moving on, the next major cryptographic development came centuries later from Al-Kindi, an Arab polymath who lived around AD 850. The term “polymath” is used to describe someone with exceptionally wide knowledge across several disciplines. Al-Kindi is considered to be “the father of Arab philosophy” and contributed to the fields of philosophy, music, mathematics, and astronomy, among others. With respect to cryptography, his writings discussed numerous cryptanalytical techniques that significantly advanced the field. Most notably, he is credited with being the first to describe the frequency analysis method for attacking substitution ciphers.

Hanne: Oh!

Bob: Jumping ahead to 1476, we encounter Leon Battista Alberti, an Italian polymath known for his contributions to architecture, art, philosophy, and cryptography. Alberti provided one of the earliest clear explanations of a polyalphabetic cipher, which became known as the Alberti cipher. For its time, it was reasonably secure.

Alice: On to 1518, when a cryptographic book by the German polymath and monk, Johannes Trithemius, was published. In this book, Trithemius discussed several cryptographic concepts and is credited with coining the term “tabula recta” to describe a square table with shifted alphabets. He also described a polyalphabetic cipher that has since become known as the “Trithemius cipher”. This cipher shifts the letters of the plaintext by an increasing amount, resetting to 0 after a shift of 25. That is, you can think of the Trithemius cipher as a Vigenère cipher with a key of “abcdefghijklmnopqrstuvwxyz”. However, technically, the Trithemius cipher does not have a key since the increasing shift is built into the algorithm.

Bob: However, in 1553, Italian cryptographer Giovan Battista Bellaso introduced the concept of using a keyword or key phrase as the starting point for the key and repeating it to match the length of the plaintext.

Hanne: Right, that's basically the Vigenère cipher.

Bob: Correct. However, it is worth noting that in Bellaso's original description, he did not use the tabula recta—where 'a' corresponds to a shift of 0, 'b' to a shift of 1, and so on. Instead, he used a different method of substitution. But over time, this was replaced with the tabula recta, leading to the Vigenère cipher that we know and love today.

Hanne: Okay… but where did the name “Vigenère” come from?

Alice: Ah, so this is where there was a bit of a mix-up. In 1586, French diplomat and cryptographer Blaise de Vigenère published a book on cryptography that expanded on the ideas from Bellaso's 1553 book. He also introduced a new cipher, known today as the “Vigenère autokey cipher”. Vigenère's work helped popularise Bellaso's cipher but, over time, created some confusion about its original inventor. Many came to believe that both Bellaso's cipher and Vigenère's autokey cipher were created by Vigenère. This eventually led to the misattribution in the 1800s, where Bellaso's cipher officially became known as the “Vigenère cipher”.

Hanne: Ohhh. And how did Bellaso feel about this misattribution?

Alice: Well, Bellaso published his work in 1553, and the misattribution happened around 300 years later. So, he probably did not feel anything.

Hanne: Ah, right. He would have been a goner.

Bob: Actually, if I may, the exact date of Giovan Battista Bellaso's death is not well documented. So, theoretically, he could still be alive. Legend has it that if you talk about the Vigenère cipher without crediting Bellaso, you will hear a bell when you are going to sleep that very night—and then, Bellaso will appear—and eat you!

Hanne: Ahhh!

Bob: That's right, Hanne. Fear the bell. Many cryptographers have been eaten by Bellaso.

Alice: Thank you, Bob, for that… interesting piece of information.

Bob: Anytime.

Alice: Don't worry, Hanne. Nobody is going to eat you.

Bob: That's what they all say, Hanne. Beware the Bellaso… ding… dong… ding… dong.

Alice: Aaaanywhos… the Vigenère cipher—first described by Bellaso—was considered unbreakable for hundreds of years, earning it the name—

Hanne: The indecipherable cipher.

Alice: Indeed. And although there were occasional reports of the Vigenère cipher being broken, the success of those attacks relied on additional information that was usually gained through espionage. It wasn't until 1863 that the first general method for breaking the Vigenère cipher was published. This method was developed by a German military officer, archaeologist, and cryptographer, Friedrich Kasiski, and it is known today as the “Kasiski examination”.

Bob: However, even though the Kasiski examination was a groundbreaking development in the field of cryptography, it initially went unnoticed, leading Kasiski to turn his attention to other pursuits. He died in 1881, with his work still largely unrecognised, and did not live to see the impact that his cryptographic contributions would eventually have. As it turned out, his work wasn't just crucial to breaking the Vigenère cipher, but it also laid the foundations for the cryptanalytic endeavours that followed.

Hanne: I see.

Bob: And to give you a sense of just how unrecognised Kasiski's cryptographic work initially was, the author and mathematician Charles Lutwidge Dodgson—better known by his pen name, Lewis Carroll—described the Vigenère cipher as unbreakable in his 1868 piece, “The Alphabet Cipher”. That was five years after Kasiski had published his method for breaking it!

Alice: Right. And speaking of initially unrecognised work, it turns out that a general method for breaking the Vigenère cipher was actually known before Kasiski published his work in 1863! About a decade earlier, the English mathematician, philosopher, and inventor Charles Babbage—widely considered to be “the father of the computer”—broke the Vigenère cipher, as well as the Vigenère autokey cipher. However, Babbage's work took place in the climate of the Crimean War of the 1850s and was therefore kept a military secret.

Hanne: Oh!

(Hanne thinks.)

Hanne: Wait. How long did the Crimean War last?

Alice: The Crimean War lasted from 1853 to 1856.

Hanne: Okay, so why wasn't Babbage's work made public after the war ended?

Alice: Oh, after war ends… interesting.

(Alice thinks.)

Alice: There are two constants in this world, Hanne. There is love, and there is war. And it seems as if, at least in this world, one cannot exist without the other. So, Babbage's work would have been kept secret, as knowing how to break the Vigenère cipher—a cipher that most of the world thought to be unbreakable—would have been a huge advantage in the wars to come.

Hanne: I see. Love and war… intriguing.

Alice: Yes, such is the way of the world. But anyways, that's it! That's the history of cryptography up until the 1800s! While we did not cover every historical use, we focused on what we felt were the key developments; you can explore the rest on your own if you're interested. For now, here's a quick recap of what we discussed: