根据对ECC的学习知道，我们常用的都是根据Weierstrass方程简化形式的曲线，实际上还存在其他形式的椭圆曲线。

蒙哥马利曲线

蒙哥马利曲线（Montgomery Curves）：

$By^2=x^3+Ax^2+x$

系数满足$B(A^2-4)\not =0$。

加法：

$P_1(x_1,y_1)+P_2(x_2.y_2)=P(x_3,y_3)$ $x_3=\frac{B(y_2-y_1)^2}{(x_2-x_1)^2}-A-x_1-x_2=\frac{B(x_2y_1-x_1y_2)^2}{x_1x_2(x_2-x_1)^2}$ $y_3=\frac{(2x_1+x_2+A)(y_2-y_1)}{x_2-x_1}-\frac{B(y_2-y_1)^3}{(x_2-x_1)^3}-y_1$

蒙哥马利曲线用来构造密码算法的实例是Curve25519。

映射到维尔斯特拉斯曲线：

$By^2=x^3+Ax^2+x \longmapsto v^2=u^3+au+b$ $(u,v)=\Big(\cfrac{x}{B}+\cfrac{A}{3B},\cfrac{y}{B}\Big)$ $a=\cfrac{3-A^2}{3B^2},b=\cfrac{2A^3-9A}{27B^3}$

爱德华曲线

爱德华曲线（Edwards Curves）：

一般方程：

$x^2+y^2=c^2(1+dx^2y^2)$

加法：

$(x_1,y_1)+(x_2,y_2)=\Big(\cfrac{x_1y_2+y_1x_2}{c(1+dx_1x_2y_1y_2)},\cfrac{y_1y_2-x_1x_2}{c(1-dx_1x_2y_1y_2)}\Big)$

倍乘：

$2(x_1,y_1)=\Big(\cfrac{2x_1y_1}{c(1+dx_1^2y_1^2)},\cfrac{y_1^2-x_1^2}{c(1-dx_1^2y_1^2)}\Big)$

取反：

$-(x_1,y_1)=(-x_1,y_1)$

映射到蒙哥马利曲线：

$x^2+y^2=1+dx^2y^2 \longmapsto Bv^2=u^3+Au^2+u$ $u=\cfrac{1+y}{1-y},v=\cfrac{2(1+y)}{x(1-y)}=\cfrac{2u}{x}$ $A=\cfrac{4}{1-d}-2,B=\cfrac{1}{1-d}$

扭曲爱德华曲线

扭曲爱德华曲线（Twisted Edwards Curves）：

一般方程：

$ax^2+y^2=c^2(1+dx^2y^2)$

加法：

$(x_1,y_1)+(x_2,y_2)=\Big(\cfrac{x_1y_2+y_1x_2}{1+dx_1x_2y_1y_2},\cfrac{y_1y_2-ax_1x_2}{1-dx_1x_2y_1y_2}\Big)$

倍乘：

$2(x_1,y_1)=\Big(\cfrac{2x_1y_1}{1+dx_1^2y_1^2},\cfrac{y_1^2-ax_1^2}{1-dx_1^2y_1^2}\Big)$

取反：

$-(x_1,y_1)=(-x_1,y_1)$

映射到蒙哥马利曲线：

$ax^2+y^2=1+dx^2y^2 \longmapsto Bv^2=u^3+Au^2+u$ $u=\cfrac{1+y}{1-y},v=\cfrac{1+y}{x(1-y)}=\cfrac{u}{x}$ $A=\cfrac{2(a+d)}{a-d},B=\cfrac{4}{a-d}$

Huff曲线

一般形式：

$x(ay^2-1)=y(bx^2-1)$

加法：

$(x_1,y_1)+(x_2,y_2)=\Big(\cfrac{(x_1+x_2)(1+ay_1y_2)}{(1+bx_1x_2)(1-ay_1y_2)},\cfrac{(y_1+y_2)(1+bx_1x_2)}{(1-bx_1x_2)(1+ay_1y_2)}\Big)$

