Vigenère Cipher — Key Reuse Breaks 'Unbreakable' Encryption

# io.thecodeforge.crypto.classical.VigenereCipher

def vigenere_encrypt(text: str, key: str) -> str:
    """Encrypt plaintext using Vigenère cipher with the given key.

    Non-alphabetic characters pass through unchanged.
    The key is case-insensitive — all shifts use uppercase key values.
    """
    key = key.upper()
    result = []
    ki = 0  # key index — only increments for alphabetic characters
    for ch in text:
        if ch.isalpha():
            base = ord('A') if ch.isupper() else ord('a')
            shift = ord(key[ki % len(key)]) - ord('A')
            result.append(chr((ord(ch) - base + shift) % 26 + base))
            ki += 1
        else:
            result.append(ch)  # spaces, punctuation pass through
    return ''.join(result)


def vigenere_decrypt(text: str, key: str) -> str:
    """Decrypt Vigenère ciphertext with the given key."""
    key = key.upper()
    result = []
    ki = 0
    for ch in text:
        if ch.isalpha():
            base = ord('A') if ch.isupper() else ord('a')
            shift = ord(key[ki % len(key)]) - ord('A')
            result.append(chr((ord(ch) - base - shift) % 26 + base))
            ki += 1
        else:
            result.append(ch)
    return ''.join(result)


# --- Step-by-step trace to show exactly how encryption works ---
def vigenere_trace(text: str, key: str):
    """Print a letter-by-letter trace of the Vigenère encryption."""
    key = key.upper()
    ki = 0
    print(f"  {'Pos':>3}  {'Plain':>5}  {'Key':>3}  {'Shift':>5}  {'Cipher':>6}")
    print(f"  {'---':>3}  {'-----':>5}  {'---':>3}  {'-----':>5}  {'------':>6}")
    for i, ch in enumerate(text):
        if ch.isalpha():
            base = ord('A') if ch.isupper() else ord('a')
            p_val = ord(ch) - base
            k_letter = key[ki % len(key)]
            k_val = ord(k_letter) - ord('A')
            c_val = (p_val + k_val) % 26
            c_letter = chr(c_val + base)
            print(f"  {i:>3}  {ch:>5}  {k_letter:>3}  {k_val:>5}  {c_letter:>6}")
            ki += 1
        else:
            print(f"  {i:>3}  {repr(ch):>5}  {'—':>3}  {'—':>5}  {repr(ch):>6}")


# --- Basic demo ---
plaintext = 'ATTACKATDAWN'
key = 'LEMON'
ct = vigenere_encrypt(plaintext, key)
print(f"Plaintext:  {plaintext}")
print(f"Key:        {key}")
print(f"Ciphertext: {ct}")
print(f"Decrypted:  {vigenere_decrypt(ct, key)}")
print()
print("Encryption trace:")
vigenere_trace(plaintext, key)

# --- Tabula Recta (first 10 rows/cols for reference) ---
print("\nTabula Recta (partial):")
print(f"  {'':>3}", end='')
for c in 'ABCDEFGHIJ':
    print(f" {c}", end='')
print()
for row_letter in 'ABCDEFGHIJ':
    print(f"  {row_letter} ", end='')
    for col_letter in 'ABCDEFGHIJ':
        val = (ord(row_letter) - ord('A') + ord(col_letter) - ord('A')) % 26
        print(f" {chr(val + ord('A'))}", end='')
    print()

# io.thecodeforge.crypto.analysis.KasiskiExamination

from math import gcd
from functools import reduce
from collections import Counter


def kasiski_distances(ciphertext: str, min_len: int = 3, max_len: int = 5) -> list:
    """Find all distances between repeated ciphertext substrings.

    Returns a list of (substring, position1, position2, distance) tuples
    so you can inspect exactly what the test found.
    """
    ct = ''.join(c for c in ciphertext.upper() if c.isalpha())
    repeats = []

    for length in range(min_len, max_len + 1):
        seen = {}  # substring -> first position
        for i in range(len(ct) - length + 1):
            substr = ct[i:i + length]
            if substr in seen:
                distance = i - seen[substr]
                repeats.append((substr, seen[substr], i, distance))
            else:
                seen[substr] = i

    return repeats


