Affine Cipher

Affine Cipher

The affine cipher generalizes the Caesar cipher with a linear transformation over $\mathbb{Z}_{26}$.

Encryption

$E(x) = (a \cdot x + b) \bmod 26$

where $x$ is the letter value (A=0, …, Z=25), $a$ and $b$ are integer keys. $a$ must satisfy $\gcd(a, 26) = 1$ so that decryption is possible.

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

Decryption

$D(y) = a^{-1} \cdot (y - b) \bmod 26$

where $a^{-1}$ is the modular inverse of $a$ modulo 26.

Modular Inverse via Extended GCD

The Extended Euclidean Algorithm finds integers $x, y$ such that $ax + 26y = \gcd(a, 26)$. When $\gcd(a, 26) = 1$, we have $ax \equiv 1 \pmod{26}$, so $x$ is the modular inverse.

def extended_gcd(a, b):
    if b == 0: return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

def mod_inverse(a, m):
    g, x, _ = extended_gcd(a, m)
    return x % m   # ensure positive

mod_inverse(5, 26)   # 21, since 5*21 = 105 = 4*26+1

Example ($a=5$, $b=8$)

Your Task

Implement:

• mod_inverse(a, m) using extended GCD
• affine_encrypt(text, a, b) — apply affine transformation, preserve case, skip non-alpha
• affine_decrypt(text, a, b) — apply inverse transformation