Skip to content

The studio of

Ahmed El Euch — Computer Science Engineering Student at INSA Lyon

Breaking systems before attackers do.

Securing Applications, Cloud Infrastructure, Networks & CI/CD

02 / Cryptography

RSA Cryptography CTF Solver

Automated RSA attack tool for CTFs

A Python and SageMath solver that reads a weak RSA key, picks the attack that breaks it — small exponent, common modulus or Wiener's — and recovers the plaintext in seconds.

Complete
RSA challenges solved
30+
In several CTFs
Top 15%
Attack families
3

RSA Cryptography CTF Solver is a project by Ahmed El Euch, who worked on it as Sole developer, built with Python, PyCryptodome, SageMath.

What was built

  1. Engineered a modular solver automating RSA attack selection across three families: small public exponent (e = 3), common modulus, and Wiener's attack on weak private exponents.

  2. Solved 30+ RSA challenges with it, placing top 15% in several competitions (Securinets Finals, DarknetsCTF, DarkesthourCTF); automated parameter analysis cuts manual solve time from minutes to seconds.

  3. Modular design: new attack families plug in without modifying the solver interface.

Problem

RSA is only as strong as its parameters. A small public exponent, a modulus shared between two keys, or a private exponent chosen too small each break it completely — and CTF cryptography challenges are built on exactly those mistakes. Solving them by hand means recognising which mistake it is, then rewriting the same number theory under time pressure, challenge after challenge.

Solution

One solver for the three families that come up most. It takes the public parameters (n, e and the ciphertexts), checks them for the tell of each weakness, and runs the matching attack: an exact integer e-th root when e is tiny, Bézout's identity across two exponents on a shared modulus, or a continued-fraction expansion of e/n when the private exponent is small. Every attack sits behind the same interface, so adding a new one does not touch the rest.

Results

Used across 30+ RSA challenges in competitive CTFs, with top 15% placings in several of them, including Securinets Finals, DarknetsCTF and DarkesthourCTF. The recognition step that used to take minutes of staring at numbers now takes seconds, which leaves the clock for the challenges that do need new thinking.

Case study

RSA encrypts a message m as c = m^e mod n, where n = p·q is the product of two secret primes and the private exponent d undoes it. The maths is sound; the parameters often aren't. This solver automates the three weaknesses that come up most in CTF cryptography, and each one leaves a recognisable trace in the public values.

How it picks an attack

  • e is tiny (typically 3) → the message may never have wrapped around the modulus → integer e-th root.
  • Two ciphertexts share the same n, with different e → the same message was encrypted twice under one modulus → common modulus attack.
  • e is almost as large as n → the private exponent d is probably small → Wiener's attack.

1. Small public exponent

Why it breaks. With e = 3 and a short, unpadded message, m³ can be smaller than n. Then the "mod n" never happens and the ciphertext is simply m³ as an ordinary integer.

The attack. Take the exact integer cube root of c. No key, no factoring: if the root is exact, it is the plaintext. When m³ only slightly exceeds n, the same idea still works by testing c + k·n for small k.

The fix it teaches. Use e = 65537 and real padding (OAEP), so the message is never small.

2. Common modulus

Why it breaks. Two parties share a modulus n but use different public exponents e₁ and e₂, and the same message is encrypted for both.

The attack. If gcd(e₁, e₂) = 1, the extended Euclidean algorithm gives integers a and b with a·e₁ + b·e₂ = 1. Then c₁^a · c₂^b = m^(a·e₁ + b·e₂) = m (mod n), using a modular inverse for whichever of a or b is negative. The plaintext comes out without ever touching a private key.

The fix it teaches. Never reuse a modulus between keys.

3. Wiener's attack

Why it breaks. To make decryption fast, d is chosen small. If d < n^(1/4) / 3, the fraction e/n is so close to k/d (for the k in e·d = 1 + k·φ(n)) that k/d appears among its continued-fraction convergents.

The attack. Expand e/n as a continued fraction and walk its convergents. Each one gives a candidate d and a candidate φ(n) = (e·d − 1)/k; the right one makes x² − (n − φ(n) + 1)·x + n = 0 have integer roots, and those roots are p and q. That recovers the factorisation and the real private key.

The fix it teaches. Keep d full-size; speed up decryption with CRT instead of a small exponent.

Design

Each attack family is a module behind one shared interface, and the solver chooses among them from the parameters it is given. Adding a family means adding a module; the solver's interface does not change.

What it gave me

Writing these attacks once, properly, meant understanding exactly where each one stops working — the bound in Wiener's theorem, the gcd condition on the exponents, the point where m^e wraps around n. That is the difference between running a script and knowing why a key is weak, which is what matters when an RSA deployment has to be reviewed rather than broken.