BabyEncryption

This challenge is a classic example of an Affine Cipher applied at the byte level. Here is a breakdown of how the encryption works and how to reverse it to retrieve the message.

Understanding the Encryption

The provided chall.py script performs a simple linear transformation on each character of the secret message. The mathematical formula for the encryption is:

$$E(x) = (ax + b) \pmod{n}$$

Based on the source code:

• $a = 123$ (Multiplicative key)

• $b = 18$ (Additive key/shift)

• $n = 256$ (The size of a byte)

For every character $x$ in the message, the script calculates $(123x + 18) \pmod{256}$ and stores the result as hex.

Decryption Strategy

To decrypt the message, we need to isolate $x$ in the equation. This requires using the modular multiplicative inverse of $a$ modulo $n$.

The decryption formula is:

$$D(y) = a^{-1} \cdot (y - b) \pmod{n}$$

Steps to Solve:

1. Find the Inverse: Calculate $123^{-1} \pmod{256}$. Since $123$ and $256$ are coprime, the inverse exists.

2. Subtract the Shift: Subtract $18$ from each ciphertext byte.

3. Multiply and Mod: Multiply by the inverse and take the result modulo $256$.

The Solution

from Crypto.Util.number import inverse

a = 123
b = 18
n = 256
y = "6e0a9372ec49a3f6930ed8723f9df6f6720ed8d89dc4937222ec7214d89d1e0e352ce0aa6ec82bf622227bb70e7fb7352249b7d893c493d8539dec8fb7935d490e7f9d22ec89b7a322ec8fd80e7f8921"
y = bytes.fromhex(y)

a_inv = inverse(a, n)

flag = []

for i in y:
    flag.append((a_inv * (i - b)) % n)

print(bytes(flag))