Chapter 2: The Evolution of Ciphers

Over the last several centuries, we have seen advancements in civilization, along with improvements in technology. As a result, we have seen an evolution in the methods used to conceal information. To set the foundation for more advanced topics that we will be covering in this book, we'll review some ancient techniques to conceal information. We'll start with a brief overview of some early ways to hide messages. We'll learn how data was concealed using a tool called a scytale, along with a radical method using a tattoo etched on a trusted servant's head. We'll then see how data was concealed using monoalphabetic and then polyalphabetic ciphers along with an example of each, using both the Caesar and Vigenère ciphers.

We'll then see how the effect of war led to advances in the way to encode and securely transmit messages. We'll discover how Claude Shannon, whose early research is still influential in modern-day encryption, outlined the concepts of using substitution and permutation to encode data more effectively. Finally, we'll see how with the advent of computerization in the 1960s and 1970s, the need to protect digital data became increasingly evident. As a result, we'll see the development of the Feistel cipher, a precursor to the Data Encryption Standard (DES) that is used to secure digital data.

In this chapter, we're going to cover the following main topics:

• Early uses of cryptography
• Encoding transmissions during war
• Entering the digital age

Early uses of cryptography

For thousands of years, we have been trying to conceal private information in a variety of ways. Today, we use cryptographic techniques to protect credit card information, personally identifiable information (PII), and online transactions. However, over the years, much of the effort to protect information has stemmed from activity surrounding war efforts. Concealing information was done in an attempt to prevent the enemy from gaining access to sensitive information.

In this section, we'll take a look at some ancient ways to hide messages. We'll start with a few of the early examples used, which includes the scytale and even tattoos. We'll also review monoalphabetic ciphers, such as the Caesar cipher. We'll then review the introduction of polyalphabetic ciphers, using the Vigenère cipher as an example.

Let's start with a brief look at some ancient ways to conceal information.

Using tattoos and scytales

Early iterations of obscuring information involved using symbols, such as hieroglyphics, during the time period around 1900 Before Common Era (BCE) by the Egyptians.

As shown in the following figure, there were several different types of symbols used:

Figure 2.1 – Hieroglyphic images

However, the meaning is unclear unless you understand what the symbols represent. While hieroglyphics may not have been intentionally vague, the concept relates to modern-day cryptography, in that the message won't mean anything unless you have a key to decode the information.

A lesser-known method involves tattooing a message on the head, as we'll see next.

Tattooing a message

What better way to conceal information than by hiding in plain sight? That is the basis of the approach used to send a message from one Greek ruler to another during the 6th century BCE.

The Greek leader Histiaeus, son of Lysagoras, wanted to launch an uprising against the king of Persia, Darius I. In order to get a message to another Greek ruler to launch a revolt against Darius I, Histiaeus devised a plan using his most trusted servant.

Histiaeus shaved the servant's scalp, tattooed a simple message on his head, and then waited for the servant's hair to grow back. Once the message was concealed by hair, Histiaeus sent the servant to an ally, Aristagoras, the leader of the Ionian Greeks. The servant told Aristagoras that he had a message from Histiaeus and explained that in order to see the message, Aristagoras had to shave his head. Aristagoras then shaved the servant's head, which revealed the message REVOLT.

This early example of concealing a message illustrates how, even centuries ago, we had a need to keep information confidential. Another example of an innovative way to hide information is by using a scytale. Let's take a look.

Wrapping parchment

The Greeks and the Spartans around the time of the 7th century BCE also devised a method to secretly communicate. The method used a carefully constructed block of wood, and a thin strip of parchment with lettering on the parchment.

The tool, called a scytale, was one of the first methods to encode text, and is considered a transposition cipher, as it transposes the letters. Both the sender and receiver had the same tool to encrypt and decrypt the secret message.

To create the message, the sender would need to do the following:

1. Wrap the parchment around the scytale.
2. Write the message across one line.
3. Fill in the rest of the lines with random characters.

