Bitcoin Forum
November 13, 2024, 12:13:57 AM *
News: Check out the artwork 1Dq created to commemorate this forum's 15th anniversary
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Maths Q1 - address to key ratio  (Read 370 times)
thirdprize (OP)
Sr. Member
****
Offline Offline

Activity: 485
Merit: 274


View Profile WWW
December 15, 2020, 09:32:21 AM
 #1

Addresses are 30+ characters long and keys are 50+ characters long.  That means there can be a lot more keys than addresses.  Does anyone now how many valid there are of each?  Does this mean each valid address can be serviced by more than one key?  If so, how many per address?

hosseinimr93
Legendary
*
Offline Offline

Activity: 2576
Merit: 5677



View Profile
December 15, 2020, 10:08:20 AM
Merited by vapourminer (1), ABCbits (1), BrewMaster (1)
 #2

There are 2256 valid private keys, 2256 valid public keys and 2160 valid addresses.
Therefore, every address can be generated by 296 private keys and 296 public keys on average.

▄▄███████▄▄
▄██████████████▄
▄██████████████████▄
▄████▀▀▀▀███▀▀▀▀█████▄
▄█████████████▄█▀████▄
███████████▄███████████
██████████▄█▀███████████
██████████▀████████████
▀█████▄█▀█████████████▀
▀████▄▄▄▄███▄▄▄▄████▀
▀██████████████████▀
▀███████████████▀
▀▀███████▀▀
.
 MΞTAWIN  THE FIRST WEB3 CASINO   
.
.. PLAY NOW ..
BrewMaster
Legendary
*
Offline Offline

Activity: 2128
Merit: 1293


There is trouble abrewing


View Profile
December 15, 2020, 10:17:09 AM
Merited by vapourminer (1)
 #3

There are 2256 valid private keys, 2256 valid public keys and 2160 valid addresses.

actually there are a little less than 2256 valid private keys which are from 1 to N(1) (equal amount of public keys).
there are also virtually unlimited number of addresses because an address is the equivalent of a customized script. for example you can create both P2PKH and P2WPKH addresses from a single private key. then you can also create custom P2SH scripts in which you set any kind of script using that same private key.

(1) in hex FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
in decimal 115792089237316195423570985008687907852837564279074904382605163141518161494337

There is a FOMO brewing...
ABCbits
Legendary
*
Offline Offline

Activity: 3052
Merit: 8079


Crypto Swap Exchange


View Profile
December 15, 2020, 11:15:03 AM
Last edit: December 15, 2020, 11:35:36 AM by ETFbitcoin
Merited by vapourminer (1), BrewMaster (1)
 #4

There are 2256 valid private keys, 2256 valid public keys and 2160 valid addresses.

actually there are a little less than 2256 valid private keys which are from 1 to N(1) (equal amount of public keys).
there are also virtually unlimited number of addresses because an address is the equivalent of a customized script. for example you can create both P2PKH and P2WPKH addresses from a single private key. then you can also create custom P2SH scripts in which you set any kind of script using that same private key.

(1) in hex FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
in decimal 115792089237316195423570985008687907852837564279074904382605163141518161494337

If we're going to such detail, don't forget there are multiple public key representation (compressed, uncompressed & hybrid) & multiple address format (P2PK, P2PKH, P2SH, P2WPKH, P2WSH) where both P2SH and P2WSH address depends on the script itself, which makes the answer to OP question more complicated.

█▀▀▀











█▄▄▄
▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄
█████████████
████████████▄███
██▐███████▄█████▀
█████████▄████▀
███▐████▄███▀
████▐██████▀
█████▀█████
███████████▄
████████████▄
██▄█████▀█████▄
▄█████████▀█████▀
███████████▀██▀
████▀█████████
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▀▀▀█











▄▄▄█
▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
▀██▀▀
thirdprize (OP)
Sr. Member
****
Offline Offline

Activity: 485
Merit: 274


View Profile WWW
December 15, 2020, 03:20:58 PM
 #5

There are 2256 valid private keys, 2256 valid public keys and 2160 valid addresses.
Therefore, every address can be generated by 296 private keys and 296 public keys on average.

