question regarding public/private key pairs

[michaschimmel]

Hi everyone,

I am a first timer here at these forums, and since I am writing my thesis about Bitcoin I was wondering if anyone could clarify something for me.

I know that for every Bitcoin address a unique public/private key pair is generated, in order to be able to send and receive Bitcointransactions. My question is: by whom and how are these keys generated? I know that there are certificate authorities that provide this service for websites, and if these CA's comply with the right regulations, then a digital signature created by the provided key pair is (legally) valid and binding. Now I can't imagine that the Bitcoin protocol relies on these CA's, but I couldn't find anything about this in the Bitcoin wiki pages.

Thanks in advance to whoever can answer my question

[CIYAM]

A public/private key pair is simply created by the appropriate maths and can very easily be verified also by maths - the purpose of CA"s has nothing to do with these low-level operations but instead is for the purpose of issuing and signing a certificate that states who the certificate belongs to and who issued it.

As Bitcoin is decentralised there is simply no need to have such authorities - when it comes to making a payment it's up to you to decide if you trust sending money to the address you are going to send it to.

BTW - welcome to the forum!

[deeplink]

A public/private key pair is simply created by the appropriate maths and can very easily be verified also by maths - the purpose of CA"s has nothing to do with these low-level operations but instead is for the purpose of issuing and signing a certificate that states who the certificate belongs to and who issued it.

I've been wanting to ask the following about key pair generation.

Key pairs are created at random and anyone can create as many as he wants. Would it theoretically be possible that someone happened to create an existing key pair that gives access to someone else's balance? Even if the probability is extremely low, wouldn't is be a matter of time for this to happen eventually?

[michaschimmel]

Thanks for your quick reply and the answer to my question! I thought this might be the case, but wasn't entirely sure.

[malevolent]

Even if the probability is extremely low, wouldn't is be a matter of time for this to happen eventually?

Yeah, but (with current technology) it is not matter of years but millenia.
(or more, lol)

[CIYAM]

Key pairs are created at random and anyone can create as many as he wants. Would it theoretically be possible that someone happened to create an existing key pair that gives access to someone else's balance? Even if the probability is extremely low, wouldn't is be a matter of time for this to happen eventually?

The amount of time before finding a "birthday" is perhaps a little more than you might think (try as much time as the universe is old or thereabouts).

To get an idea run vanitygen with a very long prefix and check it's estimate:

Code:

C:\Program Files\Bitcoin>vanitygen 11111111111
Difficulty: 1208925819614629174706176
[180.70 Kkey/s][total 323584][Prob 0.0%][50% in 1.470452e+011y]

Now lets try adding some more 1's to this:

Code:

C:\Program Files\Bitcoin>vanitygen 111111111111111
Difficulty: 5192296858534827628530500624187392
[186.16 Kkey/s][total 387328][Prob 0.0%][50% in 6.130577e+020y]

[DeathAndTaxes]

I've been wanting to ask the following about key pair generation.

Key pairs are created at random and anyone can create as many as he wants. Would it theoretically be possible that someone happened to create an existing key pair that gives access to someone else's balance? Even if the probability is extremely low, wouldn't is be a matter of time for this to happen eventually?

While there are no certainties in probability the odds are so incredibly small it is ~0% (~ indicating roughly zero).

If you built a perfect supercomputer (as in the thermodynamic limit - physically impossible to be more efficient) and used all the matter in our solar system to construct it and powered it by a dysons sphere which at perfect efficiency capture all the energy of our star ....

you couldn't even count to 2^256 before our star burned out.  Keep in mind that is counting ( 1, 2, 3, ... 2^256) not performing ECDSA computations, hashing to get the address and looking up the balance.  

Another way to look at it ....

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

http://www.schneier.com/blog/archives/2009/09/the_doghouse_cr.html

That's Bruce Schneier (inventor of the Blowfish encryption algorithm and an expert on cryptography & security in general, also a favorite author of mine.   Applied Cryptography although a little dated should be REQUIRED reading for anyone looking to build secure systems).

