Bitcoin Forum

关于比特币地址的碰撞概率，好像还没有特别详细的论证。其实这是一个非常重要的问题。因为它直接影响到大众对比特币安全的信心。
严谨的碰撞概率计算，需要考虑的因素太多，算式也复杂。所以，以下的分析仅在数量级上，进行简单的逻辑推算和对比。
u=1278112832,4057677539&fm=15&gp=0
准确度不高，仅供娱乐。
先把结论给不想看过程的朋友：
结论1：碰撞特定比特币地址的概率
假设，你掌握了比特币当前全网算力的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之间，作为私钥。
18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725

第二步，使用椭圆曲线加密算法（ECDSA-secp256k1）计算私钥所对应的非压缩公钥。 (共65字节， 1字节 0×04, 32字节为x坐标，32字节为y坐标）关于公钥压缩、非压缩的问题另文说明。
0450863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B
23522CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6
第三步，计算公钥的 SHA-256 哈希值
600FFE422B4E00731A59557A5CCA46CC183944191006324A447BDB2D98D4B408

第四步，取上一步结果，计算 RIPEMD-160 哈希值
010966776006953D5567439E5E39F86A0D273BEE

第五步，取上一步结果，前面加入地址版本号（比特币主网版本号“0×00”）
00010966776006953D5567439E5E39F86A0D273BEE

第六步，取上一步结果，计算 SHA-256 哈希值
445C7A8007A93D8733188288BB320A8FE2DEBD2AE1B47F0F50BC10BAE845C094

第七步，取上一步结果，再计算一下 SHA-256 哈希值（哈哈）
D61967F63C7DD183914A4AE452C9F6AD5D462CE3D277798075B107615C1A8A30

第八步，取上一步结果的前4个字节（8位十六进制）
D61967F6

第九步，把这4个字节加在第五步的结果后面，作为校验（这就是比特币地址的16进制形态）。
00010966776006953D5567439E5E39F86A0D273BEED61967F6

第十步，用base58表示法变换一下地址（这就是最常见的比特币地址形态）。
16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM

yiqun
base58
简单介绍一下base58。Base58其实就是58进制表示法。
http://chuantu.biz/t/22/1405607450x1822611359.jpg
打个比方，十进制的”58″，用16进制表示就是3A，用base58表示就是”20″（因为1是0，所以2是1），而十进制的”68″，Base58表示就是”2B”。
为什么使用这个奇怪的编码呢？（搞编程的同学注意一下，比特币使用的Base58和常用的base58的字典顺序有区别。）
引用中本聪在源码base58.h中的注释：
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

它是这样构造出来的：
00（版本号） 0000000000000000000000000000000000000000（任意20字节数）94A00911（校验码）

有意思的是，真的有人往这个地址里发币（大约3个币，这些币相当于被销毁了），看这里:https://blockchain.info/address/1111111111111111111114oLvT2
1
比特币地址碰撞
地址的来历搞清楚了，我们来分析一下如何碰撞。
拿全零地址：”1111111111111111111114oLvT2″举例。
仅随机碰撞出该地址对应的公钥是没有意义的。因为比特币交易需要私钥签名才有效。
所以，如果你想使用这个地址里的比特币，前提是拥有这个地址对应公钥的私钥。
也就是说，你需要：
随机生成一个私钥。
计算该私钥对应的公钥.
用公钥算出比特币地址。
与目标地址对比，看看是否一致。
如果不一致，回到第1步。
根据比特币地址理论总数，容易的看出，单次碰撞成功的理论概率是：
1 / ( 2 ^ 160 )  //”2^160″意思是2的160次方

由于每次碰撞至少需要3次SHA-256运算，我们放宽为2次。
在不考虑其他运算的情况下，假设你有1E/每秒的算力（ E = 2^60 相当于当前比特币全网算力的10倍）进行破解。那么，每秒碰撞该地址成功的概率：
( 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
———–

来源：巴比特资讯·论坛

作者：屈爽

的确好深奥啊，不过上面一般看懂了

这次真的证实我就是一般人了 ;D

好深奥 啊

这个不可能的吧

碰撞的機會率小的令人髮指，唯一可行的方案就是破解對方的隨機數的產生過程並能複製重現。

果然看不懂啊 ???

写个木马去偷小白的私钥比碰撞容易多了……
and，我是一般人……

看不懂也要看，这个是要认真学习的 :o

這一步是錯的:

( 1 / ( 2 ^ 101 ) ) * ( 2 ^ 32 )

如果概率可以這樣算, 有>2^101秒, 概率就會>1. 所以明顯是錯的


這一步也是錯的:

( 1 / 17721088 ) / ( 1 / 17179869184 )
= 969.459052627

這只能推論其中一事件比另一事件罕有969倍, 不能說某事件等於另一事件發生969次

抱歉的說, 你的概率學不及格.

被大神批评了吧 ;D

lz是用浅显易懂的语言做的一个科普，也许是没有用特别专业的词语表达而已。

时间=2^101秒，概率=1，这个一点都没有错。lz什么时候说过概率会大于1？
同样lz什么时候说过“某事件等於另一事件發生969次”？？？

证明lz概率学是否及格的最好办法，是你也来写一篇你认为合格的贴子描述一下这个事实，来证明一下你有能力评判别人的概率论水平。

這明顯是錯的, 而且是很低級的錯. 這等於說拋六面骰子6次, 就必會每個數字出現一次.

我當然可以做出合格的計算, 這兩天有時間我會寫出來

这贴子总体思路还行，后面几个算概率的地方有漏洞，LS写个纠错贴吧
碰撞攻击是一个很重要的思路

那啥，俺就是屈爽。
大神说的对，俺大学概率确实挂了，呵呵。
俺也看出错误再哪了，找机会改。
期待大神的文章，记得@我一下！

你这是在偷换概念：2^101秒已经可以顺序把所有的私钥遍历一遍，没必要再随机生成私钥去碰撞，自然可以得出所有的公钥和地址。
而且每个公钥或地址会有很多个私钥与之对应。
就像盖住的骰子让你猜点数，允许你猜六次的话你一定能猜对！
难道你会傻到六次中重复猜某一个数字两次以上吗？

呵呵，不要上火。

算法确实错了。

遍历私钥的时候，地址是随机生成的，像扔骰子。

但是，直觉上，实际算出来的数应该差不多。

直觉上，算力越大，概率增长会越慢。

确实没看懂

錯。不同的私鈅在概率上可以對應相同的地址，因此你的類比不適用。如果你要窮舉所有私鈅，這早已證明是用完太陽的能源也不能完成

So，完全不用担心这事情会发生  :P

随机生成私钥和顺序取用私钥能碰撞出公钥的概率本质上是一致的。

私钥32字节，公钥25字节（实际有效的是20字节），意味着平均每个公钥平均对应0xffffffffffffffffffffffff个私钥（不考虑私钥最大取值为0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141），
“不同的私鈅在概率上可以對應相同的地址”，仅仅是概率上可以对应相同地址？？？

2^101秒约等于80393873682662950373966年，不用证明都知道宇宙早已完结，和证明太阳的能源都不够是一个概念，那你再算概率是不是也没有意义？

本来lz的意思也没有说能做到绝对定量，你的说法也不是完美无缺，更没必要评判别人什么什么的不及格等等之类。

本人已進行了計算在此

https://bitcointalk.org/index.php?topic=653151.msg7905219#msg7905219

2^256個私鑰對應2^160個地址, 當然是肯定有重覆; 但即使不進行RIPEMD160, 讓2^256個私鑰對應2^256個地址, 在概率上仍然是可以重覆. 所以你那個"猜六次點數"的比喻根本不適用.

看你也是懂數學的, 請想清楚再回覆, 不要為辯論而辯論

先声明我数学很菜。
但每个人都有不完美的地方，我和你争论了这么多，主要是看不惯你用不屑的语气说别人什么概率学不合格，别人也是辛辛苦苦码字也是想说明比特币相对很安全的，就事论事就可以了，何必打击别人呢？

额。。。。只能说这种技术性和概率性分析真的不适合我这种人，我只要知道这个概率很低就行了

哎，我是真的看不懂。不过我想如果概率高的话QT早就更换生成地址的程序了

再说一次 闪电会击中同个目标两次的几率比这大多了

严格来说应该是比你连续中10次彩票的机率还低,但是,机率一直都是很有趣的,就算只有0.0000000000000000000000000000000000000000000000000000000000001的可能性,只要它不是0,就是有可能发生. :)

前面的真看不懂，只看了一下最后的总结