TL;DR (Too Long; Didn’t Read)

Bob encrypted a message for Alice using RSA… but Alice’s system made a critical mistake: it picked two prime numbers too close together. That tiny flaw let us break the encryption using Fermat’s 400-year-old method, recover the message (spoiler: it’s a town in England), and prove the maths works with real Python code. No chalkboard required … just curiosity, some number theory, and a little modern scripting.

Cryptography Isn’t Just for White Coats and Chalk Dust

I was scrolling through LinkedIn when a curious RSA puzzle caught my eye in the Cryptographers and Cryptanalysts group. It came courtesy of none other than Prof Bill Buchanan OBE FRSE, and it read:

“Bob uses RSA to cipher a message for Alice. The cipher value is 86594218145090370142827105263995549926 with a modulus of 238906828912334428985678707283137258157 and using e = 65,537. His generator, though, has created the two prime numbers fairly near to each other. Using this information, find the English town.”

Now, if you live and breathe crypto, your gears are already turning. But if you’re new to this world? Stay with me. This post is for you.

Demystifying Crypto, One Town at a Time

Cryptography has a bit of a PR problem. To outsiders, it often looks like the exclusive domain of academics in lab coats, filling chalkboards with Greek letters and long-dead mathematicians’ names. But at its core? Crypto is human. It’s trust. It’s secrecy. It’s mistakes. And sometimes, it’s a fun puzzle with a town name hidden inside a number.

I’ve worked in and around cryptography for over 40 years, from XOR and rotor machines to modern public key systems. This post is part nostalgia, part education, and part proof that you don’t need a maths degree to understand the magic.

Let’s break RSA. Not theoretically. Let’s actually break it.

RSA in a Nutshell

Let’s take an even simpler example … small enough to check on a pocket calculator if you’re feeling ambitious.

Imagine Bob picks two very small prime numbers:

• p = 11, q = 13 → So  n = 11 * 13 = 143
• φ(n) = (11 – 1)(13 – 1) = 10 * 12 = 120, where φ(n) (Euler’s totient function) represents the number of integers less than n that are coprime to n. For RSA, when n = p * q and both are prime, φ(n) is calculated as (p - 1) * (q - 1). This is used in determining the private key and ensures the maths works cleanly for modular inversion.
• Choose e = 7, which is co-prime to 120. Co-prime just means their greatest common divisor (GCD) is 1 … they share no common divisors except 1. Neither number needs to be prime; they just need to be relatively prime to each other.

In real-world RSA, the public exponent e is almost always 65537. Why? Because it’s a special number: large enough to avoid known small-exponent attacks (like e = 3 or e = 17), but small enough to allow fast encryption and signature verification. 65537 is also a Fermat prime (2¹⁶ + 1), which makes modular exponentiation efficient in hardware and software implementations. It strikes a perfect balance between performance and security. Co-prime just means their greatest common divisor (GCD) is 1 … they share no common divisors except 1. Neither number needs to be prime; they just need to be relatively prime to each other.

Now Bob wants to encrypt the message “abc” using Alice’s public key … which consists of (n = 143, e = 7). In RSA, the public key is openly shared, and anyone (like Bob) can use it to encrypt a message meant for Alice.

First, Bob converts each letter into its ASCII numeric value:

• a = 97, b = 98, c = 99

Using RSA encryption:

• Encrypted a = (97^7) mod 143 = 59
• Encrypted b = (98^7) mod 143 = 32
• Encrypted c = (99^7) mod 143 = 44

So Bob sends the ciphertext: 59 32 44

To decrypt, Alice uses her private key, which includes d = 103. This is derived by computing the modular inverse of e = 7 modulo φ(n) = 120. In other words, she’s solving for a number d such that:

(7 * d) % 120 = 1

She can do this using the Extended Euclidean Algorithm, or a tool like Python’s mod_inverse function. Either way, the answer is:

d = 103

This private key exponent is what allows Alice … and only Alice … to decrypt the message.
We can verify it works because 7 × 103 = 721, and 721 % 120 = 1.

Now she decrypts:

