SRA picoCTF 2023 Solution

Description

1. Step 1

   Spot the leak: c and d, no n

   Observation

   I noticed the server transcript labeled its two outputs 'anger' (ciphertext) and 'envy' (private exponent d) while never printing the modulus n, which suggested the challenge intentionally inverts the standard RSA public/private boundary and makes recovering n from the e and d relationship the first sub-problem.

   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:

   Copied!

   bash

   #   Welcome to SRA!

   Copied!

   bash

   #   anger: <ciphertext c, decimal>

   Copied!

   bash

   #   envy:  <private exponent d, decimal>

   Copied!

   bash

   #   vainglory? <waits for plaintext>

   Copied!

   What didn't work first

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

   Without n you have no modulus to reduce c against, so factoring attempts on c itself produce garbage. The server never prints n - the variable labelled 'envy' is d, the private exponent, which is what makes the challenge solvable via the e*d - 1 relation.

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

   pow(c, e, n) would encrypt a second time, not decrypt - you need pow(c, d, n) with the private exponent d. Additionally, n is unknown at this stage so there is no modulus to plug in yet; recovering n from e and d is the actual first sub-problem.

   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 2

   Factor e*d - 1 and harvest prime candidates

   Observation

   I noticed that since e*d - 1 equals k*phi(n) and e is the small standard constant 65537, the product e*d - 1 must contain p - 1 and q - 1 as divisors, which suggested factoring it with sympy/gmpy2 and filtering for divisors whose value plus one is a 128-bit prime to recover candidate primes.

   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

   Copied!

   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 itself; it is typically a product of several small primes. Adding 1 to a single prime factor of e*d - 1 usually yields a composite or a prime of the wrong bit-length. You must enumerate all divisors (every product of subsets of the prime factorization) and filter by bit-length and primality to find p - 1 and q - 1.

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

   Without gmpy2, sympy falls back to pure-Python arithmetic, which is orders of magnitude slower on the ~273-bit input. The factoring call hangs rather than finishing in seconds. Installing gmpy2 (pip3 install gmpy2) before running sympy is required for the factorization to complete in reasonable time.

   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 3

   Pair candidates and decrypt

   Observation

   I noticed that after harvesting a small set of prime candidates for p and q, the only remaining unknowns were which pair forms the real n, which suggested brute-forcing combinations of the candidates and accepting the one where pow(c, d, n) decodes to a 16-character ASCII alphanumeric string matching the challenge's known plaintext alphabet.

   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

   Copied!

   bash

   # Reconnect, paste the recovered plaintext at the 'vainglory?' prompt:

   Copied!

   bash

   nc saturn.picoctf.net <PORT_FROM_INSTANCE>

   Copied!

   What didn't work first

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

   product generates ordered pairs including (p, p) and both (p, q) and (q, p), roughly doubling the iterations. Since n = p*q = q*p, both orderings produce the same n and the same decryption result, so the duplicate work adds no new information. combinations(candidates, 2) is the correct call and is about twice as fast.

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

   Wrong candidate pairs produce 16 bytes of high-entropy garbage that will often fail UTF-8 decoding entirely and raise a UnicodeDecodeError, crashing the loop. The correct check is to test all bytes against the ascii_letters + digits byte set before decoding; this catches the right pair and skips all wrong ones without exceptions.

   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.

Flag

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.