How to Crack the Affine Cipher in Python

Kickstart your coding journey with our Python Code Assistant. An AI-powered assistant that's always ready to help. Don't miss out!

In this tutorial, we are going to learn how to crack the Affine cipher. But before we see how to do that, what is the Affine cipher? The affine cipher is a type of monoalphabetic substitution cipher that combines modular arithmetic and linear algebra to encrypt and decrypt messages.

The history of the Affine Cipher is deeply rooted in the ancient world, finding its earliest applications in classical cryptography. The fundamental concept of shifting letters, akin to the Caesar Cipher, traces back to Julius Caesar in ancient Rome. However, the Affine Cipher, as a more advanced monoalphabetic substitution cipher, gained prominence through contributions from Arabic scholars during the Islamic Golden Age.

Before you learn how to crack the Affine cipher, you must know how it encrypts data first. Refer to this tutorial to learn how to implement the Affine Cipher in Python. 

In a nutshell, In the Affine cipher, encryption involves converting each plaintext letter to its numerical equivalent, applying a modular Affine transformation (ax + b), and then converting the result back to a letter. Decryption reverses this process using the inverse transformation (a^-1(x - b)). We are going to be decrypting using Brute force. 

Brute force is a straightforward and exhaustive method of solving a problem or attempting to break a system by systematically trying all possibilities until the correct one is found. In the context of cryptography, it refers to trying all possible keys or passwords until the correct one is discovered. We’ll be trying out all possible key combinations of a and b, till we decrypt the message. And because there are only 26 alphabets, with our current computational power, that would take only seconds.

To get decrypting in code, we start off by installing colorama if you don't have it already:

$ pip install colorama

Let's import the necessary libraries:

# Import the needed libraries
import string
from colorama import Fore, init

# Initialise colorama
init()

The string module provides a collection of constants and functions specific to string manipulation. It is part of the Python standard library, and its purpose is to offer convenient tools for working with strings.

colorama was imported for colored outputs on the terminal. Next, we create a function that finds the greatest common divisor for us:

# Function to get Euclidean Algorithm
def extended_gcd(a, b):
   """
   Extended Euclidean Algorithm to find the greatest common divisor
   and coefficients x, y such that ax + by = gcd(a, b).
   """
   if a == 0:
       return (b, 0, 1)
   else:
       g, x, y = extended_gcd(b % a, a)
       return (g, y - (b // a) * x, x)

Afterward, we create another function to find the modular inverse:

# Function to get the modular Inverse
def modular_inverse(a, m):
   """
   Compute the modular multiplicative inverse of a modulo m.
   Raises an exception if the modular inverse does not exist.
   """
   g, x, y = extended_gcd(a, m)
   if g != 1:
       raise Exception('Modular inverse does not exist')
   else:
       return x % m

Now that we’ve gotten the GCD and Modular inverse, we can now proceed by creating a function that performs the actual decryption:

# Function to decrypt our message.
def affine_decrypt(ciphertext, a, b):
   """Decrypt a message encrypted with the Affine Cipher using
   the given key components a and b."""
   alphabet = string.ascii_uppercase
   m = len(alphabet)
   plaintext = ''
   # Compute the modular multiplicative inverse of a
   a_inv = modular_inverse(a, m)
   # Iterate through each character in the ciphertext
   for char in ciphertext:
       # Check if the character is in the alphabet
       if char in alphabet:
           # If it's an alphabet letter, decrypt it
           # Find the index of the character in the alphabet
           c = alphabet.index(char)
           # Apply the decryption formula: a_inv * (c - b) mod m
           p = (a_inv * (c - b)) % m
           # Append the decrypted character to the plaintext
           plaintext += alphabet[p]
       else:
           # If the character is not in the alphabet, keep it unchanged
           plaintext += char
   # Return the decrypted plaintext
   return plaintext

Finally, we create a function that will do the brute-forcing. This will be achieved by generating all possible key combinations between a and b. This is vulnerable because there are only 26 letters in the alphabet (as discussed in the implementation tutorial), so the possible combinations are very few:

# Function to peform brute force attack.
def affine_brute_force(ciphertext):
   """Brute-force attack to find possible keys for an Affine Cipher
   and print potential decryptions for manual inspection."""
   alphabet = string.ascii_uppercase
   m = len(alphabet)
   # Iterate through possible values for a
   for a in range(1, m):
       # Ensure a and m are coprime
       if extended_gcd(a, m)[0] == 1:
           # Iterate through possible values for b
           for b in range(0, m):
               # Decrypt using the current key
               decrypted_text = affine_decrypt(ciphertext, a, b)
               # Print potential decryption for manual inspection
               print(f"Key (a={a}, b={b}): {decrypted_text}")

ciphertext = input(f"{Fore.GREEN}[?] Enter Message to decrypt: ")
# Perform a brute-force attack to find potential decrypted message.
affine_brute_force(ciphertext)

And that's it! Let’s run our code:

$ python affine_cipher_decrypt.py
[?] Enter Message to decrypt: DEPFAX
Key (a=1, b=0): DEPFAX
Key (a=1, b=1): CDOEZW
Key (a=1, b=2): BCNDYV
...
<SNIPPED>

After it’s finished running, we can notice (when we manually scan through) the decrypted text:

Voila! We got the plain text. It turns out the key was a=3, b=10. 

This is why the Affine cipher is not regarded as a robust encryption mechanism. The combinations to try in order to get the key are not much (for today’s computational power). However, this is very good for understanding classical cryptography and older encryption techniques. It can also be used for Puzzles!

Check out similar tutorials:

• How to Implement the Caesar Cipher in Python
• How to Crack the Caesar cipher in Python

Finally, having explored the intriguing process of cracking the Affine Cipher with Python, you might be eager to delve further into the cryptographic realm. Our Cryptography with Python eBook is tailored for enthusiasts like you, offering a deeper dive into the intricacies of cryptography beyond what individual tutorials can cover. It's an invitation to expand your knowledge and skills in a structured, comprehensive manner, ensuring a broader understanding of cryptographic principles and Python applications. Ideal for those looking to solidify their grasp on cryptography, this eBook awaits here.

Happy ciphering ♥

Finished reading? Keep the learning going with our AI-powered Code Explainer. Try it now!

Read Also

How to Implement the Affine Cipher in Python

Discover the Affine Cipher in Python: a straightforward tutorial blending historical cryptography with modern coding, perfect for enthusiasts and programmers.

How to Create a Custom Wordlist in Python

Learn how to build a custom wordlist generator with options of minimum and maximum characters, and more with itertools in Python.

How to Crack the Caesar Cipher in Python

Unlock the secrets of the Caesar cipher with our Python tutorial. Learn the ins and outs of one of history's oldest codes and how to break it using modern computing power.

Comment panel