To read the message, the receiver would need to do the following:

1. Wrap the parchment around the scytale.
2. Read the message.

As shown in the following figure, once the thin strip of parchment was wrapped around the block of wood, the message would then appear:

Figure 2.2 – A scytale

The message meant nothing without the scytale, as it just looked like a strip of parchment with some lettering, as shown in the following figure:

Figure 2.3 – Message on parchment

Although simple by today's standards, during that time period, the scytale was an effective way to covertly send messages.

Many of the early ways to conceal messages involved using a single alphabet. Later on, methods to use more than one alphabet to further obscure the message were developed. Let's explore the concept of monoalphabetic and polyalphabetic substitution ciphers next.

Evaluating monoalphabetic ciphers

A monoalphabetic substitution cipher uses a single alphabet and substitutes one letter or character for another. Characters can include letters, special characters such as an exclamation point or a pound sign, along with punctuation marks. This basic cipher uses a key to decode the message.

An example of a monoalphabetic substitution cipher is the Caesar, or shift, cipher. Let's see an example next.

Examining the Caesar cipher

The Caesar cipher was created by Julius Caesar so that he could keep certain information confidential. This simple cipher shifts the letters over by a predetermined number of spaces to encode the message.

For example, if we shift over by two spaces, A will become F, and B will become G, and so on, as shown in the following diagram:

Figure 2.4 – Caesar shift over by two

In some, but not all, cases, the letters are wrapped around. To decode the message, you need to shift each letter back by the predetermined number of spaces.

The cipher was developed in around 50 BCE and was effective, in that you could not decode the message unless you knew the shift amount. Another reason the cipher was effective was that, during that time, scholars felt that only about 10-20% of the population could read and write. As a result, even if someone were to be able to determine the shift, they might not be able to read the message, which provided another level of security.

A monoalphabetic substitution cipher is a simple cipher that can be cracked by using letter frequency analysis. As time passed, stronger ciphers were developed. That included the use of more than one alphabet, as we'll discuss next.

Recognizing polyalphabetic ciphers

In 1563, Giovanni Battista Porta published the book De furtivis literarum notis, or The Secret of Letters, which outlined the use of various ciphers. Porta developed the Porta Cipher, which is a polyalphabetic substitution cipher.

A polyalphabetic cipher uses more than one alphabet to encode text. The additional alphabet is resistant to the use of letter frequency analysis and provides an additional layer of confusion when attempting to decode the message.

Another example of a polyalphabetic cipher is the Vigenère cipher. Let's take a look.

Studying the Vigenère cipher

In 1586, Blaise de Vigenère developed a polyalphabetic substitution cipher that used a table that had two alphabets. The two alphabets are arranged in a table, as shown in the following figure:

Figure 2.5 – The Vigenère square

The letters are arranged in a pattern using a right circular shift in each row. Once the row is shifted, the character at the end is moved to the first position. The first row does not shift; the remaining rows shift as follows:

• The second row shifts to the right by one.
• The third row shifts to the right by two.

The shifts continue until the last row, which shifts to the right by 25, and the character at the end is moved to the first position.

Text is encoded by the intersection of a key (or secret word) and the message. For example, we will use the following:

• The phrase is LET'S STUDY CRYPTOGRAPHY.
• The key, or secret word, is TIGERKITTENS.

To encode the text, we will remove any apostrophes or spaces and put the phrase LET'S STUDY CRYPTOGRAPHY along the top. Below, we will put the secret phrase, TIGERKITTENS, which will repeat until the end of the characters as follows:

Figure 2.6 – Table with phrase and secret word

Using the table, we will take the first letter, L, which will intersect with the first letter of the secret word, T, which results in the letter E, as shown in the following figure:

Figure 2.7 – The first letter of the phrase intersecting with the first letter of the secret word

