曲线

2021-01-20 crypto 曲线 ∞ 评论

数据库：

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

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

常见曲线

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

映射：

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

映射：

$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)=(\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=\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)(\cfrac{x}{xy+d_1(x+y)}+d_1+1)$

参考：

Binary Edwards Curves

模板类

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

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

Lazzaro

CTF弱鸡自进阶

曲线

常见曲线

Edwards Curves

Twisted Edwards Curves

Binary Edwards Curves

模板类

常用算法

大步小步算法（BSGS算法）

Pohlig-Hellman算法

其他映射