Official THJCC Writeups for lIne & F&S Farm

, , ,

Before all

打給賀，挖勾來水幾ㄆㄧ文啊，沒，最近應該會重回頻繁更新之路（？）
這次在 THJCC 出了三道題目，lIne, F&S Farm 兩道 Insane 難度以及一個 DAES（預設是 HARD 就隨手出個 MitM，結果好像太小看大家(和 LLM)了）。

特別來題解一下兩道 Insane 吧，不然都沒高中生要念 Crypto 了 qWq （沒有高中生做出來，公開組解出人數分別是 3/2，特別感謝 Chisheng Chen 和 papa9995 特別捧場 qq）
解這兩題分別需要的相關知識都可以在 CryptoHack 的 Lattices 和 ECC 兩個章節學到！

*題目設計雖然說防破台，但認真 Google 跟 GPT 其實都是有機會解出來的，希望下次有人挑戰成功我的 Crypto :P

lIne

給定就是一個參數比未知數大很多的複數平面線性方程，但只給一條： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from random import getrandbits
import os
import hashlib

flag=os.urandom(8).hex()
keys=[getrandbits(48) for _ in range(16)]

def to_complex(datas):
    imag_datas=[]
    for i in range(0, len(datas), 2):
        imag_datas.append(CC([datas[i], datas[i+1]]))
    return imag_datas

imag_flag=to_complex([int(chr, 16) for chr in flag])
imag_keys=to_complex(keys)

cnt=0
for i in range(8):
    cnt+=imag_flag[i]*imag_keys[i]

print(f"{imag_keys}\n{cnt}")
print(f"Gift: {hashlib.md5(b'THJCC{'+flag.encode()+b'}').hexdigest()}")

# [9.83329568728950e13 + 1.94539067458416e14*I, 4.57795946512170e13 + 5.54913449090490e13*I, 3.35752608137010e13 + 1.10651091133529e14*I, 8.09172050820060e13 + 6.09012985967910e13*I, 2.75388068605530e13 + 5.12867910525740e13*I, 2.33510497525684e14 + 9.11264352204540e13*I, 2.36186170290599e14 + 2.03323868604921e14*I, 1.37793863865401e14 + 1.40354868241912e14*I]
# 3.22421607806873e14 + 1.37668712938916E+16*I
# Gift: 69ae60327282356b2f2731e6acf624f4

首先，對於實數的 Case，其實當兩邊量級不同的時候可以參考一種叫做 LLL 的算法進行解題。
想懶人包一點可以直接看我去年在完全新手向（今年不再是）的 NoHackNoCTF 出的題目：https://blog.whale-tw.com/2024/11/17/nhnc-2024-wp/#Lion-RSA
再來，剩下其實就是一條複數平面的方程終究是帶兩個參數的，簡單的觀察（在 IrisCTF 2025 (Write Up Link)其實有很類似的題目），可以發現經由線性變換能把它直接換成兩條算式，最後再一口氣拿這兩條壓 LLL 就可以約束出解了 … 嗎（？）
沒有，我很故意的讓浮點數大小超出精度，所以對於 1.37668712938916E+16*I 這一項要爆搜後兩位（一百組），每次都找 LLL 才能解決！

*為方便解題，我直接送了 flag md5 給選手比對 :P

Solve Script 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from random import getrandbits
import os
import hashlib
from tqdm import trange

keys=[9.83329568728950e13 + 1.94539067458416e14*I, 4.57795946512170e13 + 5.54913449090490e13*I, 3.35752608137010e13 + 1.10651091133529e14*I, 8.09172050820060e13 + 6.09012985967910e13*I, 2.75388068605530e13 + 5.12867910525740e13*I, 2.33510497525684e14 + 9.11264352204540e13*I, 2.36186170290599e14 + 2.03323868604921e14*I, 1.37793863865401e14 + 1.40354868241912e14*I]
cnt1=int(3.22421607806873e14)
cnt2=int(1.37668712938916E+16)
chksum="69ae60327282356b2f2731e6acf624f4"

def arr2str(datas):
    val='THJCC{'
    for i in datas:
        val+=hex(i)[-1]
    val+='}'
    return val

def solve_2(keys1, keys2, c1, c2, size):
    A=[[0]*(size+3) for _ in range(size+1)]
    for i in range(size):
        A[i][0]=keys1[i]*-1024
        A[i][1]=keys2[i]*-1024
        A[i][i+2]=1

    A[size][0]=c1*1024
    A[size][1]=c2*1024
    A[size][-1]=2**128
    A=Matrix(ZZ, A)
    return A.LLL()

key1=[]
key2=[]

for i in range(8):
    key1.append(int(keys[i].real()))
    key1.append(int(keys[i].imag())*-1)
    key2.append(int(keys[i].imag()))
    key2.append(int(keys[i].real()))

for i in trange(100):
    sol=solve_2(key1, key2, cnt1, cnt2+i, 16)
    if hashlib.md5(arr2str(sol[-1][2:18]).encode()).hexdigest()==chksum:
        print(arr2str(sol[-1][2:18]))

F&S Farm

牛牛都在用 ECC 對話了呢 (x)
題目： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
from Crypto.Util.number import bytes_to_long
from secrets import flag