We'll then take the second letter, E, which intersects with the second letter of the secret word, I, and results in the letter M. All letters are evaluated to produce the output, as shown in the last row of the following table:

Figure 2.8 – Table with phrase after encrypting text

As you can see, the message would be difficult to decode without the key.

Throughout history, much of the need to conceal messages was during a time of conflict or war, as we'll see next.

Encoding transmissions during war

A primary driver to conceal information from prying eyes is war, mainly because, during a conflict such as a war, it's critical to communicate with allies to transmit information about the enemy, along with reports and attack plans. During any conflict, whether on land, air, or at sea, encoding the message is key in preventing information from being intercepted by the enemy.

In this section, we'll take a brief look at communication methods over the years. We'll then take a closer look at the Enigma machine, a complex German engineered device used in World War II that created strong encrypted messages.

Let's start with a discussion on communication methods that are essential during battle.

Communicating during wartime

During a war, the ability to communicate offers military leaders the advantage to control, coordinate, and oversee their armies. If a military leader is unable to effectively communicate with their allies, this could lead to a crushing defeat.

Throughout the years, communication techniques have been developed and improved, all with the goal of being able to provide split-second communication to the troops. Methods have varied according to the technology and the location of the signal.

Whether on land, sea, or air, communication methods could have included any of the following:

• Primitive methods such as riders on horseback and bicycles, homing pigeons, and messenger dogs
• Visual techniques such as sail movements, signal flags, cannon blasts, and coordinated lighting techniques
• More sophisticated approaches, such as telegraphs, radio, and telephones

Let's take a look at some of the more sophisticated techniques used. We'll start with a discussion on Morse code, which uses electrical pulses, along with flash signaling, which used lights to transmit information.

Using Morse code and flash signaling

In the years before the American Civil War, Samuel F.B. Morse developed a technique that sent electrical signals over copper wire. Called Morse code, the signaling worked in the following manner:

• Three dots equal a dash.
• Spaces within a letter equal one dot.
• Spacing between letters equals three dots.
• Spacing between two words equals seven dots.

For example, the first three letters of the alphabet use dashes and dots as follows:

Figure 2.9 – The letters A, B, and C represented in Morse code

Morse code changed the landscape for war efforts such as the American Civil War, as it enabled speedy signal communication. To hear what Morse code sounds like, visit https://www.youtube.com/watch?v=_J8YcQETyTw.

Another related technique was flash signaling, which generated signals using long and short flashes of light. An example of a device used to transmit light was a heliograph, which had two mirrors that captured sunlight, and allowed the operator to transmit Morse-code-like signals. The heliograph had limited use, in that it required sunlight to transmit the signal.

Later on, during the last half of the 19th century, came more advanced technologies that enhanced the ability to communicate, such as the telephone and radio. Let's explore these concepts.

Transmitting via phone and radio

The telephone was invented by Alexander Graham Bell in 1876. However, the telephone was not universally available to everyone until years later. The phone technology evolved, expanded, and slowly became available to more individuals from the late 1800s into the early 1900s.

Military leaders saw the value of using the telephone during wartime. Phone lines were either strung using telephone poles or buried in trenches, which allowed the ability to keep in touch with the troops during conflict.

Although an invaluable tool, there was always the threat of someone cutting the phone lines, or the lines being destroyed by artillery fire, which then severed the ability to communicate.

Near the end of the 1800s, another powerful communication method, the radio, was developed and used wireless signals instead of electrical pulses. Also called the wireless telegraph, this enhanced the ability to communicate information using radio waves, with no danger of someone cutting the wires. However, radio signals introduced a new threat, which was the ability of someone to intercept the signal.

Although in its infancy, radio was used early in the 1900s to aid in communicating during World War I. By World War II, radio use had expanded and evolved. The devices became more powerful, portable, and had the ability to transmit communications over greater ranges.

As the war progressed, the need to transmit securely became more evident. With the threat of someone eavesdropping on the signal came the need to come up with creative ways to secure the transmissions.

