infinite number of private keys / finite number of public keys

[C. Bergmann]

Hi, me again with a stupid question about cryptography.

There are 2^160 possible public keys. This is quiet a lot, but it is not infinite.

But every combination of signs works as a private key, right? I can type
"tt" or I can type
"öööööööööööööööööööösööööööööööööööööööööööööööörtrrrrööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööössssssssssssssssssssssssssssssssssssssssssskjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj"
And it's a private key.
I can use every word humankind made, every sentence which exists and even every block in every book and every page and so on.
Seems infinite to me.

Isn't the logical solution that every public key must correspond to an infinite number ob private keys?

[DannyHamilton]

Hi, me again with a stupid question about cryptography.

There are 2^160 possible public keys. This is quiet a lot, but it is not infinite.

No. There are 2²⁵⁶ possible public keys.
Public keys are a number between 0 and 2²⁵⁶.

There are 2¹⁶⁰ possible bitcoin addresses.  This is because a bitcoin address is a 160 bit hash of a public key.
Bitcoin Addresses are a number between 0 and 2¹⁶⁰ (along with a version byte and 4 checksum bytes).

But every combination of signs works as a private key, right? I can type
"tt" or I can type
"öööööööööööööööööööösööööööööööööööööööööööööööörtrrrrööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööössssssssssssssssssssssssssssssssssssssssssskjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj"
And it's a private key.
I can use every word humankind made, every sentence which exists and even every block in every book and every page and so on.
Seems infinite to me.

No.

Valid private keys are 256-bit (2²⁵⁶) numbers between 0x1 and 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141

Isn't the logical solution that every public key must correspond to an infinite number ob private keys?

Since there are nearly 2²⁵⁶ private keys, and only 2¹⁶⁰ Bitcoin Addresses, each Bitcoin address has an average of approximately 2⁹⁶ private keys.  I'm not sure if it has been proven yet that both SHA256 and RIPEMD160 are evenly distributed across the result set.  If they aren't then some addresses may have additional private keys, while others have a few less.

[sealberrder]

Valid private keys are 256-bit (2²⁵⁶) numbers between 0x1 and 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141

Any reason private keys are not just numbers between 0 and 2²⁵⁶-1 ?

[DannyHamilton]

Any reason private keys are not just numbers between 0 and 2²⁵⁶-1 ?

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

The range of valid private keys is governed by the secp256k1 ECDSA standard used by Bitcoin.

https://en.bitcoin.it/wiki/Secp256k1

As excerpted from Standards:

The elliptic curve domain parameters over Fp associated with a Koblitz curve secp256k1 are specified by the sextuple T = (p,a,b,G,n,h) where the finite field Fp is defined by:

    p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
    = 2256 - 232 - 29 - 28 - 27 - 26 - 24 - 1

The curve E: y2 = x3+ax+b over Fp is defined by:

    a = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
    b = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007

The base point G in compressed form is:

    G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

and in uncompressed form is:

    G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Finally the order n of G and the cofactor are:

    n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
    h = 01

[C. Bergmann]

Hi, me again with a stupid question about cryptography.

There are 2^160 possible public keys. This is quiet a lot, but it is not infinite.

No. There are 2²⁵⁶ possible public keys.
Public keys are a number between 0 and 2²⁵⁶.

There are 2¹⁶⁰ possible bitcoin addresses.  This is because a bitcoin address is a 160 bit hash of a public key.
Bitcoin Addresses are a number between 0 and 2¹⁶⁰ (along with a version byte and 4 checksum bytes).

But every combination of signs works as a private key, right? I can type
"tt" or I can type
"öööööööööööööööööööösööööööööööööööööööööööööööörtrrrrööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööööössssssssssssssssssssssssssssssssssssssssssskjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj"
And it's a private key.
I can use every word humankind made, every sentence which exists and even every block in every book and every page and so on.
Seems infinite to me.

No.

Valid private keys are 256-bit (2²⁵⁶) numbers between 0x1 and 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141

Isn't the logical solution that every public key must correspond to an infinite number ob private keys?

Since there are nearly 2²⁵⁶ private keys, and only 2¹⁶⁰ Bitcoin Addresses, each Bitcoin address has an average of approximately 2⁹⁶ private keys.  I'm not sure if it has been proven yet that both SHA256 and RIPEMD160 are evenly distributed across the result set.  If they aren't then some addresses may have additional private keys, while others have a few less.

Ok, thank you, I'm still a bit confused.
When I make a brainwallet on brainwallet.org I can type every passphrase I want, no matter how long it is (I tried it with one of my texts, ~6,000 signs). Ok, this is not a private key, but am I right that there is an infinite number of passphrases like this which fit to every address?