def kasiski_key_length(ciphertext: str, min_len: int = 3) -> int:
    """Estimate Vigenère key length using the Kasiski examination.

    Strategy: collect all distances between repeated substrings,
    factor each distance, and return the most common factor > 1.
    """
    ct = ''.join(c for c in ciphertext.upper() if c.isalpha())
    distances = []

    for length in range(min_len, min_len + 5):
        seen = {}
        for i in range(len(ct) - length + 1):
            substr = ct[i:i + length]
            if substr in seen:
                distances.append(i - seen[substr])
            else:
                seen[substr] = i

    if not distances:
        return 1

    # Factor each distance and count factor frequencies
    factor_counts = Counter()
    for d in distances:
        for f in range(2, d + 1):
            if d % f == 0:
                factor_counts[f] += 1

    # Return the most common factor
    most_common_factor = factor_counts.most_common(1)[0][0]
    return most_common_factor


# --- Demonstrate with a real example ---
plaintext = (
    'THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG'
    'THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG'
    'THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG'
)
key = 'CRYPTO'
ct = vigenere_encrypt(plaintext, key)

print(f"Ciphertext (first 60 chars): {ct[:60]}...")
print(f"True key length: {len(key)}")

# Show repeated substrings
repeats = kasiski_distances(ct, min_len=3)
print(f"\nFound {len(repeats)} repeated substring pairs (showing first 10):")
for substr, pos1, pos2, dist in repeats[:10]:
    print(f"  '{substr}' at positions {pos1} and {pos2}, distance = {dist}")

# Estimate key length
estimated = kasiski_key_length(ct)
print(f"\nKasiski estimated key length: {estimated}")
print(f"Divisors to also check: {[d for d in range(2, estimated+1) if estimated % d == 0]}")

# Show distances and their GCD
distances_only = [r[3] for r in repeats]
if distances_only:
    overall_gcd = reduce(gcd, distances_only)
    print(f"GCD of all distances: {overall_gcd}")

# io.thecodeforge.crypto.analysis.IndexOfCoincidence

from collections import Counter


def index_of_coincidence(text: str) -> float:
    """Compute the Index of Coincidence for the given text.

    IC = sum(f_i * (f_i - 1)) / (N * (N - 1))
    where f_i is frequency of each letter, N is total letter count.

    English text: IC ≈ 0.065
    Random text:  IC ≈ 0.038 (1/26)
    """
    letters = [c for c in text.upper() if c.isalpha()]
    n = len(letters)
    if n < 2:
        return 0.0
    counts = Counter(letters)
    return sum(c * (c - 1) for c in counts.values()) / (n * (n - 1))


def friedman_key_estimate(ciphertext: str) -> float:
    """Estimate key length using Friedman's IC-based formula.

    key_length ≈ (kappa_p - kappa_r) / (IC_ct - kappa_r)
    where kappa_p = 0.065 (English IC) and kappa_r = 0.0385 (random IC)
    """
    ic = index_of_coincidence(ciphertext)
    kappa_p = 0.065   # IC for English plaintext
    kappa_r = 0.0385  # IC for random/uniform distribution
    if abs(ic - kappa_r) < 0.001:
        return float('inf')  # IC too close to random
    return (kappa_p - kappa_r) / (ic - kappa_r)


def ic_sweep(ciphertext: str, max_key_len: int = 20) -> list:
    """Test every possible key length and return average IC per stream.

    For each candidate key length k, split ciphertext into k streams
    (every k-th letter), compute IC for each stream, and average.
    The key length with the highest average IC is most likely correct.
    """
    ct = ''.join(c for c in ciphertext.upper() if c.isalpha())
    results = []

    for k in range(1, max_key_len + 1):
        stream_ics = []
        for offset in range(k):
            stream = ct[offset::k]
            if len(stream) >= 2:
                stream_ics.append(index_of_coincidence(stream))
        avg_ic = sum(stream_ics) / len(stream_ics) if stream_ics else 0
        results.append((k, avg_ic))

    return results


