Vigenère Cipher — How It Works, Breaking It, and Python Implementation

The Vigenère cipher (1553) uses a repeating keyword to apply different Caesar shifts to each letter, foiling simple frequency analysis. It was considered unbreakable for 300 years until Kasiski cracked it in 1863.

Encode text with simple ciphers using the ROT13 Cipher.

How the Vigenère cipher works

Keyword: KEY  → K=10, E=4, Y=24 (shift amounts)
Plaintext:  HELLOWORLD
Keyword (repeating): KEYKEYKEYK

H + K(10) = R
E + E(4)  = I
L + Y(24) = J
L + K(10) = V
O + E(4)  = S
W + Y(24) = U
O + K(10) = Y
R + E(4)  = V
L + Y(24) = J
D + K(10) = N

Ciphertext: RIJVSUYV JN

Each letter of the keyword specifies a different Caesar shift. With keyword length n, there are n interleaved Caesar ciphers running simultaneously.

Python implementation

def vigenere_encrypt(plaintext: str, key: str) -> str:
    """Encrypt using Vigenère cipher."""
    result = []
    key = key.upper()
    key_len = len(key)
    key_idx = 0
    
    for char in plaintext.upper():
        if char.isalpha():
            shift = ord(key[key_idx % key_len]) - ord('A')
            encrypted = chr((ord(char) - ord('A') + shift) % 26 + ord('A'))
            result.append(encrypted)
            key_idx += 1
        else:
            result.append(char)  # Keep non-alphabetic characters
    
    return ''.join(result)

def vigenere_decrypt(ciphertext: str, key: str) -> str:
    """Decrypt using Vigenère cipher."""
    result = []
    key = key.upper()
    key_len = len(key)
    key_idx = 0
    
    for char in ciphertext.upper():
        if char.isalpha():
            shift = ord(key[key_idx % key_len]) - ord('A')
            decrypted = chr((ord(char) - ord('A') - shift) % 26 + ord('A'))
            result.append(decrypted)
            key_idx += 1
        else:
            result.append(char)
    
    return ''.join(result)

# Test:
ciphertext = vigenere_encrypt("HELLO WORLD", "KEY")
print(ciphertext)  # "RIJVS UYVJN"

plaintext = vigenere_decrypt("RIJVS UYVJN", "KEY")
print(plaintext)   # "HELLO WORLD"

Kasiski examination (breaking Vigenère)

The key insight: if the same plaintext substring happens to align with the same part of the key, it produces identical ciphertext. Find these repeated sequences to determine the key length.

def find_key_length(ciphertext: str) -> list[int]:
    """Kasiski test: find probable key lengths."""
    from collections import defaultdict
    from math import gcd
    from functools import reduce
    
    text = ciphertext.upper().replace(' ', '')
    positions = defaultdict(list)
    
    # Find all trigram (3-letter) repetitions and their positions:
    for i in range(len(text) - 3):
        trigram = text[i:i+3]
        positions[trigram].append(i)
    
    # Calculate distances between repeated trigrams:
    distances = []
    for trigram, pos_list in positions.items():
        if len(pos_list) > 1:
            for i in range(len(pos_list) - 1):
                distances.append(pos_list[i+1] - pos_list[i])
    
    if not distances:
        return []
    
    # Key length is likely a common factor of these distances:
    # Count factor frequencies:
    factor_count = defaultdict(int)
    for d in distances:
        for f in range(2, d + 1):
            if d % f == 0:
                factor_count[f] += 1
    
    # Return top 5 most likely key lengths:
    return sorted(factor_count, key=factor_count.get, reverse=True)[:5]

Index of Coincidence (finding key length)

def index_of_coincidence(text: str) -> float:
    """Calculate Index of Coincidence. English text ≈ 0.065."""
    text = ''.join(c for c in text.upper() if c.isalpha())
    n = len(text)
    if n < 2:
        return 0
    
    freqs = [text.count(chr(ord('A') + i)) for i in range(26)]
    return sum(f * (f - 1) for f in freqs) / (n * (n - 1))

def find_key_length_ic(ciphertext: str, max_key_len: int = 20) -> int:
    """Find key length using Index of Coincidence."""
    text = ''.join(c for c in ciphertext.upper() if c.isalpha())
    
    # For each candidate key length, split into k subsequences
    # and check if average IC matches English (≈0.065):
    best_len = 1
    best_ic = 0
    
    for key_len in range(1, max_key_len + 1):
        subsequences = [''.join(text[i::key_len]) for i in range(key_len)]
        avg_ic = sum(index_of_coincidence(s) for s in subsequences) / key_len
        
        if avg_ic > best_ic:
            best_ic = avg_ic
            best_len = key_len
    
    return best_len

Historical significance

Related tools

• ROT13 Cipher — Caesar cipher with shift of 13
• Caesar Cipher — single-shift substitution
• Hash Generator — modern cryptographic hashing