Vigeneru

Platform: duckerz | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-01-09 | Status: Solved Techniques: index_of_coincidence, chi_squared_test, vigenere_cryptanalysis

Summary

Files: Vigeneru.pdf - PDF with encrypted text in Russian.

Vigeneru - duckerz CTF

Description

Нашел в одной книжке рассказ, зашифровал его и забыл ключ, помогите расшифровать текст. Полученное слово для флага необходимо зашифровать с помощью sha256 и подставить к флагу, чтобы получилось DUCKERZ{sha256(word)}

Files: Vigeneru.pdf - PDF with encrypted text in Russian.

Analysis

1. Extracting the ciphertext

Encrypted text in Russian (Cyrillic) was extracted from the PDF:

ьооьчосштицрувюунхэонпбиыойбшядйафаайихькгшщтнтввуячньвтъьчцабнпютэфттк
шзшудншщскуеоюппщхмечэпщбэмшпчхрвмшпяцэпаячхкьртпшсёртеьусуэфкайёпсрмп
...

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

2. Identifying the cipher type

Signs of Vigenère cipher:

• Text in Russian (33-letter alphabet)
• Text structure preserved (no transposition)
• Task name hints at Vigenère

3. Determining key length (Index of Coincidence)

Index of Coincidence (IC) - the probability that two randomly selected letters from the text are the same.

• For Russian language: IC ≈ 0.055
• For random text: IC ≈ 0.030 (1/33)

Method: split the text into groups by position (mod key_length) and calculate the average IC.

 python read-only • copy allowed Copy
def index_of_coincidence(text):
    n = len(text)
    if n <= 1:
        return 0
    freq = Counter(text)
    return sum(f * (f - 1) for f in freq.values()) / (n * (n - 1))
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Test key lengths 1-19
for key_len in range(1, 20):
    groups = [text[i::key_len] for i in range(key_len)]
    avg_ic = sum(index_of_coincidence(g) for g in groups) / key_len
    print(f"Key length {key_len}: IC = {avg_ic:.4f}")

Result:

• Length 7: IC ≈ 0.053 (close to Russian language!)
• Other lengths: IC ≈ 0.034 (random text)

4. Key recovery (Chi-squared test)

For each of the 7 positions, try all 33 letters as the key character and select the one that produces a frequency distribution closest to Russian. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 python read-only • copy allowed Copy
RUSSIAN_FREQ = {
    'о': 0.1097, 'е': 0.0845, 'а': 0.0801, 'и': 0.0735, 'н': 0.0670,
    'т': 0.0626, 'с': 0.0547, 'р': 0.0473, 'в': 0.0454, 'л': 0.0440,
    'к': 0.0349, 'м': 0.0321, 'д': 0.0298, 'п': 0.0281, 'у': 0.0262,
    'я': 0.0201, 'ы': 0.0190, 'ь': 0.0174, 'г': 0.0170, 'з': 0.0165,
    'б': 0.0159, 'ч': 0.0144, 'й': 0.0121, 'х': 0.0097, 'ж': 0.0094,
    'ш': 0.0073, 'ю': 0.0064, 'ц': 0.0048, 'щ': 0.0036, 'э': 0.0032,
    'ф': 0.0026, 'ъ': 0.0004, 'ё': 0.0004
}

def chi_squared(text):
    n = len(text)
    freq = Counter(text)
    chi2 = 0
    for char in ALPHABET:
        observed = freq.get(char, 0)
        expected = RUSSIAN_FREQ.get(char, 0.001) * n
        chi2 += (observed - expected) ** 2 / expected
    return chi2

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

For each position, select the letter with the minimum chi-squared.

