Challenge
題目：prob.sage
Solve
首先，題目給的橢圓曲線在小 x (x=1,2,3,…) 都有對應的 y
而且橢圓曲線的參數就是 Flag （ 找這種 Flag 找到快中風 ）
那目標很簡單，我們只要利用這些點還原出其橢圓曲線的參數，就相當於拿到 FLAG 了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| a = int(FLAG.hex()[:20],16)
b = int(FLAG.hex()[20:44],16)
p = int(FLAG.hex()[44:],16)
ecc = EllipticCurve(GF(p), [a,b])
ecc.point((p-1, 759211060281786031869071242155234136314844944))
ecc.point((p+1, 1057401451679095062531151979389760885573147826))
ecc.point((p+2, 142926404549455192668575513920450762633800129))
ecc.point((p-3, 773808304364278082418521288269860813684230337))
ecc.point((p+3, 155419950529021753751813670756068418661489493))
ecc.point((p-4, 564605286683346876667536567601259285744471988))
ecc.point((p-5, 812270051867990261460153809983232723732262237))
ecc.point((p+5, 410837747859871710141162996756729573836835781))
ecc.point((p-7, 576115660671090581945855297280052151651777662))
|
橢圓曲線的公式為 ： $y^2 = x^3 + ax + b$
先把上面的點做個命名方便後續的操作
然後隨便幾個點，把多餘的參數消掉，做成兩個 p 的倍數
舉個例子：
$(y_1)^2 = (p-1)^3 + (p-1)a + b$
$(y_2)^2 = (p+1)^3 + (p+1)a + b$
$(y_4)^2 = (p-3)^3 + (p-3)a + b$
$\rightarrow (y_2)^2 + (y_4)^2 - 2(y_1)^2\ =\ ?\ \ \ mod\ \ p$
$\rightarrow (1+a+b) + (-27-3a+b) - 2(-1-a+b)\ =\ ?\ \ \ mod\ \ p$
$\rightarrow (1+a+b) + (-27-3a+b) + (2+2a-2b)\ = \ -24\ \ \ mod\ \ p$
$\rightarrow (1+a+b) + (-27-3a+b) + (2+2a-2b)\ + 24 = kp$
同理再透過另一組找到 p 的倍數
取公因數就可以找出 p 了
1
2
3
4
5
6
| k1p = (y2**2 + y4**2 - 2*y1**2 +24)
k2p = (y4**2 + y8**2 - 2*y2**2 -96)
p = gcd(k1p,k2p)
assert k1p % p == 0
assert k2p % p == 0
|
有了 p 之後就好辦了，再把 a, b 推出來就好了
1
2
| b = ((y1**2 + y2**2) // 2) % p
a = (y2**2 -1-b) %p
|
AIS3{Curv3_Mak3_M3_Th1nK_Ab0Ut_CaME1_A_P}
