# Lost Modulus Again

## Challenge Summary

We are given $e$, $d$, $p^{-1}\ \text{mod}\ q$ and $q^{-1}\ \text{mod}\ p$ for a particular RSA setting. We are also given a ciphertext $c$ that is encrypted by the aforementioned RSA key.
The objective is to find the corresponding message, $m$, for the ciphertext.

## Solution

### Part I: Forgive my bad eyesight

The most of the time spent on the challenge is to figure out $d$ is _actually_ the private key.

What was given in the output file was:

Key([e = 1048583, n = 20899..., x = 22886..., y = 13835...])

...and guess what, the $n$ was actually $d$ in disguise! I bet I better notice the challenge title and the source code next time.

### Part II: How to find the lost modulus?

#### From $e$ to $\phi(n)$

The first problem is to find $\phi(n)$. Remind that $ed\equiv 1\ (\text{mod}\ \phi(n))$, implying that there exists integers $k$ such that $ed-1=k\cdot\phi(n)$.

Since $d < \phi(n)$ in this challenge, we have $k\cdot\phi(n) = ed-1 < e\cdot \phi(n)$, therefore $k < e$.

Therefore, we can obtain a list of candidates for $\phi(n) = \frac{ed-1}{k}$ by exhausting $1 \leq k < e$.

#### From $\phi(n)$ to a _large_ multiple of $n$

Assume that we have found the correct $\phi(n)$ for the challenge. A bit of math would immediately lead us to the lost modulus: $$\phi(n)\cdot x \equiv (p-1)(q-1)\cdot x\equiv(-1)(q-1)(q^{-1})\equiv q^{-1} - 1\equiv x-1\ (\text{mod}\ p)$$

From the above, we know that there is some integer $m$ with $\phi(n)\cdot x-x+1=m\cdot p$. Similarly, there is some integer $m'$ with $\phi(n)\cdot y-y+1=m'\cdot q$.

Multiplying the two equations, we have $$Mn=mm'pq=\left(\phi(n)\cdot x-x+1\right)\left(\phi(n)\cdot y-y+1\right),$$ where $M = mm'$. This means that if we know $\phi(n)$, we can then deduce a _large_ multiple of $n$.

#### Polishing the multiple of $n$

At this moment, we are having a multiple of $n$. This is not ideal as it sounds like we need to factorize $n$ from its multiple.

However, it is not. Since we know $e$ and $d$, we can try arbitrary message $m_i$ (coprime with $n$). Since ${m_i}^{ed}\equiv m_i\ (\text{mod}\ n)$, ${m_i}^{ed} - m_i$ should be a multiple of $n$. What we can do is to compute $\text{gcd}\left({m_1}^{ed} - m_1, {m_2}^{ed} - m_2, ...\right)$.

This should be equal to $r\cdot n$ for a relatively smaller $r$. Since $n\approx \phi(n)$, $r \approx \frac{n}{\phi(n)}$. We guess $r=\left[\frac{n}{\phi(n)}\right]$ (should be right as it is quite small). Hence we can finally find the modulus $n$.

And we have the flag: `hitcon{1t_is_50_easy_t0_find_th3_modulus_back@@!!@!@!@@!}`!

###### tags: `HITCON CTF 2019 Quals` `Cryptography` `RSA`