"R U Sad" - Plaid CTF 2019

Writeup for R U Sad, a challenge from Plaid 2019.

The challenge

We’re given some Python code that generates an RSA key. It stores them as attributes of the class. Here’s what it generates:

N, e       -> the public parameters
P, Q       -> the factorisation of N (private key)
D          -> the decryption key
DmP1, DmQ1 -> the decryption key mod P^{-1} and Q^{-1}
iQmP, iPmQ -> the inverses of Q mod P and P mod Q respectively

The last two pieces here aren’t required for RSA decryption itself, but prestoring them speeds up the process.

The function that generates the public key strips out things marked as PRIVATE_INFO, but this forgets to include iQmP, iPmQ! So maybe we can use that…

Solving it

Let’s say A = iPmQ, B = iQmP.

That means that there are K, L (which we don’t know), satisfying

A*P = K*Q + 1, 0 <= K < Q
B*Q = L*P + 1, 0 <= L < P

(by the definition of modular inverses).

Multiplying these relations together, we get A*B*N = K*L*N + K*Q + L*P + 1

which gives

(A*B - K*L)*N = K*Q + L*P + 1.

Because of the bounds on K and L, the right-hand side of this must be less than 2*N, and we know it’s a multiple of N because the left-hand side is. So that tells us both sides are equal to N, so we have

K*Q + L*P + 1 = A*P + B*Q + 1 = N.

So we know

A*P + B*Q = N - 1
P*Q       = N

and that’s enough to write some quadratic equations to solve for P, Q, giving us the private key.

The flag was PCTF{Rub_your_hands_palm_to_palm_vigorously_for_at_least_20_seconds_to_remove_any_private_information}.