p=62879100257270410351378827582399744186567306643585504679294001019813699019068488434060287
G=(29744250428373565997166706391119259777317687430240284769755486706450263827970573185114321, 58040952245003801555956486798081163256240960098545028765546427006596708448541303071682039, 27494033982261584279714070225528681888589641976608352586941470965443043075381645410758543)
a=0x1ced7ea
k=Integer(bytes_to_long(flag))

def point_add_mod(P, Q, a, p):
    X1, Y1, Z1 = P
    X2, Y2, Z2 = Q
    
    if Z1 % p == 0:
        return Q
    if Z2 % p == 0:
        return P
    
    Z1_sq = pow(Z1, 2, p)
    Z2_sq = pow(Z2, 2, p)
    U1 = (X1 * Z2_sq) % p
    U2 = (X2 * Z1_sq) % p
    S1 = (Y1 * pow(Z2, 3, p)) % p
    S2 = (Y2 * pow(Z1, 3, p)) % p
    
    H = (U2 - U1) % p
    R = (S2 - S1) % p
   
    if H % p == 0:
        if R % p == 0:
            return point_double_mod(P, a, p)
        else:
            return (0, 1, 0)
    
    H_sq = pow(H, 2, p)
    H_cu = pow(H, 3, p)
    R_sq = pow(R, 2, p)
    
    X3 = (R_sq - H_cu - 2 * U1 * H_sq) % p
    Y3 = (R * (U1 * H_sq - X3) - S1 * H_cu) % p
    Z3 = (Z1 * Z2 * H) % p
    
    return (X3, Y3, Z3)

def point_double_mod(P, a, p):
    X1, Y1, Z1 = P
    
    if Z1 % p == 0:
        return (0, 1, 0)
    
    Y1_sq = pow(Y1, 2, p)
    A = pow(X1, 2, p)
    B = Y1_sq
    C = pow(B, 2, p)
    D = (2 * ((pow(X1 + B, 2, p) - A - C))) % p 
    E = (3 * A + a * pow(Z1, 4, p)) % p
    F = pow(E, 2, p)
    
    X3 = (F - 2 * D) % p
    Y3 = (E * (D - X3) - 8 * C) % p
    Z3 = (2 * Y1 * Z1) % p
    
    return (X3, Y3, Z3)

def point_scalar_mult(k, P, a, p):
    result = (0, 1, 0)
    if k == 0 or P == (0, 1, 0):
        return result
    
    Q = P
    for bit in reversed(k.bits()):
        result = point_double_mod(result, a, p)
        if bit == 1:
            result = point_add_mod(result, Q, a, p)
    
    return result

print(point_scalar_mult(k, G, a, p))
# (11124982001864013322453099807532963752362958176203400769835646437519628542120137037648651, 6911772123608455530174938059753499932701792542764880851311370143692220479290267649006859, 61659910325477356427200894513232023552537183179022949708356534152728209603841725323867499)

這道題目的 ECC 運算跟一般的 $y^2=x^3+ax+b$ 不太一樣，或許你有能力直接看出，也可能查文獻，或乾脆一點 Chat GPT 問一問應該都會得知這是一種叫做 Jocabian Form 的曲線！
有興趣認真研究的可以看看這兩篇：
https://en.wikipedia.org/wiki/Jacobian_curve
https://eprint.iacr.org/2014/1014.pdf
懶人包：他的曲線模式是 $y^2 = x^3 + axz^4 + bz^6$，然後 $(x, y, z)$ 會對應到 $(\frac{x}{z^2}, \frac{y}{z^3})$
EZ!
接下來轉換完就是去找找這條曲線的洞，本來是要算嵌入度過小做 MoV Attack：
看完這邊 https://risencrypto.github.io/WeilMOV/
懶人包：反正這種東西他可以被算成一種 order 比較好算的另一種群（$F_{p^k}$）的運算，所以 DLP 很好解

最後的 Solve Script，其中使用的座標是我經過 $(\frac{x}{z^2}, \frac{y}{z^3})$ 變換的，記得除法是對於整數同餘 $p$ 的乘法群所以除法其實是乘以模逆元 pow(z, q, -1) 的概念 :P 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
p=62879100257270410351378827582399744186567306643585504679294001019813699019068488434060287
G=(21032054291018026850893429260281324837357336859712891830625893665496718606255158332594666, 14673210533022557360839956302611064144635693910962357937771307057604112623302442480828361)
Q=(62224852567433890039016721509197121057473008753624816661744394931746383504379118854421719, 52163034654574478445279194476444315566293392088030892939008892455119127289985541051204630)

a = 0x1ced7ea
b = 0

order = p+1
print(order)
F = GF(p)
k = 2 # min_k E.order() | (p^k-1)
Fy = GF(p^k,'y')

E = EllipticCurve(F,[a,b])
Ee = EllipticCurve(Fy,[a,b])

P = E(G)
xP = E(Q)

Pe = Ee(P)
xPe = Ee(xP)

R = Ee.random_point()
m = R.order()
d = gcd(m, P.order())
Q = (m//d)*R

assert P.order()/Q.order() in ZZ
assert P.order() == Q.order()

n = P.order()
print('computing pairings')
alpha = Pe.weil_pairing(Q,n)
beta = xPe.weil_pairing(Q,n)
print(alpha, beta)
print('computing log')
dd = beta.log(alpha)
print(dd)

P.S. 因為我 ORDER Factor 後最大的是 $10^{15}$，好像有個叫做 Chisheng Chen 的人說：啊還是夠 Smooth 啊，Pohlig-Hellman 走起（