曲线

数据库:

https://www.hyperelliptic.org/EFD/

https://safecurves.cr.yp.to/equation.html

判据

单位元 $O$:$O+Q=Q$ => $(0,0)+(x_1,y_1)=(x_1,y_1)$

逆元 $-Q$:$(-Q)+Q=0$ => $(x_1,y_1)+(x_2,y_2)=(0,0)$

映射前后曲线的阶不变。

常见曲线

Edwards Curves

一般方程

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

变换:$\Big(\cfrac{X}{c}\Big)^2+\Big(\cfrac{Y}{c}\Big)^2=1+Dc^4\Big(\cfrac{X}{c}\Big)^2\Big(\cfrac{Y}{c}\Big)^2 \Rightarrow X^2+Y^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}$

参考:

https://safecurves.cr.yp.to/equation.html

Crypto CTF 2021 - RoHaLd

Twisted Edwards Curves

一般方程

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

变换:$a\Big(\cfrac{X}{c}\Big)^2+\Big(\cfrac{Y}{c}\Big)^2=1+Dc^4\Big(\cfrac{X}{c}\Big)^2\Big(\cfrac{Y}{c}\Big)^2 \Rightarrow AX^2+Y^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}$

参考:

Twisted Edwards Curves

NCTF 2022 - superecc

Binary Edwards Curves

一般方程

$d_1(x+y)+d_2(x^2+y^2)=(x+x^2)(y+y^2)$

加法

$(x_1,y_1)+(x_2,y_2)=\Big(\cfrac{d_1(x_1+x_2)+d_2(x_1+y_1)(x_2+y_2)+(x_1+x_1^2)[x_2(y_1+y_2+1)+y_1y_2]}{d_1+(x_1+x_1^2)(x_2+y_2)},\cfrac{d_1(y_1+y_2)+d_2(x_1+y_1)(x_2+y_2)+(y_1+y_1^2)[y_2(x_1+x_2+1)+x_1x_2]}{d_1+(y_1+y_1^2)(x_2+y_2)}\Big)$

倍乘

$2(x_1,y_1)=\Big(\cfrac{2d_1x_1+d_2(x_1+y_1)^2+(x_1+x_1^2)[x_1(2y_1+1)+y_1^2]}{d_1+(x_1+x_1^2)(x_1+y_1)},\cfrac{2d_1y_1+d_2(x_1+y_1)^2+(y_1+y_1^2)[y_1(2x_1+1)+x_1^2]}{d_1+(y_1+y_1^2)(x_1+y_1)}\Big)$

取反

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

映射

$v^2+uv=u^3+(d_1^2+d_2)u^2+d_1^4(d_1^4+d_1^2+d_2^2)$

其中

$u=\cfrac{d_1(d_1^2+d_1+d_2)(x+y)}{xy+d_1(x+y)}$

$v=d_1(d_1^2+d_1+d_2)\Big(\cfrac{x}{xy+d_1(x+y)}+d_1+1\Big)$

参考

Binary Edwards Curves

Hessian Curves

一般方程

$x^3+y^3+1=3dxy$

加法

$(x_1,y_1)+(x_2,y_2)=\Big(\cfrac{y_1^2x_2-y_2^2x_1}{x_2y_2-x_1y_1},\cfrac{x_1^2y_2-x_2^2y_1}{x_2y_2-x_1y_1}\Big)$

倍乘

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

取反

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

Twisted Hessian Curves

一般方程

$ax^3+y^3+1=dxy$

加法

$(x_1,y_1)+(x_2,y_2)=\Big(\cfrac{x_1-y_1^2x_2y_2}{ax_1y_1x_2^2-y_2},\cfrac{y_1y_2^2-ax_1^2x_2}{ax_1y_1x_2^2-y_2}\Big)$

倍乘

$2(x_1,y_1)=\Big(\cfrac{x_1-y_1^3x_1}{ay_1x_1^3-y_1},\cfrac{y_1^3-ax_1^3}{ay_1x_1^3-y_1}\Big)$

取反

$-(x_1,y_1)=\Big(\cfrac{x_1}{y_1},\cfrac{1}{y_1}\Big)$

Jacobi Quartics

一般方程

$y^2=ex^4-2dx^2+1$

加法

