CYS401 · Chapter 6.1 · Annotated SlidesAsymmetric Cryptography: RSA and Hash Functions
Original
Overview

Asymmetric Cryptography: RSA and Hash Functions

Symmetric vs. asymmetric, public and private keys, trapdoor one-way functions, RSA (key generation, encryption, decryption, signatures, worked examples), and hash functions (SHA, MD, collisions) vs. MACs vs. signatures. Final 221 B and Major 181 asked about keys, signatures and hash lengths.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 37 slides
  1. 1 Encryption and Cryptography (2)
  2. 2 Agenda
  3. 3 Objectives
  4. 4 Symmetric Cryptography Versus Asymmetric Cryptography
  5. 5 Symmetric Cryptography Versus Asymmetric Cryptography
  6. 6 Asymmetric Key Cryptography / Public Key Encryption
  7. 7 Keys
  8. 8 General Idea
  9. 9 Trapdoor One-Way Function
  10. 10 RSA CRYPTOSYSTEM
  11. 11 RSA Encryption...
  12. 12 RSA Decryption...
  13. 13 RSA Continued
  14. 14 RSA: Key Generation
  15. 15 RSA Procedure
  16. 16 Basic Concepts: Extended Euclidean Algorithm
  17. 17 RSA Application
  18. 18 RSA: Some Trivial Examples
  19. 19 RSA Example 2:
  20. 20 RSA Homework Practice:
  21. 21 Encryption
  22. 22 Slide 22
  23. 23 RSA for Encryption - Encrypt using public key - Decrypt using private key
  24. 24 RSA Signature
  25. 25 RSA Security
  26. 26 Data Integrity: Hash Functions
  27. 27 Hash Functions
  28. 28 Hash Functions
  29. 29 Hash Function vs Message Authentication Code (MAC
  30. 30 Hash Functions
  31. 31 Secure Hash Algorithm (SHA)
  32. 32 Message Digest (MD)
  33. 33 Examples
  34. 34 Hash vs. MAC vs. Signature
  35. 35 Hash vs. MAC vs. Signature
  36. 36 Slide 36
  37. 37 Slide 37
Slide 1 / 37

Encryption and Cryptography (2)

Slide 1: Encryption and Cryptography (2)

Notes

  1. Tip Which key? ENCRYPT for confidentiality with the RECEIVER’s public key (receiver decrypts with their private key). SIGN with the SENDER’s private key (anyone verifies with the sender’s public key).

Slide 2 / 37

Agenda

Slide 2: Agenda
Slide 3 / 37

Objectives

Slide 3: Objectives

Notes

  1. Objectives.

Slide 4 / 37

Symmetric Cryptography Versus Asymmetric Cryptography

Slide 4: Symmetric Cryptography Versus Asymmetric Cryptography

Notes

  1. Symmetric: one shared key, fast, key distribution problem. Asymmetric: key pair, slower, solves key exchange and enables signatures.

Exam angle

PredictionQ1

Compared with symmetric encryption, asymmetric encryption is:

Slide 5 / 37

Symmetric Cryptography Versus Asymmetric Cryptography

Slide 5: Symmetric Cryptography Versus Asymmetric Cryptography

Notes

  1. Comparison table, continued.

Slide 6 / 37

Asymmetric Key Cryptography / Public Key Encryption

Slide 6: Asymmetric Key Cryptography / Public Key Encryption
Slide 7 / 37

Keys

Slide 7: Keys

Notes

  1. Tip Which key? ENCRYPT for confidentiality with the RECEIVER’s public key (receiver decrypts with their private key). SIGN with the SENDER’s private key (anyone verifies with the sender’s public key).

Exam angle

Past exam · Major 181

MCQ · how the two keys relate

Past exam · Final 221 · A

Related question: MCQ · which key decrypts the sports channel

Past exam · Major 181Q1

Which statement about an asymmetric key pair is correct?

Slide 8 / 37

General Idea

Slide 8: General Idea

Notes

  1. General idea: C = f(K_public, P); P = g(K_private, C).

Slide 9 / 37

Trapdoor One-Way Function

Slide 9: Trapdoor One-Way Function

Notes

  1. Trapdoor one-way function: easy to compute, infeasible to invert without the trapdoor (the private key).

Exam angle

PredictionQ1

The core idea behind public-key cryptography is the:

Slide 10 / 37

RSA CRYPTOSYSTEM

Slide 10: RSA CRYPTOSYSTEM
Slide 11 / 37

RSA Encryption...

Slide 11: RSA Encryption...
Slide 12 / 37

RSA Decryption...

Slide 12: RSA Decryption...
Slide 13 / 37

RSA Continued

Slide 13: RSA Continued
Slide 14 / 37

RSA: Key Generation

Slide 14: RSA: Key Generation

Notes

  1. Tip RSA in 5 lines: pick primes p, q · n = p·q · φ(n) = (p−1)(q−1) · pick e coprime with φ(n) · d = e⁻¹ mod φ(n). Encrypt C = Mᵉ mod n; decrypt M = Cᵈ mod n.

Exam angle

PredictionQ1

With p = 5, q = 11, φ(n) equals:

PredictionQ2

With p = 5, q = 11 and e = 7, the private exponent d is:

Slide 15 / 37

RSA Procedure

Slide 15: RSA Procedure
Slide 16 / 37

Basic Concepts: Extended Euclidean Algorithm

Slide 16: Basic Concepts: Extended Euclidean Algorithm
Slide 17 / 37

RSA Application

Slide 17: RSA Application

Notes

  1. RSA application.

Slide 18 / 37

RSA: Some Trivial Examples

Slide 18: RSA: Some Trivial Examples

Notes

  1. Example 1: p = 7, q = 11 → n = 77, φ = 60, e = 13, d = 37.

Slide 19 / 37

RSA Example 2:

Slide 19: RSA Example 2:

Notes

  1. Example 2: p = 3, q = 11 → n = 33, φ = 20, e = 7, d = 3.

Exam angle

PredictionQ1

RSA with p = 3, q = 11, e = 7. Find n, φ(n), d, and encrypt M = 2.

Compare with the model answer

n = 33, φ(n) = 20, d = 3 (7 × 3 = 21 ≡ 1 mod 20). C = 2⁷ mod 33 = 128 mod 33 = 29. Check: 29³ mod 33 = 2.

Slide 20 / 37

RSA Homework Practice:

Slide 20: RSA Homework Practice:
Slide 21 / 37

Encryption

Slide 21: Encryption
Slide 22 / 37

Slide 22

Slide 22: Slide 22
Slide 23 / 37

RSA for Encryption - Encrypt using public key - Decrypt using private key

Slide 23: RSA for Encryption - Encrypt using public key - Decrypt using private key

Notes

  1. Tip Which key? ENCRYPT for confidentiality with the RECEIVER’s public key (receiver decrypts with their private key). SIGN with the SENDER’s private key (anyone verifies with the sender’s public key).

Exam angle

Past exam · Major 181

MCQ · digital signature uses the sender’s private key

Past exam · Major 181Q1

A digital signature is created by encrypting the message digest with:

Slide 24 / 37

RSA Signature

Slide 24: RSA Signature
Slide 25 / 37

RSA Security

Slide 25: RSA Security

Notes

  1. RSA security rests on how hard it is to factor n; key sizes keep growing (2048+ bits).

Slide 26 / 37

Data Integrity: Hash Functions

Slide 26: Data Integrity: Hash Functions
Slide 27 / 37

Hash Functions

Slide 27: Hash Functions

Notes

  1. A hash maps any input to a fixed-length digest; one-way (you can’t get the plaintext back).

Slide 28 / 37

Hash Functions

Slide 28: Hash Functions

Notes

  1. Uses: storing passwords, integrity checks, signatures.

Exam angle

Past exam · Final 221 · B

written · two differences between hashing and encryption

PredictionQ1

How is hashing different from encryption? Give two differences. (Final 221 B)

Compare with the model answer

Hashing is one-way (no key, cannot be reversed) while encryption is reversible with a key; a hash always has a fixed-length output, while ciphertext length depends on the input.

Slide 29 / 37

Hash Function vs Message Authentication Code (MAC

Slide 29: Hash Function vs Message Authentication Code (MAC

Notes

  1. Hash (no key, integrity only) vs. MAC (shared key: integrity + authenticity).

Slide 30 / 37

Hash Functions

Slide 30: Hash Functions
Slide 31 / 37

Secure Hash Algorithm (SHA)

Slide 31: Secure Hash Algorithm (SHA)

Notes

  1. SHA (NSA, NIST standard). SHA-1: 160-bit digest. SHA-2: 224–512. SHA-3: 224, 256, 384, 512 with a different internal structure (Keccak).

Exam angle

PredictionQ1

SHA-1 produces a digest of:

Slide 32 / 37

Message Digest (MD)

Slide 32: Message Digest (MD)

Notes

  1. MD (Message Digest) family: 128-bit hashes. MD4 is older and LESS secure than MD5.

Exam angle

Past exam · Final 221 · B

MCQ · MD4 is older and less secure than MD5

PredictionQ1

MD5 produces a hash of:

Slide 33 / 37

Examples

Slide 33: Examples

Notes

  1. Try hashing text online.

Slide 34 / 37

Hash vs. MAC vs. Signature

Slide 34: Hash vs. MAC vs. Signature

Notes

  1. Hash = integrity. MAC = integrity + authentication (shared key). Signature = integrity + authentication + non-repudiation (private key).

Exam angle

PredictionQ1

Which provides non-repudiation?

Slide 35 / 37

Hash vs. MAC vs. Signature

Slide 35: Hash vs. MAC vs. Signature

Notes

  1. Comparison continued.

Slide 36 / 37

Slide 36

Slide 36: Slide 36

Notes

  1. Summary.

Slide 37 / 37

Slide 37

Slide 37: Slide 37

Notes

  1. End.

  2. Seen again Ch 6.2, slide 6: Digital certificates and PKI