CYS401 · Annotated SlidesChapter 6.1 — Asymmetric Cryptography: RSA and Hash Functions
Chapter 6.1 · Annotated slides

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.

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up

Encryption and Cryptography (2)

CYS401 · Lecture 6.1
1
TipWhich 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).

Agenda

  • Symmetric Versus Asymmetric Cryptography
  • Asymmetric Ciphers/ Public Key Encryption
  • Asymmetric Cryptography Trapdoor One- Way Function
  • RSA Cryptosystem: Encryption, Decryption, key Generation
  • Extended Euclidean Algorithm
  • RSA Encryption vs. RSA Signature
  • RSA Security
  • Hash Function vs Message Authentication Code (MAC)
  • Hashing Algorithms: SHA & MD
  • Digital Signatures
2
Exam weight Low
  1. Symmetric vs. asymmetric → RSA → hashes.

Objectives

  • Distinguish between Symmetric and asymmetric key cryptography
  • Understand Asymmetric key cryptography.
  • Discuss the RSA cryptosystem
  • Learn about the mathematical foundations of RSA, including prime factorization and modular arithmetic.
  • Discuss the security of RSA
  • Understand Data Integrity: Applications of Hash Functions
3
Exam weight Low
  1. Objectives.

Symmetric Cryptography Versus Asymmetric Cryptography

4
Exam weight High
  1. Symmetric: one shared key, fast, key distribution problem. Asymmetric: key pair, slower, solves key exchange and enables signatures.
🎯 How this can come up · 1 question
MCQ

Compared with symmetric encryption, asymmetric encryption is:

Symmetric Cryptography Versus Asymmetric Cryptography

5
Exam weight Low
  1. Comparison table, continued.
Slide 6: Asymmetric Key Cryptography / Public Key Encryption
Exam weight Low
  1. Asymmetric crypto gives confidentiality, authentication, or both; separate keys for encryption and decryption.
★ Past exam
Slide 7: Keys
Exam weight High
  1. Two keys: the public key (shared) and the private key (secret).
TipWhich 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).

Asked in a real exam

★ Major 181 · MCQ · how the two keys relateFinal 221 · A · MCQ · which key decrypts the sports channel
🎯 How this can come up · 1 question
MCQ

Which statement about an asymmetric key pair is correct?

Slide 8: General Idea
Exam weight Low
  1. General idea: C = f(K_public, P); P = g(K_private, C).
Slide 9: Trapdoor One-Way Function
Exam weight Medium
  1. Trapdoor one-way function: easy to compute, infeasible to invert without the trapdoor (the private key).
🎯 How this can come up · 1 question
MCQ

The core idea behind public-key cryptography is the:

RSA CRYPTOSYSTEM

  • The most common public-key algorithm is called the RSA method after its inventors ( R ivest, S hamir and A dleman)
  • Aims to compute three factors N, D, and e based on prime numbers.
  • The private key here is a pair of numbers (N,d)
  • The public key is also a pair of numbers
  • Note that N is common to the private and public keys
RSA CRYPTOSYSTEM
10
Exam weight Low
  1. RSA (Rivest, Shamir, Adleman), the most common public-key algorithm, based on factoring large primes.
Slide 11: RSA Encryption...
Exam weight Low
  1. RSA encryption: C = Mᵉ mod n (public key e, n).

RSA Decryption...

  • The receiver uses the following algorithm to decrypt the message: (with private key) d mod N M = C
    • In this algorithm, M and C are plaintext and ciphertext
    • The two numbers d and N are components of the private key
12
Exam weight Low
  1. RSA decryption: M = Cᵈ mod n (private key d).
Slide 13: RSA Continued
Exam weight Low
  1. Encryption and decryption together.
Slide 14: RSA: Key Generation
Exam weight High
  1. Key generation steps.
TipRSA 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.
🎯 How this can come up · 2 questions
MCQ

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

MCQ

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

Slide 15: RSA Procedure
Exam weight Low
  1. RSA procedure figure.
Slide 16: Basic Concepts: Extended Euclidean Algorithm
Exam weight Low
  1. Extended Euclid to find d with e·d mod φ(n) = 1. Example p = 5, q = 11, e = 7 → n = 55, φ = 40, d = 23.
Slide 17: RSA Application
Exam weight Low
  1. RSA application.
Slide 18: RSA: Some Trivial Examples
Exam weight Low
  1. Example 1: p = 7, q = 11 → n = 77, φ = 60, e = 13, d = 37.