• 59^103 mod 143 = 97 → ‘a’
• 32^103 mod 143 = 98 → ‘b’
• 44^103 mod 143 = 99 → ‘c’

And just like that, “abc” is recovered.

Note: If you’re checking these calculations on a regular calculator (especially the macOS built-in one), be cautious. Some calculators fail to handle large exponents with modular reduction correctly, and may give you incorrect results. For reliable results, use Python or a tool that supports modular exponentiation properly. If you’re not ready to write some python code to check large powers, a website like: https://www.omnicalculator.com/math/power-modulo might help.

Even with numbers this small, the structure holds. The key point: modular exponentiation lets us encrypt and decrypt using reversible maths. Once you see it work with single letters and primes you can count on your fingers, the big-picture RSA puzzle becomes a lot less intimidating.

RSA Recap with Slightly Larger Numbers

RSA works like this:

1. Pick two large prime numbers, p and q
2. Multiply them together: n = p * q
3. Choose a public exponent e, typically 65537
4. Use n and e to encrypt your message: cipher = (message^e) mod n

The clever bit? While it’s easy to compute n, it’s hard to reverse-engineer p and q if they’re large and random enough. This is the core of RSA security.

But if your primes are too close together? You’ve made a fatal mistake. And that’s where Fermat comes in.

Let’s demonstrate the RSA idea using very small primes, just to show the principle.

Imagine Bob chooses:

• p = 61, q = 53 → So  n = 61 * 53 = 3233
• φ(n) = (p-1)*(q-1) = 3120, where φ(n) is Euler’s totient function … the count of numbers less than n that are relatively prime to it. In the RSA context, this value is essential for calculating the private key.
• Bob chooses public exponent e = 17 (which is co-prime to 3120)

Now suppose Bob wants to encrypt the letters “abc”. First, he converts “abc” into its ASCII numeric representation: 97 98 99.

Using RSA encryption:

• Encrypted a = (97^17) mod 3233 = 2790
• Encrypted b = (98^17) mod 3233 = 2545
• Encrypted c = (99^17) mod 3233 = 1207

So Bob sends the ciphertext: 2790 2545 1207

To decrypt, Alice uses her private key. She computes the modular inverse of e modulo φ(n), which gives d = 2753.

Now she decrypts:

• Decrypted 2790^2753 mod 3233 = 97 → ‘a’
• Decrypted 2545^2753 mod 3233 = 98 → ‘b’
• Decrypted 1207^2753 mod 3233 = 99 → ‘c’

And just like that, “abc” is recovered. No cloak, no dagger, no PhD required.

Returning to the Puzzle from Prof Bill Buchanan

Let’s revisit Bob’s message:

• Ciphertext: 86594218145090370142827105263995549926
• Modulus (n): 238906828912334428985678707283137258157
• Public Exponent (e): 65537

We’re told that Bob’s generator created two primes fairly close together. That’s our golden ticket. Technically Alice generated the primes, since Bob only has the Public Key.

Fermat to the Rescue

When p and q are close, you can factor n using Fermat’s factorisation, an idea dating back to the 1600s:

Find two numbers a and b such that:
n = a^2 - b^2 ➔  n = (a - b)(a + b)

I wrote a short Python script to try values of a starting at the square root of n until a^2 - n is a perfect square. A few iterations in, we struck gold:

p = 15456611171674486351
q = 15456611171674608707

# --- Fermat Factorisation ---
def fermat_factor(n):
    print("[*] Starting Fermat's factorisation...")
    a = ceiling(sqrt(n))
    b2 = a * a - n
    attempt = 0

    while True:
        b = sqrt(b2)
        if b == int(b):
            p = a - b
            q = a + b
            if isprime(p) and isprime(q):
                print(f"[+] Factors found on attempt {attempt}:")
                return int(p), int(q)
        a += 1
        b2 = a * a - n
        attempt += 1

Now that we have p and q, we can derive the private key, decrypt the message, and reveal what Bob was trying to say.

From Numbers to Town Names

Thank you to Tony Patti for feedback on this section, which I have now expanded out.