One significant device developed to encrypt data transmissions during the war was the Enigma machine, as we'll learn next.

Examining the Enigma machine

Along with the ability to transmit via radio came the threat of someone intercepting the signals. As a result, the need to conceal or encrypt messages to keep information from the enemy became paramount.

Shortly after the end of WWI, a German engineer, Arthur Scherbius, developed a mechanical device that was capable of creating strong coded messages that were nearly impossible to crack. The device, called the Enigma, had four main components, as follows:

• Five rotors, of which the operator would use three at a time; the rotors could be adjusted (or rotated) according to the desired settings
• A keyboard with 26 keys that corresponded to the letters of the alphabet and was streamlined, in that you couldn't enter any spaces, special characters, numbers, or returns
• The lampboard, which was illuminated when a letter was encoded
• A plugboard or tiny switchboard (also called the steckers)

A representation of the Enigma is shown in the following diagram, with an approximation of each of the components:

Figure 2.10 – The Enigma machine

To further encode the text, the operator could use the plugboard (or steckers), which had 26 sockets. By using a wire with two jacks, the operator would insert one end into a plug (or letter), and the other jack into another plug (or letter). For example, the operator might select Y -> T.

During World War II, German troops used the Enigma to encode strategic messages. During this time, and for several years prior to World War II, many attempted to crack the code. Ultimately, it was the mathematician Alan M. Turing who was able to break the code.

To view the mechanics of the Enigma, visit https://www.tamdistrict.org/cms/lib/CA01000875/Centricity/Domain/539/Enigma--The%20Mathematics%20Game.pdf.

The Enigma provided a solid way to encrypt data. However, when computers entered the picture, and we started using digital data, scientists started to explore ways to protect the confidentiality and integrity of our information. Let's explore this in the next section.

Entering the digital age

Throughout the 1960s and 1970s, computers started populating offices, industry, and government organizations. It soon became apparent that it was necessary to protect data in some way from prying eyes.

However, several decades earlier, the concept of encrypting data was already in the works. In this section, we'll learn how Claude Shannon, an American mathematician and cryptographer, outlined how to encrypt digital data. We'll then examine the beginnings of the DES, with the development of the Feistel and Lucifer ciphers in the 1970s, as scientists recognized the need to secure digital data.

Let's begin by learning about Shannon and his contributions to the field of computing and cryptography.

Innovating in the field of computing

In 1941, Claude Shannon was a young scientist working at Bell Telephone Laboratories (Bell Labs). Shannon worked at Bell Labs conducting research on Boolean algebra and circuit switching. The research would be instrumental in the development of telephone systems during the first half of the 1900s.

Important note

Shannon was an innovator in the field of computing and artificial intelligence. Early on, he provided the insight that digital equipment (computers) should use a binary value, either a 1 or a 0 (true or false), to communicate efficiently. Shannon expanded his research in binary, and coupled that with Boolean logic, which helped him to become a leader in the digital revolution.

Shannon also worked on classified military projects throughout World War II. One of his more influential projects was that on cryptography. In 1941, Shannon wrote A Mathematical Theory of Cryptography, which at the time was classified. The paper was later shortened, declassified, and published in 1949. This work solidified cryptography as a science and revolutionized the field.

Shannon stressed the importance of confusion and diffusion when encrypting text. The concepts are the foundation of contemporary block ciphers, and are outlined as follows:

• Confusion is obscuring any connection between the unencrypted text, the resultant ciphertext, and the key.
• Diffusion distributes the influence of the unencrypted text or key across as much of the resultant ciphertext as feasible.

When encrypting text, confusion and diffusion is achieved using successive rounds of substitution and permutations of the bits (or characters):

• Substitution substitutes or switches one bit (or character) for another.
• Permutation transforms or rearranges the order of the bits (or characters).

