Skip to main content
picoCTF Solutions
PathPart of the Advanced Cryptography path · Step 2 of 5: Broken Key Generation and Recovery
picoCTF 2023CryptographyHard

SRA picoCTF 2023 Solution

A cryptography challenge involving a custom RSA-adjacent scheme that leaks just enough to recover the key.

Published: April 26, 2023Updated: August 13, 2026

Description

I just recently learnt about the SRA public key cryptosystem... or wait, was it supposed to be RSA? Hmmm, I should probably check...

Setup

Connect to the challenge server and capture every line it prints. The server names the parameters anger and envy.

Install pwntools, sympy, and gmpy2 for fast factoring.

bash
nc saturn.picoctf.net <PORT_FROM_INSTANCE>
bash
pip3 install pwntools sympy gmpy2

Solution

Want to try it yourself first?

The guided walkthrough reveals hints one step at a time.

Walk me through it
  1. Step 1Spot the leak: c and d, no n
    Observation
    The server prints 'anger' (the ciphertext) and 'envy' (the private exponent d), but never the modulus n. That inverts the usual RSA public/private split, so the first sub-problem is recovering n from the relationship between e and d.
    The server prints the ciphertext (anger) and the private exponent d (envy), then asks for the plaintext (vainglory?). The modulus n is never printed. e is the standard 0x10001. Your job is to recover n from (e, d), decrypt c, and submit the plaintext.
    bash
    # Server transcript looks like:
    bash
    #   Welcome to SRA!
    bash
    #   anger: <ciphertext c, decimal>
    bash
    #   envy:  <private exponent d, decimal>
    bash
    #   vainglory? <waits for plaintext>
    What didn't work first

    Tried: Treat 'envy' as the public exponent e and try to factor n from (e, c) alone

    Without n there is no modulus to reduce c against, so factoring c itself gives garbage. The server never prints n; 'envy' is d, the private exponent, and that is what makes the e*d - 1 relation available.

    Tried: Use the standard RSA decryption pow(c, e, n) with the public exponent instead of d

    pow(c, e, n) encrypts a second time rather than decrypting; you want pow(c, d, n) with the private exponent. And n is still unknown at this point, so there is no modulus to plug in. Recovering n comes first.

    Learn more

    Why this is broken. Standard RSA only ever publishes (n, e). Knowing d is supposed to be equivalent to knowing the factorization of n. This server flips that on its head: it hands you d and asks you to recover n yourself. There is in fact a classical algorithm that does exactly that, and SRA is its name (a play on RSA).

    The key relation. By RSA construction e * d ≡ 1 (mod φ(n)), so e*d - 1 = k * φ(n) for some positive integer k. With e = 65537 = 2^16 + 1 and d roughly the size of φ(n), the multiplier k is at most e - 1 ≈ 2^16. So e*d - 1 is essentially φ(n) with a small extra factor stuck on.

    The pivot. φ(n) = (p - 1)(q - 1). So (p - 1) and (q - 1) both divide e*d - 1. If we factor e*d - 1 and look for divisors that are exactly one less than a prime of the right bit-length, we have a small candidate set for p and q.

    For the wider RSA-leak catalogue (Wiener, Coppersmith, common-modulus, p+q, partial bits) see the RSA Attacks for CTF guide.

  2. Step 2Factor e*d - 1 and harvest prime candidates
    Observation
    Since e*d - 1 is a multiple of phi(n), and e is the usual 65537, that product has p - 1 and q - 1 among its divisors. Factor it with sympy and gmpy2, then keep the divisors whose value plus one is a 128-bit prime.
    Run sympy.factorint on e*d - 1 (gmpy2 makes it fast enough for the 4096-bit input). Then enumerate every divisor; the candidates for p and q are divisors d_i where d_i + 1 is a 128-bit prime.
    python
    python3 - <<'PY'
from sympy import factorint, isprime, divisors

E = 0x10001
D = 0x...    # paste the 'envy' value the server printed
C = 0x...    # paste the 'anger' value

N_unknown = E * D - 1
print(f"e*d - 1 has {N_unknown.bit_length()} bits, factoring...")
fac = factorint(N_unknown, limit=10**7)
print("factorization:", fac)

# Candidate primes: divisors of e*d - 1 such that divisor + 1 is a ~128-bit prime
candidates = []
for d in divisors(N_unknown):
    p_try = d + 1
    if 120 <= p_try.bit_length() <= 130 and isprime(p_try):
        candidates.append(p_try)
