Lecture 1: Introduction to Cryptography
Definition:
Cryptography is the study of mathematical techniques for securing digital information, systems, and
distributed computation from adversarial attacks.
Originates from the Greek meaning "secret writing".
Aspects of Cryptography:
• Mathematical security definitions
•
• Algorithmic assumptions
•
• Formal proofs
•
• Intuition and creativity
Goals of Secure Communication:
1. Confidentiality – Ensuring only the intended recipient can read the message.
2. Integrity – Verifying that the message has not been tampered with and is from the claimed sender.
Attacker Models:
Passive Attacker (Eve) – Eavesdrops communication (confidentiality is required).
Active Attacker (Mallory) – Can modify data (requires both confidentiality and integrity).
Cryptography vs Steganography
Steganography:
Goal: Hide the existence of a message
Dependence:Security by obscurity
Cryptography:
Goal: Hide the meaning of a message
Dependence: Security via secret key (Kerckhoff’s Principle)
Symmetric and Asymmetric Encryption
Symmetric Key Encryption:
• Both sender and receiver share a secret key.
• Encryption and decryption use the same key.
Formal Syntax:
Message space ℳ, Key space 𝒦.
Three algorithms:
Gen(R) → generates key k ∈ 𝒦
Enc∈(m) → encrypts m ℳℳ to ciphertext c
Decₖ(c) → decrypts c to recover m
Must satisfy: Decₖ(Encₖ(m)) = m
Asymmetric Encryption:
• Uses a key pair: public key (encrypt/verify) and private key (decrypt/sign).
• Public key is shared openly; private key is kept secret.
Classical Ciphers:
1. Caesar / Shift Cipher:
Key space: 𝒦 = {0..25}
Example: BEGINTHEATTACKNOW → EHJLQWKHDWWDFNQRZ (k=3)
Easily broken with brute force (26 possibilities).
2. Substitution Cipher:
Each letter replaced based on a random permutation of the alphabet.
Key space size = 26! ≈ 2⁸⁸ (very large).
Example mapping shown in table form.
3. Vigenère Cipher:
Extension of Caesar Cipher using a repeating key of shifts.
Key space size = 26ᵗ (where t = key length).
Example:
Plaintext: "HELLO"
Key: "KEY"
Ciphertext: "RIJVS"
Playfair Cipher
• 5x5 key matrix generated from keyword (e.g., "MONARCHY").
•
• Encrypts plaintext digraphs (two-letter groups).
Rules:
1. Repeating letters in digraphs separated with filler (e.g., "X").
2. Same row → shift right.
3. Same column → shift down.
4. Else → form rectangle, take opposite corners.
Example:
Plaintext: “secret message” → Cipher: “LIDMKLCLXAXBIF”
Vernam Cipher & One-Time Pad (OTP)
Vernam Cipher:
Uses XOR between message and key.
Key reused → insecure.
One-Time Pad:
Key is truly random, same length as message, used only once.
Perfect secrecy (unbreakable).
Example:
Message: "HELLO"
Key: "XMCKL"
Ciphertext: "EQNVZ"
Hill Cipher
• Uses matrix multiplication (linear algebra).
• Hides individual letter frequencies.
Example:
Plaintext: "HELLO WORLD"
Output: "SLHZY ATGZT"
Key:
Square matrix (e.g., 2x2, 3x3)
Requires invertibility modulo 26.
Transposition Ciphers
1. Rail Fence Cipher:
Write in zigzag and read line by line.
Example:
Input: "WE ARE DISCOVERED FLEE AT ONCE"
Ciphertext: "WECRLTEERDSOEEFEAOCAIVDEN"
2. Row Transposition Cipher:
Write in matrix by rows, permute columns based on key.
Example:
Key: 4 3 1 2 5 6 7
Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ
Decryption involves reversing the column permutation using the key.
DES (Data Encryption Standard)
• 64-bit block cipher with 56-bit key (plus 8 parity bits).
• 16 rounds of Feistel structure.
DES Key Generation:
1. Apply PC-1 permutation.
2. Split into C₀ and D₀ (28 bits each).
3. Perform left shifts as per schedule.
4. Apply PC-2 to form 16 round keys.
DES Encryption Process:
Initial Permutation (IP).
16 rounds:
Expansion (E-box), Key mixing (XOR), Substitution (S-box), Permutation (P-box).
Final permutation (IP⁻¹).
S-boxes:
Maps 6-bit inputs to 4-bit outputs.
Tables S1–S8 are used in each round.
DES Example:
Message: 0123456789ABCDEF
Key: 133457799BBCDFF1
Final Ciphertext (after 16 rounds): 85E813540F0AB405
AES (Advanced Encryption Standard)
• Block cipher with 128-bit block size.
• Key sizes: 128, 192, or 256 bits.
• Uses Substitution-Permutation Network (not Feistel).
AES Process:
1. Key Expansion: Generates round keys.
2. Initial Round: AddRoundKey
3. Rounds (9 or 11 or 13):
• SubBytes (S-box)
• ShiftRows
• MixColumns
• AddRoundKey
4. Final Round: (No MixColumns)
AES Example (128-bit):
• Key: "Thats my Kung Fu"
• Plaintext: "Two One Nine Two"
• Final Ciphertext: 29C3505F571420F6402299B31A02D73A
