Bitcoin Forum
January 26, 2022, 07:00:20 PM *
News: Latest Bitcoin Core release: 22.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: [转]谈谈“熵”  (Read 1109 times)
xfli
Hero Member
*****
Offline Offline

Activity: 854
Merit: 1000


走哪算哪


View Profile
December 22, 2014, 10:34:21 PM
 #1

熵(Entropy)在物理学中用于度量一个热力学系统的无序或混乱程度(参考热力学第二定律),当它被引入到信息论(计算机科学)时,则被用来衡量信息的不确定性(不可预测性),简单的说也就是“随机性”。

假设有一枚“理想”的硬币(抛出正面和反面的几率相等),每一次抛硬币都是独立的、不可预测的,其结果不是正面、就是反面(0和1),那么这个抛硬币事件的熵就是1个比特/位,抛256次的熵就是256个比特/位(这甚至都可以用来作为“理想”的比特币私钥)。

如果不去考虑复杂的定义、恼人的公式,“熵”其实就是那么简单,本文不想从学术上更深入的讨论熵,只想阐述一个对于密码学来说很重要的定律:
任何算法(包括那些符合密码学规范的伪随机数算法)只能是“维持”熵、甚至有可能会“降低”熵,但一定不能“增加”熵!

这一点至关重要,历史上发生过的无数次随机数问题(无论是否与比特币相关),基本上都源于对这一点的忽视。

