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

橢圓曲線的公式為 ： $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 了

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}