//The Strongest Exponent I Thought 2

Flag: TSGCTF{My_power_is_too_dangerous_to_use!}

>Overview

This challenge is an RSA-style encryption where the public exponent e is computed as e = pow(p, q, phi) (i.e., p^q mod φ(n)). The challenge prints n, e and c = m^e mod n. The goal is to recover the original plaintext flag (the code shows the flag was converted to an integer via int.from_bytes(flag, 'big')).

I recovered the flag by noticing a modular property of e that lets us easily factor n and then decrypt normally.

>Files provided

• problem.py — challenge generator (shows how n, e and c were generated)

• output.txt — the printed n, e, and c

• solve.py — solver script (included below)

>Key lines from problem.py (relevant bits)

p = getPrime(1024)

q = getPrime(1024)

n = p * q

phi = (p - 1) * (q - 1)

# e = (p ** q) % phi

e = pow(p, q, phi)

  

m = int.from_bytes(flag.encode(), 'big')

  

c = pow(m, e, n)

The suspicious part is e = pow(p, q, phi) — the exponent depends on the secret prime p.

>Attack idea — why this is broken

1. Let phi = (p-1)(q-1). Since p-1 divides phi, congruence modulo phi implies congruence modulo p-1.

2. Note p ≡ 1 (mod p-1). Thus p^q ≡ 1^q ≡ 1 (mod p-1).

3. Therefore e = p^q mod phi satisfies e ≡ 1 (mod p-1).

4. For any integer x not divisible by p, if e ≡ 1 (mod p-1) then x^e ≡ x (mod p) (because e = 1 + k(p-1) and x^{p-1} ≡ 1 (mod p)). This means x is a fixed point of exponentiation by e modulo p.

5. In particular, c^e ≡ c (mod p). Hence p | (c^e - c).

6. So gcd(n, c^e - c) gives a non-trivial factor (it yields p), letting us factor n and proceed to RSA decryption.

This is a simple and robust factoring oracle triggered by the badly chosen exponent.

>Concrete steps I took

1. Read problem.py and output.txt to obtain n, e, and c.

2. Compute g = gcd(n, c^e - c); this yields the secret prime p.

3. Compute q = n // p.

4. Compute λ(n) = lcm(p-1, q-1) and d = e^{-1} (mod λ(n)) (or inverse mod φ if preferred when gcd(e, φ) = 1).

5. Decrypt m = c^d mod n and convert m back to bytes to get the flag.

>Terminal reproduction (selected commands + outputs)

output.txt (excerpts):

(full numbers in output.txt in the repo)

Quick gcd trick (Python interactive check) — shows gcd(n, c^e - c) is non-trivial and equals p

# (example snippet used in exploration)

>>> t = pow(c, e, n)

>>> g = math.gcd(n, (t - c) % n)

>>> g.bit_length()

1024

>>> 1 < g < n

True

Running the solver

>Full solver (solve.py) — included here for completeness

import math

import re

  
  

def parse_output(path: str):

    txt = open(path, "r", encoding="utf-8").read()

    vals = {}

    for name in ("n", "e", "c"):

        m = re.search(rf"^{name}\s*=\s*(\d+)\s*$", txt, re.MULTILINE)

        if not m:

            raise ValueError(f"Failed to parse {name} from {path}")

        vals[name] = int(m.group(1))

    return vals["n"], vals["e"], vals["c"]

  
  

def main():

    n, e, c = parse_output("output.txt")

  

    # Because e = p^q (mod phi), we have e ≡ 1 (mod p-1), giving c^e ≡ c (mod p).

    t = (pow(c, e, n) - c) % n

    p = math.gcd(n, t)

    if not (1 < p < n):

        raise ValueError("Failed to factor n")

    q = n // p

  

    lam = (p - 1) * (q - 1) // math.gcd(p - 1, q - 1)

    d = pow(e, -1, lam)

    m = pow(c, d, n)

  

    flag = m.to_bytes((m.bit_length() - 1) // 8 + 1, "big")

    print(flag.decode())

  
  

if __name__ == "__main__":

    main()

Save this file as solve.py and run python3 solve.py inside the extracted challenge folder.

>Why this approach (how I got the idea)

• The line e = pow(p, q, phi) is unusual: public exponents are typically chosen independent of the secret primes (like small constants 65537). Whenever the exponent relates to p or q, it is a red flag that some modular property could leak part of the secret.

• Observing p ≡ 1 (mod p-1) immediately led to the conclusion p^q ≡ 1 (mod p-1), hence e ≡ 1 (mod p-1).

• From modular arithmetic and Fermat's little theorem, that implies exponentiation by e is the identity map modulo p (on units), giving the simple factorization approach using gcd(n, c^e - c).

>References & further reading

• Basic RSA and modular arithmetic: any standard textbook or notes on RSA

• Practical notes on RSA pitfalls and common CTF patterns (search for "gcd(n, x^e-x) factor" on Crypto.SE)

• For background on using gcd(n, f(x)) tricks in crypto problems, see the Crypto.SE and CTF writeups about "bad exponent choices".

>Lessons learned / Takeaways

• Do not choose the RSA public exponent e to depend on the private primes — this can leak structure that allows factoring.

• If something in the challenge looks asymmetric or dependent on secret values, try to reason about congruences that may give fixed points or identities.

• The gcd(n, something) trick is a very powerful first check when you suspect a modulus property leaks a factor.