Sum-O-Primes picoCTF 2022 Solution

Description

1. Step 1Derive the quadratic equation from N and S
   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 2Solve for p and q with integer square root
   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!
   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 3Decrypt the flag with the recovered primes
   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.