Cyber Apocalypse 2021 | Wii Phit - crypto-writeup-public

#cyber_apocalypse_ctf_2021

from Crypto.Util.number import bytes_to_long
from secrets import FLAG,p,q

N = p**3 * q
e = 0x10001
c = pow(bytes_to_long(FLAG),e,N)

print(f'Flag: {hex(c)}')

# Hint

w = 25965460884749769384351428855708318685345170011800821829011862918688758545847199832834284337871947234627057905530743956554688825819477516944610078633662855
x = p + 1328
y = p + 1329
z = q - 1

assert w*(x*z + y*z - x*y) == 4*x*y*z

overview

#RSA っぽい感じではある
$N$ が与えられてない
かわりに $w(xz + yz - xy) = 4xyz$ という式が与えられている

solution 1

solution 2

#近似式を立てて探索
両辺 $wxyz$ で割って $\frac{1}{y} + \frac{1}{x} - \frac{1}{z} = \frac{4}{w}$
$y = x+1$ を使いつつ変形して $\frac{1}{x+1} + \frac{1}{x} - \frac{4}{w} = \frac{1}{z}$
$\frac{1}{z} \simeq 0$ と $\frac{1}{x+1} \simeq \frac{1}{x}$ を使うと $2w \approx 4x$
$x$ を探索しつつ $z$ を計算し、等式が成り立つようなペアを見つける

w = 25965460884749769384351428855708318685345170011800821829011862918688758545847199832834284337871947234627057905530743956554688825819477516944610078633662855

approx_x = w // 2

for bias in range(-10000, 10000):
    x = approx_x + bias
    y = x+1
    z = (w*x*y) // (w*x + w*y - 4*x*y)

    if w*(x*z + y*z - x*y) == 4*x*y*z:
        q = z + 1
        p = x - 1328
        print("[+] p = {}, q = {}".format(p, q))
        quit()
print("[-] not found")

solution 3

$f = x*z + y*z - x*y, g = 4*x*y*z$ とおいて
$g = d*f + r$ と書いてみる。このとき $d == w$ が成り立ちそう、かつ $d$ が一変数になっているのでを sageに解かせてみると解ける
#多項式の商や余りを考える

w = 25965460884749769384351428855708318685345170011800821829011862918688758545847199832834284337871947234627057905530743956554688825819477516944610078633662855
PR.<p, q> = PolynomialRing(QQ)  # not ZZ but QQ
x = p + 1328
y = p + 1329
z = q - 1

f = (x*z + y*z - x*y)
g = 4*x*y*z

d, r = g.quo_rem(f)
print(d)

p = (d-w).univariate_polynomial().roots()[0][0]
q = f.subs(p=p).univariate_polynomial().roots()[0][0]
print("[+] p={}, q={}".format(p, q))

solution 4

z3 で解けてしまうらしい
#作問するときに気をつけること

from z3 import *
from Crypto.Util.number import long_to_bytes

c = ...
e = ...
w = ...

p = Int("p")
q = Int("q")
x = p + 1328
y = p + 1329
z = q - 1
s = Solver()
s.add(p>0)
s.add(q>0)
s.add(w*(x*z + y*z - x*y) == 4*x*y*z)
if s.check() == sat:
    m = s.model()
    p = m[p].as_long()
    q = m[q].as_long()

e = 0x10001
N = p**3 * q
phi = p**2*(p-1)*(q-1)
d = pow(e,-1,phi)
m = pow(c,d,N)
print(long_to_bytes(m))