Information Security Systems (Cryptography)

Information Security Systems (Cryptography)

Objective:

To provide students with a thorough understanding of cryptographic techniques used to secure digital information, covering both theoretical foundations and practical applications.

Scope:

• Classical and modern encryption algorithms
• Symmetric and Asymmetric key cryptography
• Cryptographic hash functions and digital signatures
• Key management, PKI, SSL/TLS, HTTPS, SSH
• Cryptanalysis and attack models

Course Outcomes (COs):

Why Study Cryptography?

• Protects data in banking, healthcare, e-commerce
• Foundation of Internet security (HTTPS, VPN, SSH)
• Prevents unauthorized access, tampering, fraud
• Legal and compliance requirements (GDPR, PCI-DSS)

Cryptography is the science of securing communication by transforming readable data into an unreadable form and back, using mathematical algorithms and keys.

The word comes from Greek: kryptos (hidden) + graphein (writing).

Core Terminology:

Mathematical Notation:

Encryption:  C = E(K, P)  or  C = Ek(P)
Decryption:  P = D(K, C)  or  P = Dk(C)

Basic Model:

[Plaintext] → Encryption(Key) → [Ciphertext]
                                      ↓
[Plaintext] ← Decryption(Key) ← [Ciphertext]

Cryptography vs Security:

• Cryptography = ONE tool for achieving security
• Information Security = broader (policies, access control, audit)

Three Related Disciplines:

1. Cryptography (Crypto + graphy)

• Art/science of designing secure communication systems
• Focus: Creating algorithms to protect data
• Goal: Ensure confidentiality, integrity, authenticity
• Who does it: Cryptographers, security engineers

2. Cryptanalysis (Crypto + analysis)

• Art/science of breaking cryptographic systems
• Focus: Finding weaknesses in ciphers
• Goal: Recover plaintext or key without authorization
• Techniques: Brute force, differential analysis, side-channel
• Who does it: Security researchers, hackers, intelligence agencies

3. Cryptology = Cryptography + Cryptanalysis

• The complete field of secret communications
• Both creation AND breaking of ciphers

Types of Cryptanalysis Attacks:

Kerckhoffs' Principle:

> A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.

This means: security must rely on the KEY, not the algorithm's secrecy.

Importance of Cryptography:

1. Confidentiality

Ensures only authorized parties can read the data.

Example: WhatsApp end-to-end encryption

2. Data Integrity

Ensures data is not altered in transit.

Example: Hash functions in file downloads (MD5/SHA checksums)

3. Authentication

Verifies the identity of communicating parties.

Example: Digital certificates, login passwords

4. Non-repudiation

Prevents sender from denying having sent a message.

Example: Digital signatures on contracts

5. Access Control

Restricts resource access to authorized users.

Example: Encrypted file systems

Real-World Applications:

Without Cryptography:

• Passwords sent in plain text
• Credit card numbers stolen easily
• Government secrets exposed
• No secure e-commerce possible

CIA Triad is the foundational model of Information Security with three core goals:

1. Confidentiality (C)

• Ensures information is accessible only to authorized individuals
• Prevents unauthorized disclosure
• Mechanisms: Encryption, Access control, Authentication
• Threat: Eavesdropping, data breaches
• Example: Only the recipient can read an encrypted email

2. Integrity (I)

• Ensures data is accurate, complete and unmodified
• Prevents unauthorized modification
• Mechanisms: Hash functions, MACs, Digital signatures, Checksums
• Threat: Man-in-the-middle, data tampering
• Example: Downloaded file hash matches original

3. Availability (A)

• Ensures systems and data are accessible when needed
• Prevents denial of service
• Mechanisms: Redundancy, backups, DDoS protection
• Threat: DoS/DDoS attacks, hardware failure
• Example: Bank website stays online 24/7

Extended Goals (CIAAN):

Relationship with Cryptography:

Confidentiality → Encryption (AES, RSA)
Integrity       → Hash functions (SHA), MACs
Authentication  → Digital signatures, certificates
Non-repudiation → Digital signatures (RSA+SHA)

Mnemonic: CIA = Confidentiality, Integrity, Availability

Three Major Types of Cryptography:

1. Symmetric Key Cryptography (Secret Key)

• Same key used for encryption and decryption
• Fast, efficient for large data
• Key distribution problem: how to share key securely?
• Examples: DES, 3DES, AES, RC4, Blowfish

Alice → [Encrypt with K] → Ciphertext → [Decrypt with K] → Bob
           (shared secret key K)

2. Asymmetric Key Cryptography (Public Key)

• Two keys: Public Key (shared) + Private Key (secret)
• Public key encrypts, private key decrypts
• Slow but solves key distribution problem
• Examples: RSA, Diffie-Hellman, ECC, ElGamal