以前段时间发生的 blockchain.info 的随机数问题为例,blockchain.info使用的 RC4 算法(http://en.wikipedia.org/wiki/RC4 因版权问题通常也被称为ARC4)是一个广泛使用的密码学算法,通常被用来生成伪随机数的信息流。ARC4算法有一个非常“好”的特性,即:只需要一个种子(哪怕这个种子只有两位,0和1),就能生成“无限多”的随机数,你只需要反复的对结果进行 ARC4 运算即可。

比如说,使用0或者1初始化 ARC4 数组,然后反复的进行 ARC4 运算,您都可以得到任意长度的数列,数列中的每一个元素都是0-255(8位)的数字,出于篇幅限制,小太在这里只运行了256次的 ARC4next 方法。
0 : [222,24,137,65,163,55,93,58,138,6,30,103,87,110,146,109,199,26,127,163,240,204,235,151,69,43,77,50,39,150,95,158,168,204,117,7,109,159,185,197,65,122,165,203,48,252,34,25,139,52,152,45,187,98,158,192,75,79,139,5,160,113,8,80,146,160,195,88,74,72,228,163,10,57,123,138,205,29,0,158,200,125,104,17,242,44,244,156,163,229,147,84,185,69,21,53,162,24,122,134,66,108,202,125,94,130,62,186,0,68,18,103,18,87,184,216,96,174,76,189,76,73,6,187,197,53,239,225,88,127,8,219,51,149,92,219,203,173,155,16,245,63,196,229,44,89,21,101,81,132,135,254,8,77,14,63,3,222,188,201,218,28,233,13,8,92,45,138,25,216,55,48,134,22,54,146,20,43,216,252,93,122,115,73,106,142,89,238,126,207,107,148,6,99,244,166,190,230,91,210,200,92,70,152,108,27,239,52,144,211,123,56,218,133,211,46,151,57,203,35,74,43,231,64,235,8,137,54,33,153,175,204,50,131,85,153,13,79,137,251,99,195,228,81,116,172,100,77,71,2,71,63,151,209,157,98]
1 : [6,8,14,14,24,32,41,41,57,51,73,87,102,118,135,131,161,181,202,224,247,102,17,124,76,104,133,163,194,226,163,73,108,38,57,127,166,206,23,65,224,71,165,211,186,87,52,103,128,180,137,239,127,183,151,209,60,44,48,147,210,142,207,149,216,104,173,167,238,239,94,230,67,143,76,236,63,143,154,197,12,17,10,119,104,46,106,197,42,3,171,116,97,215,94,138,225,97,198,118,100,125,26,61,58,230,88,198,0,112,124,71,207,55,97,128,47,75,153,130,158,95,117,7,105,226,176,130,239,90,49,125,20,247,71,95,234,13,154,98,178,210,63,236,243,36,147,202,101,88,53,9,222,9,250,163,15,184,130,181,167,249,231,37,187,125,231,174,239,43,92,255,255,154,201,48,177,206,22,183,105,92,9,8,94,51,211,200,121,189,64,9,97,248,174,13,201,173,209,196,15,129,227,3,127,184,41,69,165,199,122,90,33,63,21,160,164,205,37,93,222,211,137,199,18,135,107,7,83,10,230,113,108,41,195,34,181,63,68,164,52,214,97,63,178,22,55,192,80,153,210,224,91,240,104,165]

这个数列中的任意一段(32个元素即256位),都可以被用来作为比特币私钥或签名时使用的 k 值,他们看起来都很“随机”。可惜,无论您进行了怎样的运算,这个数列的熵都永远小于等于1个比特(即0和1)。也就是说,其它人,如果能覆盖全部的熵,进行相同的运算,也能够计算出您的全部私钥和全部 k 值。

blockchain.info 出问题时的熵是8个比特(0-255),也就是说,您只需要使用这256个数字作为种子,反复的进行 ARC4 运算,就能覆盖出问题的时间段里 blockchain.info 用户所使用的全部随机数(考虑到浏览器缓存和 CDN 缓存,问题时间段的长度可能是数周)。当然,您还可以基于代码进行一些优化,只考虑部分可能出现的情况,比如说每进行33次 ARC4next 生成一个随机数,或者是间隔256次 ARCnext 后再用33次 ARCnext 来生成一个随机数。

例如,上述种子0所对应的数组中,我们可以进行如下简单的计算:
1、取开头的33个元素:[222,24,137,65,163,55,93,58,138,6,30,103,87,110,146,109,199,26,127,163,240,204,235,151,69,43,77,50,39,150,95,158,168];
2、按照 blockchain.info 的算法(他们自己定义的 BigInteger 类型),将第一个元素替换为0,最后一个元素加1,即得到结果数组:[0,24,137,65,163,55,93,58,138,6,30,103,87,110,146,109,199,26,127,163,240,204,235,151,69,43,77,50,39,150,95,158,169];
3、使用这个结果数组可以得到一个 k 值:188941a3375d3a8a061e67576e926dc71a7fa3f0cceb97452b4d3227965f9ea9;
4、再使用 ECDSA 算法计算出该 k 值所对应的 r 值:0dcc0b9a668d4b7b8cbde71288bf32bb659bd7fda1b66172ce97fda6f8b0a06e;
5、这个 r 值在整个区块链的交易签名中一共出现过5次,这5笔交易所对应的私钥均已暴漏;
6、比如说,地址:19hXXVpwhmu1frqKwF1VZdNfqtGrMvg87n,交易 hash:b2b63f29c379ff830f45a5165b0e374093207ddca3e737562617c1d526ef4c65,该笔交易签名就是这个 r 值,利用区块链上的数据,任何人都能够很容易的计算出该地址的私钥:5JHyRh8hwyjWjt3RR3B9X6oJt9mzJZwFe8YnF7W22XcSHdD6rxK;
7、BOOM!

看到这里,您就该明白了,对于比特币所需要的随机数来说,仅仅使用密码学安全的伪随机数算法还是不够的,您需要的是“好的”、“足够”的熵(比特币需要的是256个比特/位),无论您使用的是哪种算法,永远要保证熵的品质,永远都不要降低熵。
最后说一句,比特币本身是安全的,不安全的是错误的解决方案和有问题的熵!

注:小太之前在 github 上开源的分析程序(https://github.com/bither/analyze)中就有完整的 ARC4 算法的实现,有兴趣的不妨自己动手试试,您也能算出很多已经被“碰撞”到的随机数哈。

作者:比太钱包
官方微博:@比太钱包 http://weibo.com/bither
官网:http://bither.net
捐赠地址:1BsTwoMaX3aYx9Nc8GdgHZzzAGmG669bC3

1643223620
Hero Member
*
Offline Offline

Posts: 1643223620

View Profile Personal Message (Offline)

Ignore
1643223620
Reply with quote  #2

1643223620
Report to moderator
There are several different types of Bitcoin clients. The most secure are full nodes like Bitcoin Core, which will follow the rules of the network no matter what miners do. Even if every miner decided to create 1000 bitcoins per block, full nodes would stick to the rules and reject those blocks.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1643223620
Hero Member
*
Offline Offline

Posts: 1643223620

View Profile Personal Message (Offline)

Ignore
1643223620
Reply with quote  #2

1643223620
Report to moderator
1643223620
Hero Member
*
Offline Offline

Posts: 1643223620

View Profile Personal Message (Offline)

Ignore
1643223620
Reply with quote  #2

1643223620
Report to moderator
1643223620
Hero Member
*
Offline Offline

Posts: 1643223620

View Profile Personal Message (Offline)

Ignore
1643223620
Reply with quote  #2

1643223620
Report to moderator
tianjinlian
Sr. Member
****
Offline Offline

Activity: 266
Merit: 250


View Profile
December 23, 2014, 01:26:25 AM
 #2

熵值也能适用于比特币吗? proof of energy、

10000usdperbtc
Legendary
*
Offline Offline

Activity: 980
Merit: 1000



View Profile
December 23, 2014, 07:26:59 AM
 #3

不是很明白
justforbtc
Hero Member
*****
Offline Offline

Activity: 714
Merit: 500


View Profile
December 23, 2014, 08:10:52 AM
 #4

不是很明白

不用太明白,只需要明白blockchain.info的程序員是多麼的不專業。隨機數的seed竟然只有8個bits,只有兩個解釋,一個就是那個程序員特意這麼搞,方便偷幣,要麼就是真的沒安全概念,完全是水貨,可以直接炒了!

還有就是我搞不懂為何blockchain用的是偽隨機,就是軟件產生的隨機數,而不是用硬件產生的隨機數…
7425504
Sr. Member
****
Offline Offline

Activity: 397
Merit: 250



View Profile
December 24, 2014, 07:08:04 AM
 #5

比特币涉及的范围太广了


▄████████████████████████████████▄
██████████████████████████████████
██████████████████████████████████
██████████████████████████████████
██████              ██████████████
██████              ██████████████
██████████████▀    ▄███▀▀██▀▀▀████
████████████▀    ▄█████  ▀    ████
██████████▀    ▄███████    ▄██████
████████▀    ▄█████████   ████████
██████▀    ▄███████████   ████████
██████              ███   ████████
██████              ███   ████████
██████████████████████████████████
██████████████████████████████████
██████████████████████████████████
▀████████████████████████████████▀
Coin

.WORLD'S  FIRST  COMMODITY-BACKED  BLOCKCHAIN  OPTION.
......▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀.......
HIGH PROFIT CASH BACK ON DEMAND REAL PRODUCTION


JOIN ICO
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
.BECOME AN INVESTOR.
v0yager
Hero Member
*****
Offline Offline

Activity: 518
Merit: 500



View Profile
December 24, 2014, 10:11:15 AM
 #6

BlockChian.info就是个几个员工的小公司,不过前阵子不是得到融资了吗?还是这副样子。
IOJD
Sr. Member
****
Offline Offline

Activity: 252
Merit: 250

IO * JD


View Profile
December 24, 2014, 10:18:22 AM
 #7

BlockChian上面生成的钱包地址会不会和别人的地址重复?   不过在线钱包发币挺方便的就是不适合来存放比特币。

ossurrond
Newbie
*
Offline Offline

Activity: 21
Merit: 0


View Profile
December 24, 2014, 01:59:36 PM
 #8

我达到了条件 还是不能在其他版块发帖
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!