# --- Demonstrate IC on different text types ---
english_text = "THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG"
random_text = "XQJKVBZPYGWMFUCLDHRSNIOAET"  # shuffled alphabet, no repetition

print("Index of Coincidence for different text types:")
print(f"  English text:     IC = {index_of_coincidence(english_text):.4f}  (expect ~0.065)")
print(f"  Random/shuffled:  IC = {index_of_coincidence(random_text):.4f}  (expect ~0.038)")

# Vigenère ciphertext should have intermediate IC
long_english = "THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG" * 10
vigenere_ct = vigenere_encrypt(long_english, "SECRET")
print(f"  Vigenère (6-key): IC = {index_of_coincidence(vigenere_ct):.4f}  (between 0.038 and 0.065)")

# Friedman estimate
friedman_est = friedman_key_estimate(vigenere_ct)
print(f"\nFriedman key length estimate: {friedman_est:.1f}  (true: 6)")

# IC sweep to find best key length
print("\nIC sweep (average IC per stream for each candidate key length):")
sweep_results = ic_sweep(vigenere_ct, max_key_len=12)
for k, avg_ic in sweep_results:
    bar = '█' * int(avg_ic * 500)
    marker = ' ← best' if avg_ic == max(r[1] for r in sweep_results) else ''
    print(f"  k={k:>2}: IC={avg_ic:.4f}  {bar}{marker}")

# io.thecodeforge.crypto.analysis.VigenereCryptanalysis

from collections import Counter
import string

# Expected English letter frequencies
ENGLISH_FREQ = {
    'A': 0.08167, 'B': 0.01492, 'C': 0.02782, 'D': 0.04253,
    'E': 0.12702, 'F': 0.02228, 'G': 0.02015, 'H': 0.06094,
    'I': 0.06966, 'J': 0.00153, 'K': 0.00772, 'L': 0.04025,
    'M': 0.02406, 'N': 0.06749, 'O': 0.07507, 'P': 0.01929,
    'Q': 0.00095, 'R': 0.05987, 'S': 0.06327, 'T': 0.09056,
    'U': 0.02758, 'V': 0.00978, 'W': 0.02360, 'X': 0.00150,
    'Y': 0.01974, 'Z': 0.00074
}


def chi_squared(observed_counts: Counter, total: int, shift: int) -> float:
    """Compute chi-squared statistic for a given Caesar shift.

    Rotates observed frequencies by 'shift' positions and compares
    against expected English frequencies.
    Lower is better — means the shifted distribution matches English.
    """
    chi2 = 0.0
    for i in range(26):
        # Which ciphertext letter maps to plaintext letter i after shifting?
        ct_letter = chr((i + shift) % 26 + ord('A'))
        observed = observed_counts.get(ct_letter, 0)
        expected = ENGLISH_FREQ[chr(i + ord('A'))] * total
        if expected > 0:
            chi2 += (observed - expected) ** 2 / expected
    return chi2


def crack_caesar_stream(stream: str) -> tuple:
    """Find the best Caesar shift for a single stream of letters.

    Returns (shift, key_letter, chi_squared_value).
    """
    counts = Counter(stream.upper())
    total = len(stream)
    best_shift = 0
    best_chi2 = float('inf')

    for shift in range(26):
        chi2 = chi_squared(counts, total, shift)
        if chi2 < best_chi2:
            best_chi2 = chi2
            best_shift = shift

    key_letter = chr(best_shift + ord('A'))
    return best_shift, key_letter, best_chi2


def crack_vigenere(ciphertext: str, key_length: int) -> str:
    """Full Vigenère cryptanalysis: given ciphertext and key length,
    recover the key using per-stream frequency analysis.
    """
    ct = ''.join(c for c in ciphertext.upper() if c.isalpha())
    key_chars = []

    print(f"  {'Stream':>6}  {'Key':>3}  {'Shift':>5}  {'Chi2':>8}  {'Sample decrypted'}")
    print(f"  {'------':>6}  {'---':>3}  {'-----':>5}  {'--------':>8}  {'----------------'}")

    for i in range(key_length):
        stream = ct[i::key_length]
        shift, key_letter, chi2 = crack_caesar_stream(stream)
        key_chars.append(key_letter)

        # Show first 20 decrypted chars of this stream
        sample = ''.join(
            chr((ord(c) - ord('A') - shift) % 26 + ord('A'))
            for c in stream[:20]
        )
        print(f"  {i:>6}  {key_letter:>3}  {shift:>5}  {chi2:>8.2f}  {sample}")

    recovered_key = ''.join(key_chars)
    return recovered_key


