# TSG CTF 2020 Modulus Amittendus Writeup

## 問題

RSAで暗号化されたフラグと公開鍵が与えられる。

ただし、バグによって $N$ のかわりに $d$ が与えられ、加えて係数 $c=q^{-1}\bmod p$ が漏洩している。

ここからフラグを復号するのが問題である。

## 解法

まず、$\varphi(N)=(p-1)(q-1)$ を復元する。

$ed=1\bmod \varphi(N)$ より、ある整数 $k>0$ について $ed-1=k\varphi(N)$ が成り立つ。ここで $d<\varphi(N)$ より $k<e=65537$ なのでこのような条件を満たす $k$ を全探索することができる。よって $\varphi(N)$ を得る。

いま $\varphi(N) \bmod p$ を考えると、

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

より

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

である。

$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}
$$

よって $\left(\varphi(N)-1\right)c+1$ は $p$ の倍数となる。これを計算し $m$ とおく。

ところでオイラーの定理より $N$ と互いに素である任意の整数 $a$ について

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

である。特に $N$ は $p$ の倍数なので、$a^{\varphi(N)}-1$ は $p$ の倍数となる。

いま、

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

を計算すると、法および数値が $p$ の倍数であることから計算結果もまた $p$ の倍数となる。

この式では $a$ の値を変更することで $p$ の倍数を任意に得ることができる。よってこれらの値の最大公約数をとることによって $p$ を得る。

$\varphi(N), p$ より $q$ が求まるため、これで復号に必要な情報が求まり、解ける。

## 補遺

なお、$m$ を求めたあとオイラーの定理を用いずに、Coppersmith's Attack を用いて

$$cq=1\bmod p$$

の解 $q$ を直接得られるようにも見える。が、この方法では解を得られない。以下に証明を示す。

Coppersmith's Attack を用いて $p$ の倍数 $N$ と $p$ の下限 $p\geqq N^\beta$ および $x$ の上限 $x_{i}\leqq X_{i}$ から、n変数非同次線形方程式

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

の解 $\left(x_{1},\cdots,x_{n}\right)$ を得るための求解条件は、

$$\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)$$

である。

特に今回の式では $n=1$ なので、式を整理して

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

を得る。

ここで $c\approx p, \varphi(N)\approx p^2$ と評価できるので、$m\approx p^3$ である。よって $N=m$ とすると $p$ の下限は

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

つまり $\beta\approx 1/3$ とおける。

また $X_1=q, N\approx q^3$ より

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

以上を勘案すると、上の求解条件は

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

となり、誤差を考慮しても明らかに満たされない。