RSA. When I first saw it in the IIITK CTF 2026, I had no idea what to do. Large numbers, modular arithmetic, terms like "factorization" and "modular inverse"... it all felt like pure mathematics with no clear entry point.

But RSA challenges in CTFs don't require a PhD in number theory. They require understanding where implementations fail. Here's my journey through RSA exploitation.

First Encounter: Pure Terror

The challenge looked deceptively simple:

Given:
N = 8734973987234987234987...
e = 65537
c = 2984739284798...

Find: The plaintext message

My first thought: "How do I decrypt this? I don't have the private key!"

Then it hit me: RSA challenges in CTFs aren't asking me to break the mathematics—they're showing me broken implementations.

Understanding RSA: The Basics

Before exploiting RSA, you need to understand how it works:

RSA Key Generation:
1. Choose two large primes: p and q
2. Compute N = p × q
3. Compute φ(N) = (p-1) × (q-1)
4. Choose e (usually 65537) such that gcd(e, φ(N)) = 1
5. Compute d = e-1 mod φ(N) (modular inverse)

Public Key: (N, e)
Private Key: (N, d)

Encryption: c = me mod N
Decryption: m = cd mod N

The security of RSA depends entirely on p and q remaining secret. If someone factors N, they can compute φ(N) and then d.

The Vulnerabilities: Where RSA Breaks

1. Weak Factorization (Most Common in CTFs)

Vulnerability: N is composed of two primes that are too close together or are small enough to factor.

Why it happens: Lazy key generation or intentionally weak parameters for educational CTFs.

How to exploit: Use FactorDB.com or computational tools to find p and q.

This is the most common scenario in CTFs. When I encountered RSA in CTF's, the first thing I did was go to FactorDB and check if N could be factored.

FactorDB Approach:

# Step 1: Go to https://factordb.com/ and search for N
# If N is composite but not yet factored, you can contribute to the factorization
# But if it's already factored, you get p and q directly

# Step 2: Once you have p and q, decrypt in Python:
from gmpy2 import invert

N = 834287348723... # Given
e = 65537 # Given
c = 239847238... # Ciphertext

p = 912837912873... # From FactorDB
q = N // p

phi = (p - 1) * (q - 1)
d = invert(e, phi) # Modular inverse

m = pow(c, d, N) # Decrypt
flag = bytes.fromhex(hex(m)[2:])
print(flag)

2. Common Modulus Attack (When Multiple Ciphertexts Share N)

Vulnerability: The same N is used to encrypt multiple messages with different exponents.

Why it matters: If you have two ciphertexts c1 and c2 encrypted with e1 and e2 from the same N, you can recover the plaintext without factoring N.

This is less common but powerful when it appears.

# If gcd(e1, e2) = 1, we can use the Extended Euclidean Algorithm:

import math

# Find a, b such that a*e1 + b*e2 = 1
def extended_gcd(a, b):
  if a == 0:
    return b, 0, 1
  gcd, x1, y1 = extended_gcd(b % a, a)
  x = y1 - (b // a) * x1
  y = x1
  return gcd, x, y

gcd, a, b = extended_gcd(e1, e2)

# Then: m = (c1^a * c2^b) mod N
m = (pow(c1, a, N) * pow(c2, b, N)) % N
flag = bytes.fromhex(hex(m)[2:])
print(flag)

3. Small Exponent Attack (e = 3)

Vulnerability: When e is small (like 3) and the plaintext message is short, me might be smaller than N. You can just take the e-th root.

Why it happens: Attempting to speed up encryption without proper padding.
# If e = 3 and c < N, then m=∛c

import math

def integer_root(n, k):
  x = int(n ** (1/k))
  # Fix floating point errors
  while pow(x, k) < n:
    x += 1
  while pow(x, k) > n:
    x -= 1
  return x

m = integer_root(c, e)
flag = bytes.fromhex(hex(m)[2:])
print(flag)

4. Padding Oracle Attacks

When the server responds differently based on whether decrypted messages are validly padded, you can gradually recover the plaintext without the private key.

My RSA Toolkit

Over time, I've built a mental checklist for RSA challenges:

  1. Check FactorDB first - 80% of CTF RSA challenges will be factorable
  2. Look for multiple ciphertexts - Common modulus attack might apply
  3. Check the exponent size - Small exponents (e=3) have their own exploits
  4. Research the challenge context - Sometimes hints reveal the vulnerability
  5. Use gmpy2 for modular arithmetic - Much faster than manual computation
  6. Check CryptoHack writeups - Many RSA scenarios are standard templates

Real Example: IIITK CTF 2026 Challenge 4

In the IIITK CTF 2026, the RSA challenge gave us:

N = 79769313486231590770839736182743802948788437518959871656785857704711621913289
e = 65537
ct = 56203953485098735098734...

Solution approach:

  1. Plugged N into FactorDB → Got N is prime
  2. Computed φ(N) = (N-1)
  3. Found d using modular inverse: d = modinv(e, φ(N))
  4. Decrypted: m = pow(ct, d, N)
  5. Converted to ASCII to get the flag
Key insight: I spent more time understanding WHY RSA works than actually solving the challenge. Once I grasped the factorization vulnerability, it was trivial.

From CryptoHack to CTF Mastery

After my experience with Apoorv CTF, I dove deep into CryptoHack.org's RSA section. The platform teaches you:

Each challenge reinforced that RSA security is not about the math being hard—it's about the parameters being strong.

What I Learned

  1. Read the problem carefully: CTF hints often reveal which vulnerability to exploit
  2. Mathematics is a tool, not the goal: I don't need to prove RSA's hardness; I need to find its weaknesses
  3. Tools matter: FactorDB, gmpy2, and CryptoHack saved me countless hours
  4. Practice standard scenarios: 95% of RSA CTF challenges are variations of known attacks
  5. Understand the failure modes: Know WHY RSA fails, not just HOW to solve a given challenge

Looking Forward

RSA is foundational in cryptography. Whether it's for CTF challenges, interview preparation, or real-world security analysis, understanding RSA vulnerabilities is essential.

My next goal: dive deeper into lattice-based attacks (LLL algorithm) and implement some of these attacks from scratch to truly internalize the mathematics.

— fl4nk3r, February 2026

← BACK TO BLOG