There are more private keys than addresses ?

cajancharles

jr. member

Activity: 39

Merit: 10

Quote from: o_e_l_e_o on January 22, 2021, 09:39:58 AM

Quote from: DannyHamilton on January 22, 2021, 09:49:46 AM

Alternatively...

Study advanced mathematics
Become the top expert in the entire world in the mathematics related to ECDSA, SHA256, and RIPEMD160
Discover a mathematical weakness that nobody else in the world has ever discovered related to those algorithms
Use that mathematical weakness to calculate your private keys

Thanks for the answer and i'll go for 2nd one.

And ECC is interesting and i prefer this over pgp because you can use it for two things, encryption and bitcoin address.
It provides same level of security as rsa with much smaller key size and it is faster that rsa, but ECDSA is vulnerable to k-reuse attack. what's the solution to this problem of nonce reuse attack.
so does it takes computational power to generate unique random number k everytime and it can't be done on mobile phone?

and why RSA is not vulnerable to nonce reuse attack? , so why satoshi didn't chose RSA instead of ECC (because it provides same security with smaller key length?)

BASE16

member

Activity: 180

Merit: 38

Quote from: bigvito19 on January 22, 2021, 12:38:45 PM

Quote from: BASE16 on January 22, 2021, 12:01:42 PM

Quote from: bigvito19 on January 22, 2021, 11:32:28 AM

You already know that its software that find keys with the public key

https://bitcointalksearch.org/topic/pollards-kangaroo-ecdlp-solver-5244940
https://bitcointalksearch.org/topic/baby-step-giant-step-combined-efforts-to-find-12-bitcoin-5304368
https://github.com/JeanLucPons/Kangaroo
https://github.com/JeanLucPons/BSGS
https://github.com/WanderingPhilosopher/BSGS

And have you had any success with those ?

Yes, very small success. That's why I always promote the kangaroo, it just need some modifications to it.

And why don't you modify it then ?
What would you modify ?

bigvito19

full member

Activity: 706

Merit: 111

Quote from: BASE16 on January 22, 2021, 12:01:42 PM

Quote from: bigvito19 on January 22, 2021, 11:32:28 AM

You already know that its software that find keys with the public key

https://bitcointalksearch.org/topic/pollards-kangaroo-ecdlp-solver-5244940
https://bitcointalksearch.org/topic/baby-step-giant-step-combined-efforts-to-find-12-bitcoin-5304368
https://github.com/JeanLucPons/Kangaroo
https://github.com/JeanLucPons/BSGS
https://github.com/WanderingPhilosopher/BSGS

And have you had any success with those ?

Yes, very small success. That's why I always promote the kangaroo, it just need some modifications to it.

BASE16

member

Activity: 180

Merit: 38

Quote from: bigvito19 on January 22, 2021, 11:32:28 AM

You already know that its software that find keys with the public key

https://bitcointalksearch.org/topic/pollards-kangaroo-ecdlp-solver-5244940
https://bitcointalksearch.org/topic/baby-step-giant-step-combined-efforts-to-find-12-bitcoin-5304368
https://github.com/JeanLucPons/Kangaroo
https://github.com/JeanLucPons/BSGS
https://github.com/WanderingPhilosopher/BSGS

And have you had any success with those ?

bigvito19

full member

Activity: 706

Merit: 111

Quote from: DannyHamilton on January 22, 2021, 09:49:46 AM

EDIT: I say too much and take too long to type. o_e_i_e_o has responded with mostly thee same response, only faster. I'll leave this here just in case anyone finds that it adds any interest.

Quote from: cajancharles on January 22, 2021, 05:24:56 AM

why every bitcoin public address have 2^96 private key

Because with a version 1 P2PKH address there are approximately 2²⁵⁶ unique private-public key pairs. An address is based on a RIPEMD160 HASH of the public key (actually a RIPEMD160 HASH of a SHA256 HASH of a public key) resulting in 2¹⁶⁰ unique version 1 P2PKH addresses.

2²⁵⁶ keys divided by 2¹⁶⁰ addresses equals an average of about 2⁹⁶ private keys PER address.

Quote from: cajancharles on January 22, 2021, 05:24:56 AM

and how can i find my (2^96- 1) private key for my bitcoin public address?

To find just 1 of those private keys...

Acquire access to enough computing power to calculate addresses from 10¹⁰ private keys per second.
Run that computing power continuously for (on average) 2.3 * 10³⁰ years

To find ALL of those private keys...

Acquire access to enough computing power to calculate addresses from 10¹⁰ private keys per second.
Run that computing power continuously for (on average) 1.8 * 10⁵⁹ years

Alternatively...

