首页 > 相关教程 > 其他 > [技术帖]离散对数的破解算法及其对比特币的影响

[技术帖]离散对数的破解算法及其对比特币的影响

时间:2014-05-19  来源:巴比特  作者: 点击:loding... 分享到:

昨天看到有人在微博上发出该论文《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位密钥长度相抗衡。

四、影响评估

简要地说明论文算法对比特币的影响:论文算法不适用于比特币椭圆曲线的情况。 作一个比喻:挖土机在挖路,会让路上的汽车翻车,但对飞过的飞机没影响。

五、建议

某微博在发送该信息时,用了“比特币算法遭破解?”和“达到了量子计算机的解密能力”的字眼。前者还好说,用了怀疑的语气,但后者明显是误读了,因为新闻内容和论文内容中并未出现这些含义,建议不确定的字眼不要写。

文章来源:巴比特

①凡本网注明“来源:83楼网赚论坛”的所有作品,版权均属于83楼网赚论坛,未经本网授权不得转载、摘编或利用其它方式使用上述作品。已经本网授权使用作品的,应在授权范围内使用,并注明“来源: 83楼网赚论坛”。违反上述声明者,本网将追究其相关法律责任。

②凡本网注明“来源:XXX(非83楼网赚论坛)”的作品,均转载自其它媒体,转载目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。

③如因作品内容、版权和其它问题需要同本网联系的,请在30日内进行。

相关阅读: