Modern Cryptography | Karan Goel

Course Reflection

What I Like

I enjoy how the course uses mathematical problems such as prime factorization, the Discrete Logarithm Problem, and the Diffie–Hellman Problem—all NP problems—and applies them directly to cryptography.

It’s fascinating to see how these abstract problems are utilized in real cryptographic systems. I’ve also experimented with algorithms on small inputs, which gave me a deeper appreciation for human ingenuity, while also realizing how much we’re still teetering on the edge of the P vs NP dilemma.

What I Don’t Like

While formalization is definitely key, I feel the course focuses too much on it at times, which can detract from the overall learning experience.

Additionally, there’s a lack of detailed practical examples, which would really help in understanding how these ideas are applied in the real world.

Oh, and one more thing: when you’re giving an online exam, please check the time twice. I literally missed an hour of the exam because of it 😅
Scored a bit less because of that.

Introduction to Cryptography

Topics

Classic Cryptography
Stream Ciphers
Random Keys

📄 Lecture Slides:
Lecture 1 – Introduction

Towards Modern Cryptography

Modern Cryptography Concepts

Shannon Perfect Cipher

Encryption:
message ⊕ key → ciphertext
Decryption:
ciphertext ⊕ key → message

Perfect Secrecy

A cryptographic system achieves perfect secrecy if the probability distribution of the plaintext, given the ciphertext, is the same as the a priori distribution of the plaintext.

Formally:

Pr[M = m] = Pr[M = m

C = c]

This means that observing the ciphertext provides no additional information about the plaintext.

Definition

For every pair of messages m₀, m₁ ∈ M and every ciphertext c ∈ C:

Pr[C = c

M = m₀] = Pr[C = c

M = m₁]

Shannon’s Theorem

In a system with perfect secrecy, the number of keys must be at least equal to the number of messages.

📄 Lecture Slides:
Lecture 2 – Cryptographic Notions

Symmetric-Key Encryption & Block Ciphers

Roadmap

Classic Cipher → Caesar Cipher
One-Time Pad → Shannon
Designing Block Ciphers

Design Principles

Confusion & Diffusion

Confusion: A small change in the key causes a significant change in ciphertext
Diffusion: A small change in plaintext causes a significant change in ciphertext

This behavior is known as the avalanche effect.

Block Cipher Model

Message → Enc(key) → Ciphertext → Dec(key) → Message

Typical block sizes: 64-bit, 128-bit
Iterated ciphers use rounds (DES: 16, AES: 10)

DES (Data Encryption Standard)

Why it was developed

Need for a standard encryption scheme in the 1970s

Design Goals

High security
Compliance with Kerckhoffs’s principle
Economical
Adaptable

Technical Details

64-bit input/output
56-bit key
16-round Feistel Network

Feistel Structure

Split input into:
- L₀ (32-bit)
- R₀ (32-bit)

Each round: Lᵢ = Rᵢ₋₁ Rᵢ = Lᵢ₋₁ ⊕ F(Rᵢ₋₁, K)

S-Box

An S-box performs nonlinear substitution and is critical for cryptographic strength.

Shortcomings

Key space: 2⁵⁶ ≈ 10¹⁷ (too small today)
Vulnerable to parallel brute-force attacks

➡️ 3DES introduced as mitigation.

AES (Advanced Encryption Standard)

Secure enough for modern use
Does not use a Feistel structure
Uses a Substitution–Permutation Network

Block Cipher Security

A block cipher alone is not secure:

Preserves statistical properties of plaintext

Solution: Randomization

Choose random IV
Encrypt:

M’ = IV ⊕ M C = Enc(K, M’)

Security Definition

An encryption scheme is secure if no PPT adversary can distinguish encryptions with probability greater than:

½ + 1 / poly(λ)

Assumption: underlying block cipher behaves as a pseudorandom function (PRF).

Modes of Operation

ECB (Electronic Code Book)
- Insecure (pattern leakage)
CBC (Cipher Block Chaining)
- Uses IV and chaining
CFB (Cipher Feedback Mode)
- Cipher output feeds next block
OFB (Output Feedback Mode)
- Turns block cipher into stream cipher

📄 Lecture Slides:
Lecture 3 – Symmetric-Key Encryption