Overview

This is a big multi-part lesson that introduces the concept of public key cryptography which is an answer to the crucial question: How can two people send encrypted messages back and forth over insecure channels (the Internet) without meeting ahead of time to agree on a secret key? In a nutshell, there are two main principles we want students to understand: 1) The mechanics of communication with public key cryptography. 2) The basic mathematical principles that make it possible. The lesson gets at these two core ideas through a deliberate chain of thought experiments, demonstrations, activities, and widgets. All parts are building blocks that lead to deeper understanding of how it works.

Public Key Cryptography allows two people who have never met, and who haven't agreed on a shared key, to send encrypted messages that only they can read, using only insecure channels. Arithmetic can be used to encrypt a message which only an intended recipient can decrypt and read. Using a public key and private key, messages can be encrypted and transmitted securely even if the message itself and the method used to encrypt it are both public. The modulo operation (or "clock arithmetic" as we call it in the lesson) is a real one-way function that is used for asymmetric encryption. The modulo operation gives the remainder.

Vocabulary

Goals

Students will be able to:

Purpose

This is a fairly hefty lesson because the underlying ideas are subtly quite sophisticated. It's worth noting that much of the material here - all but the highest level takeaways - are beyond the scope of what's covered on the AP exam. Students need to know the basic public key encryption process, and what asymmetric encryption is. For programming, they need to know how the modulo operation works.

Our purpose here is to reveal some of the magic that happens every day on the Internet to enable secure transactions. To many, the fact that encrypted messages can be sent between parties who have never met before is both taken for granted and opaque. Our belief is that understanding how it works with some depth - getting to experiment with the mathematical principles that make asymmetric keys possible, and the resulting encryption hard to crack - is deeply satisfying.

The widget in this lesson mimics the RSA encryption algorithm (with smaller numbers and slightly easier math).

Resources

Getting Started

Ask the students to get into a group and answer the following

How can two people send encrypted messages to each other if they can't communicate, or agree on an encryption key ahead of time, and the only way they have to communicate is over the Internet?

Introduce public key cryptography through the following video. The public key cryptography portion starts around the 4:11 mark.

Activity 1

Ask the students to think about the following question: How can two people send encrypted messages to each other if they can't communicate, or agree on an encryption key ahead of time, and the only way they have to communicate is over the Internet? Assume that an adversary is always secretly eavesdropping on their conversation too. With a partner (if possible), come up with a strategy that they could use to send encrypted messages.

Step 1: Public Key Bean Counting (aka The "Cups & Beans" Activity)

For this activity you will need two cups/lids (for Alice and Bob) and some beans. For more information, the teacher can refer to the "Teacher Guide - Public Key Bean Counting" resource.

Okay, so that's one step. We now have a clearer idea of the public key encryption process. If we can keep extending this we'll have a solution to the problem of how two people can encrypt messages without meeting ahead of time. Next we need to see how actual data is encrypted rather than beans in cups. To learn that, we'll need to string a few more ideas together.

Step 2: Modulo - The operation behind public key encryption

The next idea we need to add is an important mathematical operation called "modulo." The cups and beans demonstration showed us how the mechanics of public key cryptography works. It's a big deal that asymmetric encryption allows for two parties to send secret messages to each other over public channels without having to agree on a secret encryption key ahead of time. Now let's look at the mathematical principles that allow private and public keys to work.

Step 3: The Modulo Calculator Widget and Multiplication + Modulo

This is a more hands on practice with the modulo operation. Ask the students to divide into groups of 2 or 3. Open the "Modulo Calculator Widget" and choose different input numbers (x) and difference modulo sizes (y).

The goal of this activity is to show that the modulo size can change and that the input numbers will "wrap around."

Discussion

After the students have went through the activity guide with the Modulo Calculator Widget, discuss the following with the students:

Why is it hard to guess which numbers multiplied together produce the result?

Some of the responses that can clarify the concept for them include:

Step 4: Use the Public Key Cryptography Widget Activity

Review the "Teachers Guide - Public Key Crypto Widget Activity" resource. Put students into groups to play as Alice and Bob (they can ignore the steps for Eve at this stage). They should play using "Hotseat" rules, where they switch off who can see the computer screen according to the instructions.

The students will have to, (1) choose a character: Alice or Bob, and (2) follow the instructions prompted by the widget.

After the activities with Alice and Bob, we introduce Eve, who is trying to decrypt the messages. The students will have to (1) choose a character: Alice, Bob, or Eve, and (2) follow the instructions on the widget. Have students play each role at least once.

As an option, the students can go over the "Public Key Cryptography Explanation" resource to see how Code.org's public key cryptography widget was built (the Quorum widget they just used is a simplified version of Code.org's).

After the activity, the students can discuss the following questions:

Wrap Up

Public Key Encryption was (and is) considered a major breakthrough in computer science. The following points should be used in a discussion with students.

The students had just spent a lot of time learning about Public Key Cryptography through a bunch of different analogies, tools and activities. And what they've been exposed to mimics the real thing pretty closely. But what are the essential elements? Ask the students to list out what you think are the most important or crucial elements of Public Key Cryptography that they've learned. Ask the students to share the list.

Here are some important ideas to remember from this lesson:

Optional: Make a table applying terminology to the various analogies we saw

Use the following table as a guide to fill in all of the terms we've learned around public key encryption and how each analogy we've seen applies.

Public Keys

Assessment

Q1: In symmetric encryption, the same key is used to encrypt and decrypt a message. In asymmetric encryption different keys are used to encrypt and decrypt. Give at least one reason (more are welcome) why asymmetric encryption is useful.

Q2: In the cups and beans activity, what is the public key? What is the private key? What is the unencrypted and encrypted message?

Q3: What are some other examples of one-way functions? Can you think of a one-way function in real life?

Q4: Using your name and the name of a friend, describe the process of sending your friend a message using public key cryptography. Your explanation should include the terms: Public Key, Private Key, Encrypt(ion), Decrypt(ion).

Q5: Explain what the modulo operation does. You may use the analogy of a clock in your answer if you like.

Q6: Why is modulo a one-way function?

Q7: Describe to a person who knows nothing about encryption why public key encryption is hard to crack.

Q8: What is 13 MOD 17?

Q9: What is 20 MOD 15?

Extended Learning

The Public Key Cryptography Widget simulates the basic mechanics of RSA Encryption, with slightly more simple math.

The students can learn more about the RSA Encryption through RSA Encryption Examples.

Standards Alignment