$(x_1,y_1)+(x_2,y_2)=\Big(\cfrac{x_1y_2+y_1x_2}{1-e(x_1x_2)^2},\cfrac{(1+e(x_1x_2)^2)(y_1y_2-2dx_1x_2)+2ex_1x_2(x_1^2+x_2^2)}{(1-e(x_1x_2)^2)^2}\Big)$

倍乘

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

取反

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

映射

$y^2=ex^4-2dx^2+1 \longmapsto v^2=u^3+Au^2+B$

其中:

$u=2\cfrac{3(y+1)-dx^2}{3x^2},v=4\cfrac{(y+1)-dx^2}{x^3}$

$A=-4\cfrac{3e+d^2}{3},B=-\cfrac{16}{27}d(d^2-9e)$

Huff Curve

一般方程

$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$

参考

2023 DASCTF CBCTF - CB curve

$x^2+ey^2 \equiv 1$

一般方程

$x^2+ey^2 \equiv 1 \pmod p$

加法

$(x_1,y_1)+(x_2,y_2)=(x_1x_2-ey_1y_2,x_1y_2+x_2y_1)$

映射

$p$ 为素数,如 $e$ 是模 $N$ 的二次剩余,设 $d$ 满足 $d^2\equiv e\pmod p$

曲线 $E$ 上的任意一点 $G(x_0,y_0)$,都满足方程:$x_0^2+e\cdot y_0^2\equiv 1\pmod p$

代数变形一下,得到:

$(x_0+i\cdot d\cdot y_0)\cdot (x_0-i\cdot d\cdot y_0)\equiv 1\pmod p,i^2+1=0$

可以看到曲线 $E$ 上的点与模 $p$ 的高斯整数 $x_0+i\cdot d\cdot y_0$ 是相互对应的。

不难验证如上的对应关系其实是一个同态。那么可以将曲线 $E$ 上的离散对数问题转换到有限域 $\mathbb{F}_{p^2}$ 上去。(注意到 $p$ 为一高斯素数)

对于 $s = x_0+i\cdot d\cdot y_0$,注意到有:

$s^{N+1}=x_0^{N+1}+\sum_{k=1}^{N-1}x_{0}^{k}{N\choose k}(i\cdot d\cdot y_0)^{N-k} + (i\cdot d\cdot y_0)^{N+1}\equiv x_0^2+e\cdot y_0^2\equiv 1\pmod p$

所以 $s$ 的阶为 $p+1$,尝试将 $p+1$ 进行分解,如果其十分光滑,可尝试用Pohlig-Hellman算法来求解DLP。

代码

模板类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
# Sage
# y^2 = ax^2 - bx (mod p)

from Crypto.Util.number import inverse, bytes_to_long, long_to_bytes
from sage.groups.generic import bsgs
from hashlib import md5

class SpecialCurve:
def __init__(self, p, a, b):
self.p = p
self.a = a
self.b = b

def __str__(self):
return f'SpecialCurve({self.p},{self.a},{self.b})'

def __call__(self, x, y):
return SpecialCurvePoint(self.p, self.a, self.b, x, y)

def __contains__(self, other):
x, y = other.x, other.y
return (self.a * x ** 2 - self.b * x - y ** 2) % self.p == 0

class SpecialCurvePoint:
def __init__(self, p, a, b, x, y):
self.p = p
self.a = a
self.b = b
self.x = x % p
self.y = y % p

def __str__(self):
return "(%d, %d)" % (self.x, self.y)

def __repr__(self):
return str(self)

def __add__(self, P1):
x1, y1 = self.x, self.y
x2, y2 = P1.x, P1.y
if x1 == 0:
return P1
elif x2 == 0:
return self
elif x1 == x2 and (y1+y2) % self.p == 0:
return SpecialCurvePoint(self.p, self.a, self.b, 0, 0)
if self == P1:
t = (2*self.a*x1-self.b)*inverse(2*y1, self.p) % self.p
else:
t = (y2-y1)*inverse(x2-x1, self.p) % self.p
x3 = self.b*inverse(self.a-t**2, self.p) % self.p
y3 = x3*t % self.p
return SpecialCurvePoint(self.p, self.a, self.b, x3, y3)

def __mul__(self, k):
assert k >= 0
Q = SpecialCurvePoint(self.p, self.a, self.b, 0, 0)
P = SpecialCurvePoint(self.p, self.a, self.b, self.x, self.y)
cnt = 0
now = 1
while k > 0:
if k % 2:
k -= 1
Q = P + Q
cnt += now
else:
k //= 2
P = P + P
now *= 2
return Q

