Sum-O-Primes picoCTF 2022 Solution

Description

1. Step 1

   Derive the quadratic equation from N and S

   Observation

   I noticed the server leaks both N = p*q and S = p+q, which are exactly the product and sum of two unknowns, and those two relations are the classic setup for Vieta's formulas, suggesting I could express p and q as roots of a single quadratic.

   Given N = p*q and S = p+q, recognize that p and q are roots of x^2 - S*x + N = 0.

   Learn more

   From Vieta's formulas: if p and q are roots of a monic quadratic x^2 - bx + c = 0, then b = p+q and c = p*q. We have exactly those values: S = p+q and N = p*q. So the quadratic is:

   x^2 - S*x + N = 0

   Applying the quadratic formula: x = (S ± sqrt(S^2 - 4N)) / 2. The two roots are exactly p and q. The discriminant S^2 - 4N = (p+q)^2 - 4pq = (p-q)^2 is always a perfect square, so the square root is exact and yields two integer solutions.

   Toy example with p = 11, q = 13:
     N = p*q = 143
     S = p+q = 24
   
   Solve x^2 - 24x + 143 = 0:
     discriminant = 24^2 - 4*143 = 576 - 572 = 4
     sqrt(disc) = 2          (note: 2 = p - q in absolute value? |11-13|=2 yes)
     x = (24 + 2)/2 = 13     (this is q)
     x = (24 - 2)/2 = 11     (this is p)
   
   Same algebra works for 1024-bit primes: math.isqrt() handles
   the exact integer square root for arbitrarily large numbers.

2. Step 2

   Solve for p and q with integer square root

   Observation

   I noticed the discriminant S^2 - 4N equals (p-q)^2, which is always a perfect square, and the primes are hundreds of bits long, so I needed math.isqrt() for exact arbitrary-precision arithmetic rather than floating-point sqrt.

   Compute the integer square root of S^2 - 4N (the discriminant). Then p = (S + sqrt_discriminant) / 2 and q = (S - sqrt_discriminant) / 2.

   python

   python3 -c "
   from math import isqrt
   from sympy import isprime
   
   # Replace with values from the server
   N = 0xYOUR_N
   S = 0xYOUR_SUM
   e = 65537
   c = 0xYOUR_CIPHERTEXT
   
   discriminant = S*S - 4*N
   sqrt_disc = isqrt(discriminant)
   
   # Verify it's a perfect square
   assert sqrt_disc * sqrt_disc == discriminant, 'Not a perfect square!'
   
   p = (S + sqrt_disc) // 2
   q = (S - sqrt_disc) // 2
   
   assert p * q == N
   assert isprime(p) and isprime(q), 'Recovered factors are not prime; recheck S and N'
   print(f'p = {p}')
   print(f'q = {q}')
   
   phi = (p-1)*(q-1)
   d = pow(e, -1, phi)
   m = pow(c, d, N)
   flag = m.to_bytes((m.bit_length()+7)//8, 'big')
   print('Flag:', flag.decode())
   "

   Copied!

   What didn't work first

   Tried: Use math.sqrt() (floating-point) instead of math.isqrt() to compute the square root of the discriminant.

   For 1024-bit or 2048-bit primes, the discriminant is a ~2048-bit integer. Python's math.sqrt() converts it to a 64-bit float first, losing the lower ~1000 bits of precision. The result is an approximate float that, when cast back to int, is off by millions and will not satisfy sqrt_disc * sqrt_disc == discriminant. math.isqrt() works on arbitrary-precision integers directly and returns an exact result.

   Tried: Compute pow(c, d, phi) instead of pow(c, d, N) when decrypting the ciphertext.

   Passing phi as the modulus to pow() instead of N reduces the ciphertext in the wrong group. The output is an integer mod phi(N), not mod N, so the resulting bytes are garbage and will not decode to a recognizable flag. RSA decryption requires exponentiation mod N (the public modulus); phi(N) is only used internally to compute the private exponent d.

   Learn more

   math.isqrt()(available in Python 3.8+) computes the exact integer square root. For large numbers, using Python's arbitrary-precision integers is essential - floating-point sqrt would lose precision on 2048-bit numbers.

   The assert statements verify our math: the square root should be exact (discriminant is a perfect square), and the recovered p*q should equal N. If either fails, double-check the input values.

   This vulnerability arises because leaking p+q along with p*q over-constrains the system - you have two equations in two unknowns, making factoring trivial. In proper RSA, only N = p*q is public; p+q must remain secret.

3. Step 3

   Decrypt the flag with the recovered primes

   Observation

   I noticed that once p and q are recovered, this reduces to standard RSA decryption, so I computed phi(N) = (p-1)*(q-1), derived the private exponent d, and decrypted the ciphertext c with pow(c, d, N).

   Use p, q to compute phi(N), then d = e^-1 mod phi(N), then m = c^d mod N. Decode the integer as bytes.

   Learn more

   Once the factorization is recovered, RSA decryption is straightforward. This is why RSA security reduces entirely to the difficulty of factoring N - any information that helps factor N breaks the encryption.

   Leaking p+q is a subtle implementation mistake. A developer might log or transmit "debug info" about key generation without realizing that sum + product uniquely determines both factors. Proper RSA implementations discard p and q (keeping only d, or the CRT components) after key generation.

   Other related attacks: leaking p+q is a special case of partial key exposure. Anything that gives you a second algebraic relation between p and q on top of N = pq reduces the system to two equations in two unknowns and breaks RSA instantly.

Flag

Vieta's formulas turn (N, p+q) into the quadratic x^2 - Sx + N = 0. The discriminant is always (p-q)^2, so isqrt is exact. Recover p and q in one step, then standard RSA decryption produces the flag.