# --- Full attack demonstration ---
original_plaintext = (
    "CRYPTOGRAPHYISTHEPRACTICEANDSTUDYOFTECHNIQUESFOR"
    "PROTECTINGINFORMATIONINPRESENCEOFADVERSARIES"
)
secret_key = "BLETCHLEY"
print(f"Original plaintext: {original_plaintext[:50]}...")
print(f"Secret key:         {secret_key}")
print(f"Key length:         {len(secret_key)}")

ciphertext = vigenere_encrypt(original_plaintext, secret_key)
print(f"Ciphertext:         {ciphertext[:50]}...")
print()

# Step 1: Estimate key length
print("Step 1: Key length estimation")
friedman_est = friedman_key_estimate(ciphertext)
print(f"  Friedman estimate: {friedman_est:.1f}")

sweep = ic_sweep(ciphertext, max_key_len=15)
best_k = max(sweep, key=lambda x: x[1])
print(f"  IC sweep best:     k={best_k[0]} (avg IC={best_k[1]:.4f})")
print()

# Step 2-3: Crack the key
print(f"Step 2-3: Per-stream frequency analysis (key length = {best_k[0]})")
recovered_key = crack_vigenere(ciphertext, best_k[0])
print(f"\nRecovered key: {recovered_key}")
print()

# Step 4: Decrypt and verify
print("Step 4: Decryption with recovered key")
decrypted = vigenere_decrypt(ciphertext, recovered_key)
print(f"Decrypted: {decrypted[:60]}...")
print(f"Match: {decrypted == original_plaintext}")

# io.thecodeforge.crypto.comparison.CipherComparison

import os
import hashlib


def one_time_pad_encrypt(plaintext: str, key: bytes) -> str:
    """Encrypt using XOR with a truly random key (One-Time Pad principle).

    Key must be at least as long as the plaintext.
    This is the theoretical 'unbreakable' cipher — IF the key is truly
    random, never reused, and kept secret.
    """
    pt_bytes = plaintext.encode('utf-8')
    if len(key) < len(pt_bytes):
        raise ValueError("Key must be at least as long as plaintext")
    ct_bytes = bytes(p ^ k for p, k in zip(pt_bytes, key[:len(pt_bytes)]))
    return ct_bytes.hex()


def one_time_pad_decrypt(ciphertext_hex: str, key: bytes) -> str:
    """Decrypt One-Time Pad ciphertext."""
    ct_bytes = bytes.fromhex(ciphertext_hex)
    pt_bytes = bytes(c ^ k for c, k in zip(ct_bytes, key[:len(ct_bytes)]))
    return pt_bytes.decode('utf-8')


def simple_stream_cipher_encrypt(plaintext: str, key: str) -> str:
    """Simplified stream cipher using SHA-256 as CSPRNG.

    This demonstrates the modern approach: use a short key to seed
    a cryptographically secure pseudorandom generator that produces
    an effectively infinite non-repeating keystream.

    NOTE: This is for educational purposes — use ChaCha20 or AES-CTR
    from the 'cryptography' library for real applications.
    """
    pt_bytes = plaintext.encode('utf-8')
    keystream = b''
    block = key.encode('utf-8')
    while len(keystream) < len(pt_bytes):
        block = hashlib.sha256(block).digest()
        keystream += block
    ct_bytes = bytes(p ^ k for p, k in zip(pt_bytes, keystream[:len(pt_bytes)]))
    return ct_bytes.hex()


