Unit 4: Cryptography - Subjective Questions

Cryptography is the science and art of securing communication in the presence of adversaries. It involves transforming readable data (plaintext) into an unreadable form (ciphertext) and back again, ensuring that only authorized parties can access the information.

Primary Objectives / Security Services:

• Confidentiality: Ensures that information is accessible only to those authorized to have access. Achieved through encryption.
• Integrity: Guarantees that data has not been altered in an unauthorized manner during storage or transmission.
• Authentication: Verifies the identity of the communicating parties (entity authentication) and the origin of data (message authentication).
• Non-repudiation: Prevents an entity from denying previous commitments or actions (e.g., a sender cannot deny sending a message).

Additional Terminology:

• Plaintext (): The original readable message.
• Ciphertext (): The encrypted, unreadable message.
• Encryption (): The process of converting plaintext to ciphertext using a key.
• Decryption (): The reverse process of recovering plaintext from ciphertext.

Thus, and , where is the secret key.

The history of cryptography spans thousands of years and can be divided into distinct eras:

1. Ancient Cryptography:

• Scytale (Spartans, ~500 BC): A transposition cipher using a rod of specific diameter to wrap a strip of parchment.
• Caesar Cipher (~50 BC): Julius Caesar used a shift cipher, shifting each letter by 3 positions.

2. Classical/Manual Cryptography:

• Substitution and transposition ciphers dominated (e.g., Vigenère cipher in the 16th century, considered unbreakable for 300 years).
• Frequency analysis was developed by Arab scholars like Al-Kindi (9th century).

3. Mechanical Era (World Wars):

• Enigma Machine (WWII): Used by Germany; broken by Allied cryptanalysts including Alan Turing at Bletchley Park.

4. Modern Cryptography (Post-1970s):

• DES (1977): Data Encryption Standard, a symmetric block cipher.
• Public-Key Cryptography (1976): Diffie-Hellman key exchange and later RSA revolutionized the field.
• AES (2001): Advanced Encryption Standard replaced DES.

