Description
An RSA challenge leaks both the product N = p*q (the modulus) and the sum S = p+q of the two primes. With both N and S, you can recover p and q by solving a simple quadratic equation.
Setup
Connect to the challenge server to receive N, the sum S, and the ciphertext c (the server prints them as x = <hex>, n = <hex>, c = <hex>).
Parse the values with pwntools (see the snippet below).
Solve p^2 - S*p + N = 0 using the quadratic formula to find p and q.
Decrypt with standard RSA.
nc saturn.picoctf.net <PORT_FROM_INSTANCE>python3 - <<'PY'
from pwn import remote
r = remote('saturn.picoctf.net', 0) # replace 0 with the instance port
s = int(r.recvline_contains(b'x =').split(b'=')[1].strip(), 16)
n = int(r.recvline_contains(b'n =').split(b'=')[1].strip(), 16)
c = int(r.recvline_contains(b'c =').split(b'=')[1].strip(), 16)
print(s, n, c)
PYSolution
Want to try it yourself first?
The guided walkthrough reveals hints one step at a time.
Step 1Derive the quadratic equation from N and S
ObservationThe server leaks both the product and the sum of the two primes. That is exactly Vieta's setup, so p and q are the 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, thenb = p+qandc = p*q. We have exactly those values:S = p+qandN = p*q. So the quadratic is:x^2 - S*x + N = 0Applying the quadratic formula:
x = (S ± sqrt(S^2 - 4N)) / 2. The two roots are exactly p and q. The discriminantS^2 - 4N = (p+q)^2 - 4pq = (p-q)^2is 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.Step 2Solve for p and q with integer square root
ObservationThe discriminant works out to the square of the difference between the primes, so it is always a perfect square. These primes run to hundreds of bits, which calls for math.isqrt and exact arbitrary-precision arithmetic rather than a floating-point 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.pythonpython3 -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()) "What didn't work first
Tried: Use math.sqrt() (floating-point) instead of math.isqrt() to compute the square root of the discriminant.
With 1024- or 2048-bit primes, the discriminant is a 2048-bit integer. math.sqrt converts it to a 64-bit float first, throwing away roughly a thousand bits of precision, so casting back to an integer leaves you off by millions and the square never matches. math.isqrt works on arbitrary-precision integers 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 reduces the ciphertext in the wrong group, giving an integer mod phi rather than mod N, so the bytes decode to nothing recognizable. RSA decryption exponentiates modulo the public modulus; phi only ever serves to compute the private exponent.
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.
Step 3Decrypt the flag with the recovered primes
ObservationWith p and q recovered, the rest is standard RSA: compute phi from (p-1)(q-1), derive the private exponent, and decrypt the ciphertext with a modular exponentiation.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 = pqreduces the system to two equations in two unknowns and breaks RSA instantly.
Interactive tools
- RSA CalculatorDecrypt RSA ciphertexts, factor n from the sum of primes, or generate key parameters. Handles arbitrarily large BigInt values.
Flag
Reveal flag
picoCTF{...}
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.