".... until computers are built from something other than matter and occupy something other than space ..."

Yeah I think we are safe.

[deeplink]

Key pairs are created at random and anyone can create as many as he wants. Would it theoretically be possible that someone happened to create an existing key pair that gives access to someone else's balance? Even if the probability is extremely low, wouldn't is be a matter of time for this to happen eventually?

The amount of time before finding a "birthday" is perhaps a little more than you might think (try as much time as the universe is old or thereabouts).

To get an idea run vanitygen with a very long prefix and check it's estimate:

Code:

C:\Program Files\Bitcoin>vanitygen 11111111111
Difficulty: 1208925819614629174706176
[180.70 Kkey/s][total 323584][Prob 0.0%][50% in 1.470452e+011y]

Now lets try adding some more 1's to this:

Code:

C:\Program Files\Bitcoin>vanitygen 111111111111111
Difficulty: 5192296858534827628530500624187392
[186.16 Kkey/s][total 387328][Prob 0.0%][50% in 6.130577e+020y]

Yes I see those are huge numbers. But luck is an important factor too. In theory you could hit the jackpot after one try.

Also, there are multiple "birthdays". If 100M people are using Bitcoin, each having 100 random key pairs (which I believe is the internal default of the official client) there are a lot of possible collisions.

So, even tough it is hyper-extremely unlikely to happen (I would like to do the math one day) is my understanding correct that it could happen? Or am I missing something?

[deeplink]

DeathAndTaxes, thanks for the clarification and links, I didn't see it in time.

[DeathAndTaxes]

Yes I see those are huge numbers. But luck is an important factor too. In theory you could hit the jackpot after one try.
...
So, even tough it is hyper-extremely unlikely to happen (I would like to do the math one day) is my understanding correct that it could happen? Or am I missing something?

Yes there are never certainties in probability.  You could try a single private key and it just happen to be the one which controls the largest Bitcoin address.  In cryptography we would say it is "infeasible" but it "could" happen.

Similarly I could also use single CPU and out hash the entire Bitcoin network to produce a longer blockchain and execute a double spend attack.   It could happen, it is "infeasible" but it could happen.  I could try 6 hashes and find 6 blocks in a row and reverse tx 6 blocks old with <$100 in computing power.  Still even as unlikely as that is, a collision between two random 256 bit numbers is quadrillions of times less likely.

Many people have difficulty realizing how large 2^256 is.  The "small" 256 is deceptive.  Even very smart people have trouble with very large or very small numbers.

Some items to put it into context.

The age of the universe is only ~2^59 seconds.
All information on planet earth (all forms) is on the order of 300 Exabytes or ~2^69 bytes.
The known universe is roughly 46 billion light years across that is about ~2^80 miles.
The planet earth consists of only ~2^167 atoms.

[deeplink]

Many people have difficulty realizing how large 2^256 is.  The "small" 256 is deceptive.  Even very smart people have trouble with very large or very small numbers.

That reassures me.

Still, some are trying really hard to prove you wrong:
https://bitcointalk.org/index.php?topic=94675.msg1140512#msg1140512

 

[DeathAndTaxes]

Cross posting for hilarity.

Raize summed it up in one photo.

[Kazimir]

My question is: by whom and how are these keys generated?

With Bitcoin, the role of certificating authorities is replaced by mathematical laws. Much more trustworthy and independent

[Kazimir]

So, even tough it is hyper-extremely unlikely to happen (I would like to do the math one day) is my understanding correct that it could happen? Or am I missing something?

Hyper-extremely unlikely is still greatly overestimated.

With all the computing power on our planet, it would take trillions and trillions times longer than the current age of the universe, to find a hit.

The probability of this happening by accident any time soon (i.e. within the foreseeable future) is far less than our entire solar system being destroyed by the sudden appearance of a super massive black hole. In other words: don't worry about it