The size of the private and public key sets, and collisions

Berghoff

newbie

Activity: 28

Merit: 0

Quote from: Lieji on June 16, 2014, 02:37:40 AM

Quote from: Berghoff on June 10, 2014, 07:32:19 PM

Quote from: odolvlobo on June 10, 2014, 05:49:25 PM

There are 2²⁵⁶ public/private key pairs.

Isn't the maximum value of private keys based on the p of secp256k1, which is 2²⁵⁶ - 2³² - 2⁹ - 2⁸ - 2⁷ - 2⁶ - 2⁴ - 1 ? It's close to 2²⁵⁶, but not exact. Not to be pedantic, just want to make sure my understanding is correct.

Yes, you are correct.

https://en.bitcoin.it/wiki/Private_key#Range_of_valid_private_keys

Quote

Range of valid private keys
Nearly every 256-bit number is a valid private key. Specifically, any 256-bit number between 0x1 and 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141 is a valid private key.
The range of valid private keys is governed by the secp256k1 ECDSA standard used by Bitcoin.

Thank you. Wasn't trying to be that guy, but just wanted to make sure I understood correctly.

Lieji

hero member

Activity: 543

Merit: 500

Quote from: Berghoff on June 10, 2014, 07:32:19 PM

Quote from: odolvlobo on June 10, 2014, 05:49:25 PM

There are 2²⁵⁶ public/private key pairs.

Isn't the maximum value of private keys based on the p of secp256k1, which is 2²⁵⁶ - 2³² - 2⁹ - 2⁸ - 2⁷ - 2⁶ - 2⁴ - 1 ? It's close to 2²⁵⁶, but not exact. Not to be pedantic, just want to make sure my understanding is correct.

Yes, you are correct.

https://en.bitcoin.it/wiki/Private_key#Range_of_valid_private_keys

Quote

Range of valid private keys
Nearly every 256-bit number is a valid private key. Specifically, any 256-bit number between 0x1 and 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141 is a valid private key.
The range of valid private keys is governed by the secp256k1 ECDSA standard used by Bitcoin.

Bernard Lerring

sr. member

Activity: 294

Merit: 250

I asked a very similar question last month. This should help satisfy your reservations:

https://bitcointalksearch.org/topic/m.6796461

I like to simplify it by thinking of the "needle in a haystack" scenario, whereby every time you remove a strand of hay it goes back on top of the pile. Combine that with natural human error (non-perfect vision, memory etc.) and you've got as much chance of finding someone’s private key as looking for a needle in a haystack.

Unless someone develops a super computer that is beyond our comprehension and/or uses a completely different system to any doped silicon transistor model we have today your private keys are safe if you follow safe procedures.

DannyHamilton

legendary

Activity: 3472

Merit: 4801

Someone that doesn't understand math, probably shouldn't be explaining math to others.

You should also consider using something more universal than "Powerball", since there are many states, and many countries that don't participate in the Powerball Lottery, and so they can't relate to your example. Regardless, lets take a look at the actual math:

2¹⁶⁰ = 1.46 X 10⁴⁸

Odds of winning the Powerball lottery are 1 in 1.75 X 10⁸

Odds of winning the Powerball lottery 3 times in a row are:

(1.75 X 10⁸)³ = 5.38 X 10²⁴

Sorry, but 5.38 X 10²⁴ is MUCH less than 1.46 X 10⁴⁸

Lets try again...

Odds of winning the Powerball lottery 5 times in a row are:
(1.75 X 10⁸)⁵ =1.65 X 10⁴¹

Odds of winning the Powerball lottery 6 times in a row are:
(1.75 X 10⁸)⁶ =2.89 X 10⁴⁹

So, it looks like the the chances of a collision with a particular address are about as good as you winning the powerball jackpot more than 5 times in a row.

ShakyhandsBTCer

sr. member

Activity: 448

Merit: 250

It's Money 2.0| It’s gold for nerds | It's Bitcoin

Quote from: Berghoff on June 10, 2014, 07:32:19 PM

Quote from: odolvlobo on June 10, 2014, 05:49:25 PM

There are 2²⁵⁶ public/private key pairs.

Isn't the maximum value of private keys based on the p of secp256k1, which is 2²⁵⁶ - 2³² - 2⁹ - 2⁸ - 2⁷ - 2⁶ - 2⁴ - 1 ? It's close to 2²⁵⁶, but not exact. Not to be pedantic, just want to make sure my understanding is correct.

For the people who do not understand math, the chances of a collision are about as good as you win the powerball jackpot three times in a row by selecting "autopick" in the same transaction

Berghoff

newbie

Activity: 28

Merit: 0

Quote from: odolvlobo on June 10, 2014, 05:49:25 PM

There are 2²⁵⁶ public/private key pairs.

Isn't the maximum value of private keys based on the p of secp256k1, which is 2²⁵⁶ - 2³² - 2⁹ - 2⁸ - 2⁷ - 2⁶ - 2⁴ - 1 ? It's close to 2²⁵⁶, but not exact. Not to be pedantic, just want to make sure my understanding is correct.

odolvlobo

legendary

Activity: 4466

Merit: 3391

There are 2²⁵⁶ public/private key pairs. There are 2¹⁶⁰ bitcoin addresses. So, for each bitcoin address, there are 2⁹⁶ public/private key pairs that produce it.

To find the private key for a particular bitcoin address, you may still have to search up to 2²⁵⁶-2⁹⁶+1 private keys because you don't know which ones give duplicate addresses. However, assuming everything is randomly distributed, the probability of any private key generating a particular address is still 1/2¹⁶⁰.

I make the distinction, because it is possible that you could try all private keys from 1 to 2¹⁶⁰ and still not find a match. It is possible for all of the 2⁹⁶ keys for that address to lie somewhere in the range from 2¹⁶⁰ to 2²⁵⁶-1.

#1 is not necessarily correct.
#2 is correct.

Also, remember that 2²⁵⁶ >> 2¹⁶⁰ >> 2⁹⁶

Berghoff

newbie

Activity: 28

Merit: 0

So a private key is any number from 1 to 115,792,089,237,316,195,423,570,985,008,687,907,852,837,564,279,074,904,382,605,163,141,518,161,494,336.... or a little under 2^256. Using the ECDSA, a public key is created that is anywhere from 1 to 2^160. And, if I remember what I read elsewhere correctly. For any of those public keys, there should be about 2^96 corresponding private keys.

Therefore....

1) If I have a bitcoin address of "1EQG7J2q4VfAgMBhetEj3cd3PNGYmBLHh" and I wanted to brute force finding a private key that corresponds to that, I could theoretically start with the number 1 as the private key, and increment by one each time, and on each iteration compute the public key (plus derive the address) and validate if the two match. I would need to do this about 2^160 times until I found a match.

2) If I did find a match, even if the new private key did not match the original private key used to create address, I could create a transaction to transfer bitcoin to another address.

Are those two statements correct.

I just need to find one of the 2^96 numbers of the 2^256 that hash into 1P1ou9XxdpdM35JdWYRE7CHRa6E6mU7ziV, and I'm living on easy street!

Topic: The size of the private and public key sets, and collisions (Read 1164 times)