AP Computer Science Principles · Unit 5 lecture · Part 9 of 11 · 9 min

5.6 Safe computing: encryptionLocking data so only the right person can read it

Mr. Thompkins
When you send a message, it passes through routers you don't own and Wi-Fi you can't see, the packets from Unit 4. Anyone along the way could read it. Encryption is how we make sure that even if they grab it, it's gibberish to them.

Cryptography is the study of keeping information secret. Encryption is the process of encoding data to prevent unauthorized access. Decryption is the process of decoding the data. A key is the secret piece of information that controls the encoding: with the right key, decryption is easy; without it, it should be practically impossible.

?Wait, what does MOD do?
a MOD b gives the remainder when a is divided by b, from Unit 3. 27 MOD 26 = 1, because 27 ÷ 26 is 1 with remainder 1. MOD is perfect for wrapping around: after 25 (the letter Z) comes 0 (the letter A) again.

Here's the oldest example in the book, the Caesar cipher. Number the letters A = 0 to Z = 25, and shift every letter forward by a key, say 3, wrapping around at the end with MOD 26. SAFE becomes VDIH, and Y wraps around to B. To decrypt, shift back by the same key. The same key both encrypts and decrypts, which makes this symmetric encryption.

LetterSAFEY
Number (A = 0)1805424
+ 3, then MOD 26213871
Encrypted letterVDIHB
A Caesar cipher with key 3. Each letter's number goes up by 3, and MOD 26 wraps Y around to B.
1PROCEDURE shiftLetter(num, key)2{3  RETURN((num + key) MOD 26)14}5DISPLAY(shiftLetter(18, 3))6DISPLAY(shiftLetter(24, 3))7DISPLAY(shiftLetter(21, 23))2
  1. line 3 MOD 26 wraps past Z back to A
  2. line 7 shifting by 23 more is the same as shifting back 3
output › 21 1 18
The shift as a procedure. Shifting by 23 more undoes a shift of 3, because 3 + 23 = 26.

Symmetric key encryption involves one key for both encryption and decryption. Modern symmetric ciphers are far stronger than Caesar's, which has only 25 useful keys and can be cracked by trying them all. But they share its big problem: both people need the same secret key, so how do you get it to the other person without anyone seeing it? Over the internet, any message carrying the key could be intercepted.

AnaBenscrambled textlock: key Kunlock: key Ksymmetric: the same key both waysproblem: how does Ben get key Kwithout anyone else seeing it?
Symmetric encryption: one shared key. It works, but the key itself has to be delivered secretly first.

Public key encryption, also called asymmetric encryption, solves that. It pairs a public key for encryption and a private key for decryption. The receiver publishes the public key for anyone to use and keeps the matching private key secret. The sender does not need the receiver's private key to encrypt a message, but the receiver's private key is required to decrypt it. So two strangers can communicate securely without ever meeting to share a secret.

AnaBenscrambled textlock withBen's PUBLIC keyunlock withBen's PRIVATE keypublic key: a matched pair of keysBen posts his public key for anyoneonly Ben ever holds his private keyan eavesdropper with the public keystill cannot unlock it
Public key encryption. Ana locks the message with Ben's public key. Only Ben's private key unlocks it, and Ben never shares that.

One question is left: how do you know a public key really belongs to your bank, and not to an impostor? Certificate authorities issue digital certificates that validate the ownership of encryption keys used in secure communications, and they are based on a trust model: your browser trusts certain certificate authorities, so it trusts the keys they vouch for. That's part of what happens when you see https and a lock icon in the address bar. Beyond the course, as a bonus: the lock means the connection is encrypted and the certificate matches the site's name. It doesn't mean the site is honest; a phishing site can have a lock too.

?Wait, which key is the secret one?
The private key. The public key is meant to be shared, posted, even printed. Only the private key's owner ever holds it. If a question says someone "keeps the public key secret", that's a trap.
Pause and think
Ben wants to reply to Ana with a secret message. Whose public key does he use now, and who can decrypt the reply?
I thought about it. Show me
Ana's public key, because now Ana is the receiver. Only Ana's private key can decrypt it. The rule never changes: lock with the receiver's public key, unlock with the receiver's private key. When the receiver changes, the keys change.
Trace and analyze
Use the Caesar cipher (A = 0, ..., Z = 25). (a) Encrypt MEET with key 4. (b) A message encrypted with key 4 reads LSA. Decrypt it. (c) Explain why the Caesar cipher is weak, and why public key encryption avoids the problem of sharing a key.
  1. (a) M = 12, E = 4, E = 4, T = 19. Add 4: 16, 8, 8, 23. Letters: Q, I, I, X. MEET becomes QIIX.
  2. (b) L = 11, S = 18, A = 0. Subtract 4: 7, 14, and 0 − 4 = −4, which wraps around to 22. Letters: H, O, W. LSA decrypts to HOW.
    Why?
    Wrapping backward: −4 MOD 26 = 22, the same as adding 22. This is why the procedure shifts "forward by 26 minus the key" to decrypt.
  3. Check by encrypting HOW with key 4: H(7) + 4 = 11 = L, O(14) + 4 = 18 = S, W(22) + 4 = 26 MOD 26 = 0 = A. It matches.
  4. (c) Weak: there are only 25 useful keys, so an attacker can try them all in seconds and look for the one that makes sense.
  5. Public key encryption never sends a secret key at all. The receiver shares only the public key, which can lock messages but can't unlock them, so intercepting it doesn't help an eavesdropper.
    Why?
    That is the CED's point: the sender doesn't need the receiver's private key, but the receiver's private key is required to decrypt.

Answer: (a) QIIX. (b) HOW. (c) Only 25 keys, so it can be cracked by trying them all. Public key encryption shares only a public key, which cannot decrypt, so no secret ever travels.

Stuck? Get a hint
  1. Turn letters into numbers first: A = 0, B = 1, and so on.
  2. For decryption, subtract the key. If you go below 0, add 26.
  3. For (c), how many different keys could an attacker try?
Check yourself
Alice wants to send Bob a message that only Bob can read, using public key encryption. Which key should Alice use to encrypt it?
  1. AAlice's private key
  2. BAlice's public key
  3. CBob's private key
  4. DBob's public key
Show the answer

D. Alice encrypts with Bob's public key, which anyone may have. Only Bob's private key can decrypt it. Alice doesn't have Bob's private key, and a message locked with her own public key could only be opened by her.

Check yourself
What is the role of a certificate authority?
  1. AIt encrypts every message sent on the internet
  2. BIt issues digital certificates that validate who owns an encryption key
  3. CIt stores everyone's private keys in a safe place
  4. DIt blocks phishing emails before they arrive
Show the answer

B. Certificate authorities vouch that a public key really belongs to a site or organization, using a trust model. They never hold your private key; nobody else should.

Exam tip from Mr. T

Say it out loud once: "lock with their public key, unlock with their private key." Every public key question on the exam is that sentence with names filled in.

  • Encryption encodes data to prevent unauthorized access; decryption decodes it.
  • Symmetric encryption: one key encrypts and decrypts. Hard part: sharing the key secretly.
  • Public key encryption: encrypt with the receiver's public key, decrypt with the receiver's private key.
  • Certificate authorities issue digital certificates that validate key ownership, based on a trust model.