# Lost Key Again

## Challenge Summary

The challenge is given a encryption oracle of RSA that allows us to encrypt up to 15 bytes, prepended with a given prefix (`"X: "`). Besides, we have an encrypted flag.

## Solution

This challenge is kind of strange in my opinion. The _only_ question that comes to my mind during the game is:

> Why the heck could I decrypt with an encryption oracle of RSA?

It is rather weird, but it made sense for me after I solved the challenge. Here's the flow:

:::info
**TL;DR:**
- Recover $n$ from the encryption oracle with the homomorphic property
- Factorize $n$ with Pollard's $p-1$ algorithm (_since $p-1$ and $q-1$ are smooth_)
- Compute $e$ with Pohlig-Hellman algorithm (_since $p-1$ and $q-1$ are smooth, again_)
- Compute $d$ and decrypt the flag
:::

### Part I: Recover the $n$ from the encryption oracle

This part did not make me struggled. Since RSA is homomorphic, that is, $$\forall m_1, m_2\in\mathcal{M}, \text{Enc}(m_1\cdot m_2)=\text{Enc}(m_1)\cdot\text{Enc}(m_2).$$

Hence, we can encrypt the three messages:

1. `m_1 = 0x583a20`
2. `m_2 = 0x583a2000`
3. `m_3 = 0x583a200000`

and with the homomorphism, we have $c_1c_3 \equiv {c_2}^2\ (\text{mod}\ n)$. This implies that $c_1 c_3 - c_2^2$ is a multiple of $n$. By using the method given in _Lost Modulus Again_, we can compute $n$ from its multiple by encrypting more messages.

### Part II: Factorize $n$ and recover $e$

:::info
**Thoughts during the game.** How can use an encryption oracle to decrypt?

In most of the cases, this can be achieved by exploiting padding oracles (for instance, Bleichenbacher's attack). However, this challenge does not have a padding scheme. This does not work.

Why are they hiding $e$ from us? Is $e$ or $d$ "special"? I tried some small $e$ and $d$'s (like up to $10^8$) during the game but in vain.

How about factoring $n$? I don't think it is useful as we still need to deal with discrete logarithms to recover $e$.

:::

I had no idea how to proceed during the game, then I _~~took an arrow on my knee~~_ tried to factorize $n$ with [Pollard's $p-1$ algorithm](https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm) - and turns out it succeed!

This paves the remaining path to the flag, since we know $p-1$ and $q-1$ consist a product of small primes. With the fact, we can compute the discrete logarithm by Pohlig-Hellman in no time.

So I am skipping the details to the flag!

`hitcon{@@@_5m00thneSS_CAN_give_y0u_everything_@@@}`

:::success
**Takeaway:** If $n$ is smooth, we can [1] factor $n$ with Pollard's $p-1$ and [2] compute its discrete logarithm with Pohlig-Hellman.
:::

###### tags: `HITCON CTF 2019 Quals` `RSA` `Factorization` `Pollard's p-1 algorithm` `Pohlig-Hellman algorithm`