测算:比特币地址碰撞概率
关于比特币地址的碰撞概率,好像还没有特别详细的论证。其实这是一个非常重要的问题。因为它直接影响到大众对比特币安全的信心。
严谨的碰撞概率计算,需要考虑的因素太多,算式也复杂。所以,以下的分析仅在数量级上,进行简单的逻辑推算和对比。
准确度不高,仅供娱乐。
先把结论给不想看过程的朋友:
结论1:碰撞特定比特币地址的概率
打个比方,十进制的”58″,用16进制表示就是3A,用base58表示就是”20″(因为1是0,所以2是1),而十进制的”68″,Base58表示就是”2B”。
为什么使用这个奇怪的编码呢?(搞编程的同学注意一下,比特币使用的Base58和常用的base58的字典顺序有区别。)
引用中本聪在源码base58.h中的注释:
假设,你掌握了比特币当前全网算力的10倍,花136年不间断地,碰撞一个特定比特币地址。 碰撞成功的概率,相当于买福彩双色球中了333103亿次500万。(注意单位是亿)结论2:碰撞任意有币地址的概率(生日攻击)
假设,你掌握了比特币当前全网算力的10倍,花136年不间断地,碰撞所有存币地址。 碰撞其中任意地址的概率,相当于买福彩双色球中1000次500万。 (注意,这些地址中50%以上存币量小于0.001BTC)下面我来看看这两个结论的推导过程。 当然,推导之前,我们首先要把比特币地址研究透彻。 比特币地址不是公钥 这句话可能出乎很多人意料。 其实,严谨的说法应该是:
我们看一下比特币地址的生成过程就比较清楚了。 比特币地址的生成过程 (说明: 有些数字以”0x”开头,意思是此数字使用十六进制表示法。”0x”本身没有任何含义,它是C语言流传下来的,约定俗成的写法,比如0xA就是十进制的10。另外,1个字节 = 8位二进制 = 2位十六进制)。 第一步,随机选取一个32字节的数、大小介于1 ~ 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141之间,作为私钥。比特币地址是加入校验的公钥摘要。
第二步,使用椭圆曲线加密算法(ECDSA-secp256k1)计算私钥所对应的非压缩公钥。 (共65字节, 1字节 0×04, 32字节为x坐标,32字节为y坐标)关于公钥压缩、非压缩的问题另文说明。18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725
0450863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B 23522CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6第三步,计算公钥的 SHA-256 哈希值
第四步,取上一步结果,计算 RIPEMD-160 哈希值600FFE422B4E00731A59557A5CCA46CC183944191006324A447BDB2D98D4B408
第五步,取上一步结果,前面加入地址版本号(比特币主网版本号“0×00”)010966776006953D5567439E5E39F86A0D273BEE
第六步,取上一步结果,计算 SHA-256 哈希值00010966776006953D5567439E5E39F86A0D273BEE
第七步,取上一步结果,再计算一下 SHA-256 哈希值(哈哈)445C7A8007A93D8733188288BB320A8FE2DEBD2AE1B47F0F50BC10BAE845C094
第八步,取上一步结果的前4个字节(8位十六进制)D61967F63C7DD183914A4AE452C9F6AD5D462CE3D277798075B107615C1A8A30
第九步,把这4个字节加在第五步的结果后面,作为校验(这就是比特币地址的16进制形态)。D61967F6
第十步,用base58表示法变换一下地址(这就是最常见的比特币地址形态)。00010966776006953D5567439E5E39F86A0D273BEED61967F6
base58 简单介绍一下base58。Base58其实就是58进制表示法。 Base58编码表:16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM
实际值 | 编码值 | 实际值 | 编码值 | 实际值 | 编码值 | 实际值 | 编码值 | |||
0 | 1 | 16 | H | 32 | Z | 48 | q | |||
1 | 2 | 17 | J | 33 | a | 49 | r | |||
2 | 3 | 18 | K | 34 | b | 50 | s | |||
3 | 4 | 19 | L | 35 | c | 51 | t | |||
4 | 5 | 20 | M | 36 | d | 52 | u | |||
5 | 6 | 21 | N | 37 | e | 53 | v | |||
6 | 7 | 22 | P | 38 | f | 54 | w | |||
7 | 8 | 23 | Q | 39 | g | 55 | w | |||
8 | 9 | 24 | R | 40 | h | 56 | y | |||
9 | A | 25 | S | 41 | i | 57 | z | |||
10 | B | 26 | T | 42 | j | |||||
11 | C | 27 | U | 43 | k | |||||
12 | D | 28 | V | 44 | m | |||||
13 | E | 29 | W | 45 | n | |||||
14 | F | 30 | X | 46 | o | |||||
15 | G | 31 | Y | 47 | p |
Why base-58 instead of standard base-64 encoding? 为啥用base58,不用base-64? Don’t want 0OIl characters that look the same in some fonts and could be used to create visually identical looking account numbers. 俺不想要0、O、I、l这几个字母。因为在很多字体里这几个字母容易混。而且转换以后,看着比以前舒服多了。 A string with non-alphanumeric characters is not as easily accepted as an account number. 数字字母组成的账户,大家好理解。 E-mail usually won’t line-break if there’s no punctuation to break at. 如果没有标点符号,E-mail一般不换行。 Doubleclicking selects the whole number as one word if it’s all alphanumeric. 双击可以选择整个字符串,哦耶。椭圆曲线加密算法、SHA-256哈希算法、RIPEMD-160哈希算法 这三个算法的原理,一句两句说不清楚,先忽略了。以后再写文章详细介绍吧(不要打我)。 只说用途:
- 椭圆曲线加密算法:把任意随机数当做私钥,生成公钥形成密码对。私钥保密,公钥公开。私钥签名的信息,可用公钥验证签名的真实性。签名无法伪造。
- SHA-256哈希算法:把任意大小的数据,经特定算法混淆后,生成一个256位二进制长度的数,作为原数据的摘要信息。(可正向验算,无法反推)
- RIPEMD-160哈希算法:把任意大小的数据,经特定算法混淆后,生成一个160位的二进制长度的数,作为原数据的摘要信息。(可正向验算,无法反推)
- 仅有比特币地址,无法反推出公钥。
- 合法的比特币地址不一定有对应的公钥。
比如这个:
它是这样构造出来的:1111111111111111111114oLvT2
有意思的是,真的有人往这个地址里发币(大约3个币,这些币相当于被销毁了),看这里:https://blockchain.info/address/1111111111111111111114oLvT2 比特币地址碰撞 地址的来历搞清楚了,我们来分析一下如何碰撞。 拿全零地址:”1111111111111111111114oLvT2″举例。 仅随机碰撞出该地址对应的公钥是没有意义的。因为比特币交易需要私钥签名才有效。 所以,如果你想使用这个地址里的比特币,前提是拥有这个地址对应公钥的私钥。 也就是说,你需要:00(版本号) 0000000000000000000000000000000000000000(任意20字节数)94A00911(校验码)
- 随机生成一个私钥。
- 计算该私钥对应的公钥.
- 用公钥算出比特币地址。
- 与目标地址对比,看看是否一致。
- 如果不一致,回到第1步。
由于每次碰撞至少需要3次SHA-256运算,我们放宽为2次。 在不考虑其他运算的情况下,假设你有1E/每秒的算力( E = 2^60 相当于当前比特币全网算力的10倍)进行破解。那么,每秒碰撞该地址成功的概率:1 / ( 2 ^ 160 ) //”2^160″意思是2的160次方
( 1 / ( 2 ^ 160 ) ) * ( 2 ^ 60 ) / 2 = 1 / ( 2 ^ 101 )假设你可以活 2^32秒 = 4294967296秒 ≈ 136.2年,你在有生之年碰撞该地址成功的概率为:
( 1 / ( 2 ^ 101 ) ) * ( 2 ^ 32 ) = 1 / ( 2 ^ 69)这是个什么概念呢? 我们看双色球命中500万的概率:
用这个概率除以碰撞概率:1/C(33,6)*16 = 1/[ (33 * 32 * 31 * 30 * 29 *28/6*5*4*3*2*1)* 16 ] = 1/17721088
( 1 / 17721088 ) / ( 1 / ( 2 ^ 69 ) ) ≈ 33310359406753.4所以,结论是:假设,你掌握了比特币当前全网算力的10倍,花136年不间断地,碰撞一个特定比特币地址。碰撞成功的概率,相当于买福彩双色球中了333103亿次500万。(注意单位是亿) 考虑生日攻击 当前,有币的地址大约为300万个。看这里:http://btc.ondn.net/search 我们把这个数字翻1万倍。假设有343亿个有比特币的地址(2^35 ≈ 343亿,相当于每个地球人有5个有余额的地址,火星人的先不算了,呵呵) 那么命中其中任意一个地址的概率:
( 1 / ( 2 ^ 69 ) ) * ( 2 ^ 35 ) = 1 / 2 ^ 34 = 1 / 17179869184再和中500万比一下:
( 1 / 17721088 ) / ( 1 / 17179869184 ) = 969.459052627咦,和中1000次500万的概率很接近了! 所以,结论是:假设,你掌握了比特币当前全网算力的10倍,花136年不间断地,碰撞所有存币地址。碰撞其中任意地址的概率,相当于买福彩双色球中1000次500万。 (注意,这些地址中50%以上存币量小于0.001BTC) 后记 以上计算有很多省略的地方,计算时考虑最宽松情况。所以实际概率更小。 比特币系统的设计,让拥有算力的人倾向去算blockchain,因为比碰撞地址划算的多。 本文计算有错误疏漏,欢迎指正。但是指正了,我也不一定改。(开个玩笑,不要打我) 没中过1000次500万的同学,不要幻想算出别人的地址了,不如去玩骰子…洗洗睡吧。 喜欢《比特币地址碰撞概率》请捐款: 122222o5a3k6dy7WL5maBBpuvKUtZJhMk4 参考文献:
- https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses
- https://en.bitcoin.it/wiki/Base58Check_encoding
- http://procbits.com/2013/08/27/generating-a-bitcoin-address-with-javascript
- https://bitcointalk.org/index.php?topic=41718.0
- https://en.bitcoin.it/wiki/List_of_address_prefixes
- https://en.bitcoin.it/wiki/Wallet_import_format
- https://en.bitcoin.it/wiki/Private_key
———–
来源:资讯·论坛
作者:屈爽
上一篇:
杰森·伯恩是如何存储他的比特币的
下一篇:
比特币协议
推荐专栏
热门币种
更多
币种
价格
24H涨跌幅
热搜币种
更多
币种
价格
24H涨跌幅
最新快讯
更多
2023-11-28 19:06:57
2023-11-28 19:03:57
2023-11-28 18:59:52
2023-11-28 18:53:43
2023-11-28 18:53:38
2023-11-28 18:52:07
2023-11-28 18:47:58