Key found: подкова

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
Vigeneru - duckerz CTF
Vigenère cipher cryptanalysis for Russian text
"""

from collections import Counter
import hashlib

ALPHABET = 'абвгдеёжзийклмнопрстуфхцчшщъыьэюя'
ALPHABET_SIZE = len(ALPHABET)

# Russian letter frequencies
RUSSIAN_FREQ = {
    'о': 0.1097, 'е': 0.0845, 'а': 0.0801, 'и': 0.0735, 'н': 0.0670,
    'т': 0.0626, 'с': 0.0547, 'р': 0.0473, 'в': 0.0454, 'л': 0.0440,
    'к': 0.0349, 'м': 0.0321, 'д': 0.0298, 'п': 0.0281, 'у': 0.0262,
    'я': 0.0201, 'ы': 0.0190, 'ь': 0.0174, 'г': 0.0170, 'з': 0.0165,
    'б': 0.0159, 'ч': 0.0144, 'й': 0.0121, 'х': 0.0097, 'ж': 0.0094,
    'ш': 0.0073, 'ю': 0.0064, 'ц': 0.0048, 'щ': 0.0036, 'э': 0.0032,
    'ф': 0.0026, 'ъ': 0.0004, 'ё': 0.0004
}
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def char_to_num(c):
    return ALPHABET.index(c)

def num_to_char(n):
    return ALPHABET[n % ALPHABET_SIZE]

def decrypt_char(c, k):
    """Decrypt single character: plaintext = ciphertext - key (mod 33)"""
    return num_to_char(char_to_num(c) - char_to_num(k))

def decrypt_vigenere(ciphertext, key):
    """Decrypt full text with Vigenère cipher"""
    return ''.join(
        decrypt_char(c, key[i % len(key)]) 
        for i, c in enumerate(ciphertext)
    )

def index_of_coincidence(text):
    """Calculate Index of Coincidence"""
    n = len(text)
    if n <= 1:
        return 0
    freq = Counter(text)
    return sum(f * (f - 1) for f in freq.values()) / (n * (n - 1))
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def find_key_length(ciphertext, max_len=20):
    """Find key length using IC method"""
    results = []
    for key_len in range(1, max_len):
        groups = [ciphertext[i::key_len] for i in range(key_len)]
        avg_ic = sum(index_of_coincidence(g) for g in groups) / key_len
        results.append((key_len, avg_ic))
        print(f"Key length {key_len:2d}: IC = {avg_ic:.4f}")
    
    # Return length with highest IC (closest to Russian ~0.055)
    return max(results, key=lambda x: x[1])[0]

def chi_squared(text):
    """Calculate chi-squared statistic against Russian frequencies"""
    n = len(text)
    if n == 0:
        return float('inf')
    freq = Counter(text)
    chi2 = 0
    for char in ALPHABET:
        observed = freq.get(char, 0)
        expected = RUSSIAN_FREQ.get(char, 0.001) * n
        chi2 += (observed - expected) ** 2 / expected
    return chi2
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def find_key(ciphertext, key_length):
    """Find key using chi-squared frequency analysis"""
    key = []
    for i in range(key_length):
        group = ciphertext[i::key_length]
        best_char = None
        best_chi2 = float('inf')
        
        for key_char in ALPHABET:
            decrypted = ''.join(decrypt_char(c, key_char) for c in group)
            chi2 = chi_squared(decrypted)
            if chi2 < best_chi2:
                best_chi2 = chi2
                best_char = key_char
        
        key.append(best_char)
        print(f"Position {i}: best key char = '{best_char}' (chi2 = {best_chi2:.2f})")
    
    return ''.join(key)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Main solution
ciphertext = "..."  # Full ciphertext from PDF

# Step 1: Find key length
print("=== Finding key length ===")
key_length = find_key_length(ciphertext)
print(f"\nBest key length: {key_length}")

# Step 2: Find key
print("\n=== Finding key ===")
key = find_key(ciphertext, key_length)
print(f"\nKey found: {key}")

# Step 3: Decrypt
plaintext = decrypt_vigenere(ciphertext, key)
print(f"\n=== Decrypted text ===")
print(plaintext[:500] + "...")

# Step 4: Find flag word in text
# Text contains: "...слово для флага это хроносплетение..."
flag_word = "хроносплетение"
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Step 5: Calculate SHA256
sha256_hash = hashlib.sha256(flag_word.encode('utf-8')).hexdigest()
print(f"\n=== Flag ===")
print(f"Flag word: {flag_word}")
print(f"SHA256: {sha256_hash}")
print(f"DUCKERZ{{{sha256_hash}}}")

Decryption result

Key: подкова

The decrypted text is a story about a boy named Maxim traveling through time. Hidden in the text is the phrase:

"...взглянуть слово для флага это хроносплетение на пергамент..."

Flag calculation

 python read-only • copy allowed Copy
import hashlib
flag_word = "хроносплетение"
sha256_hash = hashlib.sha256(flag_word.encode('utf-8')).hexdigest()
# REDACTED

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Notes

1. Index of Coincidence - key method for determining key length:

   • IC of Russian language ≈ 0.055
   • IC of random text ≈ 0.030
   • Correct key length gives IC close to the language

2. Chi-squared test - for recovering each key character:

   • Compare frequencies of decrypted text with reference frequencies
   • Minimum chi-squared = best match

3. Careful reading - the flag word was NOT the encryption key, but a word hidden in the decrypted text!

Theory

Vigenère cipher:

Encryption: C[i] = (P[i] + K[i mod len(K)]) mod N Decryption: P[i] = (C[i] - K[i mod len(K)]) mod N ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Where:

• P - plaintext
• C - ciphertext
• K - key
• N - alphabet size (33 for Russian)

Vulnerability: key periodicity allows applying frequency analysis to each position separately. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