椭圆曲线签名

今天终于了解了一番神奇的非对称加密算法:椭圆曲线乘法为什么无法反推了,下面介绍一波.

1.椭圆曲线是一个二维的散点图

这里用NIST设立的一条椭圆曲线函数来介绍,因为这条曲线就是比特币使用的.这条曲线就是secp256k1标准定义的.公式如下:

    y^2 = {{x^3+7}\over{F_p}} 

    y^2 \mod p = (x^3+7) \mod p
    

mod p 表明曲线实在素数p的限定域中的，也写作F_p，p的取值为:p = 2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1,是一个很大的整数。容易看出椭圆曲线是一个二维的散点图。

函数散点图很难画,本人手绘是画不出来滴,那么我弄了一份简化了n倍的图用来做说明.

椭圆曲线

2.椭圆曲线加法

小学老师告诉我们：研究乘法，必须先研究加法

在椭圆曲线中,任意两个点的和必然存在于曲线上.数学定义如下:

    p_3 = p_1 + p_2

这里的加法解释为:p1和p2的连线延长会和曲线唯一相交,相交的点记为p_3' = (x,y),然后取相交点对于x轴的映射,得到p_3 = (x,-y)。

如果p1和p2是相同的,那么两点的连线就是该点的切线.

如果p1是无穷远点(没有坐标点),那么p_1+p_2 = p_2,p2类比。

这就是椭圆曲线加法的定义。

3.椭圆曲线乘法

那么在乘法中的应用就简单了，无非就是两两相加。这里会介绍比特币的那个乘法:
K = k * G。k是私钥,G是一个随机常数，K则是计算出来的公钥。
那么上面的乘法等效为：

    K = k * G = G+G+....+G

每两个来看，G+G就是G的切线和曲线的交点对x轴映射取点。那么4G = 2G+2G = (G+G) + (G+G)。得G的乘法示意图：

椭圆曲线乘法

从一个G开始,2G就是G+G。同理可得k*G的结果,当然了,如果k是奇数,那么就是(k-1)*G+G。运算就是做一次两点连线延长相交于曲线的点对x轴映射即可。

4.椭圆曲线签名很难反推

接下来思考一下，对于K=k*G，为什么已知输出K和G,为什么推导不出k呢?

其实这里存在一个误区,这里的乘法是椭圆曲线乘法,并不是小学的乘法。从上面的计算可以得知，
$k*G$是在曲线上反复做切线,并对x轴取映射点。也就是说，你是无法通过输出和常数点来知道你是通过多少次的运算得来的，除非你一次计算每一个数值。而这个数值很大很大。
55066263022277343669578718895168534326250603453777594175500187360389116729240
这个数值是一个真实的随机生成的私钥k。如果你要反推，那么你一个个遍历这个随机数，计算量就是到k的阶乘的椭圆曲线乘法运算量了,所以在得出了大家常知的结论：椭圆曲线签名很难反推

---

2018-1-30 更新

前面关于椭圆曲线签名有一点补充.

椭圆曲线签名很难反推,它主要是因为你需要推导的是它的计算路径,而不仅仅是最终结果.

在椭圆曲线乘法中,你需要反推的是从常数点G开始画切线到曲线交点,再取x轴在映射点.如此反复,得到上图中的折现路径.

如果知道私钥k，那么我折线的路径是确定的。如果不知道，那么其实就是要试探每一条可能的折线路径。而这需要的计算量是极大的，就目前的计算机而言，可以认为不可被反推。