Thanks.  So for any address there is going to be a very large number of keys with any particular character at any particular position.  That is what I wanted to know.

thirdprize (OP)
Sr. Member
****
Offline Offline

Activity: 485
Merit: 274


View Profile WWW
January 02, 2021, 11:44:52 AM
 #6

What if you could just narrow it down a bit.  Third character is in this range, fourth in this range, and so on.  Everyone quotes the unsolvable probabilities but what is a solvable probability given computing powers and botnets these days? 2x?  What is x?

BlackHatCoiner
Legendary
*
Offline Offline

Activity: 1694
Merit: 8336


Fiatheist


View Profile WWW
January 05, 2021, 07:36:56 AM
 #7

What if you could just narrow it down a bit.  Third character is in this range, fourth in this range, and so on.  Everyone quotes the unsolvable probabilities but what is a solvable probability given computing powers and botnets these days? 2x?  What is x?
Are you asking what are the possibilities of successfully finding the private key of an address by brute forcing? If so, as @hosseinimr93 said, 1 in 2256. You can try calculating with custom computational power and see what are the odds.

The problem is that you don't know which of those keys generate the same address. If you had a list of 296 numbers that generate completely different addresses, then yes it would be easier to brute force, but you don't.

Specifically, if you had that list and a machine that performs 100 trillion ECDSA and SHA256 hashes per second it would take you 79,228,162,514,264 seconds to get all possible addresses' combinations.

which is equal with 1,320,469,375,237 minutes, 22,007,822,920 hours, 916,992,621 days, 30,566,420 months, 2,547,201 years. And remember, you don't have that list of special numbers.

█▀▀▀











█▄▄▄
▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄
█████████████
████████████▄███
██▐███████▄█████▀
█████████▄████▀
███▐████▄███▀
████▐██████▀
█████▀█████
███████████▄
████████████▄
██▄█████▀█████▄
▄█████████▀█████▀
███████████▀██▀
████▀█████████
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▀▀▀█











▄▄▄█
▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
▀██▀▀
o_e_l_e_o
In memoriam
Legendary
*
Offline Offline

Activity: 2268
Merit: 18746


View Profile
January 05, 2021, 09:25:45 AM
Merited by BlackHatCoiner (1)
 #8

What if you could just narrow it down a bit.  Third character is in this range, fourth in this range, and so on.
Characters of the private key? Well then your number of overall possibilities for the correct private key would simply be "number of possibilities for second character" * "number of possibilities for third character" * "number of possibilities for fourth character" * "number of possibilities for fifth character" * ... * "number of possibilities for the last character".

Once you have that number then you need to work out how many times you can perform elliptic curve multiplication, SHA-256, RIPEMD-160, and then two more SHA-256s each second, to turn each private key in to an address. DaveF made some benchmarks for doing this a couple of years ago: https://bitcointalk.org/index.php?topic=5112311.msg50823897#msg50823897. With the top end GPUs on the market - GeForce RTX 2080 Super/Ti - you are looking at about 2 - 2.5 billion keys per second.

Are you asking what are the possibilities of successfully finding the private key of an address by brute forcing? If so, as @hosseinimr93 said, 1 in 2256.
It's actually 1 in 2160, on average, since there are 296 private keys per address, on average.

Specifically, if you had that list and a machine that performs 100 trillion ECDSA and SHA256 hashes per second
It is elliptic curve multiplication, not ECDSA, that is needed here, and there are more hashes required than just a single SHA-256 as I've outlined above.
thirdprize (OP)
Sr. Member
****
Offline Offline

Activity: 485
Merit: 274


View Profile WWW
January 05, 2021, 11:43:13 AM
 #9


Are you asking what are the possibilities of successfully finding the private key of an address by brute forcing? If so, as @hosseinimr93 said, 1 in 2256. You can try calculating with custom computational power and see what are the odds.


Say someone was giving you clues to their private key.  For each character they gave you a couple of options eg, for the fifth position is either 1, 3, f or a.  How many options would they have to give you per position for it to be crackable by brute force? 

o_e_l_e_o
In memoriam
Legendary
*
Offline Offline

Activity: 2268
Merit: 18746


