Topic: 离散对数的破解算法及其对比特币的影响 (Read 576 times)
太高端了，学习，必须从新上个大学。
技术流，看不懂
发布日期 2014 年 5 月 18 日 作者 我看比特币 在 商业经济, 技术指南,
昨天看到有人在微博上发出该论文《A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic》 (《一种基于小特征有限域的离散对数拟多项式算法》)的信息后，本人花了不少时间去研究，并且把一些零碎的研究结果在微博上发出。 昨天晚上和今天继续研究，并且咨询了深圳大学ATR实验室专门研究椭圆曲线加密算法的老师，基本搞清楚了论文算法的适用范围及对椭圆曲线加密算法的影响。现成文如下，以完整说明。
一、论文算法的适用范围
该论文算法的适用范围是基于小特征有限域之上的离散对数问题。
(1) 小特征是指p小于等于2，即p<=2。
(2) 小特征有限域是针对域F(p ^ n)，n为整数且不为1
(3) 针对小特征有限域上的离散对数问题
二、比特币椭圆曲线算法
(1) 比特币椭圆曲线算法定义在F(p)有限域上，其中
p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
= 2 ^ 256 - 2 ^ 32 - 2 ^ 9 - 2 ^ 8 - 2 ^ 7 - 2 ^ 6 - 2 ^ 4 - 1 = 1.15792E+77
(2) 比特币椭圆曲线是secp256k1，(具体标准：http://www.secg.org/collateral/sec2_final.pdf)，
secp256k1是基于F(p)有限域上的椭圆曲线:
y^2 = x^3 + ax + b，其中 a = 0，b = 7
三、算法分析
(1) 论文算法针对的是小特征有限域F(p ^ n)，小特征p<=2，n为整数且不为1。而比特币椭圆曲线的有限域F(p)，p大到10的77次方。 两者在完全不同的有限域，因而论文算法根本不适用比特币椭圆曲线的情况。
(2) 论文算法针对离散对数问题DLP，比特币椭圆曲线是基于椭圆曲线离散对数问题(ECDLP)，两者的复杂度不在一个数量级。 因而椭圆曲线256位的密钥长度，其安全性就可以与RSA的1024位密钥长度相抗衡。
四、影响评估
简要地说明论文算法对比特币的影响：论文算法不适用于比特币椭圆曲线的情况。 作一个比喻：挖土机在挖路，会让路上的汽车翻车，但对飞过的飞机没影响。
五、建议
某微博在发送该信息时，用了“比特币算法遭破解？”和“达到了量子计算机的解密能力”的字眼。前者还好说，用了怀疑的语气，但后者明显是误读了，因为新闻内容和论文内容中并未出现这些含义，建议不确定的字眼不要写。
Jump to: