Big Data and Privacy - Lesson 9: Public Key Cryptography
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.
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
Private key: the complementary key to a public key that
is used to decrypt a message.
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
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
The widget in this lesson mimics the RSA encryption algorithm (with smaller
numbers and slightly easier math).
You will need two cups/lids for the "Public Key Bean Counting" demonstration
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
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
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."
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.
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?
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.
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?
B.) 1 4/13
Q9: What is 20 MOD 15?
The Public Key Cryptography Widget simulates the basic mechanics of RSA Encryption, with slightly more simple math.