print(f"{len(candidates)} prime candidates")
PY
    What didn't work first

    Tried: Scan only the prime factors of e*d - 1 and add 1, skipping the divisor enumeration

    p - 1 is almost never prime; it is usually a product of several small primes. Add 1 to a single prime factor of e*d - 1 and you get a composite, or a prime of the wrong size. Enumerate every divisor, then filter by bit-length and primality.

    Tried: Run sympy.factorint on e*d - 1 without gmpy2 installed and without a limit

    Without gmpy2, sympy drops to pure-Python arithmetic, which is orders of magnitude slower on a 273-bit input: the factoring call appears to hang instead of finishing in seconds. Install gmpy2 first.

    Learn more

    Why bit-length 128. SRA challenge code generates p and q as 128-bit primes (so n is 256-bit, intentionally tiny). That bit-length is the filter: e*d - 1 has thousands of small factors and a handful of large ones; you only care about divisors that fall in the 120-130 bit range. Without that filter you would face a combinatorial blowup of subsets to multiply.

    Why factoring works at all. A general 256-bit number with fully random factors would be hard to factor classically. e*d - 1 is special because its largest prime factors are only 128 bits, and the rest of the magnitude comes from many small primes (often 2 and small odd primes contributed by the multiplier k and the (p - 1)(q - 1) structure). sympy.factorint with limit=10**7 trial-divides the small factors quickly, then ECM peels off the medium ones, leaving only the large primes you actually need. With gmpy2 installed for the underlying arithmetic, this finishes in seconds.

    Why divisors, not prime factors. p - 1 is rarely prime itself; it is a product of small factors. So you can't just scan the prime factors of e*d - 1 and add 1. You have to walk every divisor (every product of subsets of the prime factorization) and test each one. sympy.divisors generates them.

  3. Step 3Pair candidates and decrypt
    Observation
    With a short list of prime candidates in hand, the only unknown left is which pair makes the real n. Try every combination and keep the one where pow(c, d, n) decodes to a 16-character alphanumeric string.
    Iterate over candidate pairs. For each (p, q), compute n = p*q, recompute phi, check that pow(c, d, n) decodes to a 16-character ASCII alphanumeric string. That string is the plaintext the server is waiting for.
    python
    python3 - <<'PY'
from itertools import combinations
import string

# carry over candidates, E, D, C from the previous step
E, D, C = 0x10001, 0x..., 0x...
candidates = [...]  # from previous step

ALLOWED = (string.ascii_letters + string.digits).encode()

for p, q in combinations(candidates, 2):
    n = p * q
    if n.bit_length() != 256:
        continue
    m = pow(C, D, n)
    pt = m.to_bytes(16, "big", signed=False)
    if len(pt) == 16 and all(b in ALLOWED for b in pt):
        print("plaintext:", pt.decode())
        print("n =", hex(n))
        break
PY
    bash
    # Reconnect, paste the recovered plaintext at the 'vainglory?' prompt:
    bash
    nc saturn.picoctf.net <PORT_FROM_INSTANCE>
    What didn't work first

    Tried: Use itertools.product(candidates, repeat=2) instead of combinations to search pairs

    product yields ordered pairs, including (p, p) and both orderings of (p, q), so it roughly doubles the work. Since p*q equals q*p, both orderings give the same n and the same result. combinations is the right call and about twice as fast.

    Tried: Decode the decrypted integer as UTF-8 without checking the alphanumeric alphabet first

    A wrong pair gives 16 bytes of high-entropy garbage, which often fails UTF-8 decoding and raises an exception that kills the loop. Test the bytes against the letters-and-digits set before decoding: that accepts the right pair and skips the rest without ever raising.

    Learn more

    Why ASCII-alphanumeric is the right filter. The challenge source generates the plaintext as a random 16-character string drawn from ascii_letters + digits. So the correct n is the unique candidate whose decryption falls in that exact alphabet at length 16. Wrong pairings produce 16 bytes of high-entropy garbage, which fails the alphabet check almost always.

    Why combinations not product. n = p*q = q*p, so we don't need to check both orderings. itertools.combinations(candidates, 2) visits each unordered pair once, which roughly halves the work.

    Once you have the plaintext. Reconnect (the server randomizes p, q, and the plaintext on each connection, so use the same session you ran the attack on) and paste the 16 characters at the vainglory? prompt. The server prints the flag in response.

Interactive tools
  • RSA CalculatorDecrypt RSA ciphertexts, factor n from the sum of primes, or generate key parameters. Handles arbitrarily large BigInt values.
Alternate Solution

There is also a textbook algorithm (Miller's) that recovers the factorization of n from (n, e, d) in expected polynomial time, but it requires you to already know n. In this challenge n is hidden, so the divisor-walk above is the right primitive. If you ever face a leak that gives you (n, d) directly without p, q, see the known-phi attack in jvdsn/crypto-attacks for a reference implementation.

Flag

Reveal flag

picoCTF{7h053_51n5_4r3_n0_m0r3_...}

The server hides n but leaks d. Since e*d - 1 = k*phi(n), factoring e*d - 1 and harvesting divisors that are one less than a 128-bit prime gives a small candidate set for p and q. Pair-wise decrypt c and accept the n whose plaintext is 16 alphanumeric ASCII chars; submit those at the vainglory? prompt to receive the flag.

Key takeaway

Leaking the RSA private exponent is as bad as leaking the primes, because e*d = 1 + k*phi(n) lets an attacker factor n and rebuild the whole key. The same failure shows up whenever key material is logged, sent over an insecure channel, or stored without access control, and it is not specific to RSA. Guard private key material as closely as the plaintext it protects.

Related reading

Useful tools for Cryptography

Where to go next

Try these next