# Together as one

Writer : yoshiking
[top](https://hackmd.io/ClxwWxDVSVC11Wrb-eGZIw)

yoshiking問題やっと理解できた〜:tada:
面白い！

Problem
---

# chall.py
from Crypto.Util.number import getStrongPrime, bytes_to_long

p = getStrongPrime(512)
q = getStrongPrime(512)
r = getStrongPrime(512)

n = p*q*r

x = pow(p + q, r, n)
y = pow(p + q*r, r, n)

m = bytes_to_long(open("./flag.txt", "rb").read())
assert m.bit_length() > 512
c = pow(m, 0x10001, n)

print(f"{n = :#x}")
print(f"{c = :#x}")
print(f"{x = :#x}")
print(f"{y = :#x}")

Output
---

# output.txt
n = 0x94cf51734887aa44204e7d64ed2b30763fd0715060afd5d15b697c940c272422b4ca765485f7c3116db1166ad1fec4cd4d82d3b32e881ed49f52efe31a226b307d60f2fb375400f9a19b0142e7d88d6118e02971724186e1ef13e586c744240b3ee7d6a105b82a3e3126ae364550e9b3a19d6b012083b8633ad428cf75cb200fe31121e6bf095418c5ed3819225910bc69ebe2e6a219638b830df45015c75ca9a507dc924718a540cfb5d2df09ff28d7cf8feb0e5e69a3d71057004132bb3e79
c = 0x8c0450dff19d853673d51cb2eab4cb84ffa7fa3eba900c1e96adbb2ccb6708320233e18b2d6ce487dbfb88f15b0ccac5829818ca49ac8ab08a1e5b94e27550798e6d1aae48812b784144dc7bed55cec6283042a296e25490990e07b8ff51b1a500b6d8c39af1c07c1ef57ca2b3774a4d38f6006a64f37133915f9afcbd08394e74c616fabd77d79cd9559a3eee41f2507556637bac6145bfba22319f424f07a33221a8fb9c89dc3c68e188230ed36e95a6baf977ca58d2036d136ebd55bd45d3
x = 0x38f530204337208b5bbfadd20fcd4416d8be1563c338c0ba464abbcd3699794c0c8e0b6f17f41bc5e42dd5f900d3644b34f4530157cc8c026894f97f2feb5475e58cdf9125d96bdae25bbf6afdf58129c8e1c70a5b47f2dbe3f89e851c124bed2b40f6e8ec8d6d3ff941fa5dcde893c661059fffdb5086863e35228bc79b1ba830555c3168c88a53e3c7eee17312c401914442d4e04c5014aa484994d0c680980f53aeef01c9c246ec76dcdf8816036b77629610709ccc533cbd09a818146060
y = 0x607e4383ee2f5bb068a4fb51205396c784a56e971cee8f2b2c79fbf1ce4161a4031aa10df22723005024ef592764c4391f31ca35137221a7431c68033b5f92ab5bf9c660e5cda375faf4f4e734cb8745d0b7b056b2d9ba38a733fae118f07ceb1af4fbb2818b6cf4394f166f3790a9ad39efb27a970399ed1fc04b96a282681109825c96e3784f1ee3ac1a787f28dd7c74cc6cccecffb0ce534e1ed7192ccc2bc3f822ad16dc42608d6fe1de447e4ed9474d1113bd0514d1f90b92f04769059

Solve
---
３つの素数$p,q,r$の積$n=p*q*r$と暗号文、$p,q,r$を使用した$x\equiv (p+q)^r \mod n$と$y\equiv (p+qr)^r \mod n$が与えられる。
プログラムを読むと、flagを公開鍵`e=0x10001`と$n$でRSAで暗号化したものを暗号文として出力している。

$x\equiv (p+q)^r \mod n$は二項定理より、

$$p^r+{}_r\mathrm{C}_1 p^{-1}q+{}_r\mathrm{C}_2 p^{-2}q^2+ \dots +{}_r\mathrm{C}_{r-1}pq^{r-1}+q^r$$
となり、$p^r$と$q^r$以外の項は$p*q*r$を含むので$\mod n$で消える。
よって、$x\equiv (p+q)^r\equiv p^r+q^r \mod n$
$y$も同様に、$y\equiv (p+qr)^r \equiv p^r+(qr)^r \mod n$

ここで、$y-x$とすると、$y-x=g^r(r^r-1)+k*pqr$と書くことができ、$y-x$と$n$は共に$q$の倍数となる。
よって、$\gcd(y-x,n)$とすることで、共通因数である$q$を求めることができる。

次に、Fermatの小定理より
$$
g^{r-1} \equiv 1 \mod r\\
g^rg^{-1}\equiv 1 \mod r\\
g^r\equiv g \mod r
$$
であるから、
$$
x\equiv (p+q)^r \mod n=(p+q) \mod r\\
y\equiv (p+qr)^r \mod n=(p+qr) \mod r
$$
よって、
$$
y-x+q=p+gr-p-q+q \pmod r\\
=gr \mod r
$$
となり、$gcd(y-x+q,n)=qr$を求めることができる。
$q$はすでに求まっているから$r=qr//q$
最後に、$p = (pqr//q)//r$で$p,q,r$をそれぞれ求めることができる。
$p,q,r$から秘密鍵$d$を求めて、RSAの復号を行うことでflagを取ることができる。

solver.py
from Crypto.Util.number import isPrime,long_to_bytes
import math
with open('output.txt') as f:
    n = int(f.readline()[4:],16)
    c = int(f.readline()[4:],16)
    x = int(f.readline()[4:],16)
    y = int(f.readline()[4:],16)

# Binomial theorem
q = math.gcd(y-x,n)
pr = n//q

# Fermat's little theorem
r = math.gcd((y-x+q)//q,n)
p = pr//r

assert n==p*q*r

e = 0x10001
d = pow(e,-1,(p-1)*(q-1)*(r-1))

print(long_to_bytes(pow(c,d,n)))

Flag
---
:tada: [CakeCTF{This_chall_is_inspired_by_this_music__Check_out!__https://www.youtube.com/watch?v=vLadkYLi8YE_cf49dcb6a31f}](https://www.youtube.com/watch?v=vLadkYLi8YE_cf49dcb6a31f)

###### tags: `CakeCTF` `crypto` `yoshiking`