So every adress contains 2^96 public keys and also 2^96 private keys?

Doesn't this reduce the difficulty to bruteforce an adress?

[silvestar]

For brainwallet, it just uses sha256(your passphrases) as the private key.

So every adress contains 2^96 public keys and also 2^96 private keys?

IIRC, we don't have a collision found yet for sha256 or RIPEMD160, so we don't know how it is distributed.

PS. Danny, please correct me if I am wrong. 

[grue]

Ok, thank you, I'm still a bit confused.
When I make a brainwallet on brainwallet.org I can type every passphrase I want, no matter how long it is (I tried it with one of my texts, ~6,000 signs). Ok, this is not a private key, but am I right that there is an infinite number of passphrases like this which fit to every address?

yes

So every adress contains 2^96 public keys and also 2^96 private keys?

Doesn't this reduce the difficulty to bruteforce an adress?

2^160 is such an insanely big number that it's not an issue.

[DannyHamilton]

Ok, thank you, I'm still a bit confused.
When I make a brainwallet on brainwallet.org I can type every passphrase I want, no matter how long it is (I tried it with one of my texts, ~6,000 signs).

Correct.  Brainwallets are a very bad idea.  Any brainwallet that you can think of, can be thought of by someone else.  This will result in you losing your bitcoins.

Ok, this is not a private key, but am I right that there is an infinite number of passphrases like this which fit to every address?

Sure.  There are an infinite number of phrases that will hash (with SHA-256) to each private key.  Therefore, there are an infinite number of phrases for each address.

So every address contains 2^96 public keys and also 2^96 private keys?

On average.

Some addresses may have additional private keys, some may have less.  As far as I'm aware, it has not yet been proven whether or not the results of RIPEMD-160 and SHA-256 are evenly distributed.

Doesn't this reduce the difficulty to bruteforce an adress?

Yes.  It reduces the address space from 2²⁵⁶ to 2¹⁶⁰.

In other words, it reduces it from a really, really, really big number, to a really, really, really big number that isn't quite as big.

[Rulishix]

This is very informative and educational! Didn't realize how these things work.

[C. Bergmann]

this is a bit silly ...

But isn't it one of the biggest dangers for bitcoin that an army of aliens did bruteforce every private key one million years ago and gets in contact with the blockchain via garzeks satellite?

It seems this is more plausible than some human bruteforcing it ...

I love this

[cp1]

So every adress contains 2^96 public keys and also 2^96 private keys?

Doesn't this reduce the difficulty to bruteforce an adress?

That's like saying if I tell you that a molecule of water is located in the pacific ocean, that reduces the difficulty of finding it.

[shorena]

So every adress contains 2^96 public keys and also 2^96 private keys?

Doesn't this reduce the difficulty to bruteforce an adress?

That's like saying if I tell you that a molecule of water is located in the pacific ocean, that reduces the difficulty of finding it.

Pacific ocean vs. 2^96... lets see

https://en.wikipedia.org/wiki/Pacific_Ocean#Water_characteristics

"The volume of the Pacific Ocean, representing about 50.1 percent of the world's oceanic water, has been estimated at some 714 million cubic kilometers."

714.000.000 km^3 water vs. 79.228.162.514.264.337.593.543.950.336 (since my OS is in german think of . as , and of , as .)

With ~3*10^25 water particles in 1 liter and 1 liter = 0,001 m^3

We have 714* 10^6 * 10^12 (km^3 to liter) * 3*10^25 = 714*3 * 10^(6+12+25) = 2.142 * 10^43 water molecules. While 2^96 = approx. 7,9 * 10^28.

Hmm if we take 1 liter... that would be 7,14 * 10^20.... so 1/10^8 th of a liter, thats 1/10^2 µl or 0,01 mm^3 thats a fraction of a drop of water (~ 1/20 ml). Still hard to find

PS: If some of the calculations are wrong, sorry. I checked everything twice, but due to the nature of large numbers and switching units there might be slips of the keyboard

[C. Bergmann]

So every adress contains 2^96 public keys and also 2^96 private keys?

Doesn't this reduce the difficulty to bruteforce an adress?

That's like saying if I tell you that a molecule of water is located in the pacific ocean, that reduces the difficulty of finding it.

Pacific ocean vs. 2^96... lets see

https://en.wikipedia.org/wiki/Pacific_Ocean#Water_characteristics

"The volume of the Pacific Ocean, representing about 50.1 percent of the world's oceanic water, has been estimated at some 714 million cubic kilometers."

