tags: cakeCTF crypto

[crypto] Together as one - cakeCTF 2021

Challenge

RSA問題
以下の値が貰える。

$$\begin{gathered} n=p\cdot q\cdot r \\ c\equiv m^{\text{0x10001}}(\mathrm{mod}n) \\ x\equiv (p+q{)}^r(\mathrm{mod}n) \\ y\equiv (p+q\cdot r{)}^r(\mathrm{mod}n) \end{gathered}$$

Solution

$x,y$をそれぞれ数論パワーで殴ることで、

$p,q,r$を求めることができる。

まず、二項定理より

$$\begin{array}{r}\{\begin{array}{l}x\equiv p^r+q^r(\mathrm{mod}n)\\ y\equiv p^r+(qr{)}^r(\mathrm{mod}n)\end{array}(1)\end{array}$$

となることがわかる。
ここで

$q$を法としてみると、

$$\begin{array}{r}\{\begin{array}{l}x\equiv p^r(\mathrm{mod}q)\\ y\equiv p^r(\mathrm{mod}q)\end{array}\end{array}$$

となる。（

$modn$は

$k\cdot n$となり、

$modq$では当然0となる）

つまり法

$q$において、

$x$と

$y$は合同である。よって、

$$\begin{array}{rl}x& \equiv y(\mathrm{mod}q)\\ & =y+k\cdot q\\ x-y& =k\cdot q\end{array}$$

となり、

$gcd(x-y,n)$から

$q$を求めることができる。

次に、(1)から

$r$を法としてみると

$$\begin{array}{r}\{\begin{array}{l}x\equiv p+q(\mathrm{mod}r)\\ y\equiv p(\mathrm{mod}r)\end{array}\end{array}$$

となる。（フェルマーの小定理より、

$p^r(\mathrm{mod}r)\equiv p$）
ここで、

$x,y,p$が手元にあるので、

$$\begin{array}{rl}x& \equiv y+q(\mathrm{mod}r)\\ x-y-q& \equiv 0(\mathrm{mod}r)\\ & =k\cdot r\end{array}$$

となり、

$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から