Key Shift: Modern cryptography relies on mathematical hardness assumptions and computational complexity rather than secrecy of the algorithm (Kerckhoffs's Principle).

A cryptosystem (or cipher system) is a formal mathematical structure used to achieve secure communication. It is defined as a five-tuple satisfying the following conditions:

• (Plaintext Space): A finite set of all possible plaintext messages.
• (Ciphertext Space): A finite set of all possible ciphertexts.
• (Key Space): A finite set of all possible keys.
• (Encryption Rules): A set of encryption functions. For each key , there is an encryption rule where .
• (Decryption Rules): A set of decryption functions. For each key , there is a decryption rule where .

Fundamental Property:

For each there is a corresponding such that for every plaintext :

This ensures that encryption followed by decryption (with the correct key) recovers the original message. The encryption function must be an injective (one-to-one) function to guarantee unambiguous decryption.

The Shift Cipher is one of the simplest and oldest encryption techniques, where each letter in the plaintext is shifted a fixed number of positions down the alphabet. The Caesar cipher is a special case with a shift of 3.

Mathematical Formulation:

Let each letter be represented by a number: . All operations are performed modulo 26.

• Encryption:
• Decryption:

where is the key.

Example: Encrypt "HELLO" with

Ciphertext = "KHOOR"

Security Weakness: The key space is only 26 (25 useful keys), making it trivially breakable by brute-force attack or frequency analysis.

The Affine Cipher is a type of monoalphabetic substitution cipher that combines multiplication and addition. It is a generalization of the shift cipher.

Encryption Function:

where the key is the pair , with .

Validity Condition:

For decryption to be possible, the function must be a bijection. This requires that has a multiplicative inverse modulo 26. Therefore:

Since , the valid values of are those coprime to 26. There are such values, giving a key space of .

Decryption Function (Derivation):

Starting from :

Thus:

where is the multiplicative inverse of modulo 26.

Example: If , then since .

Affine Cipher Encryption:

First verify validity: ✓, so the key is valid.

Letter-to-number mapping:

Calculations:

• A: I
• F: H
• I: W
• N: V
• E: C

Ciphertext = "IHHWVC"

A (Monoalphabetic) Substitution Cipher replaces each letter of the plaintext with another letter according to a fixed permutation of the alphabet. Unlike the shift cipher, the substitution is arbitrary rather than a simple shift.

Working:

The key is a permutation of the 26 letters. For example:

Plain: A B C D E ... Z
Cipher: Q W E R T ... M

• Encryption:
• Decryption:

Key Space Size:

Since any of the 26 letters can map to any of 26 letters (as a bijection), the number of possible keys is:

This is an enormous key space, making a brute-force attack computationally infeasible.

Why It Is Still Vulnerable:

• Frequency Analysis: Each plaintext letter always maps to the same ciphertext letter. Since natural languages have characteristic letter frequencies (e.g., 'E' is most common in English at ~12.7%), the frequency distribution is preserved in the ciphertext.
• Pattern Analysis: Common digraphs (TH, HE) and trigraphs (THE, ING) can be identified.
• Word Structure: Short words and repeated patterns give clues.

By analyzing the ciphertext letter frequencies and comparing them to known language statistics, a cryptanalyst can recover the plaintext without trying all keys. This demonstrates that a large key space alone does not guarantee security.

The Vigenère Cipher is a polyalphabetic substitution cipher that uses a keyword to apply multiple shift ciphers in sequence, thereby resisting simple frequency analysis. It was considered unbreakable for centuries ("le chiffre indéchiffrable").

Mechanism:

A keyword is repeated to match the length of the plaintext. Each letter of the plaintext is shifted by the corresponding key letter's value.

Mathematical Formulation:

Let the key be of length .

• Encryption:
• Decryption:

Worked Example:

Encrypt "HELLO" with keyword "KEY".

Repeat key: K E Y K E → values 10, 4, 24, 10, 4

Ciphertext = "RIJVS"

Strength: Since the same plaintext letter maps to different ciphertext letters depending on position, the flat frequency distribution defeats simple frequency analysis. However, it can be broken using the Kasiski examination and Index of Coincidence to find the key length .

The Hill Cipher is a polygraphic substitution cipher based on linear algebra, invented by Lester S. Hill in 1929. It encrypts blocks of letters at a time using matrix multiplication.

Working:

Plaintext is divided into blocks of letters, each represented as a column vector. An key matrix is used.

Encryption:

where is the plaintext vector and is the ciphertext vector.

Decryption:

where is the inverse of modulo 26.

Validity Condition:

For the key matrix to be invertible modulo 26, its determinant must be coprime to 26:

Computing the Inverse:

For a matrix :

where is the modular multiplicative inverse of the determinant modulo 26.

Strength & Weakness: It hides single-letter frequencies (diffusion across the block) but is vulnerable to a known-plaintext attack, since known plaintext-ciphertext pairs allow solving for .

Hill Cipher Encryption with , block size .

Step 1: Verify validity

✓ — the key is valid.

Step 2: Convert plaintext to numbers

H=7, E=4, L=11, P=15

Blocks: and

Step 3: Encrypt first block (HE)

H, I → "HI"

Step 4: Encrypt second block (LP)

A, T → "AT"

Ciphertext = "HIAT"

A Permutation Cipher (also called a Transposition Cipher) rearranges the positions of the characters in the plaintext according to a fixed permutation, without changing the actual letters themselves.

Mechanism:

The plaintext is divided into blocks of size . A permutation of defines how positions are rearranged.

• Encryption:
• Decryption:

Difference from Substitution Cipher:

Example:

Plaintext: "SECRET", block size , permutation (position 1 gets char from position 3, etc.).

Block 1: S(1) E(2) C(3) → rearranged: C S E
Block 2: R(1) E(2) T(3) → rearranged: T R E

Ciphertext = "CSETRE"

Note: Because letter frequencies are unchanged, transposition ciphers can be detected by frequency analysis (the ciphertext has the same distribution as plaintext), and broken via anagramming.

Cryptosystems are broadly classified based on how keys are managed.

Symmetric-Key Cryptography (Secret-Key):

• Uses the same key for both encryption and decryption: .
• Examples: Shift cipher, Affine cipher, Vigenère, Hill cipher, DES, AES.

Asymmetric-Key Cryptography (Public-Key):

• Uses a pair of keys: a public key for encryption and a private key for decryption.
• Examples: RSA, ElGamal, Elliptic Curve Cryptography (ECC).

Comparison Table:

Advantages of Symmetric: Fast, efficient for large data.
Disadvantages of Symmetric: Secure key distribution problem; poor scalability.

Advantages of Asymmetric: Solves key distribution; enables digital signatures and non-repudiation.
Disadvantages of Asymmetric: Slower; requires larger keys.

Hybrid systems (e.g., TLS) combine both — using asymmetric cryptography to exchange a symmetric session key.

Kerckhoffs's Principle (formulated by Auguste Kerckhoffs in 1883) states:

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

In other words, the security of a cipher must depend solely on the secrecy of the key, not on the secrecy of the algorithm.

Implications:

• The encryption algorithm can be publicly known and scrutinized.
• Only the key needs to be kept secret.
• "Security through obscurity" (hiding the algorithm) is discouraged.

Importance in Modern Cryptography:

• Public Scrutiny: Open algorithms (like AES, RSA) can be analyzed by the global cryptographic community, exposing weaknesses before deployment.
• Trust and Standardization: Standards bodies (NIST) select algorithms through open competitions.
• Practical Key Management: It is easier to change a compromised key than to redesign and redistribute a secret algorithm.
• Robustness: If the algorithm's secrecy is the only defense, its leak destroys all security. Keys, however, can be rotated.

Shannon's Maxim restated this as: "The enemy knows the system."

This principle is foundational: all widely trusted modern ciphers are publicly published and rely only on key secrecy.

Cryptanalysis is the study of breaking cryptosystems. Attacks are classified according to what information the attacker (cryptanalyst) has access to.

1. Ciphertext-Only Attack (COA):

• The attacker has access only to ciphertext.
• The goal is to deduce plaintext or the key.
• This is the weakest attacker model but represents the most common real-world scenario.
• Example: Frequency analysis on a substitution cipher.

2. Known-Plaintext Attack (KPA):

• The attacker has some plaintext-ciphertext pairs.
• Uses these pairs to deduce the key or decrypt further messages.
• Example: The Hill cipher is vulnerable to KPA.

3. Chosen-Plaintext Attack (CPA):

• The attacker can choose plaintexts and obtain their corresponding ciphertexts.
• Stronger than KPA; the attacker actively probes the system.

4. Chosen-Ciphertext Attack (CCA):

• The attacker can choose ciphertexts and obtain their decryptions.
• Very powerful; used to test the robustness of modern schemes.

Additional Approaches:

• Brute-Force Attack: Trying all possible keys exhaustively. Feasible only for small key spaces.
• Side-Channel Attacks: Exploiting physical information like timing or power consumption.

A cryptosystem is considered strong if it resists the strongest of these attacks (e.g., CCA security).

All three are monoalphabetic substitution ciphers, but they differ in complexity and security.

Comparison Table:

Security Analysis:

• Shift Cipher: Extremely weak. Vulnerable to brute-force (only 25 keys) and frequency analysis.
• Affine Cipher: Slightly stronger due to a larger key space (312), but still trivially broken by brute-force and frequency analysis.
• Substitution Cipher: Huge key space defeats brute-force, but still broken by frequency analysis because each letter maps consistently.

Common Vulnerability:

All three are monoalphabetic, meaning each plaintext letter always maps to the same ciphertext letter. This preserves the language's frequency signature, so all three fall to frequency analysis regardless of key space size.

Conclusion: Increasing the key space (Shift → Affine → Substitution) does not fix the fundamental weakness of monoalphabetic substitution.

Frequency Analysis is a cryptanalytic technique that exploits the fact that letters in a natural language occur with characteristic, predictable frequencies. Since a monoalphabetic cipher maps each plaintext letter to a fixed ciphertext letter, these frequencies are preserved (just relabeled).

English Language Frequencies (approximate):

• Most common letters: E (12.7%), T (9.1%), A (8.2%), O, I, N, S, H, R
• Least common: Z, Q, X, J
• Common digraphs: TH, HE, IN, ER
• Common trigraphs: THE, ING, AND

Step-by-Step Procedure:

1. Collect ciphertext: Obtain a sufficiently long ciphertext sample.
2. Count frequencies: Tally the occurrence of each ciphertext letter.
3. Rank letters: Order ciphertext letters by frequency.
4. Initial mapping: Match the most frequent ciphertext letter to 'E', next to 'T', and so on.
5. Analyze patterns: Look for common digraphs, trigraphs, and short words (single letters likely 'A' or 'I'; three-letter words often 'THE').
6. Refine and iterate: Substitute guessed letters into the ciphertext, look for partially readable words, and adjust the mapping.
7. Complete decryption: Continue until the full plaintext emerges and the key (permutation) is recovered.

Why It Works: Because the substitution is fixed (one-to-one), the statistical structure of the language leaks through. This is why monoalphabetic ciphers, despite large key spaces, are insecure.

Why the condition is necessary:

Decryption requires computing . The matrix inverse formula involves multiplying by , the modular multiplicative inverse of the determinant. This inverse exists if and only if is coprime to 26. If , no inverse exists, decryption is impossible, and the encryption map is not a bijection (multiple plaintexts map to the same ciphertext).

Finding the inverse of :

Step 1: Compute the determinant

✓

Step 2: Find

We need . Testing: .

So .

Step 3: Apply the inverse formula

(Since and .)

Verification: should equal the identity matrix .

The One-Time Pad (OTP) is a symmetric encryption technique that achieves perfect secrecy (proven by Claude Shannon). It is essentially a Vigenère cipher where the key is truly random and as long as the message.

Mechanism:

• The key is a random string of the same length as the plaintext .
• Encryption: (or bitwise XOR in binary: ).
• Decryption: .

Why It Is Perfectly Secure:

• Given a ciphertext, every possible plaintext of that length is equally likely, since for any candidate plaintext there exists a key that produces the observed ciphertext.
• Formally, the ciphertext reveals no information about the plaintext: .
• This is Shannon's perfect secrecy, mathematically unbreakable regardless of computing power.

Requirements for Perfect Secrecy:

1. The key must be truly random.
2. The key must be at least as long as the message.
3. The key must be used only once (never reused).
4. The key must be kept completely secret.

Practical Limitations:

• Key distribution: A key as long as the message must be securely shared in advance.
• Key storage: Large keys are difficult to store and manage.
• Key generation: Truly random keys are hard to generate.
• No reuse: Reusing a pad ("two-time pad") breaks security completely.

Due to these limitations, OTP is impractical for most applications but is used in extremely high-security scenarios (e.g., diplomatic hotlines).

Decryption using Shift Cipher: , with .

Recovered Plaintext = "HELLO"

Brute-Force Attack:

The shift cipher has only 25 possible non-trivial keys ( to ). An attacker can simply try every key:

• For each candidate key from 1 to 25, compute .
• Examine the resulting text for meaningful output.

Illustration (trying a few keys on "KHOOR"):

• : JGNNQ (nonsense)
• : IFMMP (nonsense)
• : HELLO ✓ (meaningful!)

Since only 25 keys exist, the attacker can exhaustively test all of them in a fraction of a second and recognize the correct plaintext by its readability. This tiny key space makes the shift cipher completely insecure against brute-force attacks.

The Kasiski Examination (developed by Friedrich Kasiski in 1863) is a technique to break the Vigenère cipher by first determining the length of the keyword, after which the cipher reduces to several independent shift ciphers solvable by frequency analysis.

Underlying Principle:

In the Vigenère cipher, if a repeated sequence of plaintext letters is encrypted by the same portion of the key, it produces the same repeated ciphertext sequence. The distance between such repeated sequences is a multiple of the key length.

Step-by-Step Procedure:

1. Find repeated sequences: Scan the ciphertext for repeated groups of letters (typically length 3 or more, e.g., trigraphs).
2. Measure distances: Record the distance (number of characters) between the start of each pair of identical sequences.
3. Factor the distances: Compute the factors of each distance. The key length is likely a common factor of these distances.
4. Determine key length (): The greatest common divisor (GCD) or most frequent common factor of the distances suggests the keyword length.

Example: If a repeated sequence appears at distances 16, 24, and 40, the common factors include 8. Thus is likely 8 (or a divisor of it).

After Finding Key Length:

• Split the ciphertext into groups (every -th letter belongs to one group).
• Each group was encrypted with a single shift (Caesar cipher).
• Apply frequency analysis to each group independently to recover each key letter.

Complementary Tool — Index of Coincidence (IC):

The IC statistically confirms the key length by measuring how similar the letter frequency distribution is to that of a monoalphabetic cipher. Together, these methods completely break the once-"unbreakable" Vigenère cipher.