Lesson 7: Simple Encryption

Widget

Overview

In this lesson, students are introduced to the need for encryption and simple techniques for breaking (or cracking) secret messages. Students 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 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.

Purpose

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 encrypt messages.As a resource, you may wish to read all of Chapter 5 of Blown to Bits. It provides social context which you may want to bring to your classroom.

Agenda

Getting Started (15 mins)

Activity (35 mins)

Wrap-up

Assessment

Extended Learning

View on Code Studio

Objectives

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

Preparation

  • Examine both versions of the widget

Links

Heads Up! Please make a copy of any documents you plan to share with students.

For the Teacher

Vocabulary

  • Caesar Cipher - a technique for encryption that shifts the alphabet by some number of characters
  • Cipher - the generic term for a technique (or algorithm) that performs encryption
  • 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.
  • Decryption - a process that reverses encryption, taking a secret message and reproducing the original plain text
  • Encryption - a process of encoding messages to keep them secret, so only "authorized" parties can read it.
  • Random Substitution Cipher - an encryption technique that maps each letter of the alphabet to a randomly chosen other letters of the alphabet.

Teaching Guide

Getting Started (15 mins)

The critical role of encryption in everyday life

Discussion Goal

Kick the day off with a very quick (5 mins) Think-Pair-Share to activate students' prior knowledge about encryption and why we want it.

Motivate the need for means of encrypting information as it travels across the Internet.

Potential areas to discuss:

  • 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

Thinking Prompt:

  • "In your daily life what things do you or other people rely on keeping a secret? Who are these secrets being kept from? How are these things kept secret?"

Share:

  • 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.

Content Corner

If necessary recall some of the facts we learned in Unit 1 while using the Internet Simulator.

  • The Internet is not inherently secure.
  • Packets traveling across the Internet move through many routers, each of which could be owned by different people or organizations.
  • So we should assume all information traveling across the Internet to be public, as if written on a postcard and sent through the mail.

Remarks

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.

Recall: As we saw with our activities on the Internet Simulator the internet is NOT secure

  • We need a way to send secret messages...

Classic Encryption - The Caesar Cipher

Background:

Many of the ideas we use to keep secrets in the digital age are far older than the Internet. The process of encoding a plain text message in some secret way is called Encryption

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.

Prompt:

  • This message was encrypted using a Caesar Cipher (an "alphabetic shift").
  • Let's see how long it takes you to decode this message (remember it's just a shifting of the alphabet):

Teaching Tip

Resist the urge to give students a tool or device to aid in cracking this message -- that's coming in the next part of the lesson! Part of the point here is that it's possible without tools. With tools it becomes trivial, as we'll see next.

If students are struggling to start here are a few strategy suggestions:

  • Find a small word and try alphabetic shifts until it's clear that it's an English word
  • Remember the letters aren't randomly substituted - the alphabet is just shifted.
  • Once you have found the amount of shift the rest comes easily.

Display or write this on the board

    serr cvmmn va gur pnsrgrevn
  • Give students about 3-5 minutes to work on cracking the message.
    • ANSWER: "free pizza in the cafeteria" - the A-Z alphabet is shifted 13 characters.

Recap:

  • With this simple encryption technique it only took a few minutes to decode a small message.
  • What if the message were longer BUT you had a computational tool to help you?!

Activity (35 mins)

Content Corner

If you'd like your students to read a little bit about Historical Cryptography and cracking ciphers, this lesson and the next one about the Vigenere cipher more or less follow the sequence presented in Blown to Bits, Chapter 5 - Reading pp. 165-173.

  • Substitution Ciphers and Frequency analysis pp. 165-169
  • Secret Keys and One-Time Pads (Vigenere Cipher) pp. 169-173

Cracking Substitution Ciphers

In this set of activities students will use two different versions of a simple widget in Code Studio to "crack" a messages encoded with substitution ciphers, including an alphabetic shift and random substitution.

Transition to Code Studio

Part 1 - Crack a Caesar Cipher

Teaching Tip

Don't rush it, but don't linger on cracking caesar ciphers. Presenting and cracking a caesar cipher should go pretty fast.

The widget is pretty self-explanatory. Let students figure out how to use it on their own.

The goal here is make points about cracking encryption with computational tools, and start to use some common terms.

You should move on to cracking random substitution relatively quickly.

The instructions for this activity are simple - there is no handout:

  • Put students in pairs/partners

Goal: Select a message encrypted with a caesar cipher and use the provided widget to "crack" it.

  • Experiment with the tool - Click things, poke around, figure out what it's doing.
  • Choose one of the messages from the pull down menu and try to crack it using the tool.
  • If you want to, enter you own message, encrypt it, and have a friend decrypt it.

Give students about 5 minutes to get into the tool and crack a few messages

  • Aided with the tool, cracking an alphabetic shift is trivial.
  • Once you've done one, it only takes a matter of seconds to do others.

Optional - Pause and Recap:

