# "R U Sad" - Plaid CTF 2019

by holocircuit

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}`

.

*ctf*-

*cryptography*-

*mathematics*