up vote 8 down vote favorite
share [g+] share [fb]

I am doing a presentation on Bitcoins and I was looking for some calculations to make people feel safe about the private key encryption. Please first answer, how long in bytes the private key is, then how many combinations of numbers it will contain, and then what is the fastest computer or network of supercomputers and how long it would take to crack a private key using that computer. I think the result would be very educational based on my own calculations. Thank you.

link|improve this question
38% accept rate
feedback

3 Answers

up vote 8 down vote

"how long in bytes the private key is"

32 bytes, or 256 bits

"then how many combinations of numbers it will contain"

There are 2^256 different private keys. That's a little larger than a 1 followed by 77 zeroes.

"what is the fastest computer or network of supercomputers"

At its peak around August 2011, the Bitcoin network was checking 15 trillion sha256 hashes per second. (See http://bitcoin.sipa.be/)

"how long it would take to crack a private key using that computer"

If we assume it takes the same time to run an ECDSA operation as it takes to check an sha256 hash (it takes much longer), and we use an optimisation that allows us to only need 2^128 ECDSA operations, then the time needed can be calculated:

>>> pow(2,128) / (15 * pow(2,40)) / 3600 / 24 / 365.25 / 1e9 / 1e9
0.6537992112229596

It's 0.65 billion billion years.

That's an very conservative estimate for the time taken to break one single Bitcoin address.

Edit: it was pointed out that computers tend to get exponentially faster over time, according to Moore's Law. Assuming computing speed doubles every year (Moore's law says 2 years, but we'll err on the side of caution), then in 59 years it'll only take 1.13 years. So your coins are safe for the next 60 years without a change to the algorithms used to protect the blockchain. However, I would expect the algorithms to be changed long before it's feasible to break the protection they provide.

link|improve this answer
2  
Moore's Law (or similar) would probably bring that number down a bit, but not enough to matter. As long as the answer is some form of "longer than it would take to mine the coins stored at that address" we should be safe :) – David Perry♦ Feb 5 at 0:00
1  
It matters, because people deserve to know how secure their money is. – shoeless joe Feb 7 at 21:51
feedback
up vote 2 down vote

A Bitcoin private key is a random 256-bit number. However, the public key reveals some information about the private key. The best known algorithms for breaking ECDSA require O(sqrt(n)) operations. That means 2^128 operations would be needed to break a Bitcoin account.

The largest ECDSA key broken to date of the type that Bitcoin uses was 112 bits long. A Bitcoin account is more than 4,000 billion billion times harder to break.

The only realistic risk would be quantum computing.

link|improve this answer
It should also be noted that even quantum computing is only expected to reduce the time from pow(2,N) to pow(2,N/2) which although significant is not cracking it wide open. See en.wikipedia.org/wiki/Key_size – Gary Rowe Feb 10 at 9:12
@GaryRowe You're wrong. The halving of key length applies to symmetric keys. Most asymmetric ciphers(including ECDSA which is used for bitcoint) can be broken in polynomial time with a quantum computer thanks to Shor's algorithm. To quote that wikipedia article "The general consensus is that these public key algorithms are insecure at any key size if sufficiently large quantum computers capable of running Shor's algorithm become available.". While there are quantum proof signature schemes, they'd probably bloat the blockchain a lot. – CodeInChaos Feb 25 at 14:14
@CodeInChaos Good points all - sorry to have introduced confusion. – Gary Rowe Feb 26 at 20:34
feedback
up vote -1 down vote

2^256 = 1.1x10^77 = number of key combinations

2^128 = 3.4x10^38 = the average number of guesses needed

According to this website: http://en.wikipedia.org/wiki/TOP500, the fastest supercomputer is the K computer which has 10.51 petaflops.

A petaflop is 10^15 FLOPS, floating point instructions per second.

So far so good, but I need to know how many FLOPS are needed per guess?

[I will venture a guess:]

Between 1,000 and 10,000 FLOPS (or integer equivalents) per guess.

10.51x10^15 ops/second / 1000 to 10000 ops/guess) = 10.51x10^12 to 10.51x10^11 guess/second.

3.4x10^38 guesses/crack / 10.51x10^12 guess/second = 3.2x10^25 seconds.

3.2x10^25 seconds / 60 seconds/minute / 60 minutes/hour / 24 hours/day / 365.25 days/year = 1.01x10^18 years

1.01x10^18 years / 1x10^9 / 1x10^9 = 1.014 to 10.014 billion billion years.

So the computers on the Bitcoin network are twice as fast as the single largest laboratory computer.

link|improve this answer
1  
There are exactly 0 FLOPs required to try a combination, as a FLOP is a floating-point operation, and EC math only requires integer operations. – Pieter Wuille Feb 7 at 23:21
There has never been a computer that I have worked on that couldn't do integer math. So I would assume that the South Korean K computer can do it also. – shoeless joe Feb 17 at 18:52
Yes, but the proportion between speed of integer and floating point operations differs significantly between hardware. Given a certain distribution of hardware types that constitute Bitcoin's mining power, you can give an estimate, but the answer to the question "how many FLOPS are needed per guess", the answer is certainly 0. – Pieter Wuille Feb 18 at 0:28
feedback

Your Answer

 
or
required, but never shown
discard

Not the answer you're looking for? Browse other questions tagged or ask your own question.