Alice → [Encrypt with Bob's Public Key] → Ciphertext
       → [Decrypt with Bob's Private Key] → Bob

3. Hash Functions (One-way)

• No key; maps input of any size → fixed-size digest
• One-way: cannot reverse hash to get original
• Used for integrity verification, passwords
• Examples: MD5 (128-bit), SHA-1 (160-bit), SHA-256

Message → [Hash Function] → Fixed-size Digest

Comparison Table:

Security Attack: Any action that compromises the security of information owned by an organization.

Two Categories of Attacks:

1. Passive Attacks

• Attacker only LISTENS/OBSERVES communication
• Does NOT modify data
• Hard to detect (no visible change)
• Goal: Gain information

Types:

• Eavesdropping (Interception): Wiretapping network traffic
• Traffic Analysis: Analyzing patterns (who, when, how often) even if encrypted

Defense: Encryption (makes intercepted data unreadable)

2. Active Attacks

• Attacker MODIFIES, CREATES or DISRUPTS data
• Easier to detect than passive
• Goal: Alter data, impersonate, disrupt service

Types:

• Masquerade: Attacker pretends to be another entity
• Replay: Captures and retransmits valid data
• Modification: Alters legitimate messages
• Denial of Service (DoS): Floods system to prevent access

Comparison:

X.800 Standard Classification:

• Interruption → Availability attack
• Interception → Confidentiality attack
• Modification → Integrity attack
• Fabrication → Authenticity attack

OSI Security Architecture (X.800) defines security services that can be provided by network layers.

X.800 Security Services:

1. Authentication

• Assurance that communicating entity is who it claims to be
• Two types:
• Peer Entity Authentication: Confirms identity in a connection
• Data Origin Authentication: Confirms source of a data unit

2. Access Control

• Prevents unauthorized use of a resource
• Protects against unauthorized access to services/data

3. Data Confidentiality

• Protection of data from unauthorized disclosure
• Types: Connection, Connectionless, Selective field, Traffic flow

4. Data Integrity

• Assurance that received data is exactly what was sent
• Types: With/without recovery, Selective field, Connection/connectionless

5. Non-Repudiation

• Prevents sender or receiver from denying a transmitted message
• Proof of origin + Proof of delivery

6. Availability Service

• Ensures system/resource is accessible and usable on demand
• Protection against DoS attacks

Security Mechanisms (X.800):

Mnemonic for services: A-A-C-I-N-A

(Authentication, Access Control, Confidentiality, Integrity, Non-repudiation, Availability)

Substitution Ciphers replace each letter with another letter/symbol.

1. Caesar Cipher (Shift Cipher)

• Shift each letter by a fixed amount k
• Formula: C = (P + k) mod 26 (encrypt)

P = (C - k) mod 26 (decrypt)

• Key space: only 25 possible keys → easily broken

Example (k=3):

Plaintext:  A B C D E F ... X Y Z
Ciphertext: D E F G H I ... A B C

HELLO → KHOOR

2. Monoalphabetic Cipher

• Each letter maps to a FIXED but ARBITRARY other letter
• Key = permutation of 26 letters → 26! possible keys
• Still vulnerable to frequency analysis

Example key mapping:

Plain:  a b c d e f g h i j k l m
Cipher: Q W E R T Y U I O P A S D

Plain:  n o p q r s t u v w x y z
Cipher: F G H J K L Z X C V B N M

Weakness: English letter frequencies give it away

• 'e' most frequent → maps to most frequent ciphertext letter

3. Vigenere Cipher (Polyalphabetic)

• Uses a KEYWORD; applies different shifts for each position
• Formula: Cᵢ = (Pᵢ + Kᵢ) mod 26

Example (Key = KEY):

Plaintext:  H  E  L  L  O
Key:        K  E  Y  K  E
Key values: 10 4  24 10 4
Cipher:     R  I  J  V  S

HELLO → RIJVS

Strength: Defeats simple frequency analysis

Weakness: Kasiski test, Index of Coincidence can break it

Playfair Cipher

• Encrypts PAIRS of letters (bigrams) using a 5×5 key matrix
• First practical digraph substitution cipher

Key Matrix Construction:

• 1. Fill matrix with keyword (no duplicates, I=J)
• 2. Fill remaining letters in order

Example (Key = MONARCHY):

M O N A R
C H Y B D
E F G I K
L P Q S T
U V W X Z

Encryption Rules:

• 1. Same row: Replace each letter with letter to its RIGHT (wrap)
• 2. Same column: Replace each letter with letter BELOW (wrap)
• 3. Rectangle: Each letter replaced by letter in same row, other letter's column

Preparation: Split into pairs; insert 'X' between double letters; pad with 'X' if odd

Example:

AR → RM  (rectangle rule)
HS → BL  (rectangle rule)

Security: 26²=676 possible bigrams; defeats single-letter frequency analysis

---

Hill Cipher

• Based on LINEAR ALGEBRA (matrix multiplication)
• Encrypts n letters at a time using n×n key matrix K
• Formula: C = K × P (mod 26)
• Decrypt: P = K⁻¹ × C (mod 26) where K⁻¹ = modular inverse

Example (2×2 key matrix):

K = [3  3]    Plaintext = [P] = [H=7]
    [2  5]                [A]   [I=8]

C = K×P mod 26 = [3×7+3×8] mod 26 = [45] mod 26 = [19=T]
                  [2×7+5×8]           [54]           [2 =C]

Strength: Obscures letter frequencies completely

Weakness: Vulnerable to known-plaintext attack

Transposition Ciphers

Rearrange (permute) letters without substituting them.

Same letters, different positions.

1. Rail Fence Cipher

Write message in zigzag pattern across 'rails', then read row by row:

Plaintext: HELLOWORLD (2 rails)
Rail 1: H . L . O . O . L .
Rail 2: . E . L . W . R . D
Cipher:  HLOOL + ELWRD = HLOOLELWRD

2. Columnar Transposition

Write message in rows, reorder columns by key:

Key:       3 1 4 2
Plaintext: A T T A
           C K T H
           E F E N
Read cols by key order (1,2,3,4): TKF, AHN, ATE, TEE
Cipher: TKFAHNATEETE

Cryptanalysis = Breaking ciphers without the key.

Techniques:

• Brute Force: Try all possible keys
• Frequency Analysis: Count letter/bigram frequencies
• Kasiski Test: Find repeated sequences (breaks Vigenere)
• Index of Coincidence: Measures text 'randomness'

---

Stream Cipher vs Block Cipher:

Stream Cipher: Cᵢ = Pᵢ XOR Kᵢ (bit by bit)

Block Cipher: Encrypts n-bit blocks with substitution + permutation network

OSI X.800 Security Architecture defines 6 security services:

1. Authentication

Verifies identity of communicating entity.

• Peer entity auth: confirms identity during connection
• Data origin auth: confirms source of a data unit

2. Access Control

Prevents unauthorized use of resources.

Mechanisms: ACLs, capability tables, passwords

3. Data Confidentiality

Protects data from unauthorized disclosure.

• Connection confidentiality (entire connection)
• Traffic-flow confidentiality (hide routing patterns)

4. Data Integrity

Ensures data not modified in transit.

• With/without recovery from detected modification

5. Non-repudiation

Prevents denial of involvement:

• Proof of origin: sender cannot deny sending
• Proof of delivery: receiver cannot deny receiving

6. Availability

System accessible and usable on demand.

Protects against DoS attacks.

X.800 Security Mechanisms:

Mnemonic for services: All Agencies Can Investigate Network Attacks

(Authentication, Access Control, Confidentiality, Integrity, Non-repudiation, Availability)

Substitution Ciphers replace plaintext letters with other letters/symbols.

1. Caesar Cipher (k=3)

C = (P + k) mod 26    [encrypt]
P = (C - k) mod 26    [decrypt]

Plaintext:  HELLO
Ciphertext: KHOOR  (each letter +3)

Key space: only 25 keys → brute-force trivial

2. Monoalphabetic Cipher

Each letter maps to a fixed arbitrary other letter:

Plain:  a b c d e f g h i j k l m n o p q r s t u v w x y z
Cipher: Q W E R T Y U I O P A S D F G H J K L Z X C V B N M

Key space: 26! ≈ 4×10²⁶ — but broken by frequency analysis.

In English: e(12.7%), t(9.1%), a(8.2%), o(7.5%) are most frequent.

3. Playfair Cipher (Digraph)

• Encrypts letter PAIRS using 5×5 key matrix
• Fill matrix with keyword, then remaining alphabet (I=J)
• Three rules: same row → shift right; same column → shift down; rectangle → swap corners

Key = MONARCHY:
M O N A R
C H Y B D
E F G I K
L P Q S T
U V W X Z

Example: AR → RM (rectangle rule)

4. Vigenere Cipher (Polyalphabetic)

Cᵢ = (Pᵢ + Kᵢ) mod 26

Plaintext:  H  E  L  L  O  W  O  R  L  D
Key:        K  E  Y  K  E  Y  K  E  Y  K
Cipher:     R  I  J  V  S  U  Y  V  J  N

Resists simple frequency analysis.

Broken by: Kasiski test (find repeated patterns to determine key length)

Hill Cipher (Matrix Cipher)

Uses linear algebra — encrypts n letters at a time using n×n matrix K.

Encrypt: C = K × P (mod 26)
Decrypt: P = K⁻¹ × C (mod 26)

Example (2×2 matrix, key K):

K = [3 3]    Plaintext HI = [7]
    [2 5]                   [8]

C = [3×7+3×8] mod 26 = [45 mod 26] = [19 = T]
    [2×7+5×8]            [54 mod 26]   [2  = C]

Strength: Hides individual letter frequencies completely.

Weakness: Vulnerable to known-plaintext attack.

---

One-Time Pad (OTP)

• Key is a random string, same length as message
• Each character XOR'd with corresponding key character
• Key used ONLY ONCE and then discarded

Plaintext:   H  E  L  L  O
Key:         X  M  C  K  L  (random)
Ciphertext:  P  Q  N  V  Z

Why is OTP Theoretically Unbreakable?

• Every possible plaintext is equally likely for any ciphertext
• Attacker gains ZERO information from ciphertext
• Proved by Claude Shannon (1949): perfect secrecy

Practical Problems with OTP:

• Key must be truly random
• Key must be same length as message
• Key must NEVER be reused (if reused → easily broken)
• Key distribution problem (how to share securely?)

Use: Hot-line between Washington-Moscow used OTP during Cold War.

Transposition Ciphers rearrange (permute) letters without substituting them.

Same letters, different order.

1. Rail Fence Cipher (2 rails):

Plaintext: MEETMEATNOON
Rail 1: M . E . M . A . N . O .
Rail 2: . E . T . E . T . O . N
Read rows: MEMANO + ETETN = MEMAOETN... 
Cipher: MEMANOETN ON (read row by row)

2. Columnar Transposition:

Key:  3 1 4 2
Msg:  A T T A  (row 1)
      C K T H  (row 2)
      E F E N  (row 3)
Read columns by key order: col1=TKF, col2=AHN, col3=ATE, col4=TEE
Cipher: TKFAHNATEETE

Double Transposition: Apply columnar transposition twice for added security.

---

Cryptanalysis Attack Models:

Techniques:

• Brute Force: Try all keys — O(2^k) for k-bit key
• Frequency Analysis: Count letter occurrences (breaks monoalphabetic)
• Kasiski Test: Find repeated sequences → determine Vigenere key length
• Index of Coincidence: Measures randomness of text
• Differential Cryptanalysis: Analyzes effect of input differences on output
• Linear Cryptanalysis: Uses linear approximations of cipher

Stream Cipher

Encrypts data ONE BIT/BYTE at a time using a keystream.

Cᵢ = Pᵢ XOR Kᵢ   (bitwise XOR with keystream)

• Keystream generated from a seed/key
• Fast, low latency, good for real-time
• Examples: RC4, ChaCha20, A5/1 (GSM)

Block Cipher

Encrypts data in FIXED-SIZE BLOCKS (64 or 128 bits).

• Same key applied to each block
• Uses substitution + permutation networks
• Examples: DES (64-bit), AES (128-bit), Blowfish

Comparison:

RC4 (Rivest Cipher 4) — Stream Cipher:

• Variable key length (1–256 bytes)
• Uses S-box of 256 bytes initialized by key (KSA: Key Scheduling Algorithm)
• Generates pseudorandom keystream (PRGA: Pseudo-Random Generation Algorithm)
• Once used in SSL/WEP — now considered WEAK (biases in initial keystream)

Security Rule:

Never reuse stream cipher key+IV combination → XOR of two ciphertexts = XOR of plaintexts → broken!

Modern Choice: ChaCha20-Poly1305 (used in TLS 1.3, Signal Protocol)

Block Cipher Structure

Divides plaintext into fixed-size blocks and encrypts each block.

General structure uses Substitution-Permutation Network (SPN):

• Substitution (S-box): Non-linear substitution (adds confusion)
• Permutation (P-box): Rearranges bits (adds diffusion)
• Multiple rounds of S-P operations

Shannon's Design Principles:

• Confusion: Obscure relationship between key and ciphertext (via substitution)
• Diffusion: Change in one plaintext bit affects many ciphertext bits (via permutation)

---

Feistel Cipher Structure (used by DES)

Splits block into Left (L) and Right (R) halves, applies rounds:

For each round i:
  Lᵢ = Rᵢ₋₁
  Rᵢ = Lᵢ₋₁ XOR F(Rᵢ₋₁, Kᵢ)

Where:
  F = round function (expand, S-box, permute)
  Kᵢ = subkey for round i

Key Properties:

• Decryption uses SAME algorithm with subkeys in REVERSE order
• F function does not need to be invertible
• Security increases with number of rounds

Feistel Parameters:

Used in: DES, 3DES, Blowfish, CAST-128

DES (Data Encryption Standard)

• Published: 1977 by NIST (then NBS)
• Block size: 64 bits
• Key size: 64 bits (56 effective + 8 parity bits)
• Rounds: 16 Feistel rounds
• Structure: Feistel network

DES Steps:

1. Initial Permutation (IP) — reorders 64 input bits
2. Split into L₀ (32 bits) and R₀ (32 bits)
3. 16 Rounds of Feistel:
   Lᵢ = Rᵢ₋₁
   Rᵢ = Lᵢ₋₁ XOR F(Rᵢ₋₁, Kᵢ)
4. 32-bit swap: (R₁₆, L₁₆)
5. Final Permutation IP⁻¹

Round Function F(R, K):

R (32 bits) → Expansion E → 48 bits
                             XOR with Kᵢ (48-bit subkey)
                             → 8 S-boxes (6→4 bits each) → 32 bits
                             → Permutation P → 32 bits output

S-Boxes: 8 substitution boxes, each takes 6-bit input, gives 4-bit output.

Provide NON-LINEARITY (the core of DES security).

Key Schedule:

• 64-bit key → remove parity → 56 bits
• Split into C₀, D₀ (28 bits each)
• 16 rounds: circular left shift + PC-2 permutation → 48-bit Kᵢ

Decryption: Same algorithm, subkeys K₁₆ to K₁ (reverse order)

Strength of DES:

• 56-bit key → 2⁵⁶ ≈ 7.2×10¹⁶ possible keys
• Broken in 1998 by EFF's DES Cracker in 22 hours
• Vulnerable to: Brute force, Differential cryptanalysis, Linear cryptanalysis
• NOW CONSIDERED INSECURE — replaced by AES

Triple DES (3DES / TDEA)

Applies DES three times to increase security.

3DES Variants:

EDE (Encrypt-Decrypt-Encrypt):

C = Ek₃(Dk₂(Ek₁(P)))
P = Dk₁(Ek₂(Dk₃(C)))

With 3 different keys (K₁, K₂, K₃): effective key = 168 bits

With K₁=K₃: two-key 3DES = 112 bits effective key

Why not Double DES?

Double DES uses C = Ek₂(Ek₁(P)) — 112-bit key space

But vulnerable to Meet-in-the-Middle (MITM) Attack:

MITM Attack on Double DES:

Attacker has: (P, C) pair
1. Encrypt P with ALL possible K₁ → table X[] (2⁵⁶ entries)
2. Decrypt C with ALL possible K₂ → table Y[]
3. Find matches: X[K₁] = Y[K₂]
4. Result: found K₁,K₂ with only 2×2⁵⁶ = 2⁵⁷ operations
   (not the expected 2¹¹²)

MITM reduces Double DES security to just ~2⁵⁷ operations!

3DES Security:

• Immune to MITM (3 keys required)
• Effective security: ~112 bits with 2 keys, 168 bits with 3 keys
• Slow (3× slower than single DES)
• Block size still 64 bits (birthday attack risk for large data)

Status: 3DES deprecated by NIST in 2017, disallowed after 2023.

Replaced by AES everywhere.

AES (Advanced Encryption Standard)

• Selected by NIST in 2001 (Rijndael algorithm by Daemen & Rijmen)
• Block size: 128 bits (4×4 byte State matrix)
• Key sizes: 128 / 192 / 256 bits
• Rounds: 10 / 12 / 14 (for 128/192/256-bit keys)
• NOT Feistel — uses Substitution-Permutation Network (SPN)

AES State Matrix (4×4 bytes):

4 Transformation Functions per Round:

1. SubBytes (Confusion)

• Each byte independently replaced using S-box lookup table
• S-box constructed via GF(2⁸) multiplicative inverse
• Provides non-linearity

2. ShiftRows (Diffusion)

• Row 0: no shift
• Row 1: shift left by 1
• Row 2: shift left by 2
• Row 3: shift left by 3

3. MixColumns (Diffusion)

• Each column multiplied by fixed polynomial matrix in GF(2⁸)
• Spreads one byte's influence across entire column
• Skipped in LAST round

4. AddRoundKey (Key mixing)

• XOR state with 128-bit round key derived from key schedule
• Applied in EVERY round (including initial round)

AES Encryption Flow:

AddRoundKey(initial)
For rounds 1 to N-1:
  SubBytes → ShiftRows → MixColumns → AddRoundKey
Final round (no MixColumns):
  SubBytes → ShiftRows → AddRoundKey

Key Expansion (Key Schedule):

• Expands original key into (Nr+1) × 128-bit round keys
• Uses SubWord, RotWord, and Rcon (round constants) operations

Block cipher modes define how to encrypt messages LONGER than one block.

1. ECB — Electronic Code Book

Cᵢ = E(K, Pᵢ)    each block encrypted independently

• Identical plaintext blocks → IDENTICAL ciphertext blocks
• INSECURE: Patterns revealed (penguin problem)
• Use: Only for single-block encryption

(most common)

Cᵢ = E(K, Pᵢ XOR Cᵢ₋₁)    C₀ = IV (Initialization Vector)
Pᵢ = D(K, Cᵢ) XOR Cᵢ₋₁

• Each block depends on all previous blocks
• Requires IV (should be random, never reused)
• Error in one ciphertext block affects 2 plaintext blocks
• Use: Disk encryption, SSL (old)

3. CFB — Cipher Feedback

Cᵢ = Pᵢ XOR E(K, Cᵢ₋₁)    [stream-cipher-like]
Pᵢ = Cᵢ XOR E(K, Cᵢ₋₁)

• Converts block cipher into stream cipher
• Can encrypt data smaller than block size
• Use: Stream encryption of data

4. OFB — Output Feedback

Oᵢ = E(K, Oᵢ₋₁)    [keystream]
Cᵢ = Pᵢ XOR Oᵢ

• Keystream generated independently of plaintext/ciphertext
• Bit errors in ciphertext affect only corresponding plaintext bit
• Use: Noisy channels (satellite), error-sensitive apps

(modern favorite)

Cᵢ = Pᵢ XOR E(K, Nonce || Counter)

• Encrypts counter values to generate keystream
• Fully parallelizable (encryption AND decryption)
• Random access to any block
• Use: TLS 1.3, disk encryption, high-performance apps

Comparison:

Public Key Cryptography (Asymmetric Cryptography)

Uses a mathematically related KEY PAIR:

• Public Key (KU): Shared with everyone
• Private Key (KR): Kept secret by owner

Introduced by: Diffie & Hellman (1976) — 'New Directions in Cryptography'

Two uses:

1. Encryption/Decryption:
   C = E(KU_Bob, P)       [encrypt with Bob's public key]
   P = D(KR_Bob, C)       [decrypt with Bob's private key]

2. Authentication (Digital Signature):
   S = Sign(KR_Alice, M)  [sign with Alice's private key]
   Verify(KU_Alice, M, S) [verify with Alice's public key]

Requirements for Public Key Systems:

• 1. Easy to generate key pair (KU, KR)
• 2. Easy for sender to compute ciphertext: C = E(KU, P)
• 3. Easy for receiver to decrypt: P = D(KR, C)
• 4. Computationally infeasible to derive KR from KU
• 5. Computationally infeasible to recover P from C and KU
• 6. Either key can be used for either operation (optional)

Comparison:

Mathematical Foundations (Trapdoor Functions):

• RSA: Difficulty of factoring large numbers
• DH/ElGamal: Discrete logarithm problem
• ECC: Elliptic curve discrete logarithm

RSA (Rivest, Shamir, Adleman — 1977)

Based on difficulty of factoring product of two large primes.

Key Generation:

1. Choose two large primes p and q
2. Compute n = p × q         [modulus]
3. Compute φ(n) = (p-1)(q-1) [Euler's totient]
4. Choose e: 1 < e < φ(n), gcd(e, φ(n)) = 1  [public exponent]
5. Find d: d × e ≡ 1 (mod φ(n))               [private exponent]

Public Key:  (n, e)
Private Key: (n, d)  — keep p, q, φ(n) secret too

Encryption/Decryption:

Encrypt: C = Mᵉ mod n
Decrypt: M = Cᵈ mod n

Worked Example (small primes for illustration):

p = 11, q = 13
n = 143,   φ(n) = 10 × 12 = 120
Choose e = 7  (gcd(7,120)=1 ✓)
d: 7d ≡ 1 (mod 120) → d = 103  (7×103=721=6×120+1 ✓)

Public Key: (143, 7)
Private Key: (143, 103)

Encrypt M=2:  C = 2⁷ mod 143 = 128
Decrypt C=128: M = 128¹⁰³ mod 143 = 2 ✓

RSA Security:

• Security relies on Integer Factorization Problem
• n = 2048 bits recommended (NIST)
• Breaking RSA = factoring n to get p, q → then get d
• Best known factoring: General Number Field Sieve (GNFS)

RSA in Practice:

• Never encrypt raw data directly with RSA
• Use RSA to encrypt a symmetric session key (hybrid encryption)
• Always use OAEP padding (RSA-OAEP) for security

Applications: TLS/HTTPS key exchange, SSH, PGP, digital certificates

RSA Cryptanalysis — Known Attacks:

1. Brute Force / Factoring Attack

• Factor n to find p, q → compute φ(n) → find d
• Best algorithm: GNFS — still infeasible for 2048-bit n
• Mitigation: Use large n (2048+ bits)

2. Timing Attack

• Measures time taken to perform decryption operations
• Can deduce private key bits
• Mitigation: Constant-time implementations, blinding

3. Small Exponent Attack

• If e is very small (e.g., e=3) and same message sent to 3 recipients
• Chinese Remainder Theorem reveals M
• Mitigation: Use e=65537, always pad messages (OAEP)

4. Common Modulus Attack

• If same n used with different e values and same message encrypted
• Can recover plaintext using extended Euclidean algorithm
• Mitigation: Each user must have unique n

5. Chosen Ciphertext Attack (CCA)

• Attacker submits chosen ciphertexts and gets plaintexts
• Mitigation: Use OAEP padding (RSA-OAEP)

6. Side-Channel Attacks

• Power analysis, electromagnetic analysis
• Exploit physical implementation, not the math

---

Rabin Cryptosystem

Based on computing square roots modulo n (related to factoring).

Key Gen: n = p × q (p,q ≡ 3 mod 4)
Public Key: (n)   Private Key: (p, q)
Encrypt: C = M² mod n
Decrypt: M = √C mod n (4 possible values, padding identifies correct one)

Security: Breaking Rabin = factoring n (proven equivalent)

RSA security is NOT proven equivalent to factoring.

Drawback: 4 possible plaintexts on decryption

ElGamal Cryptosystem (1985)

Based on Discrete Logarithm Problem (DLP):

Given g, p, y, find x such that y = gˣ mod p → computationally hard.

Key Generation:

1. Choose large prime p and generator g of Z*p
2. Choose random private key x (1 < x < p-1)
3. Compute y = gˣ mod p
Public Key: (p, g, y)   Private Key: x

Encryption (message M):

1. Choose random k (1 < k < p-1)
2. Compute r = gᵏ mod p       [ephemeral key]
3. Compute s = M × yᵏ mod p
Ciphertext: (r, s)

Decryption:

M = s × r⁻ˣ mod p = s × (gᵏ)⁻ˣ mod p
  = M × yᵏ × g⁻ᵏˣ mod p = M (since y=gˣ)

Features:

• Probabilistic (same message + different k = different ciphertext)
• Ciphertext is TWICE the size of plaintext
• Used in DSA (signature variant)

---

Elliptic Curve Cryptography (ECC)

Based on Elliptic Curve Discrete Logarithm Problem (ECDLP):

Given P and Q=kP on an elliptic curve, find k → extremely hard.

Elliptic Curve: y² = x³ + ax + b (mod p) where 4a³+27b² ≠ 0

Point Addition: If P=(x₁,y₁) and Q=(x₂,y₂):

Slope λ = (y₂-y₁)/(x₂-x₁) mod p
x₃ = λ²-x₁-x₂ mod p
y₃ = λ(x₁-x₃)-y₁ mod p
R = P+Q = (x₃, y₃)

ECC vs RSA — Security Level:

ECC Advantages:

• Smaller keys = less computation, less bandwidth, less power
• Ideal for mobile, IoT, smart cards
• Used in Bitcoin (secp256k1), TLS 1.3 (P-256, X25519)

Hash Function H maps input of ANY size to a FIXED-SIZE digest:

h = H(M)   where |M| = any length, |h| = fixed (128/160/256/512 bits)

Requirements (7 Properties):

1. Variable Input Size

Can process messages of any length.

2. Fixed Output Size

Produces fixed-length hash (digest) regardless of input size.

3. Efficiency

H(M) easy to compute for any M.

4. Preimage Resistance (One-Way)

Given h, computationally infeasible to find M such that H(M) = h.

Protects passwords stored as hashes.

5. Second Preimage Resistance (Weak Collision Resistance)

Given M₁, infeasible to find M₂ ≠ M₁ such that H(M₁) = H(M₂).

Protects against document forgery.

6. Collision Resistance (Strong Collision Resistance)

Infeasible to find ANY two messages M₁ ≠ M₂ such that H(M₁) = H(M₂).

Harder to achieve; required for digital signatures.

7. Pseudorandomness

Output should be indistinguishable from random data.

Birthday Attack (Collision Attack):

Exploits birthday paradox — need only ~2^(n/2) operations to find collision in n-bit hash.

• SHA-1 (160-bit): collision in 2⁸⁰ ops → broken in 2017 by Google
• SHA-256 (256-bit): collision in 2¹²⁸ ops → currently secure

Hash Algorithms Comparison:

|

|

(Keccak) |

SHA (Secure Hash Algorithm) Family

Developed by NSA, standardized by NIST.

SHA-1 Structure (160-bit output):

1. Pad message to multiple of 512 bits
   (append 1-bit, then zeros, then 64-bit length)
2. Initialize 5 hash values: H₀..H₄ (160 bits total)
3. Process each 512-bit block:
   - Expand 16 words → 80 words using:
     Wₜ = (Wₜ₋₃ XOR Wₜ₋₈ XOR Wₜ₋₁₄ XOR Wₜ₋₁₆) <<< 1
   - 4 rounds × 20 steps using A,B,C,D,E registers
   - Each step: T = (A<<<5) + f(B,C,D) + E + Wₜ + Kₜ
   - Update: E=D, D=C, C=B<<<30, B=A, A=T
4. Add round output to H₀..H₄
5. Final hash = concatenation of H₀..H₄

SHA-256 (256-bit output):

• 512-bit blocks, 64 rounds
• 8 working variables (a,b,c,d,e,f,g,h)
• Uses 64 round constants (cube roots of first 64 primes)
• Compression function: Ch, Maj, Σ₀, Σ₁, σ₀, σ₁ functions
• Each bit of output depends on every bit of input (avalanche effect)

---

Hash Functions Based on Cipher Block Chaining (CBC-MAC style):

H₀ = IV  (initialization vector)
Hᵢ = E(Mᵢ, Hᵢ₋₁)   [encrypt message block with previous hash]
Final hash = Hₙ

• Uses block cipher (e.g., DES, AES) as building block
• Called Davies-Meyer construction:

Hᵢ = E(Mᵢ, Hᵢ₋₁) XOR Hᵢ₋₁

• Used in MDx, SHA families
• Security = security of underlying block cipher

Merkle-Damgård Construction:

Iterative hashing where each block feeds into next:

H₀(IV) → H₁ → H₂ → ... → Hₙ = Final Hash
         M₁   M₂          Mₙ

Used by MD5, SHA-1, SHA-256.

MAC (Message Authentication Code)

A short tag computed from a message and a SECRET key:

Tag = MAC(K, M)   [sender computes]
Verify: MAC(K, M') == Tag?  [receiver verifies]

Provides: Integrity + Authentication (not confidentiality)

Requirements for MAC:

• 1. Computation resistance: Without key K, cannot compute valid MAC
• 2. Collision resistance: Hard to find M₁ ≠ M₂ with same MAC
• 3. Variable-length input: Works on messages of any size

Difference: Hash vs MAC:

HMAC (Hash-based MAC) — RFC 2104:

HMAC(K, M) = H[(K XOR opad) || H[(K XOR ipad) || M]]

Where:
ipad = 0x36 repeated (inner padding)
opad = 0x5C repeated (outer padding)
|| = concatenation

• Two nested hash computations
• Security proved if underlying hash is secure
• Used in TLS, IPSec, JWT tokens

CBC-MAC:

MAC based on block cipher in CBC mode:
T₀ = E(K, M₁)
T₁ = E(K, M₂ XOR T₀)
...
Tₙ = MAC

• Only the FINAL block is the tag (intermediate blocks discarded)
• CMAC (NIST standard): Improved CBC-MAC, handles variable length
• GMAC: Galois MAC, used in AES-GCM (authenticated encryption)

Digital Signature

A cryptographic mechanism providing authentication, integrity and non-repudiation using asymmetric keys.

How it Works:

Properties Required:

• 1. Verifiable: Anyone with signer's public key can verify
• 2. Unforgeable: Only private key holder can create valid signature
• 3. Non-reusable: Signature tied to specific document
• 4. Unalterable: Signed document cannot be changed
• 5. Non-repudiable: Signer cannot deny having signed

ElGamal Digital Signature:

Sign:    Choose random k; r = gᵏ mod p
         s = (H(M) - x·r) · k⁻¹ mod (p-1)
Sig: (r, s)
Verify:  gᴴ⁽ᴹ⁾ ≡ yʳ · rˢ (mod p)

Schnorr Signature:

Setup: p,q primes; q|(p-1); g generator of order q
Sign:   r = gᵏ mod p;  e = H(M||r);  s = k - xe mod q
Sig: (e, s)
Verify: r' = gˢyᵉ mod p; check H(M||r') == e

Advantage: Short signatures, fast verification

DSA — Digital Signature Algorithm (NIST FIPS 186):

Domain: p (1024-bit prime), q (160-bit prime, q|p-1), g
Sign:   k random; r=(gᵏ mod p) mod q; s=k⁻¹(H(M)+xr) mod q
Sig: (r,s)
Verify: w=s⁻¹ mod q; u₁=H(M)w mod q; u₂=rw mod q
        v=(g^u₁·y^u₂ mod p) mod q; check v==r

• Cannot be used for encryption (signature only)
• ECDSA: DSA on elliptic curves (used in Bitcoin, TLS)

Problem: For n users to communicate privately, need n(n-1)/2 keys.

For 1000 users = 499,500 keys! Key distribution is a major challenge.

Methods of Symmetric Key Distribution:

1. Key Distribution Center (KDC) / Needham-Schroeder Protocol:

Each user shares a master key with KDC.

Step 1: Alice → KDC: "I want to talk to Bob" + nonce NA
Step 2: KDC → Alice: E(KA, [KS || IDB || NA || E(KB, [KS || IDA])])
  [KS = session key; E(KB,...) = ticket for Bob]
Step 3: Alice → Bob: E(KB, [KS || IDA])   [ticket]
Step 4: Bob → Alice: E(KS, NB)            [challenge]
Step 5: Alice → Bob: E(KS, NB-1)          [response]

Now Alice & Bob share session key KS.

Problems: KDC is single point of failure, replay attacks.

2. Diffie-Hellman Key Exchange:

• No secret transmitted over network
• Vulnerable to Man-in-the-Middle attack without authentication
• Solved by: Authenticated DH (station-to-station protocol)

3. Using Asymmetric Encryption to distribute symmetric key:

Alice generates random session key KS
Alice → Bob: E(KU_Bob, KS)   [encrypt KS with Bob's public key]
Bob decrypts: KS = D(KR_Bob, ciphertext)
Now use KS for symmetric encryption

This is the basis of TLS/HTTPS key exchange.

Problem: Anyone can claim a public key belongs to anyone else → Man-in-the-Middle attack.

Methods of Public Key Distribution:

1. Public Announcement: Post public key on website/forum — easy but no authentication.

2. Publicly Available Directory: Trusted authority maintains directory of {name → public key}.

3. Public Key Authority: Users register keys; authority provides certified copies on request.

4. Public Key Certificates (Best solution):

X.509 Digital Certificate Format:

┌─────────────────────────────────┐
│ Version (v1/v2/v3)              │
│ Serial Number                   │
│ Signature Algorithm ID          │
│ Issuer (CA Name)                │
│ Validity Period (Not Before/After)│
│ Subject (Owner Name)            │
│ Subject Public Key Info         │
│   - Algorithm                   │
│   - Public Key                  │
│ Extensions (v3 only)            │
│   - Key Usage, SAN, etc.        │
│ CA's Digital Signature          │
└─────────────────────────────────┘

PKI (Public Key Infrastructure):

A framework of policies, processes, and technologies to manage digital certificates.

Components:

• CA (Certification Authority): Issues and signs certificates (DigiCert, Let's Encrypt)
• RA (Registration Authority): Verifies identity before cert issuance
• CRL (Certificate Revocation List): Lists revoked certificates
• OCSP (Online Certificate Status Protocol): Real-time revocation check
• Repository: Stores certificates and CRLs

Certificate Chain (Trust Hierarchy):

Root CA (self-signed, pre-installed in browser)
  └── Intermediate CA (signed by Root CA)
        └── End-Entity Certificate (signed by Intermediate CA)

Browser verifies chain up to trusted Root CA.

Kerberos is a network authentication protocol using symmetric key cryptography and trusted third-party (KDC) to authenticate users to services.

Named after the three-headed dog of Greek mythology.

Components:

• Client (C): User wanting to access service
• AS (Authentication Server): Verifies identity, issues TGT
• TGS (Ticket Granting Server): Issues service tickets
• SS (Service Server): The actual service (file server, mail, etc.)

Kerberos Protocol (Version 5):

Phase 1 — Authentication:
1. C → AS: Username (in plaintext)
2. AS → C: E(KC, [KS_tgs || TGT])
   TGT = Ticket Granting Ticket = E(KTGS, [KC, addr, time, KS_tgs])
   KC = key derived from user's password
   User decrypts with password → gets KS_tgs

Phase 2 — Get Service Ticket:
3. C → TGS: {TGT || Authenticator || service_id}
   Authenticator = E(KS_tgs, [C, timestamp])
4. TGS → C: E(KS_tgs, [KS_service || Service Ticket])
   Service Ticket = E(Kservice, [C, addr, time, KS_service])

Phase 3 — Use Service:
5. C → SS: {Service Ticket || Authenticator2}
   Authenticator2 = E(KS_service, [C, timestamp])
6. SS → C: E(KS_service, timestamp+1)  [optional mutual auth]

Why Kerberos?

• Passwords never sent over network (only ticket + authenticator)
• Tickets are time-limited (typically 8 hours) → replay protection
• Single Sign-On (SSO): one login gives access to multiple services
• Used in: Windows Active Directory, MIT networks

Weaknesses:

• KDC is single point of failure
• Time synchronization required (5-minute window)
• Weak password → AS_REP roasting attack

Web Security Threats:

---

SSL (Secure Sockets Layer) / TLS (Transport Layer Security)

Provides: Confidentiality (encryption) + Integrity (MAC) + Authentication (certificates)

TLS 1.3 Handshake (simplified):

Client                              Server
  │──── ClientHello ────────────────▶│
  │  (supported ciphers, DH keyshare)│
  │◀─── ServerHello ────────────────│
  │  (chosen cipher, DH keyshare)   │
  │◀─── Certificate ────────────────│
  │◀─── CertificateVerify ──────────│
  │◀─── Finished ───────────────────│
  │──── Finished ───────────────────▶│
  │═══════ Encrypted Data ══════════▶│

TLS Cipher Suite Example:

TLS_AES_256_GCM_SHA384

= TLS protocol + AES-256-GCM (encryption) + SHA-384 (integrity)

TLS 1.2 vs TLS 1.3:

---

HTTPS = HTTP + TLS

All web data encrypted; URL shows 🔒 padlock.

SSH (Secure Shell):

• Secure remote login, file transfer (SCP/SFTP)
• Uses: asymmetric key auth + symmetric session encryption
• Port 22; replaces insecure Telnet (port 23)
• Authentication: password or SSH key pair (more secure)

SSH Key-Based Auth:

1. Generate: ssh-keygen → private key + public key
2. Place public key on server (~/.ssh/authorized_keys)
3. Login: server sends challenge → client signs with private key
4. Server verifies with public key → access granted

Protocol Comparison:

TLS Record Protocol (data transmission):

1. Fragment data into blocks
2. Optionally compress
3. Add MAC (integrity)
4. Encrypt (confidentiality)
5. Add TLS record header

Forward Secrecy (Perfect Forward Secrecy - PFS):

• Even if server's private key is compromised LATER, past sessions cannot be decrypted
• Achieved by using ephemeral DH keys for each session
• TLS 1.3 mandates ECDHE (no more RSA key exchange)

Attacks TLS Prevents:

Security Recommendations (2024):

• Use TLS 1.3 (minimum TLS 1.2)
• Cipher suite: AES-256-GCM or ChaCha20-Poly1305
• Key exchange: ECDHE with P-256 or X25519
• Certificate: RSA-2048 or ECDSA P-256 minimum
• HSTS: Strict-Transport-Security header
• OCSP Stapling for certificate validation

Mnemonic for TLS services: CIA

• Confidentiality (encryption)
• Integrity (MAC/AEAD)
• Authentication (certificates)