## 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

• Modulo (or "mod"): the name of the mathematical operation. Modulo gives the remainder from dividing two numbers. For example: 17 MOD 13 is 4.
• Asymmetric encryption: a type of cryptographic based on algorithms that require two keys -- one of which is secret (or private) and one of which is public (freely known to others).
• Public key: a value that can be used to encrypt a message. However, only when combined with a mathematically-related private key, can the message be decrypted.
• Private key: the complementary key to a public key that is used to decrypt a message.

## Goals

Students will be able to:

• Explain what the modulo operation does and how it operates as a "one-way" function
• Follow an asymmetric encryption algorithm to encrypt a numerical message using the Public Key Cryptography widget
• Explain the difference between symmetric and asymmetric encryption
• Describe the basic process of encrypting data using public key encryption
• Explain the benefits of public key cryptography

## 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).

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

• Ask the students to assume that an adversary is always secretly eavesdropping on their conversation too.
• With a partner, have students come up with a strategy they could use to send encrypted messages.

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.

• Alice chooses a private key (some number of beans)
• Alice makes a "public key cup" by placing beans in a clear cup and sealing it
• Pass the cup to Bob over the "Internet"
• Bob grabs the "public key cup" and adds a secret number (of beans) to it
• Pass the cup back to Alice over "The Internet"
• Alice opens cup and subtract the number of beans she added originally
• What's left is Bob's secret number
• Alice and Bob now have a private and public key that can be used to encrypt their messages!

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.

• The kind of "Clock Arithmetic" discussed (officially known as "modular arithmetic") is a one-way function because you can't tell what the input number was, just by looking at the clock face.
• The mathematical operation modulo is the remainder after dividing two whole numbers.
• We can visualize this idea as trying to count up to some number using a clock and seeing where the hand ends up.
• For example: if you're trying to count up to 43 on a normal clock with 12 numbers:
• You are doing: 43 MOD 12.
• The result of 43 MOD 12 is: 7. Reason: 43 / 12 = 3 remainder 7
• The clock helps you visualize in your mind another way to think about division - how many times can I count up by 12s until I get to 43 without going over? 12... 24... 36. Then how much do I need to add to 36 to make it 43? Answer: 7 - that's the remainder.

#### 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:

• You cannot solve it like an equation in math class. If you are looking for A * ___ MOD 13 = 1 for example, what you are really trying to find is a number that you could multiply by A that comes out to one of a list of infinite values: 1, 14, 27, 40, 53, ... and so on.
• Numbers kind of jump all over the place.
• You kind of have to just guess randomly, or at least systematically try every number.

#### 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:

• What made the encryption harder/easier for Eve to crack?
• The widget right now only lets you send one secret number at a time. Furthermore, it's kind of slow - it requires multiple trips over the "Internet" to send one message. What's the fastest way you could use this tool (or any public key encryption) to send a secure text message?

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

• Public key cryptography is what makes secure transactions on the Internet possible.
• In the history of the Internet, the creation of public key cryptography is one of the most significant innovations; without it we could not do much of what we take for granted today -- we couldn't buy things, communicate without being spied on, use banks, or keep our own conduct on the Internet secret or private.
• Until asymmetric encryption was invented, the only way to ensure secure transactions on the Internet was to establish a shared private key, or to use a third party to guarantee security.
• The implications of this are huge. It means any person can send any other person a secret message transmitting information over insecure channels!

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:

• Public Key Cryptography is a form of asymmetric encryption
• For Bob to send Alice a message, Bob must obtain Alice's public key
• The underlying mathematics ensure that both the public key and a message encrypted with the public key are computationally hard to crack while making it easy to decrypt with a private key
• It is strong because the method of encryption is publicly known, but keys are never exchanged.
• A public and private key are mathematically related so that decrypting is easy
• The modulo operation acts as a one-way function to obscure inputs that are very large numbers
• No one owns it - it's a public standard

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

• A.) 0
• B.) 1 4/13
• C.) 4
• D.) 13
• E.) 17

• A.) 0
• B.) 1.5
• C.) 5
• D.) 15
• E.) 20

## Extended Learning

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