测算:比特币地址碰撞概率

区块链技术巴比特2017-11-25 06:50:28  阅读 -评论 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

测算:比特币地址碰撞概率

base58

简单介绍一下base58。Base58其实就是58进制表示法。

Base58编码表:

实际值

编码值

实际值

编码值

实际值

编码值

实际值

编码值

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

打个比方,十进制的”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

比特币地址碰撞

地址的来历搞清楚了,我们来分析一下如何碰撞。

拿全零地址:”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

———–

来源:巴比特资讯·论坛

作者:屈爽

声明:链世界登载此文仅出于分享区块链知识,并不意味着赞同其观点或证实其描述。文章内容仅供参考,不构成投资建议。投资者据此操作,风险自担。此文如侵犯到您的合法权益,请联系我们100@7234.cn

    参与讨论 (0 人参与讨论)

    相关推荐

    区块链投资趋势报告:巨头入场布局行业趋于成熟

    区块链投资趋势报告:巨头入场布局行业趋于成熟

    来自:https://mp.weixin.qq.com/s?__biz=MzI4NzIxOTY1NA==&mid=2650632639&idx=1&sn=e6d1c29731d992a80410aaee82ec3ea6&chksm=f3d8db16c4af520097e4a64a71b1d4743ac326b9f027

    重新发明货币

    重新发明货币

    一、货币的演化过程 先简单回顾一下人类货币的演化过程,大概有以下阶段: a. 1.0版本:自然货币(贝壳、牲口、金银……) 这个阶段,货币基于一般等价物的稀有性或者实用性,货币不可能出现人为操纵的超发。 b. 2.0版本:早期纸币、银票到本位纸币 当贸易量越来越大,实物货币太不方便了,而且大家发现其实并不在意货币本身有什么价值,在意的只是这么多的货币能不能交换到足够的物品,于是纸币这种信用货

    从比特币交易看欧洲央行虚拟货币分类

    从比特币交易看欧洲央行虚拟货币分类

      互联网对传统社会的颠覆从未停止,在其完成对信息流、商流、物流、资金流的初步改造之后,或将以虚拟货币的形式打破现有货币体系   4月18日,在中国极客张沈鹏创办的比特币交易平台(42BTC.com)上,比特币对人民币的平均交易价为576元。当天,该平台完成了100个比特币的交易量。仅仅过去一周,4月25日上午,比特币对人民币的平均交易价已达到906元。据42BTC网站统计:在过去的32个月

    欧洲央行-比特币报告

    3.1 比特币 3.1.1 基本特征          比特币可能是最成功的,也可能是最有争议的虚拟货币方案,由日本程序员中本聪(译者注:事实上,中本聪是不是日本人,甚至是不是单个人无从考证)在2009年设计并实现。该计划基于一个类似于BitTorrent的P2P网络。BitTorrent是互联网上著名的共享文件协议,应用在电影,游戏和音乐领域。比特币在全球层面上运作,可用于各类货币交易(虚

    彻底玩转比特币地址和私匙

    彻底玩转比特币地址和私匙

    比特币地址和私匙是所有比特币初学者面对的一大难题,再加上那一串超长的字符串,让人更是摸不到头脑。 现在编者以问答的形式,带你一步步的揭开比特币地址和私匙的面纱。 还不知道什么是比特币地址和私匙的同学请点这里 问题一、比特币钱包由什么组成? 答 我们知道,比特币地址和私匙组成了比特币钱包,而私匙则决定了比特币地址上比特币的归属。 地址和私匙 问题二、如果只记得私匙我们还能还原比特币地址么? 答

    用GO语言实现比特币算法

    用GO语言实现比特币算法

    本节的这个例子展示一点点高精度数学包math/big、一点点散列包hash、一点点加密包crypto,还有一点点测试包testing的知识。这里不介绍bitcoin协议和算法——尽管它们很有趣,而是试图指出,Go对多种操作系统的支持,是实现这种跨平台应用的理想语言。 位钱(bitcoin)是一种使用加密手段制作的分布式电子货币。它最初于1998年由Wei Dai提出,并由中本聪(Satoshi

    详解比特币的找零机制

    详解比特币的找零机制

    比特币的找零机制一直让人有些迷惑,明明只向一个地址发送了比特币为什么 blockchain 上面的显示的有时是1个地址对多个地址,有时是多个地址对1个地址,有时又显示多个地址对多个地址? 为什么比特币资深用户要提醒大家当比特币钱包交易100次以上时再次交易后要重新备份钱包,恢复以前的钱包备份有可能会遭遇损失? 是的,这一切都是因为比特币的找零(Change)机制。本文参考 Bitcoin的维

    玩转比特币客户端之一:C盘转移和加速下载

    玩转比特币客户端之一:C盘转移和加速下载

    C盘空间不足?交易数据下载速度太慢?别着急,乐享比特币教你轻松玩转比特币官方客户端。 所有新人开始接触比特币时做的第一件事情大多数是安装比特币的官方客户端。 安全起见大家最好直接访问官方发布渠道sourceforge的地址进行下载:http://sourceforge.net/projects/bitcoin/files/Bitcoin/ 该网页列出了各版本的官方比特币客户端,目前

    麦妖榜
    更新日期 2019-01-17
    排名用户贡献值
    1等待的宿命23695
    2BitettFan23632
    3六叶树20309
    4天下无双16192
    5lizhen00214782
    6区块大康14502
    7让时间淡忘14188
    8冷风大q11188
    9momo11174
    10linjm122710573
    返回顶部 ↑