Смежный (Contiguous)

Platform: duckerz | Category: Crypto | Type: Challenge | Difficulty: Easy | OS: Linux | Author: XESXOR | Date: 2026-01-09 | Status: Solved Techniques: affine_decryption, modular_inverse

Summary

Task: Decrypt ciphertext encrypted with affine cipher where parameters a=7 and b=20 are known. Solution: Calculate modular inverse of a (a^(-1)=15) and apply decryption formula D(y) = a^(-1) * (y - b) mod 26.

Смежный (Contiguous) — duckerz CTF

Description

Ко мне в руки попал алгоритм шифрования и результат его работы. Ключа, конечно же, у меня нет.

(Translation: "I got my hands on an encryption algorithm and its output. Of course, I don't have the key.")

Files:

• encoder.py — encryption script
• res.txt — encrypted result

Analysis

encoder.py

 python read-only • copy allowed Copy
from secret import FLAG

cp = ""
a = 7
b = 20

for letter in FLAG:
    if letter.isalpha():
        if letter.islower():
            tmp = ord(letter) - ord('a')
            enc = (a * tmp + b) % 26
            cp += chr(enc + ord('a'))     
        else:
            tmp = ord(letter) - ord('A')
            enc = (a * tmp + b) % 26
            cp += chr(enc + ord('A'))
    else:
        cp += letter
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

with open('res.txt', 'w') as file:
    file.write(cp)

res.txt

PEIMWJN{xr3_udd1h3_iyvr3j_1q_qx1tt_h0x_q0_j3t14bt3}

Cipher Identification

This is a classic Affine cipher with the formula:

E(x) = (a * x + b) mod 26

Where:

• a = 7 — multiplier
• b = 20 — shift
• x — letter position in the alphabet (0-25)

Features:

• Case is preserved (upper/lower handled separately)
• Non-letter characters are unchanged (digits, {, }, _)

Solution

Decryption Math

To decrypt the affine cipher, we need to find the inverse function:

D(y) = a^(-1) * (y - b) mod 26

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

Where a^(-1) is the modular multiplicative inverse of a modulo 26.

Finding a^(-1):

• We need to find a number such that a * a^(-1) ≡ 1 (mod 26)
• For a = 7: check 7 * 15 = 105 = 4 * 26 + 1 ≡ 1 (mod 26)
• Therefore a^(-1) = 15

Decryption Script

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
Affine Cipher Decoder
duckerz CTF - Contiguous
"""

a = 7
b = 20

def mod_inverse(a, m):
    """Finds the modular multiplicative inverse of a modulo m"""
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return None
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

a_inv = mod_inverse(a, 26)  # a_inv = 15

ciphertext = "PEIMWJN{xr3_udd1h3_iyvr3j_1q_qx1tt_h0x_q0_j3t14bt3}"

plaintext = ""
for letter in ciphertext:
    if letter.isalpha():
        if letter.islower():
            enc = ord(letter) - ord('a')
            dec = (a_inv * (enc - b)) % 26
            plaintext += chr(dec + ord('a'))
        else:
            enc = ord(letter) - ord('A')
            dec = (a_inv * (enc - b)) % 26
            plaintext += chr(dec + ord('A'))
    else:
        plaintext += letter
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

print(plaintext)

Execution

 bash read-only • copy allowed Copy
$ python3 solve.py
DUCKERZ{REDACTED}

Theory

Valid values for a: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25 (12 values)

Total number of keys: 12 * 26 = 312 (easy to brute force)

Alternative Approaches

1. Brute force — iterate through all 312 combinations of (a, b)
2. Known plaintext — if the flag format DUCKERZ{ is known, parameters can be calculated
3. Frequency analysis — for long texts without known plaintext ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

References

• Affine cipher - Wikipedia
• dCode Affine Cipher ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