def order(self):
return self.p + 1

def is_zero(self):
return self.x == 0 and self.other == 0

def __eq__(self, other):
return self.a == other.a and self.b == other.b and self.p == other.p and self.x == other.x and self.y == other.y

def __hash__(self):
return int(md5(("%d-%d-%d-%d-%d" % (self.p, self.a, self.b, self.x, self.y)).encode()).hexdigest(), 16)

def invert(P):
return SpecialCurvePoint(P.p, P.a, P.b, P.x, -P.y % P.p)

def add(P1, P2):
return P1 + P2

转三元齐次方程

1
2
3
4
5
6
7
8
9
10
11
12
13
p = 
a =
P = (, )
Q = (, )

R.<x,y,z> = Zmod(p)[]
cubic = a*x^3 + y^3 + z^3 - d*x*y*z
E = EllipticCurve_from_cubic(cubic,morphism=True)
order = EllipticCurve_from_cubic(cubic,morphism=False)
P = E(P)
Q = E(Q)
m = Q.log(P)
print(long_to_bytes(m))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
p = 
d =
c =
F = GF(p)

x, y, z = QQ["x,y,z"].gens()
eq = 2 * x ^ 3 + y ^ 3 + c * z ^ 3 - d * x * y * z
phi = EllipticCurve_from_cubic(eq)
E = phi.codomain().change_ring(GF(p))

P = (, )
Q = (, )
fx, fy, fz = map(lambda f: f.change_ring(F), phi.defining_polynomials())
phiP = lambda x, y, z=1: E(fx(x, y, z) / fz(x, y, z), fy(x, y, z) / fz(x, y, z))
EP = phiP(*P)
EQ = phiP(*Q)
n = E.order()
factors = list(factor(n))
m = 1
moduli = []
remainders = []
print(f"[+] Running Pohlig Hellman")
print(factors)
count = 0

for i, j in factors:
count += 1
if i < 10**12:
continue
mod = i**j
print(mod)
g2 = EP*(mod)
q2 = EQ*(mod)
r = discrete_log(q2, g2, ord=E.order(), operation='+')
print(long_to_bytes(r))

常用算法

计算曲线方程:

$(x_1,y_1)=(x_2,y_2)$ 情况下的斜率 $k=f’(x)$,逆推 $f(x)+C$,根据已知点确定 $C$ 值。

大步小步算法(BSGS算法)

计算离散对数,套用sagemath中自带的bsgs。

sage自带的bsgs算法有bug,文件 /opt/sagemath-9.3/local/lib/python3.7/site-packages/sage/groups/generic.py 中468行没写全,这导致bsgs自定义群的计算报错,解决方案就是把这一行参数补全即可。

c = op(inverse(b), multiple(a, lb, operation=operation, identity=identity, inverse=inverse, op=op))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
curve =
G =
Q =
p =
E = curve(0, 0)
order = p + 1
factors = [..]
ans = []