714.000.000 km^3 water vs. 79.228.162.514.264.337.593.543.950.336 (since my OS is in german think of . as , and of , as .)

With ~3*10^25 water particles in 1 liter and 1 liter = 0,001 m^3

We have 714* 10^6 * 10^12 (km^3 to liter) * 3*10^25 = 714*3 * 10^(6+12+25) = 2.142 * 10^43 water molecules. While 2^96 = approx. 7,9 * 10^28.

Hmm if we take 1 liter... that would be 7,14 * 10^20.... so 1/10^8 th of a liter, thats 1/10^2 µl or 0,01 mm^3 thats a fraction of a drop of water (~ 1/20 ml). Still hard to find

PS: If some of the calculations are wrong, sorry. I checked everything twice, but due to the nature of large numbers and switching units there might be slips of the keyboard

Thank you for your calculations.

Do I understand correctly: it's as hard to find a private key as to find 0.01mm^3 of water in the world's ocean?

This would be the most precise comparison I've ever read

[shorena]

So every adress contains 2^96 public keys and also 2^96 private keys?

Doesn't this reduce the difficulty to bruteforce an adress?

That's like saying if I tell you that a molecule of water is located in the pacific ocean, that reduces the difficulty of finding it.

Pacific ocean vs. 2^96... lets see

https://en.wikipedia.org/wiki/Pacific_Ocean#Water_characteristics

"The volume of the Pacific Ocean, representing about 50.1 percent of the world's oceanic water, has been estimated at some 714 million cubic kilometers."

714.000.000 km^3 water vs. 79.228.162.514.264.337.593.543.950.336 (since my OS is in german think of . as , and of , as .)

With ~3*10^25 water particles in 1 liter and 1 liter = 0,001 m^3

We have 714* 10^6 * 10^12 (km^3 to liter) * 3*10^25 = 714*3 * 10^(6+12+25) = 2.142 * 10^43 water molecules. While 2^96 = approx. 7,9 * 10^28.

Hmm if we take 1 liter... that would be 7,14 * 10^20.... so 1/10^8 th of a liter, thats 1/10^2 µl or 0,01 mm^3 thats a fraction of a drop of water (~ 1/20 ml). Still hard to find

PS: If some of the calculations are wrong, sorry. I checked everything twice, but due to the nature of large numbers and switching units there might be slips of the keyboard

Thank you for your calculations.

Do I understand correctly: it's as hard to find a private key as to find 0.01mm^3 of water in the world's ocean?

This would be the most precise comparison I've ever read

If the calculations and the data I researched are correct: its as hard to find a private key to a given address as its hard to find 0,01mm^3 of water in the pacific (!) ocean. Since its the biggest ocean I dont think throwing in the other 2 makes a big difference.
Lets see

Atlantic: "354,700,000 cubic kilometers" https://en.wikipedia.org/wiki/Atlantic_Ocean
indian:  "292,131,000 km³" https://en.wikipedia.org/wiki/Indian_Ocean
pacific: 714.000.000 km^3

Sooo: 714 + 292 + 355 (rounded to 100 million km^3) hmm 1,361 10^9 km^3... ~ 0,019mm^3, actually doubles it.

But I think the biggest problem with this comparission is that while you "know" how big the oceans are you dont know how small ~0,02mm^3 is. Well maybe someone else can find an everyday object that is ~0,02mm^3

[zetaray]

There are 2^96 private keys to my address and I only hold 1 of them? However unlikely that someone else might find another one of them, this is a worrying thought.

Thanks for the post, very informative.

[DannyHamilton]

However unlikely that someone else might find another one of them, this is a worrying thought.

No, it really isn't.

There are things that are far more dangerous, that are also far more likely to happen, and yet you worry about none of them.

[DannyHamilton]

If the calculations and the data I researched are correct: its as hard to find a private key to a given address as its hard to find 0,01mm^3 of water in the pacific (!) ocean.

This is not correct.

There are 2⁹⁶ = 7.9*10²⁸ private keys for each address, but you don't know any of them.

If you had the list of those 7.9*10²⁸ private keys, it would be as difficult to find the particular private key that someone was using as it would be to find find 0,01mm^3 of water in the pacific ocean.  However, if you had the list of those private keys, then you wouldn't need to find the particular private key that someone was using, because any and all of the keys that you have in that list would work just fine to sign the transaction.

The problem you'll run into it that there are nearly 2²⁵⁶ possible private keys, and only 2⁹⁶ of them are useful if you are trying to find a private key to sign transactions that spend someone else's bitcoins.  As such, the ratio you are working with is 2⁹⁶ / 2²⁵⁶ which you'll find is one out of every 2¹⁶⁰ private keys that you check (which makes sense, since there are 2¹⁶⁰ possible addresses and you're looking for a private key to exactly one of them).