Keep in mind, during a digital transformation, the bits will be transformed; however, when doing a manual transformation, such as the Caesar shift, the characters will be manipulated.

Let's take a look at each of these concepts, starting with substitution.

Substituting values

Substitution can be achieved by using a substitution or S-BOX, also called a lookup table, which replaces characters and satisfies Shannon's property of confusion.

Let's step through an example of how we use the S-BOX to substitute bits (or characters):

1. We start with an input array that holds the initial values, as shown on the left. We also need the S-BOX that provides the values to substitute, as shown on the right in the following diagram:
   

   Figure 2.11 – The initial state

2. Next, we see the first value from the input array, 43, is mapped to column 4 row 3 in the S-BOX:
   

   Figure 2.12 – Using the S-BOX to replace the value 43

3. Once the first value is substituted, this then becomes C1 in the input table:
   

   Figure 2.13 – The input box replaced with the first value, C1

4. The rest of the values for the input box are then replaced, which now completes the substitution.

Next let's take a look at how we can provide permutation.

Grasping permutation

During permutation, the bits (or characters) will transform from their original order. One way to achieve permutation is by using a circular shift.

A circular shift is a basic concept that shifts the bits (or characters) either to the left or to the right.

Let's start with an example of a left circular shift.

Shifting to the left

For a left circular shift for x bits (or characters), where x represents the number of bits (or characters), you would do the following:

• Remove x bits (or characters) from the left and append the bits (or characters) to the right.
• Shift the remaining bits (or characters) to the left:

  Input: 00010111

  Shift to the left 2: 01011100

Now let's reverse the process to achieve a right circular shift.

Shifting to the right

For a right circular shift for x bits (or characters), where x represents the number of bits (or characters), you would do the following:

• Remove x bits (or characters) from the right and append the bits (or characters) to the left.
• Shift the remaining bits (or characters) to the right:

  Input: 00010011

  Shift to the right 2: 11000100

To check your work, visit https://www.browserling.com/tools/rotate-binary.

Throughout the years, Shannon's influence has provided a template for cryptographic techniques. Next, let's learn how scientists in the 1970s used Shannon's tenets to develop some early ciphers.

Developing the early ciphers

In the 1970s, computers began to infiltrate industry, universities, and government. During that time, much of the data protection and restrictions started with the military, as they were the first to classify data.

Data was labeled according to its sensitivity; for example, data could be considered top secret, secret, or classified. The United States Government started to take a greater interest in protecting data. Scientists David E. Bell and Leonard J. La Padula (Bell-La Padula) published a paper in 1976 on access control, to provide data confidentiality and integrity.

Around the same time, in 1973, at IBM, scientist Horst Feistel developed a block cipher, which was called the Feistel cipher. Feistel outlined a structure that used successive and repeatable rounds on each block, to adhere to Shannon's principles of substitution and permutation.

The Feistel cipher is not a specific cipher; rather, it provides a basis or template for a block cipher design. It provides an elegant and simple encryption technique that is significant in that most modern block ciphers, including the DES, mimic the Feistel structure.

To see a more detailed illustration of the Feistel cipher, you can visit http://homepages.math.uic.edu/~leon/mcs425-s08/handouts/feistal-diagram.pdf.

As part of early experiments in cryptographic techniques at IBM, Feistel and his colleagues used the structure to develop the Lucifer cipher. Lucifer used a 128-bit key to encrypt 128 bits block of text and is the precursor of the DES.

We'll learn more about the Feistel and Lucifer ciphers, along with the DES, when we cover symmetric encryption in Chapter 4, Introducing Symmetric Encryption.

Summary

In this chapter, we learned about some of the early uses of encryption. We saw how primitive methods such as tattoos, along with tools such as the scytale, were used to conceal information. We then took a closer look at the differences between a monoalphabetic and polyalphabetic cipher and outlined examples of both. We discovered how, throughout the centuries, military leaders sought ways to send and receive messages to their allies during times of war or conflict. Methods to send messages included using dogs, along with homing pigeons, telegraph, telephones, and radio.

