OKCoin

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

申屠青春 发布在 币头条,技术指南,比特币 33 9843

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

四、影响评估

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

五、建议

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

BTC地址:1faVxBp2KmST98p3tJjx2MQP98JLLnF2Q

版权声明: by nc" sa 作者保留权利。文章为作者独立观点,不代表巴比特立场。

评论:33

您需要登录后才可以回复 登录|注册
    Author Image
    巴比特资讯 902 天前

    1bdadc0c856c24247d85c8fd2f552bf1f850051207a59554aba02de96820de4e

    +1
    +1
    我要点评
    洋HUST
    洋HUST 925 天前

    不懂。。。

    +1
    +1
    我要点评
    御坂65536
    御坂65536 926 天前

    我為什麼這麼懼怕數學(´ ・ω・`) //@长铗:比特币现在成了密码学上的皇冠,谁都想挑而战之,只是要担心别闪了腰。申屠出品,质量保证。

    +1
    +1
    我要点评
    南蛮子w
    南蛮子w 935 天前

    需要技术大拿来维护并升级,方可长远

    +1
    +1
    我要点评
    赵乐天
    赵乐天 936 天前

    //@宋欢平:[酷] //@长铗:比特币现在成了密码学上的皇冠,谁都想挑而战之,只是要担心别闪了腰。申屠出品,质量保证。

    +1
    +1
    我要点评
    等一轮残月
    等一轮残月 936 天前

    [酷]//@宋欢平:[酷] //@长铗:比特币现在成了密码学上的皇冠,谁都想挑而战之,只是要担心别闪了腰。申屠出品,质量保证。

    +1
    +1
    我要点评
    宋欢平
    宋欢平 936 天前

    [酷] //@长铗:比特币现在成了密码学上的皇冠,谁都想挑而战之,只是要担心别闪了腰。申屠出品,质量保证。

    +1
    +1
    我要点评
    招财资本
    招财资本 937 天前

    回复@DOGECOIN2014:加qq

    +1
    +1
    我要点评
    COIN2018
    COIN2018 937 天前

    回复@无处不在的猫先生: 好啊,你是做什么的?

    +1
    +1
    我要点评
    招财资本
    招财资本 937 天前

    回复@DOGECOIN2014:要不利用起来推广狗币吧

    +1
    +1
    我要点评
    招财资本
    招财资本 937 天前

    回复@DOGECOIN2014:我靠 我有个大微博 @温哥华-经商知道

    +1
    +1
    我要点评
    招财资本
    招财资本 937 天前

    回复@DOGECOIN2014:打算继续囤点

    +1
    +1
    我要点评
    Author Image
    沣述 938 天前

    论文发在了今年的欧密会上,Advances in Cryptology – EUROCRYPT 2014
    A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic
    这篇论文最早于2013年年中就放在了IACR的网站上,见 http://eprint.iacr.org/2013/400.pdf
    该出问题13年都出问题了,就不会有后面的跌宕起伏了。
    能发现这篇论文与比特币可能存在的关系固然好,拥有发现这篇文章的能力都还去乱解读就有点那个啥了。

    +1
    +1
    我要点评
    轻公益基金
    轻公益基金 937 天前

    //@长铗:比特币现在成了密码学上的皇冠,谁都想挑而战之,只是要担心别闪了腰。申屠出品,质量保证。

    +1
    +1
    我要点评
    COIN2018
    COIN2018 937 天前

    回复@无处不在的猫先生: 呵呵,一样别着急,只要狗币没死,人气没减,总有机会的

    +1
    +1
    我要点评
    就爱BIT
    就爱BIT 937 天前

    看还能打压多久//@Longinus://@长铗: 比特币现在成了密码学上的皇冠,谁都想挑而战之,只是要担心别闪了腰。申屠出品,质量保证。

    +1
    +1
    我要点评
    Longinus
    Longinus 937 天前

    //@长铗: 比特币现在成了密码学上的皇冠,谁都想挑而战之,只是要担心别闪了腰。申屠出品,质量保证。

    +1
    +1
    我要点评
    日韩潮流衣服
    日韩潮流衣服 937 天前

    分享图片

    +1
    +1
    我要点评
    疯狂-BTC
    疯狂-BTC 937 天前

    //@长铗:比特币现在成了密码学上的皇冠,谁都想挑而战之,只是要担心别闪了腰。申屠出品,质量保证。

    +1
    +1
    我要点评
    重楼SAMA
    重楼SAMA 937 天前

    一直有个问题很好奇。未来为什么就一定是比特币呢?可不可能是用同样的算法造出其他的币种呢?

    +1
    +1
    我要点评
    智比特
    智比特 937 天前

    //@长铗:比特币现在成了密码学上的皇冠,谁都想挑而战之,只是要担心别闪了腰。申屠出品,质量保证。

    +1
    +1
    我要点评
    长铗
    长铗 937 天前

    比特币现在成了密码学上的皇冠,谁都想挑而战之,只是要担心别闪了腰。申屠出品,质量保证。

    +1
    +1
    我要点评

    好像是用来破解银行卡的吧

    +1
    +1
    我要点评
    招财资本
    招财资本 938 天前

    回复@DOGECOIN2014:是啊。结果现在变成中本狗,一文不值啊 还亏废了

    +1
    +1
    我要点评
    潘玉明
    潘玉明 938 天前

    貌似很牛x的样子

    +1
    +1
    我要点评
    COIN2018
    COIN2018 938 天前

    回复@无处不在的猫先生: 哪你要是不毕业也可以成为中本猫了

    +1
    +1
    我要点评
    招财资本
    招财资本 938 天前

    擦,当年我研究生就是搞椭圆加密算法研究的,早毕业了2年,否则比特币我估计囤了一堆//@DOGECOIN2014:转发微博

    +1
    +1
    我要点评
    Caroline荼蘼
    Caroline荼蘼 938 天前

    答辩完毕[奥特曼][奥特曼] 学生生涯即将结束[拜拜][拜拜] 还没离开就已经开始怀念了。。。[泪][泪] 我在这里:http://t.cn/z8A9tBa

    +1
    +1
    我要点评
    巴比特资讯
    巴比特资讯 938 天前

    【离散对数的破解算法及其对比特币的影响】http://t.cn/RvzWyQ8 作者:@我看比特币 比特币算法遭破解?本文通过研究离散对数破解算法的适用范围,发现其与比特币椭圆曲线算法在完全不同的有限域,作个形象比喻:挖土机在挖路,会让路上的汽车翻车,但对上空飞过的飞机没影响。

    +1
    +1
    我要点评
    JadRuby
    JadRuby 938 天前

    看完了文章,完全看不懂

    +1
    +1
    我要点评
    秋风牧神
    秋风牧神 938 天前

    不管我们的距离有多遥远,关怀你的好活动的心永不变。` 地址:http://t.cn/RvhrVR6

    +1
    +1
    我要点评
    冷荣蓉
    冷荣蓉 938 天前

    隔着玻璃打不到鱼也抓不到鱼

    +1
    +1
    我要点评