当前位置: 首页 > 下载 > 正文

离散对数的破解算法及其对比特币的影响

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

四、影响评估

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

五、建议

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

来自:http://www.8btc.com/ecc_dlp

固定链接: 离散对数的破解算法及其对比特币的影响 | 三个硬币

该日志由 bitman 于2014年05月18日发表在 下载 分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
原创文章转载请注明: 离散对数的破解算法及其对比特币的影响 | 三个硬币
关键字:

离散对数的破解算法及其对比特币的影响:等您坐沙发呢!

发表评论

快捷键:Ctrl+Enter