Podcast
Questions and Answers
What is the dictionary definition of cryptography?
What is the dictionary definition of cryptography?
Cryptography is defined as 'secret writing.'
Who are the traditional actors in classical cryptography?
Who are the traditional actors in classical cryptography?
In the Caesar cipher, shifting every character by a constant offset is known as __________.
In the Caesar cipher, shifting every character by a constant offset is known as __________.
encryption
Perfect security exists in practice for cryptographic systems.
Perfect security exists in practice for cryptographic systems.
Signup and view all the answers
What is the formula for encrypting a message using the Enigma machine?
What is the formula for encrypting a message using the Enigma machine?
Signup and view all the answers
In the example provided, what is the ciphertext generated for the message TESTING with the key CODE?
In the example provided, what is the ciphertext generated for the message TESTING with the key CODE?
Signup and view all the answers
What process is involved in Enigma II for encryption?
What process is involved in Enigma II for encryption?
Signup and view all the answers
What are the goals of an attacker in different attack scenarios? (Select all that apply)
What are the goals of an attacker in different attack scenarios? (Select all that apply)
Signup and view all the answers
What type of attack involves trying all possible keys until the correct one is found?
What type of attack involves trying all possible keys until the correct one is found?
Signup and view all the answers
What is the name of the method used for attacks on the Vigenère cipher where key repeats every ||k|| positions?
What is the name of the method used for attacks on the Vigenère cipher where key repeats every ||k|| positions?
Signup and view all the answers
In long texts, the same bigram/trigram/etc. appears at positions which are an integer multiple of the key length.
In long texts, the same bigram/trigram/etc. appears at positions which are an integer multiple of the key length.
Signup and view all the answers
What is computed to identify the key length in the auto-correlation method for attacking the Vigenère cipher?
What is computed to identify the key length in the auto-correlation method for attacking the Vigenère cipher?
Signup and view all the answers
Study Notes
Overview of Cryptography
- Cryptography is the scientific study of techniques for securing digital information.
- Goals of cryptography include secret communication, authentication, secret/key management, and proof of security.
Actors in Classical Cryptography
- Alice: Message/Secret sender
- Bob: Message/Secret receiver
- Eve: Eavesdropper (wants to listen/intercept)
Terms in Classical Cryptography
- Plaintext (message) m: Original message
- Ciphertext c: Encrypted message
- Key k: Secret information
- Encryption function E(k, m): Converts a plaintext message into a ciphertext
- Decryption function D(k, c): Converts a ciphertext back into its plaintext
Types of Ciphers
- Symmetric (secret key) cryptography: Uses the same key for encryption and decryption
- Asymmetric (public key) cryptography: Uses different keys for encryption and decryption
- Block cipher: Processes data in blocks of, e.g., multiple bytes
- Stream cipher: Processes data character by character (or bit by bit)
Security Assumptions
- Perfect security does not exist in practice
- Some people always need to have access (inherent risk)
- Human factor is a risk in addition to technical aspects
- Any system is only as strong as its weakest link
- Threat model: Security only against certain attacks → How powerful is the attacker?
Kerckhoffs' Principle
- The security of a cipher only depends on the secrecy of the key
- Must not rely on the cipher/algorithm being secret
- Modern ciphers/algorithms are public
The Vernam Cipher
- Also called one-time pad (OTP)
- Provably secure if message m and key k have exactly the same length
- Key never reused
- Key bit string is uniformly distributed
- Ciphertext does not reveal anything about plaintext since all plaintexts are equally likely under a random key
Overview of Classical Ciphers
- Susceptible to various kinds of attacks
- No longer secure (do not use them)
- Examples of classical ciphers include Caesar cipher, Vigenère cipher, and Enigma
Caesar Cipher
- General idea: Shifting the alphabet by a constant offset (with rollover)
- Offset is the (cipher) key
- Poly-alphabetic substitution cipher
Vigenère Cipher
- General idea: Shifting the alphabet by a position-dependent offset (with rollover), repeated in regular intervals if necessary
- For individual characters: Caesar cipher with position-dependent key
- Poly-alphabetic substitution cipher
- Key length determines how many different shifts/position-dependent keys exist
Enigma
- Complex substitution cipher with multiple variants
- Machine-assisted encryption and decryption with code books
Overview of Cryptanalysis
- Dictionary definition: “the solving of [ciphers] or cryptographic systems”
- Old threat model: The cipher/algorithm is not known
- Modern threat model: The cipher is known
- Recap: Security only against certain attacks → How powerful is the attacker?
- Different attack scenarios
- Examples of simple cryptanalysis include frequency analysis and attacks on the Vigenère cipher
Attack Scenarios
- Different potential goals of an attacker
- Recover/decrypt plaintext from a particular ciphertext
- Recover key to recover plaintexts from arbitrary ciphertexts (stronger attacker)
Brute-Force Search Attack
- Try all possible keys until the correct one is found
- More work (processing power) for longer keys
- Key space: The set of all possible keys
- Infeasible key space sizes for attackers (e.g., 256 bits)
Simple Cryptanalysis Example: Frequency Analysis
- Assumption: Plaintext is a message in natural language, e.g., English
- The letter frequencies in natural-language texts are known
- Frequent characters in the English language are E, T, A,...### Simple Cryptanalysis Example: Frequency Analysis
- For mono-alphabetic substitution ciphers (e.g., Caesar), frequencies are expected to be similar, with corresponding letters being shifted.
- Consistent shift (in the alphabet) between similarly frequent characters allows offset/key recovery (some margin of error is useful!).
- Example: Most frequent letter (G vs. E) → Difference of +2 (C); Second-most frequent letter (V vs. T) → Difference of +2 (C)...→ Key is C.
- Caveat: Longer text required, as character frequencies only converge for longer, language-typical texts; foreign words harm analysis.
Attacks on the Vigenère Cipher: Frequency Analysis Attempt
- For poly-alphabetic substitution ciphers like Vigenère, frequency analysis on the whole ciphertext does not work.
- Same plaintext letter is mapped to different ci at different positions → Character frequencies are “smeared” (more for longer keys).
Attacks on the Vigenère Cipher: Modified Frequency Analysis
- Vigenère cipher is Caesar cipher with position-dependent key → slide 15.
- Key repeats every ||k|| positions: Vigenere(k, mi) = Caesar (ki mod ||k|| , mi) → slide 16.
- A Vigenère ciphertext is a merge of ||k|| Caesar ciphertexts: C0 = {ci : i mod ||k|| = 0}, ..., C||k||−1 = {ci : i mod ||k|| = ||k|| − 1}.
- If the key length ||k|| is known, perform frequency analysis on each Caesar ciphertext Cn individually and determine shift/key for each Caesar ciphertext.
- Combine keys of Caesar ciphertexts into Vigenère key.
Attacks on the Vigenère Cipher: Kasiski’s Method
- Key repeats every ||k|| positions → same plaintext words result in same ciphertext words if they are an integer multiple of ||k|| apart.
- In long texts, the same bigram/trigram/etc. appears at positions which are an integer multiple of ||k||.
- Differences in positions are very likely multiples of the key length → Greatest common divisor (gcd) of the position differences is very likely the key length or a multiple thereof.
Attacks on the Vigenère Cipher: Kasiski’s Method (continued)
- Example: WS bigram from example (→ slide 29): At positions 126, 294, 470, and 550 → Position differences 168, 80, and 80.
- Example: OQH trigram from example (→ slide 30): At positions 93 and 313 → Position difference 220.
- gcd(168, 80, 80, 220) = 4 → Key length is likely 4 or a multiple of 4.
- Alternative approach: Perform frequency analysis of the factors of the position differences (e.g., of all bigrams) → More/most frequent factors are very likely factors of the key length.
Attacks on the Vigenère Cipher: Auto-correlation
- Key repeats every ||k|| positions → Ciphertext characters which are an integer multiple of the key length apart are more likely to be the same.
- Compute incidence of identical characters (coincidence) at ciphertext character positions i + l for all ciphertext characters ci with any plausible key length l.
- Compute incidence Il for all plausible key lengths l ∈ N+ → Key length arg maxl Il with highest incidence is very likely the key length or a multiple thereof.
- Illustration of character coincidence (reference: R at position 2): Assuming key length of l = 4 → 3 out of 15 matches (20%); Assuming key length of l = 3 → 0 out of 20 matches (0%); Expected coincidence: ≈ 4% (in longer texts).
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
Learn about the basics of cryptography, including its definition and importance. This quiz covers the fundamental concepts of cryptography.