There is a page in Code studio which recaps terminology (encryption, decryption, crack, cipher, Caesar ciper) and poses the next problem.

You may optionally pause here to recap and go over terms if you like or just let students proceed (see activity part 2 below).

Part 2 - Crack a Random Substitution Cipher

After re-capping the first activity make sure students understand the following before proceeding:

  • Cracking a Caesar cipher is easy...trivial with a computational tool like the one we used.
  • The next step is to make the encryption slightly harder...

New Challenge:

  • What if 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.

  • The new version of the widget you'll see is a more sophisticated version of the encryption tool that shows you lots of different stuff.

  • But what it does is bit of a mystery! Let's check it out...

Get Cracking

Use a Discovery-based approach

REMINDER: Discovery-based introduction of tools in a nutshell:

  • Get students into to the tool without much or any introduction
  • Give students working in partners a fixed amount of time (5 minutes or so) to poke around and see if they can figure out what it does and doesn’t do – typically this might be presented as a mystery worth investigating
  • Ask the group to report what they found
  • Teacher fill in any gaps or explanations of how the tool works afterwards

This widget, like all others, are meant as a learning tool. You cannot break it so you are encouraged to let students play and investigate to figure out how the tools work.

These discovery-based methods of introducing tools have been tested in professional development and have worked well for teachers who use this curriculum. This method is effective for a few reasons, but overall students find this approach more engaging and fun, and they tend to be more receptive to, and motivated to hear, explanations of how the tool works after trying to “solve the mystery” themselves.

  • Have students click to the next bubble to see the frequency analysis version of the widget. (It should look like the screen shown below)

Goal: let students explore for 5-10 minutes to see if they can discover what the tool is showing them and allowing them to do.

The tasks laid out for students in code studio are:

  • Figure out what is going on in this new version of the tool
  • What information is being presented to you?
  • Figure out what the the tool let's you do
  • As usual: you can't break it. So click on things, poke around.
  • If you figure it out you might be able to crack a message encoded with random substitution.

  • After some exploration time regroup to clarify what the tool is and how it works.

  • If necessary point out to students that the next level in code studio (the one after the frequency analysis tool) explains a little bit about how frequency analysis works and suggests a few strategies for how to get started.

Give students about 15-20 minutes to crack one of the messages.

  • If they finish there are more to try.
  • Students can enter their own messages, do a random substitution to encrypt it, then copy/paste the encrypted version and see if a friend can crack it.
  • It is possible to get pretty proficient at cracking these messages with the tool.

Wrap-up

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.

Here are a couple of thought-provoking prompts you can use to bring closure to the lesson and as an avenue to draw out the points above. Choose one or more.

Prompts:

How much easier is it to crack a caesar cipher than a random substitution cipher? Can you put a number on it?

  • 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?

  • 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?

  • 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.

  • Definitions of cryptography, encryption, decryption, cracking/breaking an encryption, cipher, etc.

Assessment

Questions (also included in Code Studio):

  1. What is a Caesar cipher?

  2. 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.

  3. 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

Extended Learning

Teaching Tips

Students should be encouraged to chat with their partner while completing the worksheet. The questions are fairly straightforward and the point is more to use the questions as a guide to the reading, than to find all the answers as quickly as possible.

Read Blown to Bits

More Blown to Bits

  • 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?

View on Code Studio

Crack a Caesar cipher!

This tool lets you play with text and do Caesar ciphers. You can use this to either encrypt a message or decrypt it.

Do this

  • Load a Sample message from the message dropdown. This will load a message that has been encrypted with a Caesar cipher.

  • Using the buttons in the Caesar substitution tab, you can shift the alphabet forwards or backwards to try to unscramble the message.

See how long it takes you to crack the cipher! Is this a good method of encrypting secret data?

View on Code Studio

Pause and Recap

Messages encrypted with the Caesar cipher are very easy to crack, especially with a computational tool. Now that you've had a little practice cracking an alphabetic shift cipher (pretty easy, huh?) let's try something more difficult.

Recap terminology:

  • 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.
  • 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.

Click Continue to see the Next Challenge...

View on Code Studio

New Challenge: Crack a Random Substitution Cipher...with a new widget

What if 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.

Now, instead of the secret message being encoded with a simple alphabetic shift, you'll face messages encoded with random substitution.

This is much harder to crack and requires a more sophisticated tool, so...

When you click continue, you'll see a new, more sophisticated version of the encryption tool that shows you lots of different stuff.

But what it does is bit of a mystery!

Your Task:

  • Figure out what is going on in this new version of the tool
  • What information is being presented to you?
  • Figure out what the tool lets you do
  • As usual: you can't break it. So click on things, poke around.
  • If you figure it out you might be able to crack a message encoded with random substitution.

Hint

  • Did you know that E is the most common letter used in English?

Reconvene and Discuss

After some time playing with it, you should get together with someone - partner, small group, whole class - to discuss what you found and verify that you know what's going on and the various ways you can use the tool.

View on Code Studio