2¹⁶⁰ is approximately 1.5 * 10⁴⁸

As you pointed out:

We have 714* 10^6 * 10^12 (km^3 to liter) * 3*10^25 = 714*3 * 10^(6+12+25) = 2.142 * 10^43 water molecules.

As such, it IS easier to find a single molecule of water in the entire Pacific Ocean than it is to find someone's private key.

Try the math again, and I suspect you'll find that it is easier to find a single molecule of water on the entire earth (including buried deep underground, in the ice caps, or vapor in the atmosphere).

After that, try this math:

How many total molecules (water or otherwise) exist on the earth?

[shorena]

-snip-
2¹⁶⁰ is approximately 1.5 * 10⁴⁸
-snip-

Ah yes, 1 in 2¹⁶⁰ needs to be compared.

Well since we allready have 2.142 * 10⁴³ water molecules in the pacific and ~ double that (approx 4.28 * 10⁴³) in all oceans, we just need 10 ⁵ times of all of earths oceans

But thats not a nice comparisson. How about "Earth's volume is approximately 1,083,210,000,000 km³" https://en.wikipedia.org/wiki/Volume_of_the_Earth

Thats approx. 1,083 * 10¹² km³, lets just see how low we need to go with the unit till we hit 10⁴⁸

1,083 * 10¹²km³ = 1,083 * 10¹²*10¹⁸ mm³ ... hmm 10¹⁸ more to go the particles/molecules might fit, but lets take something else.

According to this site http://htwins.net/scale2/

the known universe is approx 10²⁷ m (diameter) so we just need to find something has an diameter of ~ 10^-21 m...

While zooming in @ 10^-16,3 i noticed "length shorter than this are not confirmed", well lets keep going...

10^-21 has nothing, but @ 10^-22 there is a Top Quark. So lets just take 10 of those


So getting the correct private key to a given public address is like hitting a specific wall of 10*10 top quarks from the edge of the observable universe.

This assumes that the observeable universe is flat, which makes it easier to imagine.

-snip-
this is a worrying thought.
-snip-

Is it still? If your answer is yes, please visit the page I linked above and play with it a bit. I allready though 2¹⁶⁰ is big, but this...

Edit: After thinking about this for a while, I think I made a big mistake. The problem is that the Information given is a diameter which has 1 dimension. So instead of thinking about the observeable universe as a big disc youd have to think about it as a line, which I dont like tbh. I will edit this again later with a better 3d comparission (as the fraction of a drop of water in the ocean was).


Edit2:

Lets do this proper now

We need to find something with approx 1.5 * 10⁴⁸m³ in order for 1m³ to be equivalent to 1 in 2¹⁶⁰

http://htwins.net/scale2/
Gives us diameters of pretty much anything. E.g. the observeable universe (OU) has a diameter of approx 9.3 * 10²⁸m. This gives the OU a Volume of:

V_OU = 1/6 * pi * (9.3 * 10²⁸)³ ~ 4.2*10⁸⁶

Thats way bigger than we need. So in order to find something with a volume of approx 1.5 * 10⁴⁸ we can take the same formula but this time we let the diameter be unknown. Since this forum is not supporting latex commands Ill spare you the details.

1.5 * 10⁴⁸ = 1/6 * pi * d³ is equiv. to d = 1.4 * 10¹⁶

which gives us the "Rotten Egg Nebula", "Raw Egg Nebula" or "Calabash Nebula" https://en.wikipedia.org/wiki/Calabash_Nebula

In this nebular I have hidden a ball with diameter ~ 1.24 meter and you have to find it.

Im not sure I like this comparisson better, but at least the numbers add up.


Last Edit (promise):

Earth has a diameter of 1.27 * 10⁷m which gives it a volume of 1.07 * 10²¹m³
So in order for the comparisson to hold up we need something with a volume of 7.13*10^-28m³ or a diameter of approx 1.11 * 10^-9m.
According to http://htwins.net/scale2/ a single water molecule has a diameter of 2.8*10^-10m, thats close but a little to small. But a buckyball* has a diamter of 1*10^-9m. The water molecule might be a better comparisson though.

Thats the last one. I like it. 1 in 2¹⁶⁰ is like finding a single buckyball in the whole earth.

* https://en.wikipedia.org/wiki/Buckminsterfullerene

[Abdussamad]

There are 2^96 private keys to my address and I only hold 1 of them? However unlikely that someone else might find another one of them, this is a worrying thought.

It's OK. I have the others and I'll keep them safe for you