for factor in factors:
this = bsgs(G * (order // factor), Q * (order // factor), (0, factor), operation='other', op=add, inverse=invert, identity=E)
ans.append(this)
print(this)

k = crt(ans, factors)

Pohlig-Hellman算法

适用情况:曲线的阶光滑。

有些时候,尽管BSGS能够将复杂度降至 $\sqrt{p}$,但是这个数依然很大,所以不能用。这时可以考虑Pohlig-hellman方法能不能起作用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def bsgs(g, y, p):
m = int(ceil(sqrt(p - 1)))
S = {}
point = (u,0)
for i in range(m):
point = point + g
pointg = point[0] << 800 | point[1]
S[pointg] = i

gs = m * g
for i in range(m):
pointy = y[0] << 800 | y[1]
if pointy in S:
return S[pointy] - i * m + 1
y = y + gs
return None

def Pohlig_Hellman(G,P):
ea = []
na = []
for i in range(len(fac)):
c = fac[i]
n = (p - 1) // c
gi = n * G
yi = n * P
ei = bsgs(gi,yi,c)
ea.append(ei%c)
na.append(c)
ee = crt(ea,na)
return ee

e = Pohlig_Hellman(G,P)

其他映射

Montgomery型 -> Weierstrass型

$By^2=x^3+Ax^2+x \longmapsto v^2=u^3+au+b$

其中:

$(x,y) \longmapsto (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}$

参考:Montgomery curve

$x^2 - Dy^2 = k^2$ 型

将曲线上的DLP问题转化为模p的DLP问题

性质:

满足 $(p+1)G=(1,0)$,阶为 $p+1$。

曲线其实是一个 $\text{GF}(p)$ 上的pell方程,而pell方程的解可以通过以下方法得到:

$x_i+y_i\sqrt{n}=(x_1+y_1\sqrt{n})^i$

或递推关系式:

$\begin{cases} x_{i+1}=x_1x_i+ny_1y_i \newline y_{i+1}=x_1y_i+y_1x_i \end{cases}$

对矩阵 $\begin{bmatrix} x_1 & Dy_1 \newline y_1 & x_1\end{bmatrix}$ 进行对角化,可以得到其特征值为 $Dy+x,-Dy+x$,之后求得

$x_n = \cfrac{(y_1\sqrt D + x_1)^n + (-y_1\sqrt D + x_1)^n}{2 u^{n-1}}, y_n = \cfrac{(y_1\sqrt D + x_1)^n - (-y_1\sqrt D + x_1)^n}{2 \sqrt Du^{n-1}}$

容易得到

$\cfrac{x_n - \sqrt D y_n}{ u} = \Big(\cfrac{x_1 - \sqrt D y_1}{u} \Big) ^ n, \cfrac{x_n + \sqrt D y_n}{ u} = \Big(\cfrac{x_1 + \sqrt D y_1}{u}\Big) ^ n$

即找到了两个将曲线上点映射到 GF 的映射

$f: f(x, y) = \cfrac{x - \sqrt D y}{ u}, g: g(x, y) = \cfrac{x + \sqrt D y}{ u}$

此时,利用hackergame2020的OT中的技巧,且 $D$ 已知,对于每一个点,可以得到 $x - \sqrt D y$,得到两组数据后相除,即可得到

$\cfrac{x_{1n} + \sqrt D y_{1n}}{ x_{2n} + \sqrt D y_{2n}} = \Big(\cfrac{x_1 + \sqrt D y_1}{x_2 + \sqrt D y_2}\Big) ^ n$

对这两个数通过Pohlig Hellman算法求DLP,即可得到 $e$。

参考:

DUCTF 2021 - yadlp

D^3CTF 2021 - EasyCurve

SUSCTF 2022 - SpecialCurve3

$x^2+e\cdot y^2=N$ 型

性质:

形如$4\cdot k + 1$的素数$p$可以被分解为如下的二平方和:

其证明方法有很多,这里给出一种较为有趣的证明方法。

$\textbf{Proof}$

首先注意到$-1$为模$p$的二次剩余,这里我们设$e$满足:$e^2\equiv-1\bmod p$。

然后我们构造格$\mathcal{L}$,其格基矩阵如下:

$M = \begin{bmatrix}
1 & e\\
0 & p\\
\end{bmatrix}
$

对于其中的向量$\vec{t}=\vec{v}\cdot M=(x_0,y_0)\cdot M=(x_1,y_1)$

有$x_1=x_0,y_1=e\cdot x_0+p\cdot y_0$,考虑其范数,有

两边模$p$,得到$\Vert \vec{t} \Vert \equiv 0 \bmod p$,也就是说对于格$\mathcal{L}$中的任意一个向量$\vec{t}$,均有$\Vert \vec{t}\Vert=k\cdot p$。

考虑格$\mathcal{L}$中的最短非零向量,尝试估计其长度。

因为有$\det(M)=p$,所以格$\mathcal{L}$中的最短非零向量长度满足
$0<\Vert \vec{t_0} \Vert^2 < 2\cdot p$。

综上有$\Vert \vec{t_0} \Vert^2 = x_0^2 + y_0^2 = p$。证明完毕。

注:上面的证明过程其实提供了一种求解方程$x^2+y^2=p$的有效算法:在格$\mathcal{L}$中利用格基规约算法去寻找短向量。

有了上面的theoremproof,对于丢番图方程$x^2+e\cdot y^2 = N$,可以尝试几乎完全相同的方法去求解。

其他:

在sympy中,有个 cornacchia() 函数专门求解此类方程,即 cornacchia(1,e,n)