Public key encryption (asymmetric encryption) uses two different keys: one to encrypt, another to decrypt. This solves the fundamental problem of symmetric encryption, which is that both parties need to share the same secret key somehow. The modulus (MOD) operator, which calculates remainders, is the mathematical foundation that makes generating secure keys possible.
Difficulty: Beginner to Intermediate | Prerequisites: Understanding of symmetric encryption, the Caesar Cipher, and the algorithm-vs-key distinction from the first part of this lesson. Basic comfort with division and remainders.
The first half of this lesson established that symmetric ciphers (Caesar, random substitution) all share a weakness: the same key encrypts and decrypts, so both sender and receiver need the key. Sharing a secret key over an insecure channel defeats the purpose.
Public key encryption solves this. It is considered one of the most important breakthroughs in computer science and is the reason secure internet transactions exist. This section also introduces modulus (remainder) arithmetic, which underpins the maths that generates encryption keys. You will not need to perform these calculations on the AP exam, but you do need to understand the concept.
Public Key Encryption (aka asymmetric encryption, public key cryptography)
An encryption system that uses two mathematically related but different keys: a public key for encryption and a private key for decryption. Think of it as a postbox: anyone can drop a letter in through the slot (encrypt with the public key), but only the owner with the postbox key can open it and read the letters (decrypt with the private key).
Public Key
The key that is shared openly. Anyone can use it to encrypt a message intended for the key's owner. Knowing the public key does not let you decrypt messages.
Private Key
The key that is kept secret by its owner. It is the only key that can decrypt messages encrypted with the matching public key. This key must never be shared.
Asymmetric Encryption
Any encryption scheme where the encryption key and the decryption key are different. Public key encryption is the primary example. In simple terms, the key that locks the box is different from the key that opens it.
Modulus / Modulo (MOD)
A mathematical operation that returns the remainder after division. For example, 7 MOD 3 = 1, because 7 divided by 3 gives a quotient of 2 with a remainder of 1. In simple terms, it answers the question: "what is left over?"
One-Way Function
A mathematical operation that is easy to perform in one direction but extremely difficult to reverse. The modulus operator is a one-way function: given 7 MOD 3 = 1, there are infinitely many values of x where x MOD 3 = 1 (4, 7, 10, 13, 16 ...), making it practically impossible to work backwards to a single answer.
The Caesar Cipher and random substitution cipher are both symmetric: the same key encrypts and decrypts. This creates a practical problem. If Alice wants to send Bob a secret message, she needs to get the key to Bob first, but if she sends the key over the same insecure channel, an attacker can intercept it and read everything. Public key encryption was invented to solve exactly this problem.
In asymmetric encryption, every person has two keys that are mathematically linked:
A public key, which they share with everyone
A private key, which they keep secret
The process works like this:
Bob publishes his public key openly
Alice uses Bob's public key to encrypt her message
Only Bob's private key can decrypt the message
Even Alice cannot decrypt it once she has encrypted it with Bob's public key
The sender does not need the receiver's private key. The receiver's private key never leaves the receiver's possession. This is the breakthrough: two people who have never met and have no shared secret can communicate securely.
The modulus (MOD) operation calculates the remainder of a division. This is the mathematical foundation that makes secure key generation possible.
7 / 3 = 2 remainder 1, so 7 MOD 3 = 1
10 / 3 = 3 remainder 1, so 10 MOD 3 = 1
13 / 3 = 4 remainder 1, so 13 MOD 3 = 1
All values of x where x MOD 3 = 1 follow the pattern: (n x 3) + 1, for any positive integer n. That gives 4, 7, 10, 13, 16, 19, and so on, infinitely.
The critical property of MOD for encryption is that it is easy to compute in one direction but impossible to reverse to a single answer. If someone tells you that x MOD 3 = 1, you cannot determine x, because there are infinitely many solutions.
Public key encryption exploits this property using very large prime numbers and complex modular arithmetic. The details are beyond the scope of this course, but the core idea is: the maths that links the public and private keys is easy to perform one way (encrypting) and computationally impractical to reverse (trying to derive the private key from the public key).
The MOD operator
x MOD n = remainder when x is divided by n
Generating values with a given remainder
All values of x where x MOD n = r follow the pattern:
x = (k x n) + r, for k = 0, 1, 2, 3 ...
Example: x MOD 3 = 1
k | Calculation | x |
|---|---|---|
0 | (0 x 3) + 1 | 1 |
1 | (1 x 3) + 1 | 4 |
2 | (2 x 3) + 1 | 7 |
3 | (3 x 3) + 1 | 10 |
4 | (4 x 3) + 1 | 13 |
Public key encryption is the backbone of secure internet communication. Every time you visit a website with HTTPS (the padlock in the address bar), your browser and the server use public key cryptography to establish a secure connection. Online banking, e-commerce checkouts, encrypted messaging apps, and email encryption all depend on it.
The modulus operator itself appears across computing: it is used in hashing algorithms, clock arithmetic, checksums for error detection, and load balancing across servers.
Students often think the public key can also decrypt messages. It cannot. The public key encrypts only. Decryption requires the private key. Even the person who encrypted the message cannot decrypt it without the private key.
A frequent confusion is thinking that "asymmetric" means "unrelated." The public and private keys are mathematically linked. "Asymmetric" means they are different from each other, not that they are unconnected.
Some students believe that modulus math is the same as division. It is not. Division gives you a quotient (how many times the divisor fits). Modulus gives you the remainder (what is left over).
Students sometimes assume that because the modulus operation is simple to understand, the encryption built on it must also be simple to break. The security comes from using extremely large numbers and prime-number relationships that make the reverse computation take an impractical amount of time, even for powerful computers.
⚠️ You need to understand the concepts of modulo, public vs private keys, and public key encryption in general. The lesson explicitly says you do NOT have to perform encryption calculations on the AP test.
⚠️ Know that encryption is based on maths, not magic. This is stated directly in the source material as something you must understand.
⚠️ Be able to explain why the modulus operator is considered a one-way function: given the output and the divisor, there are infinitely many inputs that produce the same result.
⚠️ Understand the practical implication of public key encryption: any person can send any other person a secret message over an insecure channel, without needing to share a secret key beforehand.
⚠️ Know the roles of the public key (encrypt, shared openly) and the private key (decrypt, kept secret). Exam questions may present a scenario and ask which key is used at each step.
True or False: In public key encryption, the same key is used to encrypt and decrypt.
False. The public key encrypts, the private key decrypts. They are different.
Fill in the blank: 15 MOD 4 = ______.
3 (because 15 / 4 = 3 remainder 3).
True or False: The modulus operator is considered a one-way function because there are infinitely many inputs that produce the same output.
True.
Fill in the blank: In public key encryption, the key that is shared openly is called the ______ key.
Public.
True or False: You need to perform modular arithmetic calculations on the AP exam.
False. You need to understand the concept, not perform the calculations.
Q: Alice wants to send Bob a secret message using public key encryption. Which key does she use to encrypt the message, and which key does Bob use to decrypt it?
A: Alice encrypts with Bob's public key. Bob decrypts with his own private key. Alice does not need Bob's private key at any point.
Q: Why is the modulus operator described as a "one-way" operation?
A: Because given a result like x MOD 3 = 1, there are infinitely many values of x that satisfy it (1, 4, 7, 10, 13 ...). You cannot work backwards from the result to a single original value.
Q: What is 23 MOD 5?
A: 3. Because 23 / 5 = 4 remainder 3.
Q: Why is public key encryption considered a major breakthrough in computer science?
A: It allows two parties to communicate securely without needing to share a secret key in advance. Before public key encryption, both parties had to somehow exchange a key securely, which was itself a difficult problem. Public key encryption means anyone can send a secret message to anyone else, even over insecure channels.
Q: Can a message encrypted with a public key be decrypted using that same public key?
A: No. A message encrypted with a public key can only be decrypted with the corresponding private key. This is the defining feature of asymmetric encryption.
This material builds directly on the symmetric encryption concepts from the first half of the lesson. The algorithm-vs-key distinction carries forward: in public key encryption, the algorithm is the underlying mathematical process (involving modular arithmetic with large primes), and the keys are the specific public and private values generated by that process.
Public key encryption connects to broader AP CSP topics around internet security, including HTTPS, SSL/TLS, digital certificates, and secure data transmission. It also ties into the data privacy themes from earlier in Unit 10: encryption is the technical tool that makes privacy protections enforceable.
Public key encryption, asymmetric encryption, public key cryptography, private key, public key, key pair, modulus, modulo, MOD operator, remainder, one-way function, prime numbers, RSA, HTTPS, SSL, TLS, secure communication, digital certificates, internet security, data protection, computationally hard, AP Computer Science Principles, CSP, Unit 10 Lesson 9