Confused by complex code? Let our AI-powered Code Explainer demystify it for you. Try it 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:
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 ♥
Just finished the article? Now, boost your next project with our Python Code Generator. Discover a faster, smarter way to code.
View Full Code Improve My Code
Got a coding query or need some guidance before you comment? Check out this Python Code Assistant for expert advice and handy tips. It's like having a coding tutor right in your fingertips!