AIS3 2020 - 🐪 Camel (Crypto, 372)
Challenge
題目:prob.sage
Solve
首先,題目給的橢圓曲線在小 x (x=1,2,3,…) 都有對應的 y
而且橢圓曲線的參數就是 Flag ( 找這種 Flag 找到快中風 )
那目標很簡單,我們只要利用這些點還原出其橢圓曲線的參數,就相當於拿到 FLAG 了
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))
|
橢圓曲線的公式為 : y2=x3+ax+b
先把上面的點做個命名方便後續的操作
然後隨便幾個點,把多餘的參數消掉,做成兩個 p
的倍數
舉個例子:
(y1)2=(p−1)3+(p−1)a+b
(y2)2=(p+1)3+(p+1)a+b
(y4)2=(p−3)3+(p−3)a+b
→(y2)2+(y4)2−2(y1)2 = ? mod p
→(1+a+b)+(−27−3a+b)−2(−1−a+b) = ? mod p
→(1+a+b)+(−27−3a+b)+(2+2a−2b) = −24 mod p
→(1+a+b)+(−27−3a+b)+(2+2a−2b) +24=kp
同理再透過另一組找到 p
的倍數
取公因數就可以找出 p
了
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
推出來就好了
b = ((y1**2 + y2**2) // 2) % p a = (y2**2 -1-b) %p
|
AIS3{Curv3_Mak3_M3_Th1nK_Ab0Ut_CaME1_A_P}