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)) # -> y1
ecc.point((p+1, 1057401451679095062531151979389760885573147826)) # -> y2
ecc.point((p+2, 142926404549455192668575513920450762633800129)) # -> y3
ecc.point((p-3, 773808304364278082418521288269860813684230337)) # -> y4
ecc.point((p+3, 155419950529021753751813670756068418661489493)) # -> y5
ecc.point((p-4, 564605286683346876667536567601259285744471988)) # -> y6
ecc.point((p-5, 812270051867990261460153809983232723732262237)) # -> y7
ecc.point((p+5, 410837747859871710141162996756729573836835781)) # -> y8
ecc.point((p-7, 576115660671090581945855297280052151651777662)) # -> y9

橢圓曲線的公式為 : y2=x3+ax+by^2 = x^3 + ax + b

先把上面的點做個命名方便後續的操作

然後隨便幾個點,把多餘的參數消掉,做成兩個 p 的倍數

舉個例子:

(y1)2=(p−1)3+(p−1)a+b(y_1)^2 = (p-1)^3 + (p-1)a + b
(y2)2=(p+1)3+(p+1)a+b(y_2)^2 = (p+1)^3 + (p+1)a + b
(y4)2=(p−3)3+(p−3)a+b(y_4)^2 = (p-3)^3 + (p-3)a + b

→(y2)2+(y4)2−2(y1)2 = ?   mod  p\rightarrow (y_2)^2 + (y_4)^2 - 2(y_1)^2\ =\ ?\ \ \ mod\ \ p

→(1+a+b)+(−27−3a+b)−2(−1−a+b) = ?   mod  p\rightarrow (1+a+b) + (-27-3a+b) - 2(-1-a+b)\ =\ ?\ \ \ mod\ \ p

→(1+a+b)+(−27−3a+b)+(2+2a−2b) = −24   mod  p\rightarrow (1+a+b) + (-27-3a+b) + (2+2a-2b)\ = \ -24\ \ \ mod\ \ p

→(1+a+b)+(−27−3a+b)+(2+2a−2b) +24=kp\rightarrow (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}