from Crypto.Util.number import * from secret import Curve,gx,gy
# flag = "hgame{" + hex(gx+gy)[2:] + "}"
defison(C, P): c, d, p = C u, v = P return (u**2 + v**2 - c**2 * (1 + d * u**2*v**2)) % p == 0
defadd(C, P, Q): c, d, p = C u1, v1 = P u2, v2 = Q assert ison(C, P) and ison(C, Q) u3 = (u1 * v2 + v1 * u2) * inverse(c * (1 + d * u1 * u2 * v1 * v2), p) % p v3 = (v1 * v2 - u1 * u2) * inverse(c * (1 - d * u1 * u2 * v1 * v2), p) % p return (int(u3), int(v3))
defmul(C, P, m): assert ison(C, P) c, d, p = C B = bin(m)[2:] l = len(B) u, v = P PP = (-u, v) O = add(C, P, PP) Q = O if m == 0: return O elif m == 1: return P else: for _ inrange(l-1): P = add(C, P, P) m = m - 2**(l-1) Q, P = P, (u, v) return add(C, Q, mul(C, P, m))
c, d, p = Curve
G = (gx, gy) P = (423323064726997230640834352892499067628999846, 44150133418579337991209313731867512059107422186218072084511769232282794765835) Q = (1033433758780986378718784935633168786654735170, 2890573833121495534597689071280547153773878148499187840022524010636852499684) S = (875772166783241503962848015336037891993605823, 51964088188556618695192753554835667051669568193048726314346516461990381874317) T = (612403241107575741587390996773145537915088133, 64560350111660175566171189050923672010957086249856725096266944042789987443125) assert ison(Curve, P) and ison(Curve, Q) and ison(Curve, G) e = 0x10001 print(f"eG = {mul(Curve, G, e)}")
for i inrange(2,1000): if p_almost % i == 0: p_almost = p_almost // i
return p_almost
defc_sq_d(u1,u2,v1,v2,p): """ Helper function to computer c^2 d """ a1,b1 = a_and_b(u1,u2,v1,v2) return a1 * pow(b1,-1,p) % p
defc(u1,u2,v1,v2,p): """ Compute c^2, d from two points and known modulus """ ccd = c_sq_d(u1,u2,v1,v2,p) cc = (u1**2 + v1**2 - ccd*u1**2*v1**2) % p d = ccd * pow(cc, -1, p) % p return cc, d
P = (423323064726997230640834352892499067628999846, 44150133418579337991209313731867512059107422186218072084511769232282794765835) Q = (1033433758780986378718784935633168786654735170, 2890573833121495534597689071280547153773878148499187840022524010636852499684) S = (875772166783241503962848015336037891993605823, 51964088188556618695192753554835667051669568193048726314346516461990381874317) T = (612403241107575741587390996773145537915088133, 64560350111660175566171189050923672010957086249856725096266944042789987443125)
u1, v1 = P u2, v2 = Q u3, v3 = S u4, v4 = T
p = find_modulus(u1,u2,u3,u4,v1,v2,v3,v4) cc, d = c(u1,u2,v1,v2,p)
C = cc, d, p assert happy(C, P) assert happy(C, Q) assert happy(C, S) assert happy(C, T)
""" Found curve parameters p = 67943764351073247630101943221474884302015437788242536572067548198498727238923 c^2 = 12908728488299650872377430201970332178171657588185291326485782119189255844928 d = 8779982120820562807260290996171144226614358666469579196351820160975526615300 """
求G:
# sage #part1 get c2、d P = (423323064726997230640834352892499067628999846, 44150133418579337991209313731867512059107422186218072084511769232282794765835) Q = (1033433758780986378718784935633168786654735170, 2890573833121495534597689071280547153773878148499187840022524010636852499684) S = (875772166783241503962848015336037891993605823, 51964088188556618695192753554835667051669568193048726314346516461990381874317) T = (612403241107575741587390996773145537915088133, 64560350111660175566171189050923672010957086249856725096266944042789987443125) eG = (40198712137747628410430624618331426343875490261805137714686326678112749070113, 65008030741966083441937593781739493959677657609550411222052299176801418887407)
p = 67943764351073247630101943221474884302015437788242536572067548198498727238923 c2 = 12908728488299650872377430201970332178171657588185291326485782119189255844928 d = 8779982120820562807260290996171144226614358666469579196351820160975526615300 a = 1
PR.<c> = PolynomialRing(Zmod(p)) f = c^2 - c2 #print(f.roots())
c = f.roots()[0][0] #c = f.roots()[1][0]
#part2 map to ECC F = GF(p) dd = F(d*c^4) A = F(2) * F(a+dd) / F(a-dd) B = F(4) / F(a-dd) a = F(3-A^2) / F(3*B^2) b = F(2*A^3-9*A) / F(27*B^3)