|
今天终于了解了一番神奇的非对称加密算法:椭圆曲线乘法为什么无法反推了,下面介绍一波.
1.椭圆曲线是一个二维的散点图
这里用NIST设立的一条椭圆曲线函数来介绍,因为这条曲线就是比特币使用的.这条曲线就是secp256k1标准定义的.公式如下:
y2=x3+7Fpy2=x3+7Fp
y2modp=(x3+7)modp
mod p 表明曲线实在素数p的限定域中的，也写作Fp，p的取值为:p=2256−232−29−28−27−26−24−1,是一个很大的整数。容易看出椭圆曲线是一个二维的散点图。
函数散点图很难画,本人手绘是画不出来滴,那么我弄了一份简化了n倍的图用来做说明.
2.椭圆曲线加法
小学老师告诉我们：研究乘法，必须先研究加法
在椭圆曲线中,任意两个点的和必然存在于曲线上.数学定义如下:
p3=p1+p2
这里的加法解释为:p1和p2的连线延长会和曲线唯一相交,相交的点记为
p3=(x,y)
,然后取相交点对于x轴的映射,得到
p3=(x,−y)
。
如果p1和p2是相同的,那么两点的连线就是该点的切线.
如果p1是无穷远点(理解为加法中的零),那么p1+p2=p2,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，那么我折线的路径是确定的。如果不知道，那么其实就是要试探每一条可能的折线路径。而这需要的计算量是极大的，就目前的计算机而言，可以认为不可被反推。
简书地址：https://www.jianshu.com/p/f5c64f21fcd5
|