Along with the advances in technology came the threat of someone intercepting the messages. As we moved into the digital age, scientist Claude Shannon helped shape the field of computing and cryptography. We learned how substitution and permutation could provide confusion and diffusion during encryption. We then learned how the Feistel cipher provides the template for most modern block ciphers. We saw how the Feistel structure was used to develop the Lucifer cipher, and then DES, as scientists recognized the need to secure digital data.

In the next chapter, we'll compare the different types of attacks that threaten the security of our data. We'll outline the two main types: passive attacks, such as reconnaissance attacks, and active attacks, designed to destroy, steal, modify, or disrupt services or data. So that you can understand why it's necessary to protect data, we'll outline how data exists either in an organization or with an individual, and how not providing sufficient defense methods can lead to an attack and the exposure of sensitive data. Finally, you'll see how it's essential to keep data in its original form. We'll then discover how using encryption can ensure data integrity.

Questions

Now it's time to check your knowledge. Select the best response, then check your answers, found in the Assessment section at the end of the book:

1. The ___ used a carefully constructed block of wood and a thin strip of parchment with lettering on the parchment to conceal information.

   a. Enigma

   b. Blaise

   c. scytale

   d. Prussian

2. A monoalphabetic _____ cipher uses a single alphabet and substitutes one letter or character for another. Characters can include letters and special characters, along with punctuation marks.

   a. allocation

   b. substitution

   c. transposition

   d. Blaise

3. An example of a polyalphabetic cipher is the _____ cipher, which uses more than one alphabet to encode text.

   a. Vigenère

   b. Caesar

   c. scytale

   d. Prussian

4. The telephone was invented by Alexander Graham Bell in _____.

   a. 1923

   b. 1861

   c. 1917

   d. 1876

5. Shortly after the end of World War I, a German engineer, Arthur Scherbius, developed the _____, a mechanical device that was capable of creating strong coded messages.

   a. Enigma

   b. Caesar

   c. Blaise

   d. Parker

6. For a right circular shift of 3 bits using the input value of 10011010, the result would be _____.

   a. 00011110

   b. 11011100

   c. 11010100

   d. 01010011

7. The _____ cipher is a precursor the Data Encryption Standard.

   a. Lucifer

   b. Porta

   c. Basta

   d. Blaise

Further reading

Please refer to the following links for more information:

• For a review of some ancient uses of encryption, go to https://medium.com/tokenring/ancient-uses-of-cryptography-four-examples-that-pre-date-the-internet-14679ae4f509.
• Take a closer look at ancient languages and their origins by visiting https://www.ancient-origins.net/artifacts-ancient-writings/hidden-hieroglyphs-ancient-egyptian-lost-language-006653.
• Read more on the revolt against Darius here: https://storytellershat.com/2017/11/13/the-tattoo-which-sparked-the-ionian-revolt/.
• Learn how the Spartans concealed messages using a scytale by visiting ozscience.com/technology/a-scytale-cryptography-of-the-ancient-sparta/.
• Read an excerpt from Jewish Literacy in Roman Palestine: https://books.google.com/books?id=zlrxbYml2ioC&pg=PA23&hl=en#v=onepage&q&f=false to gain insight on the literacy rate during the time period around the 4th century BCE.
• Try out the Porta cipher by going to http://practicalcryptography.com/ciphers/porta-cipher/.
• Learn more about the Vigenère cipher, and try the cipher yourself, at http://practicalcryptography.com/ciphers/classical-era/vigenere-gronsfeld-and-autokey/.
• Visit the Computer Museum of America to see an image of the Enigma: https://www.computermuseumofamerica.org/2020/02/25/cmoa-unveils-rare-enigma-machine/.
• To encrypt data using an Enigma simulator, visit https://cryptii.com/pipes/enigma-machine.