View Profile
January 05, 2021, 12:31:33 PM
Merited by ranochigo (3)
 #10

Say someone was giving you clues to their private key.  For each character they gave you a couple of options eg, for the fifth position is either 1, 3, f or a.  How many options would they have to give you per position for it to be crackable by brute force?
Well, we can work out a rough idea. Let:

x = number of addresses you can derive from their respective private keys each second
y = length of time in seconds you are willing to wait

Given that a private key has 64 characters, then the number of possibilities for each character would then be given by the 64th root of the product of these two numbers, so 64√(x*y)

For example

Let's say you are running a GeForce RTX 2080 Ti, which can turn 2.5 billion private keys in to their corresponding addresses each second, and you are willing to let this run for two weeks. 14 days * 24 hours * 60 minutes * 60 seconds * 2.5 billion = 3.024*1015 private keys. The 64th root of this number is 1.745, so you wouldn't even be able to exhaust the search space of 2 characters per position in 2 weeks.

264 is 1.845*1019, so again running your GeForce RTX 2080 Ti and checking 2.5 billion keys per second, it would take you ~234 years to check all combinations, or ~117 years if you wanted a 50% chance of finding the correct key.
BlackHatCoiner
Legendary
*
Offline Offline

Activity: 1694
Merit: 8336


Fiatheist


View Profile WWW
January 05, 2021, 12:35:15 PM
Last edit: January 05, 2021, 01:18:59 PM by BlackHatCoiner
Merited by o_e_l_e_o (2)
 #11

It's actually 1 in 2160, on average, since there are 296 private keys per address, on average.
I was wrong about that. Yes, it's actually 1 in 2160.

Say someone was giving you clues to their private key.  For each character they gave you a couple of options eg, for the fifth position is either 1, 3, f or a.  How many options would they have to give you per position for it to be crackable by brute force?
First of all let's define the private key's format. Is it going to be hexadecimal or WIF? [the difference]
Secondly what do you mean by saying crackable by brute force? Are we trying to find his private key or a private key that unlocks his address?
If we assume that you want his private key and that his private key is hexadecimal then a character of the fifth position isn't going to help you. You still have almost 2252 different combinations. (for every hex character you remove you have 24 less combinations)

If you want to find a private key that unlocks his address then, as @o_e_l_e_o wrote, you have 1 in 2160 on average. To cut a long story short, if he doesn't give you at least 25 hexadecimal characters of his private key then you have less possibilities of finding it than succeeding on an address' brute force.

Knowing 25 hex characters and their positions is 16 times easier than 2160. It's 1 in 2156. Still impossible, but easier than the stupidly enormous range of [1, 2160].

@thirdprize, note that we use the phrase "on average". There may be addresses like this one: 1111111111111111111114oLvT2 that have no private keys that unlock them. Every address most likely has more than 1 billion, but you can't prove it if you don't try all the possible combinations. It is quite funny to think that there are so many numbers that unlock you 69 bitcoins, but no one knows them. And that happens because most of us can't imagine the largeness of 2160.


[the difference]
Example of a private key in hexadecimal:
Code:
e1398ffab41618b4c63313912d2c407e57c60feeb799544503e0aeca8c5aede1

Example of a private key in WIF (Wallet Import Format):
Code:
L4mX2hsUq4LFbMmAomWHCARAuMkzTuAZjmGCQsvmny1aahRE1Aie
(The above works only on mainnet)

A WIF is nothing but the original hex private key encoded in base58 plus some other technical stuff like version byte and checksum. This code shows exactly how we end up with a WIF:

Code:
privatekey = "e1398ffab41618b4c63313912d2c407e57c60feeb799544503e0aeca8c5aede1"
extended = "80" + privatekey + "01"
extendedchecksum = extended + checksum(extended)
wif = base58_encode(extendedchecksum)

// wif is "L4mX2hsUq4LFbMmAomWHCARAuMkzTuAZjmGCQsvmny1aahRE1Aie"

You can read more about the WIF here: https://learnmeabitcoin.com/technical/wif

P.S, o_e_l_e_o is faster.

█▀▀▀











