###### tags: `cakeCTF` `crypto`

# [crypto] Together as one - cakeCTF 2021

## Challenge
RSA問題
以下の値が貰える。
$$
n = p \cdot q \cdot r\\
c \equiv m^{\text{0x10001}} \pmod{n} \\
x \equiv (p + q)^r \pmod{n}\\
y \equiv (p + q\cdot r)^r \pmod{n}
$$

## Solution
$x, y$をそれぞれ数論パワーで殴ることで、$p, q, r$を求めることができる。

まず、二項定理より

$$
\begin{eqnarray}
\left\{
\begin{array}{l}
x \equiv p^r + q^r \pmod{n} \\
y \equiv p^r + (qr)^r \pmod{n}
\end{array}
\qquad (1)
\right.
\end{eqnarray}
$$

となることがわかる。
ここで$q$を法としてみると、

$$
\begin{eqnarray}
\left\{
\begin{array}{l}
x \equiv p^r \pmod{q} \\
y \equiv p^r \pmod{q}
\end{array}
\right.
\end{eqnarray}
$$

となる。（$\bmod{n}$は$k\cdot n$となり、$\bmod{q}$では当然0となる）

つまり法$q$において、$x$と$y$は合同である。よって、

$$
\begin{align}
x &\equiv y \pmod{q}\\
&= y + k\cdot q\\
x - y &= k\cdot q
\end{align}
$$

となり、$gcd(x-y, n)$から$q$を求めることができる。

次に、(1)から$r$を法としてみると

$$
\begin{eqnarray}
\left\{
\begin{array}{l}
x \equiv p + q \pmod{r} \\
y \equiv p \pmod{r}
\end{array}
\right.
\end{eqnarray}
$$

となる。（フェルマーの小定理より、$p^r\pmod{r} \equiv p$）
ここで、$x, y, p$が手元にあるので、

$$
\begin{align}
x &\equiv y + q \pmod{r}\\
x - y - q &\equiv 0 \pmod{r}\\
&= k\cdot r
\end{align}
$$

となり、$gcd(x - y - q, n)$から$r$を求めることができる。

以上より、$q, r$が求まったので$p$も求めることができ、フラグを入手できる。

from Crypto.Util.number import long_to_bytes, inverse, GCD

exec(open("./../distfiles/output.txt").read())

q = GCD(n, x-y)
r = GCD(n//q, y - (x - q))
p = n // (q * r)

assert n == p*q*r

d = inverse(0x10001, (p-1)*(q-1)*(r-1))
print(long_to_bytes(pow(c, d, n)))

$ python3 solver.py
b'cakeCTF{This_chall_is_inspired_by_this_music__Check_out!__https://www.youtube.com/watch?v=vLadkYLi8YE}\n'

問題名とフラグはTimmy Trumpetの[Diamonds](https://www.youtube.com/watch?v=vLadkYLi8YE)から