In this lesson, students are introduced to the need for encryption and simple techniques
for breaking (or cracking) secret messages. They will try their own hand at cracking a message
encoded with the classic Caesar cipher and also a Random Substitution Cipher. Students should
become well-acquainted with the idea that in an age of powerful computational tools, techniques of
encryption will need to be more sophisticated. The most important aspect of this lesson is to
understand how and why encryption plays a role in all of our lives every day on the Internet, and
that making good encryption is not trivial. Students will get their feet wet with understanding the
considerations that must go into making strong encryption in the face of powerful computational
tools that can be used to crack it. The need for secrecy when sending bits over the Internet is
important for anyone using the Internet.
Encryption is a process - an algorithm - for transforming a message so that the
original text is hidden from anyone who is not the intended recipient. This is often called a
"secret code." Reversing the encryption process to reveal the original message is called decryption.
History is full of examples of people encrypting messages and attempting to crack secret codes.
- Encryption: a process of encoding messages to keep them
secret, so only "authorized" parties can read it.
- Decryption: a process that reverses encryption, taking a
secret message and reproducing the original plain text.
- Cipher: the generic term for a technique (or algorithm)
that performs encryption.
- Caesar's Cipher: a technique for encryption that shifts
the alphabet by some number of characters.
- Random Substitution Cipher: an encoding technique that
maps each letter of the alphabet randomly to different letters or characters.
- Cracking encryption: When you attempt to decode a secret
message without knowing all the specifics of the cipher, you are trying to crack the encryption.
Students will be able to:
- Explain why encryption is an important need for everyday life on the Internet
- Crack a message encrypted with a Caesar cipher using a Caesar Cipher Widget
- Crack a message encrypted with random substitution using Frequency Analysis
- Explain the weaknesses and security flaws of substitution ciphers
This lesson is the first in a series of lessons about cryptography and encryption.
"Encryption" is a process for transforming a message so that the original is "hidden" from anyone
who is not the intended recipient. Encryption is not just for the military and spies anymore. We
use encryption everyday on the Internet, primarily to conduct commercial transactions, and without
it our economy might grind to a halt. This lesson gives students a first taste of the kind of
thinking that goes into encrypting messages in the face of computational tools. Computational tools
dramatically increase the strength and complexity of the algorithms we use to encrypt information,
but these same tools also increase our ability to crack an encryption. Developing strong encryption
relies on knowledge of problems that are "hard" for computers to solve, and using that knowledge to
Ask the students to think about what things do they or
other people rely on keeping a secret in their daily life? Who are these
secrets being kept from? How are these things kept secret?
Make sure to:
- Provide a couple minutes for students to share their ideas with their classmates.
- Ask them to brainstorm as many areas as they can where they or other people rely on secrecy.
- Try to touch on as many different people and contexts as possible.
Some ideas that the class can discuss include:
- Social interactions (e.g., a surprise birthday party)
- A play in a sports game, your hand in a card game
- Personal identification information, PIN numbers, etc.
- Business and government negotiations
- Military activity
Secrecy is a critical part of our lives, in ways big and small. As our lives
increasingly are conducted on the Internet, we want to be sure we can maintain the privacy of
our information and control who has access to privileged information. Digital commerce, business,
government operations, and even social networks all rely on our ability to keep information from
falling into the wrong hands.
For example, in Roman times, Julius Caesar is reported to have encrypted messages to his soldiers and generals by using a simple alphabetic shift - every character was encrypted by substituting it with a character that was some fixed number of letters away in the alphabet. As a result an alphabetic shift is often referred to as the Caesar Cipher.
Spark the student's interest by asking them to decode the following:
serr cvmmn va gur pnsrgrevn
Give the students about 3-5 minutes on this. The correct answer is "free pizza in the cafeteria" with the A-Z alphabet shifted 13 characters.
Cracking the Caesar Cipher
In this set of activities the students will "crack" some encrypted messages with the use of tools. First, let's begin with messages encrypted with Caesar ciphers. Use the "Caesar Cipher Widget in the Resources Section.
Using the cipher, select a sample and crack the encryption.
Crack a Random Substitution Cipher
instead of shifting the whole alphabet, we mapped every letter of the alphabet to a random
different letter of the alphabet? This is called a random substitution cipher. Use the "Random Substitution Cipher Widget" in the Resources section
to crack a randomly substituted message.
Let the students know that the best technique for cracking a random substitution cipher is known as frequency analysis. Hint: Did you know that "e" is the most common letter in the English language?
Paraphrased from Wikipedia:
Frequency analysis is a technique that is based on how frequently certain letters appear in English versus others.
For instance, given a section of English text, E, T, A and O are the most common, while Z, Q and X are rare. Likewise, TH, ER, ON, and AN are the most common pairs of letters that occur next to each other.
In fact, the distribution of letters is roughly the same for almost all samples of English text.
By analyzing the frequency of the letters in the encrypted message compared to the frequency of letters in a typical piece of English prose, you can start to narrow in on what some of the letter mappings might be.
As part of wrap up the major points we want to draw out are:
- Encryption is essential for every day life and activity.
- The "strength" of encryption is related to how easy it is to crack a message, assuming adversary knows the technique but not the exact "key."
- A random substitution cipher is very crackable by hand though it might take some time, trial and error.
- However, when aided with computational tools, a random substitution cipher can
be cracked by a novice in a matter of minutes.
- Simple substitution ciphers give insight into encryption algorithms, but as
we've seen fall way short when a potential adversary is aided with computational tools... our
understanding must become more sophisticated.
- If we are to create a secure Internet, we will need to develop tools and
protocols which can resist the enormous computational power of modern computers.
Please use the following topics to bring closure to the lesson and as an avenue to draw out the points above.
- How much easier is it to crack a caesar cipher than a random substitution cipher? Can you put a number on it? Possible Response: For Caesar's Cipher there are only 25 possible ways to shift the alphabet. Worst case, you only need to try 25 different possibilites. A random substitution cipher has MANY more possibilities (26 factorial = 4x10^26 possibilities). However, as we learned, with frequency analysis we can avoid having to try all of them blindly.
- Was it difficult to crack a Random Substitution cipher? Did it take longer than you thought? shorter? Why? Possible Response: Computational tools aid humans in the implementation of encryption, decryption, and cracking algorithms. In other words, using a computer changes the speed and complexity of the types of encryption we can do, but it also increases our ability to break or circumvent encryption.
- Any encryption cipher is an algorithm for transforming plaintext into ciphertext. What about the other way around? Can you write out an algorithm for cracking a Ceasar cipher? What about a random substitution cipher? Possible Response: An algorithm for cracking a Caesar cipher is pretty easy - for each possible alphabetic shift, try it, see if the words come out as english. An algorithm for cracking random substitution is trickier and more nunanced. There might not be a single great answer but through thinking about it you realize how tricky it is to codify human intelligence and intuition for doing something like frequency analysis into a process that a machine can follow. It probably requires some human intervention which is an interesting point to make.
- Recall that in RFC 3271, "The Internet is for Everyone" Vint Cerf wrote the following. What did he mean by "cryptographic technology?" What does it mean to you now? "Internet is for everyone - but it won't be if its users cannot protect their privacy and the confidentiality of transactions conducted on the network. Let us dedicate ourselves to the proposition that cryptographic technology sufficient to protect privacy from unauthorized disclosure should be freely available, applicable and exportable."
- Review of Terminology -- you can use this opportunity to review new vocabulary introduced in the activity and respond to questions students may have encountered during the activity. Possible Response: Definitions of cryptography, encryption, decryption, cracking/breaking an encryption, cipher, etc.
Q1: What is a Caesar cipher? As part of your answer demonstrate encrypting the plaintext messages: CS IS COOL with a caesar cipher.
Q2: What is the "key" to a Caesar Cipher that someone needs to know (or discover) to decrypt the message?
- A.) A secret word only know by Caesar.
- B.) The number of characters to shift each letter in the alphabet.
- C.) The letter that occurs most often in the encrypted message.
- D.) The day of the month that the encrypted message was sent.
Q3: The Caesar Cipher has 25 different shifts to try. How many possibilities are there to try in a random substitution cipher?
- A.) 26
- B.) 26 × 25
- C.) 26 × 25 × 24 ×···× 3 × 2 x 1
- D.) 2626
Q4: List 3 characteristics of the ideal encryption scheme.
Q5: Knowing what you know now about frequency analysis, would you feel comfortable sending your password over the Internet using a substitution cipher? Why or why not?
The earlier sections of Chapter 5 of "Blown to Bits" make reference to the significance of and controversies surrounding encryption in the aftermath of September 11th. This reading may be a useful tool for further introducing the impact of cryptography on many aspects of modern life.
Ask students to review the history of their Internet browsing and calculate roughly what percentage they conduct with the assumption that it is "private." Do they have any way of being sure this is the case? Are there any websites they visit where they feel more confident in the secrecy of their traffic than others? Are they justified in this conclusion?
- Computer Science Principles: 1.2.2 (A)
- Computer Science Principles: 3.3.1 (B, F)
- Computer Science Principles: 6.3.1 (C, H, I, K)
- Computer Science Principles: 7.3.1 (G)