# 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