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}modp$ is leaked.

The problem is to restore the plaintext from these information.

Solution

First, we have to restore

$\phi (N)=(p-1)(q-1)$.

From

$ed=1mod\phi (N)$, for some integer

$k>0$,

$ed-1=k\phi (N)$ holds true. Then from

$d<\phi (N)$, we can observe

$k<e=65537$ and we can brute-force the

$k$ which satisfies that condition. Now we got

$\phi (N)$.

Let's think about

$\phi (N)modp$. Here:

$$\begin{array}{rl}\phi (N)& =(p-1)(q-1)\\ & =p(q-1)-q+1\end{array}$$

and then,

$$\phi (N)-1=-qmodp$$

and if we multiply both sides by

$c=q^{-1}modp$,

$$\begin{array}{rlr}(\phi (N)-1)c& =-q{q}^{-1}& modp\\ (\phi (N)-1)c+1& =0& modp\end{array}$$

can be obtained. So

$(\phi (N)-1)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^{\phi (N)}=1modN$$

In particular, since

$N$ is a multiple of

$p$,

$a^{\phi (N)}-1$ will also become a multiple of

$p$.

Now if we calculate the following:

$$a^{\phi (N)}-1modm$$

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

$\phi (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=1modp$$

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

With Coppersmith's Attack, the condition required to get the solution

$(x_1,\cdots ,x_n)$ of n-variable non-identical linear equations

$$a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n\equiv Cmodp$$

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\leqq 1-{(1-\beta )}^{\frac{n+1}{n}}-(n+1)(1-{}^n\sqrt{1-\beta })(1-\beta )$$

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,\phi (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.