国城杯2024——Curve

相关知识链接：https://tangcuxiaojikuai.xyz/post/187210a7.html

#sagemath
from Crypto.Util.number import *def add(P, Q):(x1, y1) = P(x2, y2) = Qx3 = (x1*y2 + y1*x2) * inverse(1 + d*x1*x2*y1*y2, p) % py3 = (y1*y2 - a*x1*x2) * inverse(1 - d*x1*x2*y1*y2, p) % preturn (x3, y3)def mul(x, P):Q = (0, 1)while x > 0:if x % 2 == 1:Q = add(Q, P)P = add(P, P)x = x >> 1return Qp = 64141017538026690847507665744072764126523219720088055136531450296140542176327
a = 362
d = 7
e=0x10001gx=bytes_to_long(b'D0g3xGC{*****************}')PR.<y>=PolynomialRing(Zmod(p))
f=(d*gx^2-1)*y^2+(1-a*gx^2)
gy=int(f.roots()[0][0])assert (a*gx^2+gy^2)%p==(1+d*gx^2*gy^2)%pG=(gx,gy)eG = mul(e, G)
print(eG)#eG = (34120664973166619886120801966861368419497948422807175421202190709822232354059, 11301243831592615312624457443883283529467532390028216735072818875052648928463)

标准型的扭曲爱德华曲线：(Twisted Edwards Curves)

---

这一题需要安装SageMath，在kali linux中安装：

（https://www.sagemath.org/download.html）

tar xvf sage-9.4-Debian_GNU_Linux_11-x86_64.tar.bz2

在解压后的目录下输入./sage启动

---

但由于个人熟练度不够，不会用sagemath直接运行python文件，改用sagemath在线运行python网站来进行操作：

（https://cocalc.com/features/sage）

from Crypto.Util.number import *
p = 64141017538026690847507665744072764126523219720088055136531450296140542176327
a = 362
d = 7
e=0x10001
c=1eG = (34120664973166619886120801966861368419497948422807175421202190709822232354059, 11301243831592615312624457443883283529467532390028216735072818875052648928463)
gx=34120664973166619886120801966861368419497948422807175421202190709822232354059
PR.<y>=PolynomialRing(Zmod(p))
f=(d*gx^2-1)*y^2+(1-a*gx^2)
gy=int(f.roots()[0][0])#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)def edwards_to_ECC(x,y):x1 = F(x) / F(c)y1 = F(y) / F(c)#now curve is a*x^2+y^2 = 1+dd*x^2*y^2x2 = F(1+y1) / F(1-y1)y2 = F(x2) / F(x1)#now curve is By^2 = x^3 + Ax^2 + xx3 = (F(3*x2) + F(A)) / F(3*B)y3 = F(y2) / F(B)#now curve is y^2 = x^3 + ax + breturn (x3,y3)def ECC_to_edwards(x,y):x2 = (F(x) * F(3*B) - F(A)) / F(3)y2 = F(y) * F(B)#now curve is By^2 = x^3 + Ax^2 + xx1 = F(x2) / F(y2)y1 = F(1) - (F(2) / F(x2+1))#now curve is a*x^2+y^2 = 1+dd*x^2*y^2x_ = F(x1) * F(c)y_ = F(y1) * F(c)#now curve is a*x^2+y^2 = c^2(1+d*x^2*y^2)return (x_,y_)E = EllipticCurve(GF(p), [a, b])
order = E.order()
eG = E(edwards_to_ECC(eG[0],eG[1]))
t = inverse(e,order)
G = t*eG
G = ECC_to_edwards(G[0],G[1])
print(long_to_bytes(int(G[0])))

得到flag：

D0g3xGC{SOlvE_The_Edcurv3}