Kasiski’s Method and the Principles of Modern Cryptography
Topic: Cryptography · Reading time: ~7–10 min
Contents
From Monoalphabetic Substitution to Polyalphabetic Ciphers
As we previously described, the classical statistical attack on a monoalphabetic substitution cipher is possible because the mapping between plaintext letters and ciphertext letters is fixed. Each plaintext character is always replaced by the same ciphertext character, so letter-frequency patterns remain visible to an attacker.
A natural way to reduce the effectiveness of frequency analysis is to map different instances of the same plaintext character to different ciphertext characters. This idea leads to polyalphabetic substitution ciphers, with the most famous example being the Vigenère cipher.
The Vigenère Cipher
The Vigenère cipher applies multiple shift (Caesar) ciphers in sequence. A short secret string is chosen as the key. Each plaintext character is encrypted by combining it with the corresponding key character, and the key repeats (wraps around) as needed.
Example
Encrypt the message tellhimaboutme using the key cafe.
| Item | Value |
|---|---|
| Plaintext | tellhimaboutme |
| Key | cafe |
| Repeated key | cafecafecafeca |
| Ciphertext | WFRQKJSFEPAYPF |
Conceptually: each plaintext letter is shifted by an amount determined by the corresponding key letter (typically computed modulo 26).
How to Break Vigenère
Let the length of the key be t. This is often called the period. If an attacker learns (or guesses) t, the ciphertext can be split into t subsequences: every t-th character belongs to the same subsequence.
Each subsequence is effectively encrypted with a single shift cipher. Therefore, classical statistical techniques can be applied:
- Compute the frequency distribution of letters for a subsequence.
- Try all 26 possible shifts.
- Select the shift whose decrypted output best matches expected English letter frequencies.
We can also use improved attacks on the shift cipher that do not rely on recognizing specific plaintext words, but instead compare distributions more directly.
Kasiski’s Method
A stronger method to recover the Vigenère key length is Kasiski’s method.
Step 1: Find repeated patterns
Search the ciphertext for repeated patterns of length 2 or 3 (repeated bigrams or trigrams). These repetitions are often caused by frequent English sequences that happen to align with the same key positions.
The key observation
The main observation of Kasiski is: the distance between repeated appearances of the same ciphertext pattern is likely to be a multiple of the period (key length).
So, by measuring distances between repeated patterns and taking the greatest common divisor (GCD) of those distances, an attacker can often infer the key length.
Illustrative example
Plaintext: the man and the woman retrieved the letter from the office
Key (repeating): beadsbeadsbeadsbeadsbeadsbeads...
Ciphertext:
VMF QTP FOH MJJ XSFCS SIMTNFZXF YIS EIYUIK HWPQ MJJ QSLV TGJKGFMain Principles of Modern Cryptography
Classical ciphers teach us what fails. Modern cryptography formalizes what it means to be secure and proves security under explicit assumptions.
- Definition first: The first step in solving any cryptographic problem is the formulation of a rigorous and precise definition of security.
- State assumptions clearly: When the security of a cryptographic construction relies on an unproven assumption, the assumption must be precisely stated and should be as minimal as possible.
- Prove security: Cryptographic constructions should be accompanied by a rigorous proof of security with respect to the chosen definition.
What is a Secure Encryption Scheme?
Intuitively, there are several possible definitions of what “secure encryption” might mean. Importantly, some are weaker than others.
- (1) Key recovery resistance: secure if no adversary can recover the secret key from a ciphertext.
- (2) Full plaintext recovery resistance: secure if no adversary can recover the plaintext from a ciphertext.
- (3) Partial leakage resistance: secure if no adversary can determine even a single character of the plaintext.
- (4) Meaningful information resistance: secure if no adversary can derive any meaningful information about the plaintext.
In its strongest form, we aim for the idea that:
An encryption scheme is secure if no adversary can compute any function of the plaintext from the ciphertext.
This last idea is close in spirit to what modern cryptography formalizes through notions like semantic security—the goal that ciphertext should reveal essentially nothing about the underlying message.