SRA picoCTF 2023 Solution

Description

1. Step 1Spot the leak: c and d, no n
   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!
   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
   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!
   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 4096-bit number is far beyond classical factoring. 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
   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!
   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.

Alternate Solution

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.