曲线

2021-01-20 crypto 曲线 ∞ 评论

数据库：

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。

代码

模板类

# 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

转三元齐次方程

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

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

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方法能不能起作用。

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$可以被分解为如下的二平方和：

$x^2+y^2=p\quad x,y\in\mathbb{N}$

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

$\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$，考虑其范数，有

$\Vert \vec{t}\Vert=x_0^2+(e\cdot x_0+p\cdot y_0)^2=(e^2+1)\cdot x_0^2 + p^2\cdot y_0^2 + 2\cdot e\cdot p\cdot x_0\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}$中利用格基规约算法去寻找短向量。

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

其他：

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

Lazzaro

CTF弱鸡自进阶

曲线

判据

常见曲线

Edwards Curves

Twisted Edwards Curves

Binary Edwards Curves

Hessian Curves

Twisted Hessian Curves

Jacobi Quartics

Huff Curve

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

代码

模板类

转三元齐次方程

常用算法

大步小步算法（BSGS算法）

Pohlig-Hellman算法

其他映射

Montgomery型 -> Weierstrass型

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

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

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