With p and q found using Fermat’s method, we can derive everything needed to decrypt the message.

• Modulus (n) Declared: 238906828912334428985678707283137258157
• p = 15456611171674486351
• q = 15456611171674608707
• n = p * q = 238906828912334428985678707283137258157
• φ(n) = (p-1)*(q-1) = 238906828912334428954765484939788163100
• Public exponent: e = 65537
• Ciphertext (c): 86594218145090370142827105263995549926

We can see that the declared Modulus matches the two primes (p * q) when multiplied together.

We then compute the private exponent:

d = mod_inverse(e, φ(n))
d = mod_inverse(65537, 238906828912334428954765484939788163100)
# d = 232035300272028183649369556851662361073

With d in hand, we can decrypt:

m = pow(c, d, n)
m = pow(86594218145090370142827105263995549926, 232035300272028183649369556851662361073, 238906828912334428985678707283137258157) 
# m = 29117719734608505
# m = 0x6772696d736279

This decrypted integer can then be converted back to text:

plaintext = int_to_text(m)
# plaintext = "grimsby"

Just like that, the cipher reveals its secret: an English town on the Humber estuary.

Technical aside: The decrypted integer 29117719734608505 corresponds to the hexadecimal value 0x6772696d736279. When converted from hex to ASCII, this gives us the string “grimsby”, confirming our result from another angle.

That’s right, Bob’s message was a town on the Humber estuary.

The Code Behind the Puzzle

Before we dive into the full script, let’s take a closer look at the tools that made this possible, namely, Python and the excellent sympy library.

Why SymPy?

SymPy is a symbolic mathematics library that supports:

• Arbitrary-precision integers, essential for RSA key sizes
• Symbolic expressions and modular arithmetic, no rounding errors, no loss of precision
• Built-in tools like sqrt(), ceiling(), isprime(), and mod_inverse() — all vital to cryptographic calculations

If you’re used to regular integers in Python, here’s where SymPy steps in:

from sympy import Integer, isprime, sqrt, ceiling, mod_inverse

# Arbitrary-precision integer
n = Integer(2) ** 1024
print(f"Digits: {len(str(n))}")  # 309-digit number

# Prime testing
print("Prime?", isprime(n))

# Square root and ceiling (used in Fermat factorisation)
a = ceiling(sqrt(n))

# Modular inverse (used in RSA decryption key)
d = mod_inverse(65537, 120)

Unlike standard Python floats or ints, SymPy allows us to do these calculations exactly, which is why we can safely factor large moduli, test primality, and recover plaintext from huge cipher numbers, all in pure Python.

To install SymPy, simply run:

pip install sympy

Now that you know what tools we’re using, and why, let’s look at the actual code that cracked the puzzle:

#!/usr/bin/env python3
"""
RSA Decryption using Fermat's Factorisation
Includes round-trip check to confirm encryption/decryption correctness.
Written for educational purposes by Jason Brooks & ChatGPT
Why chatGPT? Have you seen my python code? It optimises and tidies my code up much better than I
My original libraries for this stuff was written by me in the 90s using C++ and far too much overkill for this
"""

from sympy import Integer, sqrt, ceiling, isprime, mod_inverse

# --- Configuration ---
n = Integer(238906828912334428985678707283137258157)
e = Integer(65537)
c = Integer(86594218145090370142827105263995549926)


# --- Fermat Factorisation ---
def fermat_factor(n):
    print("[*] Starting Fermat's factorisation...")
    a = ceiling(sqrt(n))
    b2 = a * a - n
    attempt = 0

    while True:
        b = sqrt(b2)
        if b == int(b):
            p = a - b
            q = a + b
            if isprime(p) and isprime(q):
                print(f"[+] Factors found on attempt {attempt}:")
                return int(p), int(q)
        a += 1
        b2 = a * a - n
        attempt += 1


