Crypto进阶篇-ECC

ECC，即椭圆曲线密码学，其安全性主要依赖于椭圆曲离散对数问题的困难性，与其他算法相比之下的优点主要是它能够在使用较短密钥的情况下保持相同的密码强度。目前其主要采用的有限域包括以素数为模的整数于$GF(p)$ 和特征为2的伽罗华域$GF(2^m)$

由于这里我对特征为2的伽罗华域$GF(2^m)$下的椭圆曲线还不是很懂，下面的讨论默认都是在$GF(p)$有限域中进行的。

一、曲线

定义式：$y^2+axy+by=x^3+cx2+dx+e$

最常见的曲线是 Weierstrass 曲线：
$$
y^2 = x^3+ax+b
$$
其中，$\Delta = -16(4a^3+27b)\neq 0$，来保证曲线是光滑的，也就是说曲线上的每个点位置都只能有一种切线方式。

二、零点

定义把一个无穷远点作为零点$O$

三、阶

曲线的阶

概念：表示曲线上所有符合方程的点的总数，并包括一个无穷远点 $O$，我们把阶用 $N$ 表示
Hasse定理： 曲线的阶 $N$ 大约就在 $p$ 附近，误差范围不超过 $2\sqrt{p}$：
$$
|N-(p+1)| \leq 2\sqrt{p}
$$
准确来说，$N=p+1-t$，其中 $t$ 称为曲线的迹。

点的阶

对于曲线上一个特点的点 $P$，使 $kP=O$ 成立的最小的正整数 $k$，我们称它为点 $P$ 的阶。

拉格朗日定理

任何一个点的阶，都必须能整除曲线的阶。
也就是说，$N \equiv 0 \mod k$

t=0 的特殊情况

1.曲线：$y^2=x^3+x$

条件：$p\equiv 3 \mod 4$
曲线的阶 = p+1

2.曲线：$y^2=x^3+1$

条件：$p\equiv 2 \mod 3$
曲线的阶 = p+1

四、加法

设 $P=(x_1,y_1),Q=(x_2,y_2)\in E_p(a,b)$，且$P,Q$既不为 0 也不对称，$P+Q=(x_3,y_3)$
斜率：
$$
P\neq Q时，k = \frac{y_2-y_1}{x_2-x_1}
$$
$$
P= Q时，k = \frac{3x^2_1+a}{2y_1}
$$
求点：
$$
x_3 = k^2-x_1-x_2
$$
$$
y_3 = k(x_1-x_3)-y_1
$$

五、乘法

这里只考虑点和标量之间的乘法，转换成加法来做，如
$Q = nP = P+P+…+P$

六、加密

设有$K=kG$，其中 $K,G$ 都是椭圆曲线 $E_p(a,b)$ 上的点， $n$ 是 $G$ 的阶，即 $nG=0$，$k$ 是小于 $n$ 的整数。
给定 $K,G$，求 $k$，由于 $p$ 通常上会是一个比较大的值，所以 $n$ 也会是较大的值，逐个求解几乎是不可能的。
因此，我们称 $G$ 为基点，$k$ 为私钥，$K$ 为公钥。

七、代码实现

sagemath 中常用函数

1. E = EllipticCurve(GF(p),[a,b]) :定义曲线
2. E.random_point():在椭圆曲线E上随机取一点
3. E.set_order():设置椭圆曲线的阶
4. E.point((x,y)):创建一个椭圆曲线上的点对象，该点对象的坐标为(x,y)
5. discrete_log(K,G,operation='+'):求解，自动选取BSGS算法或Pohlig-Hellman算法
6. E.order()：计算椭圆曲线的阶。
7. discrete_log_rhp(K,G,operation='+'):用Pollard rho算法求解私钥
8. discrete_log_lambda(K,G,bound,operation='+'):用Pollard Lambda算法求解私钥，能够确定所求值在某一小范围时效率较高

参考：
ECC | Lazzaro
ECC | DexterJie’Blog
ECCNotes1 - huangx607087’s Blog
ECC - CTF Wiki