█▄▄▄
▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄
█████████████
████████████▄███
██▐███████▄█████▀
█████████▄████▀
███▐████▄███▀
████▐██████▀
█████▀█████
███████████▄
████████████▄
██▄█████▀█████▄
▄█████████▀█████▀
███████████▀██▀
████▀█████████
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▀▀▀█











▄▄▄█
▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
▀██▀▀
j2002ba2
Full Member
***
Offline Offline

Activity: 206
Merit: 447


View Profile
January 05, 2021, 01:01:19 PM
 #12

Say someone was giving you clues to their private key.  For each character they gave you a couple of options eg, for the fifth position is either 1, 3, f or a.  How many options would they have to give you per position for it to be crackable by brute force? 

Assuming known legacy address, wif private key contains 85 characters, first is always "5", second one of "H", "J", "K", leaving us with 83 characters. Let's assume the second character is know. When we have 4 possibilities for each character, there are 2166 possible combinations. Direct brute forcing has been solved for private keys with 263 possibilities up to now.

We could accelerate the calculations a bit, by dropping the checksum characters (last 5), and doing checksum on the rest. This drops the complexity to 2156.

If the public key of the address is known (i.e. spent from, or signed with), then it's "easier" to do Pollard Rho on it - complexity is only 2128.

With 2 possibilities per character, the complexity is 278, so few billions of dollars, many years, and giga-watt-hours later it could be cracked.

o_e_l_e_o
In memoriam
Legendary
*
Offline Offline

Activity: 2268
Merit: 18746


View Profile
January 05, 2021, 09:09:08 PM
 #13

You still have almost 2252 different combinations.
Minor correction: If you have 4 possibilities for one character in a 64 character private key, then the total number of possibilities is 2254. If you knew for certain one character in the key, then you would have 2252 possibilities.

There may be addresses like this one: 1111111111111111111114oLvT2 that have no private keys that unlocks them.
Another correction: This address does have a private key. In fact, it has many. It is just that nobody knows what any of them are (or at least, as far as we know nobody knows what any of them are). That address is generated from a RIPEMD-160 of:

Code:
0000000000000000000000000000000000000000

Any private key which produces a public key, which when hashed with SHA-256 then RIPEMD-160 produces the above number, would be able to spend coins at that address.
BlackHatCoiner
Legendary
*
Offline Offline

Activity: 1694
Merit: 8336


Fiatheist


View Profile WWW
January 05, 2021, 10:56:39 PM
 #14

Any private key which produces a public key, which when hashed with SHA-256 then RIPEMD-160 produces the above number, would be able to spend coins at that address.
I didn't say the opposite. I said it may. It may also have none, it's just extremely unlikely.

Minor correction: If you have 4 possibilities for one character in a 64 character private key, then the total number of possibilities is 2254. If you knew for certain one character in the key, then you would have 2252 possibilities.
Why do you have 4 possibilities for one character? Isn't it 16? (0-F). I don't get this.

Actually this needs a correction:
Quote
(for every hex character you remove you have 24 times less combinations)

█▀▀▀











█▄▄▄
▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄
█████████████
████████████▄███
██▐███████▄█████▀
█████████▄████▀
███▐████▄███▀
████▐██████▀
█████▀█████
███████████▄
████████████▄
██▄█████▀█████▄
▄█████████▀█████▀
███████████▀██▀
████▀█████████
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▀▀▀█











▄▄▄█
▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
▀██▀▀
o_e_l_e_o
In memoriam
Legendary
*
Offline Offline

Activity: 2268
Merit: 18746


View Profile
January 06, 2021, 08:26:51 AM
 #15

Why do you have 4 possibilities for one character? Isn't it 16? (0-F). I don't get this.
You are right that each character can be one of 16 possibilities, from 0-F, and you are right that if you know one character then then instead of it being 1664 = 2256 combinations it is 1663 = 2252 combinations.

My point was that OP had asked what would happen if the person gave you a number of different options for a character - "eg, for the fifth position is either 1, 3, f or a". In that case, instead of that position having 24 possibilities, it instead has 22 possibilities, so the total number of possibilities would reduce from 2256 to 2254. Given that, even if you only had 4 possibilities for every character in the key, you would still be left with 2128 possibilities overall, which is still impossible to even consider brute forcing.
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!