RSA Example 2:

  • Select primes: p=3 & q=11 ×
  • Compute n = pq =3 11= 33 ×
  • Compute ø(n) = (p – 1)(q-1)=2 10= 20
  • Select e such that gcd(e,20) = 1; choose e=7
  • Determine d such that de = 1 mod 20, d= 3
  • Publish public key PU={7, 33}
  • Keep secret private key PR={3, 33}

Given message M = 2

  • Encryption: C = 2 7 mod 33 = 29 3 mod 33 = 2
  • Decryption: M = 29
19
Exam weight High
  1. Example 2: p = 3, q = 11 → n = 33, φ = 20, e = 7, d = 3.
🎯 How this can come up · 1 question
Written

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

RSA Homework Practice:

Find the public key and private key of RSA for the following factors:

p = 7, q = 13 n = 7  13 = 91

 

ø(n) = 6  12 = 72

e = 5

d = 29

  • Keys: public key: (91, 5)   private key: 29
20
Exam weight Low
  1. Homework: find the key pair for given factors.

Encryption

vs.

Signature

21
Exam weight Low
  1. Encryption vs. signature.

22
Exam weight Low
  1. Encryption vs. signature, continued.
★ Past exam
Slide 23: RSA for Encryption - Encrypt using public key - Decrypt using private key
Exam weight High
  1. Encrypt with the public key, decrypt with the private key. Sign with the private key, verify with the public key.
TipWhich 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).

Asked in a real exam

★ Major 181 · MCQ · digital signature uses the sender’s private key
🎯 How this can come up · 1 question
MCQ

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

Slide 24: RSA Signature
Exam weight Low
  1. Signature example: p = 7, q = 13, n = 91, φ = 72, e = 5, d = 29.
Slide 25: RSA Security
Exam weight Low
  1. RSA security rests on how hard it is to factor n; key sizes keep growing (2048+ bits).

Data Integrity: Hash Functions

26
Slide 27: Hash Functions
Exam weight Low
  1. A hash maps any input to a fixed-length digest; one-way (you can’t get the plaintext back).
★ Past exam

Hash Functions

  • Common use of hashing algorithms
    • store computer passwords
    • to ensure message integrity
  • Hash Function produces a unique message digest, but
    • reproducible by anyone else running the same algorithm against the same data.
      • We need a secure way!
  • So you could hash a message to get a message authentication code (MAC), and the computational number of the message would show that no intermediary has modified the message
    • Hash function is public, and anyone can run it; so we need a secret key.
28
Exam weight High
  1. Uses: storing passwords, integrity checks, signatures.

Asked in a real exam

★ Final 221 · B · written · two differences between hashing and encryption
🎯 How this can come up · 1 question
Written

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

Slide 29: Hash Function vs Message Authentication Code (MAC
Exam weight Low
  1. Hash (no key, integrity only) vs. MAC (shared key: integrity + authenticity).

Hash Functions

  • A hash algorithm can be compromised with what is called a collision attack, in which an attacker finds two different messages that hash to the same value.
  • This type of attack is very difficult and requires generating a separate algorithm that attempts to find a text that will hash to the same value of a known hash
  • The consequence of a hash function that suffers from collision is a loss of integrity
30
Exam weight Low
  1. Collision attack: two different messages with the same hash.
★ Past exam
Slide 31: Secure Hash Algorithm (SHA)
Exam weight High
  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).

Asked in a real exam

★ Final 221 · B · MCQ · SHA-3 hash lengths
🎯 How this can come up · 1 question
MCQ

SHA-1 produces a digest of:

★ Past exam

Message Digest (MD)

  • Produce 128 bit hash
  • Vulnerable without the checksum appended to the message
  • It is a fast algorithm, but it is subject to more attacks than more secure algorithms such as MD5
  • Structured after MD4 but with additional security to overcome the problems in MD4
  • Therefore it is very similar to the MD4 algorithm, only slightly slower and more secure
Message Digest (MD)
32
Exam weight High
  1. MD (Message Digest) family: 128-bit hashes. MD4 is older and LESS secure than MD5.

Asked in a real exam

★ Final 221 · B · MCQ · MD4 is older and less secure than MD5
🎯 How this can come up · 1 question
MCQ

MD5 produces a hash of:

Examples

https://www.fileformat.info/tool/ha sh.htm

33
Exam weight Low
  1. Try hashing text online.
Slide 34: Hash vs. MAC vs. Signature
Exam weight High
  1. Hash = integrity. MAC = integrity + authentication (shared key). Signature = integrity + authentication + non-repudiation (private key).
🎯 How this can come up · 1 question
MCQ

Which provides non-repudiation?

Slide 35: Hash vs. MAC vs. Signature
Exam weight Low
  1. Comparison continued.

36
Exam weight Low
  1. Summary.