def simple_stream_cipher_decrypt(ciphertext_hex: str, key: str) -> str:
    """Decrypt simple stream cipher ciphertext."""
    ct_bytes = bytes.fromhex(ciphertext_hex)
    keystream = b''
    block = key.encode('utf-8')
    while len(keystream) < len(ct_bytes):
        block = hashlib.sha256(block).digest()
        keystream += block
    pt_bytes = bytes(c ^ k for c, k in zip(ct_bytes, keystream[:len(ct_bytes)]))
    return pt_bytes.decode('utf-8')


# --- Compare all three approaches ---
message = "MEETMEATTHEOLDCABINATMIDNIGHTBRINGTHEPLANS"

print("=" * 60)
print("CIPHER COMPARISON")
print("=" * 60)

# 1. Vigenère
vig_key = "SECRET"
vig_ct = vigenere_encrypt(message, vig_key)
print(f"\n1. VIGENÈRE (key='{vig_key}', length={len(vig_key)})")
print(f"   Ciphertext: {vig_ct}")
print(f"   Key repeats every {len(vig_key)} characters")
print(f"   Vulnerable to: Kasiski test, IC analysis, frequency analysis")

# 2. One-Time Pad
otp_key = os.urandom(len(message))  # truly random, same length as message
otp_ct = one_time_pad_encrypt(message, otp_key)
print(f"\n2. ONE-TIME PAD (key length={len(otp_key)} bytes, truly random)")
print(f"   Ciphertext: {otp_ct[:60]}...")
print(f"   Key never repeats — unbreakable if key is kept secret")
print(f"   Vulnerable to: nothing (mathematically proven secure)")
print(f"   Practical problem: key distribution at scale")

# 3. Stream cipher
stream_key = "short_secret_key_16"  # 18 characters → 144 bits of entropy
stream_ct = simple_stream_cipher_encrypt(message, stream_key)
print(f"\n3. STREAM CIPHER (key='{stream_key}', length={len(stream_key)} chars)")
print(f"   Ciphertext: {stream_ct[:60]}...")
print(f"   Key is short but generates infinite non-repeating keystream")
print(f"   Vulnerable to: nothing practical (CSPRNG is computationally secure)")

# Show decryption works
stream_dec = simple_stream_cipher_decrypt(stream_ct, stream_key)
print(f"   Decrypted: {stream_dec[:30]}... matches? {stream_dec == message}")

# Show key length comparison
print(f"\n{'Cipher':<20} {'Key length':<15} {'Repeats?':<12} {'Broken?'}")
print(f"{'-'*20} {'-'*15} {'-'*12} {'-'*12}")
print(f"{'Vigenère':<20} {str(len(vig_key))+' chars':<15} {'Yes':<12} {'Yes (Kasiski)'}")
print(f"{'One-Time Pad':<20} {str(len(otp_key))+' bytes':<15} {'No':<12} {'No (proven)'}")
print(f"{'Stream Cipher':<20} {str(len(stream_key))+' chars':<15} {'No (practical)':<12} {'No (practical)'}")

# io.thecodeforge.crypto.pitfalls.VigenerePitfalls


def demonstrate_key_index_bug():
    """Show the most common implementation bug: key index drift."""
    print("=== Bug: Key Index Drifts on Non-Alphabetic Characters ===")
    print()

    def buggy_encrypt(text, key):
        """WRONG: increments key index for every character."""
        key = key.upper()
        result = []
        ki = 0
        for ch in text:
            if ch.isalpha():
                base = ord('A') if ch.isupper() else ord('a')
                shift = ord(key[ki % len(key)]) - ord('A')
                result.append(chr((ord(ch) - base + shift) % 26 + base))
            else:
                result.append(ch)
            ki += 1  # BUG: increments even for spaces!
        return ''.join(result)

    def correct_encrypt(text, key):
        """RIGHT: only increments key index for alphabetic characters."""
        key = key.upper()
        result = []
        ki = 0
        for ch in text:
            if ch.isalpha():
                base = ord('A') if ch.isupper() else ord('a')
                shift = ord(key[ki % len(key)]) - ord('A')
                result.append(chr((ord(ch) - base + shift) % 26 + base))
                ki += 1  # CORRECT: only increments for letters
            else:
                result.append(ch)
        return ''.join(result)

    plaintext = 'HELLO WORLD'
    key = 'KEY'

    buggy_ct = buggy_encrypt(plaintext, key)
    correct_ct = correct_encrypt(plaintext, key)

    print(f"  Plaintext: '{plaintext}'")
    print(f"  Key:       '{key}'")
    print(f"  Buggy:     '{buggy_ct}'")
    print(f"  Correct:   '{correct_ct}'")
    print(f"  Match:     {buggy_ct == correct_ct}")
    print()
    print("  The buggy version shifts 'WORLD' using key positions 4,5,6")
    print("  instead of 3,4,5 — the space consumed a key position.")
    print("  Decryption with the correct function produces garbage.")