# --- Convert Integer to Plaintext ---
def int_to_text(m):
    m_int = int(m)
    m_bytes = m_int.to_bytes((m_int.bit_length() + 7) // 8, byteorder='big')
    try:
        return m_bytes.decode()
    except UnicodeDecodeError:
        return m_bytes.decode(errors='ignore')


# --- Convert Plaintext to Integer ---
def text_to_int(plaintext):
    return int.from_bytes(plaintext.encode(), byteorder='big')

# --- Main Execution ---
def main():
    print("[*] RSA modulus (n):", n)
    print("[*] Public exponent (e):", e)
    print("[*] Ciphertext (c):", c)

    p, q = fermat_factor(n)

    print(f"    p = {p}")
    print(f"    q = {q}")

    phi_n = (p - 1) * (q - 1)
    d = int(mod_inverse(e, phi_n))
    m = int(pow(c, d, n))
    plaintext = int_to_text(m)

    print("[*] φ(n):", phi_n)
    print("[*] Private exponent (d):", d)
    print("[*] Decrypted integer:", m)
    print("[*] Decrypted message:", plaintext)

    # --- Round-Trip Check ---
    print("\n[*] Performing round-trip verification...")
    m_check = text_to_int(plaintext)
    c_check = pow(m_check, int(e), int(n))

    print("[*] Re-encrypted ciphertext:", c_check)
    if c_check == c:
        print("[✓] Match confirmed: encryption and decryption are consistent.")
    else:
        print("[✗] Mismatch detected: something's off.")

if __name__ == "__main__":
    main()

Round-Trip Proof

And here’s the output the program produced … concrete proof that everything worked as expected:

[*] RSA modulus (n): 238906828912334428985678707283137258157
[*] Public exponent (e): 65537
[*] Ciphertext (c): 86594218145090370142827105263995549926
[*] Starting Fermat's factorisation...
[+] Factors found on attempt 0:
    p = 15456611171674486351
    q = 15456611171674608707
[*] φ(n): 238906828912334428954765484939788163100
[*] Private exponent (d): 232035300272028183649369556851662361073
[*] Decrypted integer: 29117719734608505
[*] Decrypted message: grimsby

[*] Performing round-trip verification...
[*] Re-encrypted ciphertext: 86594218145090370142827105263995549926
[✓] Match confirmed: encryption and decryption are consistent.

To prove the process was correct, I took the plaintext (grimsby), converted it back into an integer, re-encrypted it with the public key (n, e), and verified it matched the original ciphertext.

Mathematics doesn’t lie … and it doesn’t forgive poor key generation. In this case, it wasn’t Bob’s mistake at all. The real vulnerability came from Alice’s side: her system generated two primes far too close together, opening the door for Fermat’s factorisation to break the encryption.

PEM Keys and OpenSSL (Or Why Bob Wouldn’t Get a Job at GCHQ)

I also constructed valid RSA private and public key PEM files using Python’s cryptography library. However, since the modulus was only 128 bits … and to be precise, this was part of Alice’s key. In RSA, the key pair is generated by the recipient (in this case, Alice), and the public portion is shared with the sender (Bob). So while Bob used the key to encrypt the message, it was Alice’s key generation process that made the critical mistake: choosing two primes too close together. This is often a result of poor random number generation (RNG) or insecure keygen implementation. Because this was a toy key (only 128 bits), OpenSSL rightly refused to process it. Real-world crypto requires at least 2048 bits.

Still, this puzzle was never about real-world security. It was about learning. And breaking. And solving.

Lessons from Bob (and Fermat)

• Crypto isn’t scary when you break it down (pun intended)
• Predictability is the enemy of security
• You don’t need 2048-bit keys to learn how the pieces fit
• Fermat’s ideas are still relevant 400 years later

Try It Yourself

Want to replicate this? Here’s what you can do:

• Grab the Python Script LinkedInPuzzle.py from https://github.com/muckypaws/PuzzleSolvers
• Feed in the cipher, modulus, and exponent
• Watch the puzzle unfold

One More Thing…

Cryptography isn’t just about hiding secrets. It’s about curiosity, creativity, and trust. If this post helped you understand RSA just a little better … or sparked a new interest in this fascinating field…

We got the message through.

Written by Jason Brooks, who has spent decades cracking, securing, and storytelling his way through cryptographic history.