Study advanced mathematics
Become the top expert in the entire world in the mathematics related to ECDSA, SHA256, and RIPEMD160
Discover a mathematical weakness that nobody else in the world has ever discovered related to those algorithms
Use that mathematical weakness to calculate your private keys

Quote from: cajancharles on January 22, 2021, 05:24:56 AM

since Elliptical curve private key and public key has 1:1 ratio, and that public key is encoded & hashed with some operation to get bitcoin public address.

Correct.

Quote from: cajancharles on January 22, 2021, 05:24:56 AM

also is it possible to encrypt message with bitcoin public address and then decrypt with private key which is generated by ECC.

Don't bother. It's not worth the effort. There are better systems to encrypt and decrypt messages. I believe that some have created some software to do it (with the public key, it can't be done with the address), but I wouldn't use any of it.

You already know that its software that find keys with the public key

https://bitcointalksearch.org/topic/pollards-kangaroo-ecdlp-solver-5244940
https://bitcointalksearch.org/topic/baby-step-giant-step-combined-efforts-to-find-12-bitcoin-5304368
https://github.com/JeanLucPons/Kangaroo
https://github.com/JeanLucPons/BSGS
https://github.com/WanderingPhilosopher/BSGS

DannyHamilton

legendary

Activity: 3472

Merit: 4801

EDIT: I say too much and take too long to type. o_e_i_e_o has responded with mostly thee same response, only faster. I'll leave this here just in case anyone finds that it adds any interest.

Quote from: cajancharles on January 22, 2021, 05:24:56 AM

why every bitcoin public address have 2^96 private key

Because with a version 1 P2PKH address there are approximately 2²⁵⁶ unique private-public key pairs. An address is based on a RIPEMD160 HASH of the public key (actually a RIPEMD160 HASH of a SHA256 HASH of a public key) resulting in 2¹⁶⁰ unique version 1 P2PKH addresses.

2²⁵⁶ keys divided by 2¹⁶⁰ addresses equals an average of about 2⁹⁶ private keys PER address.

Quote from: cajancharles on January 22, 2021, 05:24:56 AM

and how can i find my (2^96- 1) private key for my bitcoin public address?

To find just 1 of those private keys...

Acquire access to enough computing power to calculate addresses from 10¹⁰ private keys per second.
Run that computing power continuously for (on average) 2.3 * 10³⁰ years

To find ALL of those private keys...

Acquire access to enough computing power to calculate addresses from 10¹⁰ private keys per second.
Run that computing power continuously for (on average) 1.8 * 10⁵⁹ years

Alternatively...

Study advanced mathematics
Become the top expert in the entire world in the mathematics related to ECDSA, SHA256, and RIPEMD160
Discover a mathematical weakness that nobody else in the world has ever discovered related to those algorithms
Use that mathematical weakness to calculate your private keys

Quote from: cajancharles on January 22, 2021, 05:24:56 AM

since Elliptical curve private key and public key has 1:1 ratio, and that public key is encoded & hashed with some operation to get bitcoin public address.

Correct.

Quote from: cajancharles on January 22, 2021, 05:24:56 AM

also is it possible to encrypt message with bitcoin public address and then decrypt with private key which is generated by ECC.

Don't bother. It's not worth the effort. There are better systems to encrypt and decrypt messages. I believe that some have created some software to do it (with the public key, it can't be done with the address), but I wouldn't use any of it.

o_e_l_e_o

legendary

Activity: 2268

Merit: 18748

Quote from: cajancharles on January 22, 2021, 05:24:56 AM

why every bitcoin public address have 2^96 private key and how can i find my (2^96- 1) private key for my bitcoin public address?
since Elliptical curve private key and public key has 1:1 ratio, and that public key is encoded & hashed with some operation to get bitcoin public address.

There are 2²⁵⁶ private keys (actually just less than, but that is irrelevant to this discussion), 2²⁵⁶ public keys, and 2¹⁶⁰ addresses.

As you say, private and public keys have a 1:1 ratio, but since to turn a public key in to an address you have to pass it through a RIPEMD-160 function, which only has 2¹⁶⁰ possible outputs, then there cannot be 1 public key per address. There are 2²⁵⁶ inputs in to RIPEMD-160, but only 2¹⁶⁰ outputs, meaning that each output has 2⁹⁶ inputs.

Quote from: cajancharles on January 22, 2021, 05:24:56 AM

also is it possible to encrypt message with bitcoin public address and then decrypt with private key which is generated by ECC.

It is possible to encrypt a message with a bitcoin public key and decrypt it with the associated private key, but not with the address. You need to either extract their public key from a transaction they have made, or ask them to share it with you directly.

Dabs

legendary

Activity: 3416

Merit: 1912

The Concierge of Crypto

Quote from: BlackHatCoiner on January 21, 2021, 02:10:01 AM

If you understand the possibilities behind this, then you should not worry about it.

I meant "impossible" the way Peppa Pig would say it. She can't whistle, says it's impossible.

The accurate answer is, it's highly unlikely or very improbable. Your chances of getting hit by lightning or winning the lottery jackpot are higher.

There are addresses out there with more than 100 BTC. Feel free to try and guess a private key for them. There are 2^96 that could possibly work.

cajancharles

jr. member

Activity: 39

Merit: 10

why every bitcoin public address have 2^96 private key and how can i find my (2^96- 1) private key for my bitcoin public address?
since Elliptical curve private key and public key has 1:1 ratio, and that public key is encoded & hashed with some operation to get bitcoin public address.

also is it possible to encrypt message with bitcoin public address and then decrypt with private key which is generated by ECC.

odolvlobo

legendary

Activity: 4466

Merit: 3391

Quote from: cajancharles on January 20, 2021, 09:51:24 AM

If every bitcoin address can be generated by 2^93 private keys, then chances of brute-forcing and finding private keys of that specific address are respectively higher?

This. video is appropriate: https://www.youtube.com/watch?v=zMRrNY0pxfM

BlackHatCoiner

legendary

Activity: 1512

Merit: 7340

Farewell, Leo

Quote from: Dabs on January 20, 2021, 10:31:56 AM

What is the real question? Or is this a purely academic exercise?

The answer is: it's impossible.

Or rather, don't worry about it.

I would disagree with this one. If people are interested, they have to find out more about it. Humans cannot understand the huge range of 2²⁵⁶ and that's why it seems strange that every address has 2⁹⁶ different private keys which is also a huge number.
(It's 79,228,162,514,264,337,593,543,950,336 precisely)

If you understand the possibilities behind this, then you should not worry about it.

Quote from: bigvito19 on January 20, 2021, 10:41:00 AM

Yes, 2^96 has a much higher chance to brute-forcing compared to 2^256, 2^160, and 2^128.

But you're not brute forcing 2⁹⁶. You're brute forcing a base58 encoded RIPEMD-160 hash, which means 2¹⁶⁰.

For example if you generate a private ECDSA key that once you take the corresponding public key (compressed) and hash it with SHA-256 and then with RIPEMD-160 and after all you get this result:

Code:

f54a5851e9372b87810a8e60cdd2e7cfd80b6e31

Then you've found a private key for this address:

Code:

1PMycacnJaSqwwJqjawXBErnLsZ7RkXUAs

If not, you're trying different combinations until you find a collision to this RIPEMD-160.

bigvito19

full member

Activity: 706

Merit: 111

Quote from: cajancharles on January 20, 2021, 09:51:24 AM

Quote from: hosseinimr93 on January 17, 2021, 01:11:22 PM

There are 2²⁵⁶ valid private keys and 2¹⁶⁰ valid addresses.

Quote from: Kostelooscoin on January 17, 2021, 01:00:13 PM

1 address can therefore have several private keys ?

Yes, every bitcoin address can be generated by 2⁹⁶ private keys, on average.

If every bitcoin address can be generated by 2^93 private keys, then chances of brute-forcing and finding private keys of that specific address are respectively higher?

Yes, 2^96 has a much higher chance to brute-forcing compared to 2^256, 2^160, and 2^128.

o_e_l_e_o

legendary

Activity: 2268

Merit: 18748

Quote from: cajancharles on January 20, 2021, 09:51:24 AM

If every bitcoin address can be generated by 2^93 private keys, then chances of brute-forcing and finding private keys of that specific address are respectively higher?

Yes. Given that, on average, each address will have 2⁹⁶ associated private keys, then rather for searching for 1 key in 2²⁵⁶, you are searching for any one of 2⁹⁶ keys in 2²⁵⁶. This is the same as saying 1 in 2¹⁶⁰.

Note that this is still many orders of magnitude more secure than the 128 bit security provided by the secp256k1 curve that bitcoin uses. Anyone trying to crack an address would try to break ECDLP in 2¹²⁸ operations rather than trying to randomly brute force 2¹⁶⁰ private keys. Note also that both of these things are completely impossible, and will be for a long time.

Dabs

legendary

Activity: 3416

Merit: 1912

The Concierge of Crypto

What is the real question? Or is this a purely academic exercise?

The answer is: it's impossible.

Or rather, don't worry about it.

cajancharles

jr. member

Activity: 39

Merit: 10

Quote from: hosseinimr93 on January 17, 2021, 01:11:22 PM

There are 2²⁵⁶ valid private keys and 2¹⁶⁰ valid addresses.

Quote from: Kostelooscoin on January 17, 2021, 01:00:13 PM

1 address can therefore have several private keys ?

Yes, every bitcoin address can be generated by 2⁹⁶ private keys, on average.

If every bitcoin address can be generated by 2^93 private keys, then chances of brute-forcing and finding private keys of that specific address are respectively higher?

o_e_l_e_o

legendary

Activity: 2268

Merit: 18748

Quote from: Kostelooscoin on January 19, 2021, 11:12:32 AM

how do you know how many combinations between 5hraaa...... and 5hrzzzz ?

By the same method I used to calculate how many addresses start with "12345".

The very first possible private key is:

Code:

0000000000000000000000000000000000000000000000000000000000000001

That is 63 zeroes followed by a single 1. When converting to WIF, this gives the following private key:

Code:

5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAnchuDf

This gives us the lower bound for private keys which start with 5H when converted to WIF.

Now we calculate the upper bound. Remembering that like address, WIF private keys are in Base58 encoding with the last 6 characters being a checksum. So, we use the private key 5H, followed by 43 "z"s, and then append the correct checksum. This gives the following WIF key:

Code:

5HzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzuQu3WC

When you convert that WIF back to hex and strip the prefix and checksum, you get the following private key:

Code:

1853E65BF4DDC28AA8C27A71F65671928ED6E1D612946BB3E94B8B36E5E9FFFF

Nw simply calculate the difference between those two hex numbers, and that gives you the number of valid WIF keys which start with 5H.

BASE16

member

Activity: 180

Merit: 38

Because that is the hexadecimal representation of the 256 bits binary private key.
Or better said the BASE16 key of the BASE2 private key.

BASE2:
1111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111
111111111111111111111111

BASE10:
11579208923731619542357098500868790785326998466564
0564039457584007913129639935

BASE16:
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFF

What you are reffering to is a WIF key
https://en.bitcoin.it/wiki/Wallet_import_format

Kostelooscoin

member

Activity: 206

Merit: 16

Quote from: o_e_l_e_o on January 17, 2021, 03:07:31 PM

Quote from: BlackHatCoiner on January 17, 2021, 01:15:46 PM

Actually a bitcoin address doesn't differ that much from a RIPEMD 160 result. It's just encoded with base58.

There's a little more to it than that. To turn a RIPEMD160 result in to an address, you first need to add a prefix byte (00 for P2PKH addresses, 05 for P2SH addresses), hash that number using SHA256 twice, add the first four bytes of the result to the end of the previous number, and then encode that number in Base58.

Quote from: Kostelooscoin on January 17, 2021, 01:22:13 PM

each private key starts with 5H, 5J, 5K
if I take all private keys beginning with 5H all bitcoin addresses would be there?

If you take all the WIF private keys which start with 5H, and convert them to hexadecimal, they are between the following two numbers:

Code:

0000000000000000000000000000000000000000000000000000000000000001

and

Code:

1853E65BF4DDC28AA8C27A71F65671928ED6E1D612946BB3E94B8B36E5E9FFFF

This is approximately 2^252.6 private keys (and around 9.5% of all possible private keys). So theoretically yes, there will a private key in there which would give every legacy address, of which there are "only" 2¹⁶⁰.

how do you do your calculation ?

how do you know how many combinations between 5hraaa...... and 5hrzzzz ?

o_e_l_e_o

legendary

Activity: 2268

Merit: 18748

Quote from: BlackHatCoiner on January 18, 2021, 03:32:43 PM

Can you explain me how you calculated this?

The Base58 character set looks like this (with the 4 missing characters being 0, I, O, and l):

Code:

1 2 3 4 5 6 7 8 9 A B C D E F G H J K L M N P Q R S T U V W X Y Z a b c d e f g h i j k m n o p q r s t u v w x y z

Therefore, the first character in the set is 1, and the last character in the set is z.

With a 34 character address, and the first characters set at "12345", and the last 6 characters being the checksum,* then it is simply a case of filling in 23 "1"s or 23 "z"s, and then calculating the correct checksum.

Once you've done that, you can decode both addresses in to hexadecimal, strip away the checksum bytes and the prefix bytes, and then calculate the difference between the two numbers.

*Much like a seed phrase where the last word contains some data and some checksum, in this case the 6th last letter encodes some data and some checksum.

BlackHatCoiner

legendary

Activity: 1512

Merit: 7340

Farewell, Leo

Quote from: o_e_l_e_o on January 18, 2021, 12:53:39 PM

The first address starting with "12345" is 12345111111111111111111111114o2pK8, which corresponds to a pubkey hash of 0B5B8501474371E179BFBE6E08AEA6DAC6D84557.

The last address starting with "12345" is 12345zzzzzzzzzzzzzzzzzzzzzzzq2Caed, which corresponds to a pubkey hash of 0B5B88B07F4F1265E590BF6672462DAFDD698ED7.

Can you explain me how you calculated this?

Topic: There are more private keys than addresses ? (Read 656 times)