Big Data and Privacy - Lesson 9: Public Key Cryptography

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

Resources

• You will need two cups/lids for the "Public Key Bean Counting" demonstration
• Teacher Guide - Public Key Bean Counting
• Multiplication + Modulo - PDF
• Multiplication + Modulo - DOCX
• Teachers Guide - Public Key Crypto Widget Activity
• Public Key Cryptography Explanation (Optional)
• Modulo Calculator Widget
• Public Key Cryptography Widget

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.

• Video: The Internet: Encryption and Public Keys

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.

• 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 determine 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 review 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 inspecting the clock face.
• The mathematical operation modulo is the remainder after dividing two whole numbers.
• We can perceive this idea as trying to count up to some number using a clock and determining 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 perceive 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 trying to determine 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 Cryptograph to learn how the widget was built.

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 come across applies.

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?

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

Q9: What is 20 MOD 15?

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

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

Standards Alignment

• Computer Science Principles: 4.2.1 (A, B, C, D)
• Computer Science Principles: 4.2.2 (A)
• Computer Science Principles: 4.2.3 (A)
• Computer Science Principles: 4.2.4 (A, B, C)
• Computer Science Principles: 6.3.1 (H, I, L)