Introduction

Cryṗtography is the study of hi̇ddeṅ writing, or reading and writing secret messages or codes. The word cryptograpḣy cȯmes from the Greek word kryptos (\(\kappa \rho \upsilon \tau \varsigma\)), meaning "hidden", and graphein (\(\gamma \rho \alpha \phi \omega\)), meaning "writing". There are some key words that wil̇l come up frequently in today’s lėsson.

• Plaintext: The original message or information the sender wants to encode or hide

• Encryption: The process of encrypting plaintext such that only authorized parties, such as the sender and intended receiver, can read it

• Ciphertext: The plaintext that was encrypted using a cipher (the method of encryption)

• Decryption: The process of decoding ciphertext back into its original plaintext

The ciphers we will look at in this lesson are substitution ciphers. Substitution ciphers take letters in the alphabet and replace them with other letters in the alphabet, switching them with other letters such that the phrase "Hello!" becomes the gibberish "Svool!" to an eavesdropper.

Atbash Cipher

Originally created using the Hebrew alphabet, the Atbash cipher is created by reversing the alphabet. That is that A becomes Z, B becomes Y, C becomes X, and so on, until Z becomes A.

This is more easily represented below.

• A \(\Leftrightarrow\) Z
• B \(\Leftrightarrow\) Y
• C \(\Leftrightarrow\) X
• D \(\Leftrightarrow\) W
• E \(\Leftrightarrow\) V
• F \(\Leftrightarrow\) U
• G \(\Leftrightarrow\) T
• H \(\Leftrightarrow\) S
• I \(\Leftrightarrow\) R
• J \(\Leftrightarrow\) Q
• K \(\Leftrightarrow\) P
• L \(\Leftrightarrow\) O
• M \(\Leftrightarrow\) N

Caesar Cipher

This is one of the most well-known substitution ciphers. It is named after Julius Caesar who would encrypt communication intended for his army. Caesar encrypted his messages by shifting over every letter of the alphabet by 3 units. The cipher is as follows:

The idea of the Caesar shift can be improved by using shift numbers other than 3.

1. MY SALAD NEEDS DRESSING (8)

   plaintext	A	B	C	D	E	F	G	H	I	J	K	L	M
   ciphertext	I

   plaintext	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
   ciphertext

The last Exercise shouldn’t be too difficult since the shift number was provided. This is why the shift number, or key, is usually not sent along with the ciphertext itself, but agreed on before hand by both sender and receiver.

When talking about the effectiveness of ciphers, we also ask about the security of the cipher. A cipher is secure when it is very difficult to decrypt a given ciphertext without the shift number, key, or context of the message.

Breaking Ciphers

So far we have looked at certain ciphers and how to encrypt or decrypt their messages as intended. But a major component of cryptography is how ciphers are to be broken. To break a cipher means to decrypt the ciphertext using brute force or clever guesses.

Cryptography has its historical roots in warfare as we saw in the case of the Caesar cipher. If our communications to our allies are not encrypted when sent, enemies who intercept our messages gain unwanted access to our secret plans. By encrypting communications however, enemies may never understand our plans, or at the very least, we slow them down as they need to take some time to decipher them.

Notably World War II took place during a time where ciphers were becoming more and more complex. Emerging technologies were invented to encode, decode, and break ciphers much quicker. The Enigma Machine is a notable and well-known example of a cipher machine used by the Germans. Alan Turing, the "Father of Computer Science" was on the team of cryptographers who broke Enigma. This breakthrough not only contributed to the war ending sooner, but it was a major feat in computing and mathematics at the time.

Applying the remaining 25 shifts to a Caesar ciphertext might have been a long and tedious process in the times of Caesar, it is very accessible to break Caesar ciphers with the use of modern technology. For example, I ran the ciphertext through a website that brute-forced all possible shifts in a couple of seconds.

The security of the Caesar cipher, or the Atbash cipher for that matter, can be easily challenged by a computer program or very determined codebreaker. This doesn’t mean that all substitution ciphers can be broken as easily.

Consider this random substitution cipher I created just now with no pattern and no shift number in mind.

• A \(\Leftrightarrow\) U
• B \(\Leftrightarrow\) Q
• C \(\Leftrightarrow\) Z
• D \(\Leftrightarrow\) V
• E \(\Leftrightarrow\) P
• F \(\Leftrightarrow\) X
• G \(\Leftrightarrow\) O
• H \(\Leftrightarrow\) W
• I \(\Leftrightarrow\) R
• J \(\Leftrightarrow\) Y
• K \(\Leftrightarrow\) S
• L \(\Leftrightarrow\) N
• M \(\Leftrightarrow\) T

If I send out the message HWUM MRTP RK NALZW? without the cipher attached, anyone who intercepts the cipher may try to break it using the Caesar or Atbash ciphers without success. They will have to resort to other means of decoding it. This means that the security of substitution ciphers is not weak at all. You can easily upgrade my shift by not having the same letters map to each other (e.g. A encodes to U, but U encodes to G, G encodes to W, etc.).

Even if you are a computer programmer, there are \(26! = 403291461126605635584000000\) possible arrangements of the English alphabet, meaning there are far too many possible substitution ciphers to brute force. This implies that we will need to be more clever with the ways that we narrow down the best approaches to breaking a cipher.

Frequency Analysis

One method of breaking an encryption is known as frequency analysis. Since we are dealing with letters, frequency is the number of times a letter occurs. This is particularly useful for substitution ciphers. By noting the most frequent letters in a ciphertext, we can begin to deduce what letters they might correspond to in the plaintext.

Below is the frequency graph that shows the average frequency of each letter in the English alphabet.

The most commonly used letter of the English alphabet is the letter E. Following E, we have the letters T, A, O, I, N, etc.

In knowing the most frequent letters of a message, we can begin to take guesses at possible substitutions of its letters. If the message is long enough, we might even observe common groups of letters being used multiple times, indicating frequently used words of the language.

Vigenère Cipher

Let us look at one more substitution cipher that can be considered more secure than ciphers we have seen before. The Vigenère cipher was invented in by Giovan Battista Bellaso in 1553 despite being named after Blaise de Vigenère.

Vigenère encryption uses a keyword. Using this keyword, we will apply several Caesar ciphers at a time. We will also need to translate the alphabet into numbers:

The Vigenère Cipher is much harder to break compared to the ciphers from before. In the last example, the two O’s in COOKIE will be shifted by 2 and 14 respectively, leading to them not sharing the same ciphertext letter despite being the same plaintext letter. In the Problem Set, we will work on decrypting Vigenère ciphertexts and explore how frequency analysis can be used to break it.