解密椭圆曲线签名

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

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

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

y2=x3+7Fp$y^2=\frac{x^3+7}{F_p}$ 或
y2modp=(x3+7)modp$y^2\mathrm{mod}p=(x^3+7)\mathrm{mod}p$

     mod p$p$表明曲线实在素数p$p$的限定域中的，也写作Fp$F_p$，p$p$的取值为:p=2256−232−29−28−27−26−24−1$p=2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$,是一个很大的整数。
     容易看出椭圆曲线是一个二维的散点图。函数散点图很难画,本人手绘是画不出来滴,那么我会画一份简化了n倍的图用来做说明.

2.椭圆曲线加法

     小学老师告诉我们：研究乘法，必须先研究加法
     在椭圆曲线中,任意两个点的和必然存在于曲线上.数学定义如下:

p3=p1+p2$p_3=p_1+p_2$ 这里的加法解释为:p1$p_1$和p2$p_2$的连线延长会和曲线唯一相交,相交的点记为p′3=(x,y)$p_3^{\prime }=(x,y)$,然后取相交点对于x轴的映射，得到p3=(x,−y)$p_3=(x,-y)$。
     如果p1$p_1$和p2$p_2$是相同的，那么两点的连线就是该点的切线；如果p1是无穷远点(理解为加法中的零)。那么p1+p2=p2$p_1+p_2=p_2$，p2$p_2$类比。

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

3.椭圆曲线乘法

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

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

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

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

     接下来思考一下，对于K=k∗G$K=k\ast G$，为什么已知输出K$K$和G$G$,为什么推导不出k$k$呢?
     其实这里存在一个误区,这里的乘法是椭圆曲线乘法,并不是小学的乘法。从上面的计算可以得知，
     k∗G$k\ast G$是在曲线上反复做切线,并对x轴取映射点。也就是说，你是无法通过输出和常数点来知道你是通过多少次的运算得来的，除非你一次计算每一个数值。而这个数值很大很大。

55066263022277343669578718895168534326250603453777594175500187360389116729240$55066263022277343669578718895168534326250603453777594175500187360389116729240$
     这个数值是一个真实的随机生成的私钥k$k$。如果你要反推，那么你的一个个遍历这个随机数，计算量就是到k$k$的阶乘的椭圆曲线乘法运算量了,所以在得出了大家常知的结论：椭圆曲线签名很难反推