曲线

数据库:https://www.hyperelliptic.org/EFD/

常见曲线

Edwards Curves

一般方程:$x^2+y^2=c^2(1+dx^2y^2)$

加法:$(x_1,y_1)+(x_2,y_2)=(\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)})$

倍乘:$2(x_1,y_1)=(\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)})$

取反:$-(x_1,y_1)=(-x_1,y_1)$

Twisted Edwards Curves

一般方程

$ax^2+y^2=1+dx^2y^2$

加法

$(x_1,y_1)+(x_2,y_2)=(\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})$

倍乘

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

取反

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

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)=(\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)})$

倍乘

$2(x_1,y_1)=(\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)})$

取反

$-(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=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)(x/(xy+d_1(x+y))+d_1+1)$

参考

Binary Edwards Curves

模板类

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

常用算法

大步小步算法(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)

映射

  • $x^2 \equiv Dy^2+u^2$ 形

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

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

    img

    对矩阵 $\begin{bmatrix} x_1 & Dy_1 \ 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$。

    参考:

    D^3CTF 2021 - EasyCurve

    SUSCTF 2022 - SpecialCurve3