# TSG CTF 2020 Modulus Amittendus Writeup

## Problem

The flag encrypted with RSA and its public key are given.

But we are given $d$ instead of $N$, by bug. Additionally, the coefficient $c=q^{-1}\bmod p$ is leaked.

The problem is to restore the plaintext from these information.

## Solution

First, we have to restore $\varphi(N)=(p-1)(q-1)$.

From $ed=1\bmod \varphi(N)$, for some integer $k>0$, $ed-1=k\varphi(N)$ holds true. Then from $d<\varphi(N)$, we can observe $k<e=65537$ and we can brute-force the $k$ which satisfies that condition. Now we got $\varphi(N)$.

Let's think about $\varphi(N) \bmod p$. Here:

$$
\begin{aligned}
\varphi(N)&=\left(p-1\right)\left(q-1\right)\\&=p\left(q-1\right)-q+1
\end{aligned}
$$

and then,

$$
\varphi(N)-1=-q\bmod p
$$

and if we multiply both sides by $c=q^{-1}\bmod p$,

$$
\begin{aligned}
\left(\varphi(N)-1\right)c&=-qq^{-1}&\bmod p\\\left(\varphi(N)-1\right)c+1&=0&\bmod p
\end{aligned}
$$

can be obtained. So $\left(\varphi(N)-1\right)c+1$ is a multiple of $p$. We can calculate this and put it as $m$.

By the way, from Euler's theorem in number theory, the following holds for any integer $a$ that is prime to $N$ and each other.

$$
a^{\varphi(N)}=1\bmod N
$$

In particular, since $N$ is a multiple of $p$, $a^{\varphi(N)}-1$ will also become a multiple of $p$.

Now if we calculate the following:

$$a^{\varphi(N)}-1\bmod m$$

the result will be also a multiple of $p$ since the modulo and the original number is a mulitple of $p$.

In this formula we can get a multiple of $p$ as many as we like, by changing the value of $a$. So we can obtain $p$ by getting GCD of these values.

From $\varphi(N), p$ we can get $q$, so all the information needed to decrypt RSA is given. Then we can get the flag.

## Appendix

By the way, after we got $m$ it seems we can obtain $q$ by not using Euler's theorem and by using Coppersmith's Attack on the formula:

$$cq=1\bmod p$$

But this must be impossible. The following is the proof.

With Coppersmith's Attack, the condition required to get the solution $\left(x_{1},\cdots,x_{n}\right)$ of n-variable non-identical linear equations

$$a_{1}x_{1}+a_{2}x_{2}+\cdots+a_{n}x_{n}\equiv C\bmod p$$

from $N$, a multiple of $p$ and $p\geqq N^\beta$, the lower boundary $p$ and $x_{i}\leqq X_{i}$, the upper boundary of $x$ is

$$\frac{1}{\log N}\sum_{i=1}^{n}\log X_{i}\leqq1-\left(1-\beta\right)^{\frac{n+1}{n}}-\left(n+1\right)\left(1-{}^{n}\sqrt{1-\beta}\right)\left(1-\beta\right)$$

In our situation $n=1$, so by sorting out the formula we get

$$\frac{\log X_1}{\log N}\leqq\beta^2$$

Then we can evaluate that $c\approx p, \varphi(N)\approx p^2$, and we get $m\approx p^3$. Then if we put $N=m$, the lower boundary of $p$ is:

$$p\geqq N^{1/3}$$

and we can assume $\beta\approx 1/3$.

And from $X_1=q, N\approx q^3$:

$$\frac{\log X_1}{\log N}\approx \frac{1}{3}$$

Considering the above, the above condition will become

$$\frac{1}{3}\leqq \left(\frac{1}{3}\right)^2$$

which is clearly not satisfied even after considering the error.