Affine Cipher

Nerd Cafe

The Affine Cipher is a type of substitution cipher that uses a mathematical function to encrypt and decrypt messages. Here's a step-by-step guide with a practical example:

Step 1: Understand the Encryption Formula

The Affine Cipher encryption formula is:

$$E(x)=(a.x+b)\;\;mod\;\;m$$

Where:

• 𝑥 is the numerical value of a letter (e.g., A = 0, B = 1, ..., Z = 25 for English).

• 𝑎 and 𝑏 are keys of the cipher.

• 𝑎 must be coprime with 𝑚, meaning gcd(𝑎,𝑚)=1.

• 𝑚 is the size of the alphabet (26 for English).

Step 2: Choose Keys

Select values for 𝑎 and 𝑏. For this example:

• 𝑎=5

• 𝑏=8

• 𝑚=26 (English alphabet)

Step 3: Encryption Example

Plaintext: "HELLO"

Convert Letters to Numbers:

Using 𝐴=0,𝐵=1,...,𝑍=25:

• 𝐻=7,𝐸=4,𝐿=11,𝑂=14

Apply Encryption Formula:

For each letter, compute:

$$E(x)=(5.x+8)\;\;mod\;\;26$$

• 𝐻(7):𝐸(7)=(5⋅7+8) mod 26 =43 mod 26 = 17 (R)

• 𝐸(4):𝐸(4)=(5⋅4+8) mod 26 =28 mod 26 = 2 (C)

• 𝐿(11):𝐸(11)=(5⋅11+8) mod 26 =63 mod 26 = 11 (L)

• 𝐿(11):𝐸(11)=(5⋅11+8) mod 26 =63 mod 26 = 11 (L)

• 𝑂(14):𝐸(14)=(5⋅14+8) mod 26 =78 mod 26 = 0 (A)

Encrypted Message: "RCLLA"

Step 4: Understand the Decryption Formula

The decryption formula is:

$$D(y)=a_{inv}.(y-b)\;\;mod\;\;m$$

Where:

• 𝑦 is the numerical value of the ciphertext letter.

• 𝑎_inv is the modular multiplicative inverse of 𝑎 modulo 𝑚, satisfying:

$$a.a_{inv}\equiv 1\;\;mod\;\;m$$

Step 5: Find 𝑎_inv

For 𝑎=5 and 𝑚=26:

• Find 𝑎_inv such that 5⋅𝑎_inv≡1 mod 26.

• 𝑎_inv=21 (calculated using the Extended Euclidean Algorithm).

Step 6: Decrypt Example

Ciphertext: "RCLLA"

Convert Letters to Numbers:

• 𝑅=17, 𝐶=2, 𝐿=11, 𝐴=0

Apply Decryption Formula:

For each letter, compute:

$$D(y)=21.(y-8)\;\;mod\;\;26$$

• R(17):D(17)=21⋅(17−8) mod 26=21⋅9 mod 26=189 mod 26=7 (H)

• C(2):D(2)=21⋅(2−8 ) mod 26=21⋅(−6) mod 26=−126 mod 26=4 (E)

• L(11):D(11)=21⋅(11−8) mod 26=21⋅3 mod 26=63 mod 26=11 (L)

• L(11):D(11)=21⋅(11−8) mod 26=21⋅3 mod 26=63 mod 26=11 (L)

• A(0):D(0)=21⋅(0−8) mod 26=21⋅(−8) mod 26=−168 mod 26=14 (O)

Decrypted Message: "HELLO"

Step 7: Python Code

Here’s a Python implementation of the Affine Cipher, using the example provided. The code includes functions for both encryption and decryption.

from math import gcd

def affine_encrypt(plaintext, a, b, m):
    """Encrypts plaintext using the Affine Cipher."""
    if gcd(a, m) != 1:
        raise ValueError("Key 'a' must be coprime with 'm'.")

    # Convert plaintext to uppercase and remove non-alphabetic characters
    plaintext = ''.join(filter(str.isalpha, plaintext.upper()))
    
    ciphertext = ''
    for char in plaintext:
        x = ord(char) - ord('A')  # Convert character to number (A=0, B=1, ..., Z=25)
        y = (a * x + b) % m       # Apply encryption formula
        ciphertext += chr(y + ord('A'))  # Convert number back to character

    return ciphertext

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
    raise ValueError("Modular inverse does not exist.")

def affine_decrypt(ciphertext, a, b, m):
    """Decrypts ciphertext using the Affine Cipher."""
    if gcd(a, m) != 1:
        raise ValueError("Key 'a' must be coprime with 'm'.")

    a_inv = mod_inverse(a, m)  # Find modular inverse of 'a'
    plaintext = ''
    for char in ciphertext:
        y = ord(char) - ord('A')  # Convert character to number (A=0, B=1, ..., Z=25)
        x = (a_inv * (y - b)) % m  # Apply decryption formula
        plaintext += chr(x + ord('A'))  # Convert number back to character

    return plaintext

# Example usage
def main():
    m = 26  # Size of the alphabet
    a = 5   # Key 'a'
    b = 8   # Key 'b'

    plaintext = "HELLO"
    print(f"Plaintext: {plaintext}")

    # Encrypt the plaintext
    ciphertext = affine_encrypt(plaintext, a, b, m)
    print(f"Ciphertext: {ciphertext}")

    # Decrypt the ciphertext
    decrypted_text = affine_decrypt(ciphertext, a, b, m)
    print(f"Decrypted Text: {decrypted_text}")

if __name__ == "__main__":
    main()

Output:

Plaintext: HELLO
Ciphertext: RCLLA
Decrypted Text: HELLO