Source: SH365CTF
Author: hiikunZ

※ SH365CTFはSecHack365（2024 4th Event Week）にて、有志によって非公式に開催されたCTFです。

ヒント付きRSAの問題。

6_3_4_RSA.py

from Crypto.Util.number import bytes_to_long, getPrime
import os

flag = os.getenv("FLAG", "SecHack365{DUMMY_FLAG}").encode()

p = getPrime(256)
q = getPrime(256)
n = p * q
e = 0x10001
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

m2 = p * 63 + q * 4
c2 = pow(m2, e, n)
print(f"c2 = {c2}")

m3 = p * 6 + q * 34
c3 = pow(m3, e, n)
print(f"c3 = {c3}")

n, e, cの他、c2, c3が与えられている。

n = 8787853186604501465350440400554867782683216927926017112267287590780322575979212002323860584291544916443498557046604413617496140916981417512780552626597057
e = 65537
c = 6994703800679360207351562852610768968758729109353781576204971881715149388015793249124620755345161501651173676074901239500988866504240518770986069965529302
c2 = 6385814305925723080682880515729304169424155137644522369442741557055936719078382330339372646166228859072058894989677178856926023196039446519300197152837681
c3 = 644703175078956118713579365177642398682242507389616543933739174119564639977801086892890065740791849826185480118205694510645997115106095875550962657999393

\displaylines{
c2 ≡ (63p+4q)^{e} \qquad (mod \: n)
\\
c3 ≡ (6p+34q)^{e} \qquad (mod \: n)
}

c2, c3からp, qを復元したい。

以下、mod n の世界で考える。n = pq より、mod n の世界においてpqを含む項は全て0となるので、

\displaylines{
c2 ≡ (63p+4q)^{e} ≡ 63^{e}p^{e}+4^{e}q^{e}
\\
c3 ≡ (6p+34q)^{e} ≡ 6^{e}p^{e}+34^{e}q^{e}
}

が得られる。開催期間中はここで詰まってしまったので、ここからはupsolveとなる。

ここからqを消去する。c2の式は

\displaylines{
q^{e} ≡ (c2-63^{e}p^{e}) / 4^{e}
}

と変形できるので、これををc3の式に代入して、

\displaylines{
c3 ≡ 6^{e}p^{e}+34^{e}(c2-63^{e}p^{e}) / 4^{e}
\\
(34^{e}63^{e} - 4^{e}6^{e}) p^{e} ≡ 34^{e}c2 - 4^{e}c3
}

が得られ、この式の右辺はpの倍数であることが十分に期待できる。よって、n = pq との最大公約数を求めることでpが求まる。

あとは復号するだけ。

import math
from Crypto.Util.number import long_to_bytes

n = 8787853186604501465350440400554867782683216927926017112267287590780322575979212002323860584291544916443498557046604413617496140916981417512780552626597057
e = 65537
c = 6994703800679360207351562852610768968758729109353781576204971881715149388015793249124620755345161501651173676074901239500988866504240518770986069965529302
c2 = 6385814305925723080682880515729304169424155137644522369442741557055936719078382330339372646166228859072058894989677178856926023196039446519300197152837681
c3 = 644703175078956118713579365177642398682242507389616543933739174119564639977801086892890065740791849826185480118205694510645997115106095875550962657999393

a = 34**e
b = 4**e

p = math.gcd(a*c2 - b*c3, n)
q = n // p
assert p*q == n
print(f"p = {p}")
print(f"q = {q}")

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

m = pow(c, d, n)
flag = long_to_bytes(m)
print(f"flag: {flag.decode()}")

flagが得られた。
SecHack365{don't_3ncrypt_f4ctors_relat3d_number5_in_RSA!}