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

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

昨天看到有人在微博上发出该论文《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

文章标签: 比特币
评论(33)
登录 账号发表你的看法,还没有账号?立即免费 注册
  • 沣述 2014-05-18
    论文发在了今年的欧密会上,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年都出问题了,就不会有后面的跌宕起伏了。 能发现这篇论文与比特币可能存在的关系固然好,拥有发现这篇文章的能力都还去乱解读就有点那个啥了。
  • 离散对数的破解算法及其对比特币的影响 | 三个硬币 2014-05-19
    [...] 转自:巴比特 [...]
  • 巴比特资讯 2014-06-23
    1bdadc0c856c24247d85c8fd2f552bf1f850051207a59554aba02de96820de4e
  • 冷荣蓉 2014-05-18
    隔着玻璃打不到鱼也抓不到鱼
  • JadRuby 2014-05-18
    看完了文章,完全看不懂
  • 招财资本 2014-05-18
    擦,当年我研究生就是搞椭圆加密算法研究的,早毕业了2年,否则比特币我估计囤了一堆//@DOGECOIN2014:转发微博
  • COIN2018 2014-05-18
    回复@无处不在的猫先生: 哪你要是不毕业也可以成为中本猫了
  • 潘玉明 2014-05-18
    貌似很牛x的样子
  • 招财资本 2014-05-18
    回复@DOGECOIN2014:是啊。结果现在变成中本狗,一文不值啊 还亏废了
  • 星期六不死星人 2014-05-18
    好像是用来破解银行卡的吧
  • 长铗 2014-05-18
    比特币现在成了密码学上的皇冠,谁都想挑而战之,只是要担心别闪了腰。申屠出品,质量保证。
  • 重楼SAMA 2014-05-18
    一直有个问题很好奇。未来为什么就一定是比特币呢?可不可能是用同样的算法造出其他的币种呢?
  • COIN2018 2014-05-18
    回复@无处不在的猫先生: 呵呵,一样别着急,只要狗币没死,人气没减,总有机会的
  • 轻公益基金 2014-05-18
    //@长铗:比特币现在成了密码学上的皇冠,谁都想挑而战之,只是要担心别闪了腰。申屠出品,质量保证。
  • 招财资本 2014-05-18
    回复@DOGECOIN2014:打算继续囤点
  • 招财资本 2014-05-18
    回复@DOGECOIN2014:我靠 我有个大微博 @温哥华-经商知道
  • 招财资本 2014-05-18
    回复@DOGECOIN2014:要不利用起来推广狗币吧
  • COIN2018 2014-05-18
    回复@无处不在的猫先生: 好啊,你是做什么的?
  • 招财资本 2014-05-18
    回复@DOGECOIN2014:加qq
  • 洋HUST 2014-05-31
    不懂。。。
  • 1
  • 2