def demonstrate_short_text_problem():
    """Show why short texts break frequency analysis."""
    print("\n=== Problem: Short Texts Have Unreliable Statistics ===")
    print()

    short_text = 'ATTACK'
    long_text = 'THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG' * 20
    key = 'AB'

    ct_short = vigenere_encrypt(short_text, key)
    ct_long = vigenere_encrypt(long_text, key)

    # Each stream for key length 2
    short_stream_0 = ct_short[0::2]  # positions 0,2,4
    short_stream_1 = ct_short[1::2]  # positions 1,3,5
    long_stream_0 = ct_long[0::2]
    long_stream_1 = ct_long[1::2]

    print(f"  Short text ({len(short_text)} chars): '{short_text}'")
    print(f"    Stream 0: '{short_stream_0}' ({len(short_stream_0)} letters — too few for frequency analysis)")
    print(f"    Stream 1: '{short_stream_1}' ({len(short_stream_1)} letters — too few for frequency analysis)")
    print(f"    IC stream 0: {index_of_coincidence(short_stream_0):.3f} (meaningless with <20 letters)")
    print()
    print(f"  Long text ({len(long_text)} chars)")
    print(f"    Stream 0: {len(long_stream_0)} letters")
    print(f"    Stream 1: {len(long_stream_1)} letters")
    print(f"    IC stream 0: {index_of_coincidence(long_stream_0):.3f} (reliable)")
    print()
    print("  Rule of thumb: need 100+ characters per stream for reliable IC.")
    print("  With key length k, total ciphertext should be at least 100*k characters.")


def demonstrate_case_handling_bug():
    """Show bug with mixed case."""
    print("\n=== Bug: Mixed Case Causing Incorrect Shifts ===")
    print()

    def buggy_case_encrypt(text, key):
        """WRONG: doesn't normalise case."""
        result = []
        ki = 0
        for ch in text:
            if ch.isalpha():
                # BUG: uses ASCII values directly — 'a' (97) vs 'A' (65) cause different shifts
                shift = ord(key[ki % len(key)].upper()) - ord('A')
                ct_val = ord(ch) + shift
                # This is completely broken for lowercase plaintext
                result.append(chr(ct_val))
                ki += 1
            else:
                result.append(ch)
        return ''.join(result)

    def correct_case_encrypt(text, key):
        """RIGHT: normalise to uppercase before arithmetic."""
        key = key.upper()
        result = []
        ki = 0
        for ch in text:
            if ch.isalpha():
                base = ord('A') if ch.isupper() else ord('a')
                shift = ord(key[ki % len(key)]) - ord('A')
                result.append(chr((ord(ch) - base + shift) % 26 + base))
                ki += 1
            else:
                result.append(ch)
        return ''.join(result)

    plaintext = 'AttackAtDawn'
    key = 'LEMON'

    buggy_ct = buggy_case_encrypt(plaintext, key)
    correct_ct = correct_case_encrypt(plaintext, key)

    print(f"  Plaintext: '{plaintext}'")
    print(f"  Key: '{key}'")
    print(f"  Buggy (no normalisation): '{buggy_ct}'")
    print(f"  Correct: '{correct_ct}'")
    print(f"  Expected: LXFOPVEFRNHR")


demonstrate_key_index_bug()
demonstrate_short_text_problem()
demonstrate_case_handling_bug()