Break a random substitution cipher!

This version of the tool gives you more information about the encrypted text and more options for how to try out different substitutions.

Different ways to analyze text

  • Play with some of the sorting options available in the Random substitution cipher tab to get different views on the letter frequencies in the input text as well as standard English text.

Different ways to substitute

  • To substitute a letter you can drag a blue letter of the alphabet directly underneath the orange letter you want changed in the original ciphertext.

Play. Always play.

  • There are other ways to analyze and substitute characters that you can find by clicking on the buttons and trying out whatever you like.
  • Remember: you can't break it :)

See how long it takes you to crack the cipher! Is this a good method of encrypting secret data?

View on Code Studio

Cracking Substitution Ciphers

The best technique for cracking a random substitution cipher is known as frequency analysis

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.

The version of the widget on the previous page is intended to help you crack a substitution cipher through frequency analysis.

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.

The tool shows you how the frequency of letters in the encrypted text (orange) compares with frequencies from typical english (blue).

Hint: Where to start?

  1. Find the short words and "crack" them first. How many one-letter words do you know? ("a"). A very common 3-letter word is "the".
  2. Once you've done that, you have substitions for some of the most common letters. You should be able to use intuition to look at other words with these partial subsititions and make good guesses.
  3. After finding only a handful of hard-fought letters, the rest will tumble quickly.
  4. Comparing the frequencies of letters gives good insight for making sensible guesses.

Try this:

The animation below shows someone getting started. Here's what they tried

  • First sort the characters by frequency.
  • Identify a group of characters that might map to the word the.
    It's a good start!

Is random substitution good?

  • After a little practice, how long does it take you to crack a random substitution cipher?
  • Is this good or not?
View on Code Studio

Student Instructions

In what situations on the Internet do you typically want to keep information secret?

From whom do you want to keep it to be secret?

How do you think your privacy is maintained on the Internet now?

View on Code Studio

Student Instructions

What is a Caesar cipher? As part of your answer demonstrate encrypting the plaintext messages: CS IS COOL with a caesar cipher.

View on Code Studio

Teaching Tip

Answer:

  • The number of characters to shift each letter in the alphabet.

Student Instructions

View on Code Studio

Teaching Tip

Answer:

  • 26 x 25 x 24 x***x 3 x 2 x 1

Student Instructions

View on Code Studio

Student Instructions

List 3 characteristics of the ideal encryption scheme.

View on Code Studio

Student Instructions

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?

Standards Alignment

View full course alignment

CSTA K-12 Computer Science Standards (2011)

CI - Community, Global, and Ethical Impacts
  • CI.L3A:10 - Describe security and privacy issues that relate to computer networks.
CL - Collaboration
  • CL.L2:2 - Collaboratively design, develop, publish and present products (e.g., videos, podcasts, websites) using technology resources that demonstrate and communicate curriculum. concepts.
CPP - Computing Practice & Programming
  • CPP.L3A:9 - Explain the principles of security by examining encryption, cryptography, and authentication techniques.
  • CPP.L3B:5 - Deploy principles of security by implementing encryption and authentication strategies.
CT - Computational Thinking
  • CT.L3B:4 - Evaluate algorithms by their efficiency, correctness, and clarity.

Computer Science Principles

1.2 - Computing enables people to use creative development processes to create computational artifacts for creative expression or to solve a problem.
1.2.2 - Create a computational artifact using computing tools and techniques to solve a problem. [P2]
  • 1.2.2A - Computing tools and techniques can enhance the process of finding a solution to a problem.
3.3 - There are trade offs when representing information as digital data.
3.3.1 - Analyze how data representation, storage, security, and transmission of data involve computational manipulation of information. [P4]
  • 3.3.1B - Security concerns engender tradeoffs in storing and transmitting information.
  • 3.3.1F - Security and privacy concerns arise with data containing personal information.
6.3 - Cybersecurity is an important concern for the Internet and the systems built on it.
6.3.1 - Identify existing cybersecurity concerns and potential options to address these issues with the Internet and the systems built on it. [P1]
  • 6.3.1C - Implementing cybersecurity has software, hardware, and human components.
  • 6.3.1H - Cryptography is essential to many models of cybersecurity.
  • 6.3.1I - Cryptography has a mathematical foundation.
  • 6.3.1K - Symmetric encryption is a method of encryption involving one key for encryption and decryption.
7.3 - Computing has a global affect -- both beneficial and harmful -- on people and society.
7.3.1 - Analyze the beneficial and harmful effects of computing. [P4]
  • 7.3.1G - Privacy and security concerns arise in the development and use of computational systems and artifacts.

CSTA K-12 Computer Science Standards (2017)

NI - Networks & the Internet
  • 2-NI-06 - Apply multiple methods of encryption to model the secure transmission of information.
  • 3A-NI-07 - Compare various security measures, considering tradeoffs between the usability and security of a computer system.
  • 3B-NI-04 - Compare ways software developers protect devices and information from unauthorized access.