Symmetric vs Asymmetric - The Big Picture
Chapter 6 builds on symmetric encryption from Chapter 5 and focuses entirely on asymmetric (public-key) cryptography - a fundamentally different approach that solves the key distribution problem.
🔐 Symmetric (Review)
- One shared secret key for encryption + decryption
- ~30,000× faster than asymmetric
- Big problem: How do you securely share the key?
- Best for: bulk data encryption
🗝️ Asymmetric (This Chapter)
- Two keys: one public (shared openly), one private (kept secret)
- Slower - but solves key distribution
- Can be used for confidentiality, authentication, or both
- Best for: key exchange, digital signatures
The Golden Rule (appears on every exam)
Encrypt → use receiver's-public-key.-Decrypt-→-use-receiver's private key. Sign → use sender's-private-key.-Verify-→-use-sender's public key.
Bob's-Public-Key
Insecure Channel
Bob's-Private-Key
Trapdoor One-Way Function
The main idea behind asymmetric-key cryptography is the concept of the trapdoor one-way function. Understanding this concept explains why RSA is secure.
↗️ One-Way Function (OWF)
A function that is:
- Easy to compute forward: given x, compute f(x) = y quickly
- Hard to invert: given y, computing f⁻¹(y) = x is computationally infeasible
🚪 The "Trapdoor"
A trapdoor makes the inverse easy if you know a secret (the private key) - but hard without it.
- Without the private key: reversing the function is practically impossible
- With the private key (the trapdoor): decryption is straightforward
- This asymmetry is what makes public-key cryptography work
Multiplying 17 × 19 = 323 is trivial. But given 323 and asked to find which two primes multiply to give it - that's much harder. Now scale that to 2048-bit numbers: finding the factors becomes computationally infeasible, securing RSA.
RSA Cryptosystem
The most common public-key algorithm. Named after its inventors: Rivest, Shamir, and Adleman. RSA computes three key factors - N, e, and d - based on prime numbers.
📤 Encryption
Uses the public key (e, N)
M = plaintext, C = ciphertext, e = public exponent, N = modulus
📥 Decryption
Uses the private key (d, N)
C = ciphertext, M = recovered plaintext, d = private exponent, N = modulus
⚠️ Note on N
N is shared between both keys - it appears in both the public key pair (N, e) and private key pair (N, d). N is public; keeping d secret keeps the private key secure.
🔑 RSA Key Generation - Step by Step
This same setup is used in the RSA Signature example below.
RSA Encryption vs RSA Signature
RSA can be used in two fundamentally different modes - one for privacy, one for authentication. The key direction flips.
🔐 RSA for Encryption (Confidentiality)
- Encrypt with receiver's public key
- Decrypt with receiver's private key
- Only the intended receiver can read the message
- Formula: C = Mᵉ mod N → M = Cᵈ mod N
Public-Key
Private-Key
✍️ RSA for Signature (Authentication)
- Sign with sender's private key
- Verify with sender's public key
- Anyone can verify; only the sender could have signed
- Formula: S = Mᵈ mod N → M = Sᵉ mod N
Private-Key
Public-Key
Q10: What is used to CREATE a digital signature?
a) Receiver's private key b) Sender's public key c) Sender's-private-key-✅- -d)-Receiver's public key
Q8: In public key cryptography, if the public key encrypts, then…
a) Only private key can encrypt b) Only public key can encrypt c) Public key encrypts and decrypts d) Only the private key can decrypt ✅
RSA Security
The security of RSA rests on the computational difficulty of factoring large numbers into their prime components. This is known as the integer factorization problem.
| Key Size | Year Factored / Status | Resources Used |
|---|---|---|
| 512-bit | 1999 - factored in 4 months | 35.7 CPU-years (SGI, Sun, Pentium II machines) |
| 640-bit (RSA-640) | 2005 - factored | 30 processors × 2.2 GHz |
| 2048-bit | Prize: $200,000 (2004) - still unfactored | Theoretically infeasible with current tech |
| 2048-bit (current practice) | ✅ Current recommended minimum | Standard for modern RSA deployments |
Key Size Matters
Old RSA keys of 512 bits are completely broken. Always use at minimum 2048-bit keys. Best known factoring algorithms take exponential time - but as computing power grows, key sizes must increase.
Hash Functions, MAC & Digital Signatures Compared
Three related but distinct mechanisms for ensuring data integrity and authenticity. Knowing the differences is critical for exams.
| Feature | Hash | MAC | Digital Signature |
|---|---|---|---|
| Keys Used | None | Shared secret key | Asymmetric key pair |
| Protects | Integrity only | Integrity + Authenticity | Integrity + Authenticity + Non-repudiation |
| Who can verify? | Anyone (public algorithm) | Only those with the key | Anyone with sender's public key |
| Non-repudiation? | ❌ No | ❌ No | ✅ Yes |
| Reversible? | ❌ One-way | ❌ One-way | ❌ One-way hash |
| Example algorithms | SHA-256, MD5 | HMAC-SHA256 | RSA, DSA, ECDSA |
# Hash Function (One-Way Encryption)
A special mathematical function that produces a fixed-length output (message digest) from any input. Once hashed, you cannot reverse it to get the original message.
- Two different inputs should never produce the same hash - if they do, it's a collision attack
- The message digest has fixed length regardless of input size
- Common uses: storing passwords, message integrity verification
🔑 MAC (Message Authentication Code)
A hash function combined with a secret key. Since hash functions are public (anyone can run them), adding a secret key proves the message came from someone who knows the key.
- Provides integrity (message wasn't tampered with)
- Provides authenticity (came from someone with the shared key)
- Does NOT provide non-repudiation - anyone with the shared key could have made it
🔒 SHA - Secure Hash Algorithm (from slides)
| Version | Year | Digest Size | Status |
|---|---|---|---|
| SHA-1 | 1993 | 160 bits | ⚠️ Vulnerable to collision attacks - deprecated |
| SHA-2 | 2002 | SHA-256 or SHA-512 | ✅ Widely used today |
| SHA-3 | 2015 | 224, 256, 384, or 512 bits | ✅ Latest NIST standard |
📋 MD - Message Digest Family
| Version | Year | Output | Notes |
|---|---|---|---|
| MD2 | 1989 | 128 bits | Vulnerable without checksum appended |
| MD4 | 1990 | 128 bits | Fast but subject to many attacks |
| MD5 | 1991 | 128 bits | More secure than MD4 but also deprecated - collision attacks known |
Collision Attack
Attacker finds two different messages that hash to the same value. This is a loss of integrity. SHA-1 and MD5 are vulnerable. Always use SHA-256 or higher for security-critical applications.
Digital Signatures - Full Process
A digital signature proves who sent the message and that the message was not tampered with. It also provides non-repudiation - the sender cannot deny signing.
🖊️ Signing Process (Sender Side)
Hash the message
Apply a hash function (SHA-256) to the plaintext → produces a fixed-length digest
Encrypt the hash
Encrypt the hash using the sender's private key → this is the digital signature
Send both
Send the original message + the signature together
✅ Verification Process (Receiver Side)
Hash the received message
Apply the same hash function to the received message → new digest
Decrypt the signature
Decrypt the received signature using the sender's public key → original digest
Compare both digests
If both hashes match → message is authentic and unmodified ✓
- Complete Sign + Encrypt Flow -
Receiver Public Key
Hash
Sender Private Key
Alice wants to send Bob a signed contract. She hashes the document with SHA-256 → gets digest "3a7f...". She encrypts this digest with her private key → creates the digital signature "9b2e...". She sends Bob: [document + signature]. Bob hashes the received document → "3a7f...". He decrypts the signature using Alice's-public-key-→-"3a7f...".-They-match-→-Alice-definitely-signed-it-and-it-wasn't tampered with.
Why Digital Signatures ≠ Just Encryption
Encryption provides confidentiality. Digital signatures provide authentication + integrity + non-repudiation. They use keys in opposite directions. You can have both simultaneously (sign then encrypt).
Digital Certificates
Before two parties exchange data using public-key cryptography, each wants to be sure the other party is authenticated. The critical question: "How do I know this public key actually belongs to who I think it does?"
Before Bob accepts a message with Alice's Digital Signature, Bob wants to be sure the public key belongs to Alice - not to someone masquerading as Alice on an open network. Without verification, a man-in-the-middle could substitute their own public key.
A trusted third party (Certification Authority / CA) authenticates that a public key belongs to a specific entity. Once Alice provides proof of identity, the CA creates a message containing Alice's name + public key - digitally signed by the CA. This signed message is the Digital Certificate.
📜 X.509 Certificate Structure
A Digital Certificate is an X.509 defined data structure with a Digital Signature. Since the data is signed by the CA, it cannot be altered without detection.
🚫 Certificate Revocation List (CRL)
The CA periodically publishes a Certificate Revocation List (CRL) - a list of certificates that have been revoked before their expiry date. Described in the X.509 standard.
- Each revoked certificate is identified by its serial number
- CRL is distributed via a known web URL or from the CA's X.500 directory entry
- Relying parties must check the CRL before trusting a certificate
Q11: Why would a CA revoke a certificate?
a) User's public key compromised b) User switched to PEM model c) User's private key has become compromised ✅ d) User moved to a new location
Public Key Infrastructure (PKI)
PKI is the complete system of technology, policies, and procedures that supports the use of public-key cryptography at scale. It answers the critical questions about trust.
Privacy
Encryption using public key technology ensures only the intended recipient can read data
Authentication
Digital certificates prove identity - you know who you're talking to
Integrity
Digital signatures ensure the message wasn't altered in transit
Non-Repudiation
The sender cannot deny having signed - the private key proves authorship
👥 PKI Players
🏛️ Certification Authority (CA)
The basis of trust in PKI. A trusted third party that:
- Enrolls and validates subscribers (users/devices)
- Issues and manages digital certificates
- Manages revocation (CRLs) and renewal of certificates
- Establishes policies and procedures
Q12: What best describes a CA?
→ An organization that issues certificates ✅
📋 Registration Authority (RA)
Works alongside the CA to handle identity verification:
- Enrolling, de-enrolling, approving/rejecting certificate attribute changes
- Validating certificate applications
- Authorizing key-pair or certificate generation requests
- Authorizing requests for key recovery
- Accepting and authorizing requests for revocation or suspension
- Physically distributing personal tokens to authorized holders
🗄️ Repository
A publicly available database that holds:
- Issued digital certificates
- Certificate Revocation Lists (CRLs)
Allows anyone to look up a certificate and check if it has been revoked - ensuring the trust infrastructure works publicly and transparently.
📜 Certificate Policy (CP)
A Certificate Policy is the basis for trust between unrelated entities. It is:
- Not a formal "contract" (but implied)
- A framework that both informs and constrains PKI implementation
- A statement of what a certificate means
- A set of rules for certificate holders
- A way of giving advice to Relying Parties
- The foundation for cross-organizational trust
Exam Tips & Tricks 🎯
Key Direction - Never Get It Wrong
Encrypt (confidentiality): receiver's-public-key.-Decrypt:-receiver's private key. Sign: sender's-private-key.-Verify:-sender's public key.
RSA Key Formula Order
Remember: n = p×q, then φ(n) = (p-1)(q-1), then choose e, then compute d. Public = {e, n}. Private = {d, n}. N is in both!
CA Revocation Reason
A CA revokes a certificate when the user's private key is compromised (not public key). If the private key leaks, the certificate can no longer be trusted.
Hash vs MAC vs Signature
Hash = integrity only. MAC = integrity + authenticity (shared key). Signature = integrity + authenticity + non-repudiation (asymmetric keys).
CA = Basis of Trust
The CA doesn't just issue certificates - it's the entire foundation of trust in PKI. Without a trusted CA, there's no way to verify a public key belongs to who you think.
RSA Security = Factoring Problem
RSA is secure because factoring large numbers is hard. Use at least 2048-bit keys. 512-bit is broken. The bigger the key, the more exponentially harder to break.
X.509 = Certificate Standard
The CRL (Certificate Revocation List) is described in the X.509 standard. Each revoked certificate is identified by its serial number in the CRL.
Trapdoor = One-Way with a Secret
Easy forward (multiply primes), hard backward (factor). But with the private key (trapdoor), the inverse (decryption) becomes easy. This asymmetry is the heart of RSA.
Quick Reference - Master Cheat Sheet
| Topic | Key Point |
|---|---|
| Asymmetric Cryptography | Two keys: public (open) + private (secret); solves key distribution |
| Trapdoor One-Way Function | Easy to compute forward; hard to reverse without the private key (trapdoor) |
| RSA Inventors | Rivest, Shamir, Adleman - most common public-key algorithm |
| RSA n | n = p × q; appears in BOTH public and private keys |
| RSA Public Key | { e, n } - share openly |
| RSA Private Key | { d, n } - keep secret |
| RSA Encrypt | C = Mᵉ mod n (using public key) |
| RSA Decrypt | M = Cᵈ mod n (using private key) |
| RSA Sign | S = Mᵈ mod n (using sender's private key) |
| RSA Verify | M = Sᵉ mod n (using sender's public key) |
| RSA Security | Based on difficulty of prime factorization; use 2048-bit minimum |
| Hash Function | One-way; fixed-length output; integrity only; no key |
| MAC | Hash + shared key; integrity + authenticity; no non-repudiation |
| Digital Signature | Encrypt hash with private key; integrity + authenticity + non-repudiation |
| SHA-1 | 160-bit; vulnerable - deprecated |
| SHA-2/3 | 256/512 bits; current standard |
| MD5 | 128-bit; deprecated - collision attacks |
| Digital Certificate | X.509 structure binding public key to identity; signed by CA |
| Certification Authority (CA) | Trusted third party; issues & manages certificates; basis of PKI trust |
| Registration Authority (RA) | Validates identities; approves certificate requests before CA issues |
| Repository | Public database holding certificates and CRLs |
| CRL | Certificate Revocation List; X.509 standard; revoked by serial number |
| CA Revocation Reason | Private key compromised (NOT public key) |
| Certificate Policy | Basis for trust between unrelated entities; defines what a cert means |
| PKI provides | Privacy + Authentication + Integrity + Non-repudiation |