倍乘：

$2(x_1,y_1)=\Big(\cfrac{2x_1(1+ay_1^2)}{(1+bx_1^2)(1-ay_1^2)},\cfrac{2y_1(1+bx_1^2)}{(1-bx_1^2)(1+ay_1^2)}\Big)$

取反：

$-(x_1,y_1)=(x_1,y_1)$

映射到蒙哥马利曲线：

$x(ay^2-1)=y(bx^2-1) \longmapsto v^2=u^3+Au^2+Bu$ $u=\cfrac{bx-ay}{y-x},v=\cfrac{b-a}{y-x}$ $A=a+b,B=ab$

题目

EdRSA

#sagemath
from Crypto.Util.number import *
from secrets import flag

def add(P, Q):
    (x1, y1) = P
    (x2, y2) = Q

    x3 = (x1*y2 + y1*x2) * inverse(1 + d*x1*x2*y1*y2, p) % p
    y3 = (y1*y2 - a*x1*x2) * inverse(1 - d*x1*x2*y1*y2, p) % p
    return (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 >> 1
    return Q

p = 64141017538026690847507665744072764126523219720088055136531450296140542176327
a = 362
d = 7
gx=bytes_to_long(flag)
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)%p

G=(gx,gy)
e=0x10001
print("eG = {}".format(mul(e, G)))

#eG = (602246821311345089174443402780402388933602410138142480089649941718527311147, 17625197557740535449294773567986004828160284887369041337984750097736030549853)

根据assert (a*gx^2+gy^2)%p==(1+d*gx^2*gy^2)%p可以写出公式：

$ax^2+y^2=1+dx^2y^2\pmod p$

这是标准的扭曲爱德华曲线。题目加密为：

$G'=eG$

我们知道了$e,G’$，现在要求解$G$，如果我们能知道$e$在曲线阶下的逆元，那么就可以得到$G$，但是这里的扭曲爱德华曲线我们不能直接表示，所以思考可以通过还原将椭圆曲线映射成常见的椭圆曲线形式，就可以求出阶，并计算逆元得到flag了。

首先先转换为蒙哥马利曲线方程，然后转化为Weierstrass椭圆曲线方程。

利用标准椭圆曲线方程形式，就可以用sage求解椭圆曲线阶，解得原点$G$，再逆变换成Edcurve，横坐标即为flag。

# sagemath
from Crypto.Util.number import *

p = 64141017538026690847507665744072764126523219720088055136531450296140542176327
a = 362
d = 7
c = 1
e = 0x10001

eG = (
    602246821311345089174443402780402388933602410138142480089649941718527311147,
    17625197557740535449294773567986004828160284887369041337984750097736030549853,
)
F = GF(p)

A = (2 * (a + d)) / (a - d)
B = 4 / (a - d)
a = (3 - A ^ 2) / (3 * B ^ 2)
b = (2 * A ^ 3 - 9 * A) / (27 * B ^ 3)


def TEd_to_ECC(x, y):
    x1 = F(1 + y) / F(1 - y)
    y1 = F(x1) / F(x)
    u = F(x1) / F(B) + F(A) / F(3 * B)
    v = F(y1) / F(B)
    return (u, v)


def ECC_to_TEd(x, y):
    x1 = F(B) * F(x) - F(A) / F(3)
    y1 = F(B) * F(y)
    u = F(x1) / F(y1)
    v = (F(x1) - F(1)) / (F(x1) + F(1))
    return (u, v)


E = EllipticCurve(F, [a, b])
o = E.order()
eG = E(TEd_to_ECC(eG[0], eG[1]))
t = inverse(e, o)
G = ECC_to_TEd((t * eG)[0], (t * eG)[1])

print(long_to_bytes(int(G[0])))

ECC中的常见曲线

蒙哥马利曲线

爱德华曲线

扭曲爱德华曲线

Huff曲线

题目

EdRSA