[Technical] How the address and private key are generated?

[btcb3g1nn3r]

hello,
I'm an IT guy at my basis but with limited time nowadays.
I see a Javascript implementation on bitaddress.org that is great solution for portability.
Even if I'm "pathological" a curious person, I'm a bit overwhelmed about this crypto world due to its complexity and my limited time to study.

Do you know the algorithm applied to generate an address and a private key out of a string (any sequence of letters/numbers or special characters) ?
I see the dedicated thread herehttps://bitcointalk.org/index.php?topic=43496.840, the tool owner not being active since two years so maybe some of you can give me an answer and save my time from reviewing the js code

As these addresses / private keys are generated there is always a probability that another address was already generated at a certain time in the past, as a matter a fact, I searched for one address I generated via bitaddress.org and I could find 2 of them on blockchain.com transactions explorer => how this system can work if uniqueness is not ensured?

[ranochigo]

The ECDSA private key can be anything from 1 to (approx.) 1.15*10^77, and that is converted to hexadecimal format when you're talking about the actual format generally used. Public key is generated with the private key, it's generator point and is from the secp256k1 curve. If you want to generate a legacy address, check the Wiki out[1]. For bech32 address, it's quite long and I'll link you to that[2].

As these addresses / private keys are generated there is always a probability that another address was already generated at a certain time in the past, as a matter a fact, I searched for one address I generated via bitaddress.org and I could find 2 of them on blockchain.com transactions explorer => how this system can work if uniqueness is not ensured?

Correct. If the RNG is flawed, it could result in the addresses that are generated to not be random enough and thus would be susceptible to being compromised. The key space is so big so it's hard for collisions to happen given enough entropy.

Do the addresses have transactions within or is it empty? If it's empty, then it's perfectly normal because block explorers will always display addresses that are empty as it's easy to validate the addresses' validity.




[1] https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses
[2] https://bitcointalk.org/index.php?topic=4992632.0

[btcb3g1nn3r]

the address found on blockchain.com looked empty, thanks for your explanation and references

[webtricks]

I had created a thread about this few months ago - https://bitcointalk.org/index.php?topic=5223167.0. The thread covers in-detailed explanation for creating private key, deriving public key from it, generating bitcoin address and WIF. It only covers the process for P2PKH address (Legacy) but since you are looking for Bitaddress.org substitute (which also only provides legacy address creation), the above thread will cater your need.

I have also included minimal Javascript (Node.js) code so if you are proficient in this language, you can easily understand the code; no need to spend time studying bitaddress.org source code.

And if you have any doubt, you can ask in this thread or in the above thread.

the address found on blockchain.com looked empty, thanks for your explanation and references

If addresses are empty then most probably no one else has used those addresses. RNG of Bitddress.org is quite strong and it's highly unlikely that bitaddress will generate same private key for two different users.

[btcb3g1nn3r]

I've read your thread and it was great, I was a bit confused with your mix when referring to characters (as hex or ASCII) and bytes and bits but in the end I got the essence, if your intention is not necessarily to have a letter post then it'll be great for a beginner like me but with very simplified way of thinking to really have clusters / steps for the algorithm behind the private key, public key creation, example:
step 1: generate a random number in the range of 1 .. X digits
step 2: apply hashing functions on it (what / how many) - you can put some references about what that hash function
step 3: apply a fixed set of computations (eg. add the prefixes, checksums)
step 4: apply conversion (where applicable) to specific format

Then you continue with concrete example:
step 1: <number here>
step 2: <output out of the hashes>
...etc...

And you do this for the private key and the public one

I was really efficient in js 16-18 years ago, I'm way outdated with the new js versioning and libs created out of it but I still have my programmer way of thinking

[webtricks]

I've read your thread and it was great, I was a bit confused with your mix when referring to characters (as hex or ASCII) and bytes and bits but in the end I got the essence, if your intention is not necessarily to have a letter post then it'll be great for a beginner like me but with very simplified way of thinking to really have clusters / steps for the algorithm behind the private key, public key creation....snip..

Okay! Here's a relatively simpler explanation then. But note: to make it easier to understand, I will be using simple words which maybe not be 100% technically correct. Also, I will give few links to the online tools which you can use to understand the process. However, I don't personally endorse those tools and won't recommend you to use them for creating addresses for real-use.

Now let's start:

Step 1: The first step involves generating a private key. Like @ranochigo said above, private key can be anything between 1 to (approx.) 1.15*10^77 which is then converted to hexadecimal. But since Bitcoin uses secp256k1 parameter of Elliptic Curve Cryptography to generate public key, private key needs to be 256-bits long. So suppose you pick 3 as your private key (which is a 2-bit number) then you need to add empty bits to make the length of private key equals to 256 bits. So your private key will look like this:
0000000000000000000000000000000000000000000000000000000000000003 (every hexadecimal character represents 4-bits so the length will be 64)

Step 2: Once you have private key, you then need to create public key from it. This is achieved by using Elliptic Curve Cryptography. Without going into much detail, ECC is a cryptography approach which gives you point on a curve based upon a private key provided. If you remember then we were taught in schools about graphs. A point on graph is plotted like this: (2,4) where 2 represents its X-value and 4 represents its Y-value. ECC will also give you a point (A,B) which is your public key.

Step 3: Now we need to create bitcoin address from the public key. Using 'compressed public key' for address generation has become the standard. Compressed means that we only take X-value of public key. Then we add 02 or 03 in-front of X-value depending upon whether Y is even or odd number. So if our public key is (A,B) and B is odd number then we take 03+A for further calculation.

Step 4: The next step involves creating SHA-256 hash of 03+A. In easy words, SHA-256 is a digital fingerprint of a message. Every message has a unique fingerprint of a fixed size (which is 64 in hexadecimal).

Step 5: Now we will create RIPEMD-160 hash of the hash obtained in previous step. RIPEMD-160 is another hashing function like SHA-256. It is primarily used in address generation to shorten the length of hash. SHA-256 produces hash which is of 32 bytes (1 byte = 8 bits). RIPEMD-160 then reduces it to 20 bytes (40 in hexadecimal).

Step 6: Then we add 00 in front of hash obtained in step 5. This 00 signifies that we are going to use this address on the main Bitcoin network.

Step 7: Okay, so far we have a value which is equal to = 00 + RIPEMD-160 hash of [SHA-256 hash of ( 03 + X-value of public key )]. Keep this value aside and let's generate checksum.

Step 8: The purpose of using checksum is to avoid the mistake in copying bitcoin address. If a user misses a character while copying or types wrong character in address then wallet will show it as invalid address because checksum won't match. To generate checksum, perform SHA-256 hashing on the value obtained in Step 7. Then perform SHA-256 hashing again on the hash received.

Step 9: The length of checksum is 4-bytes. Since, the length of SHA-256 is 32 bytes (64 in hexadecimal), we will only need first 4 bytes or 8 hexadecimal digits of the hash.

Step 10: Now add the checksum obtained in step 9 at the end of the value obtained in Step 7. So, now we have a value which is equal to = 00 + RIPEMD-160 hash of [SHA-256 hash of ( 03 + X-value of public key )] + checksum.

Step 11: Final step is to convert the value from Step 10 into Base58 string. Base58 is encoding format with 58 characters. It is used to shorten the length of address as much as possible by just using alpha-numeric characters after removing few characters to avoid confusion.


EXAMPLE:

Step 1: Let's start by picking 256-bit number as private key. You can use -  This Tool, select 256-bit from menu, tick 'hex' checkbox. I generated one - 6D2FD98D6EBAA0D1A96A0B5B2482FCC813A855242CFF93D76B67C09FE0122E66 (you can use this one for further steps).

Step 2: Now let's generate public key from private key. I didn't find any tool for this online so I created one real fast - https://webtricks.website/secp256k1/. By filling the above private key, we get:
[870dac978a24321b6a7dffe26bb19270d8c9bd4f074c510b80a115ce050eb652 , 959e77411b6ea35833d2006ddbd8a90aa9c8c1a3b310bf607ba6352e5b80e144] which is our public key.

Step 3: Now let's first take Y-value i.e. 959e77411b6ea35833d2006ddbd8a90aa9c8c1a3b310bf607ba6352e5b80e144 and determine whether it's even or odd value. You can use - This Tool to convert from hexadecimal to decimal. In decimals, the number is 67674599338242423768515926925083934807011987438106446435693057967227469357380 which is even number so we will add 02 in front of X-value. Hence, we will take 02870dac978a24321b6a7dffe26bb19270d8c9bd4f074c510b80a115ce050eb652 for further calculation.

Step 4: Use - This Tool to generate SHA-256 of the value from Step 3. Don't forget to check 'input type' as 'hex' on the page. SHA-256 of above value is def9edc5650c3e791c2de616ff81a671966fe60609b45598589853e13a1551ac.

Step 5: Use - https://webtricks.website/ripemd160/ to calculate RIPEMD-160 hash of SHA-256 hash obtained in 4th step. The result is - 6ce830ddca6af06a6c8b3e7b351a25ab8ee94751.

Step 6: Adding 00 in front. The value becomes - 006ce830ddca6af06a6c8b3e7b351a25ab8ee94751.

Step 8: To generate checksum, we will generate SHA-256 of 006ce830ddca6af06a6c8b3e7b351a25ab8ee94751 using same tool from Step 4. The result is e90a5fa47b270435fea4251fc732838ae1ae77a16c90c776a2a2156aee93cd64. Then we will again generate hash of e90a5fa47b270435fea4251fc732838ae1ae77a16c90c776a2a2156aee93cd64 which is 646219ed043d40606c70f4cc9950264795faf81b8b171928caae82b066628050.

Step 9: Since checksum is only 4-byte, we will take first 8-digits of the hash generated in step 8 i.e. 646219ed.

Step 10: Adding the checksum at the end of value obtained in step 6 - 006ce830ddca6af06a6c8b3e7b351a25ab8ee94751646219ed

Step 11: Use This Tool for creating Base58 string of the value obtained in Step 10. Don't forget to change 'Treat Input As' to 'HEX' on the page. The result will be 1Avr8d9HWAV86QtHmqBhco3W67DiKNA9Gp which is our bitcoin address.

You can verify that the address is correct by going to BitAddress.org and entering the private key from Step 1 on Wallet Details page.

[btcb3g1nn3r]

Very nice post and thanks a lot for your explanations! As I told you, I got the essence from your thread, your post above just makes it crystal clear for the next beginner diving into crypto swamp
I admire your passion!
I'm a very curious person so probably my next personal study will go into "how's made" of these functions applied and mainly on your step 2.

Another question, can I just type random 64 characters to get a private key? Can I assume that it'll match someone's private key so I can accidentally benefit of his/her funds??
Can I just try sweeping this key? 0000000000000000000000000000000000000000000000000000000000000003
Is this something that an attacker can actually attempt to use, to try sweeping such randomly created keys (eg. as brute force) ?

[webtricks]

I'm a very curious person so probably my next personal study will go into "how's made" of these functions applied and mainly on your step 2.

Yeah! It is always nice to learn about encryption and encoding functions and how these functions add the layers of security to any protocol or application. Step 2 is all about Elliptic Curve Cryptography which creates public key from private key.
I have dedicated thread about ECC here: https://bitcointalk.org/index.php?topic=5232734.0
NotATether summarized more info about ECC nicely here: https://bitcointalk.org/index.php?topic=5235482.0
Then of-course, you have Google and YouTube.

Another question, can I just type random 64 characters to get a private key?

The 64-characters are actually the representation of hexadecimal number. So yes, if you randomly type characters between 0-9 and A-F then it's a valid private key, provided that the value of such hexadecimal number is lower than:

Code:

FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140

But it is highly inadvisable to create private key manually. It is always better to use pseudo-random number generator algorithms and libraries which most of the bitcoin wallets use.

Can I assume that it'll match someone's private key so I can accidentally benefit of his/her funds??

Yes! There's a probability that you may hit a private key which is already being used. But that probability is so-so low that it doesn't worth an effort. Let me quote a post from o_e_l_e_o stating the magnitude of the difficulty to find a used address:

The reason it will never happen is simply down to math. The numbers we are dealing with here are unimaginably large. For example, if every human on the planet each generated 1 million new addresses every second, and had been doing so since the birth if the universe 13.7 billion years ago, we would only have generated approximately 0.0000000000002% of all possible addresses.

Can I just try sweeping this key? 0000000000000000000000000000000000000000000000000000000000000003
Is this something that an attacker can actually attempt to use, to try sweeping such randomly created keys (eg. as brute force) ?

Yep! You can sweep that key, it's a valid private key as it is within the range of 1 to (approx.) 1.15*10^77. But you mustn't. Attackers can easily brute-force such private keys. In-fact, any manually written private key isn't safe because humans are worst random generator. They are always tend to go for patterns which make the keys predictable.

[coinsolidation.org]

Hi,

I share a link where he explains step by step how to generate a bitcoin address with java programming.

Hope this can help you.

https://www.novixys.com/blog/generate-bitcoin-addresses-java/

[btcb3g1nn3r]

Can I just try sweeping this key? 0000000000000000000000000000000000000000000000000000000000000003
Is this something that an attacker can actually attempt to use, to try sweeping such randomly created keys (eg. as brute force) ?

Yep! You can sweep that key, it's a valid private key as it is within the range of 1 to (approx.) 1.15*10^77. But you mustn't. Attackers can easily brute-force such private keys. In-fact, any manually written private key isn't safe because humans are worst random generator. They are always tend to go for patterns which make the keys predictable.

I meant, one can generate such private keys "hoping" it will match an existing one then he/she can sweep it into a new wallet, eg. like an attacker would do.
You can always start with a good randomly generated private key then do some random changes using that initial key as seed. Is there any protection for such attempts?
Still I don't understand why uniqueness is not ensured by design, one centralized mirrored server could track all transactions queue.
People are winning lottery from time to time...from those cases when people are complaining about stolen funds, are they really sure it was their fault of just the current design?

[erikoy]

<snip>

I happen to get worried sometimes thinking that it would be possible that your wallet private key would also be generated to other wallets. Well, yes the the generation of private keys at random would be possible to get the same generated key by other users due to the vast private keys created that even compare to the pieces of sand. It will almost impossible to get the same private key at the same . Well, I hope that it will not going to happen on anyone one day.

[nc50lc]

As these addresses / private keys are generated there is always a probability that another address was already generated at a certain time in the past, as a matter a fact, I searched for one address I generated via bitaddress.org and I could find 2 of them on blockchain.com transactions explorer

FYI, the two results on blockchain.com explorer are for two different blockchains that support the same legacy address format, namely, Bitcoin (BTC) and Bitcoin Cash (BCH).

Plus most block explorers will show an address whether it's used or not; it just means that it has a valid checksum if there's a search result, the address is invalid if there's no search result.
It does not indicate that the address was already generated by someone.

[pooya87]

I meant, one can generate such private keys "hoping" it will match an existing one then he/she can sweep it into a new wallet, eg. like an attacker would do.
You can always start with a good randomly generated private key then do some random changes using that initial key as seed. Is there any protection for such attempts?

There is a protection against it and that is the vast range of valid keys. One can search for thousands of years and still not be able to cover a tiny portion of it.

People are winning lottery from time to time...from those cases when people are complaining about stolen funds, are they really sure it was their fault of just the current design?

Finding an already used key is like winning lottery every single time forever, after all lottery is just 1 in ~10 million chance!

[webtricks]

~snip~

I meant, one can generate such private keys "hoping" it will match an existing one then he/she can sweep it into a new wallet, eg. like an attacker would do.
You can always start with a good randomly generated private key then do some random changes using that initial key as seed. Is there any protection for such attempts?
Still I don't understand why uniqueness is not ensured by design, one centralized mirrored server could track all transactions queue.
People are winning lottery from time to time...from those cases when people are complaining about stolen funds, are they really sure it was their fault of just the current design?

You are seriously understating the magnitude of data size we have here. Even with the most advance devices having greatest of the computational power, you will most probably fail to brute-force even a single used private key created with strong RNG script in your lifetime. If someone's funds got stolen, it's either his own mistake or RNG used by his wallet to create private key is pretty weak.

No security system is unique by design, read this post:

The whole security system for bitcoin is not that it is impossible (which would be good) but that it is vvvveeerrryyy unlikely.

It is impossible to have a security system which is impossible to hack, and as far as security systems go, bitcoin's is pretty darn good.

Given that most 2FA codes are 6 digits long, there is a 1 in 10⁶ chance of someone guessing your 2FA code.
Assuming an average house lock as 8 tumblers, and each tumbler can adopt one of 10 positions, then there is a 1 in 10⁸ chance that someone will be able to guess your exact house key shape and unlock your door.
Given a standard credit card has a 15 or 16 digit number on it, there is at most a 1 in 10¹⁶ chance that someone will be able to guess your credit card number.
If you use a password manager to generate a long and totally random 16 character password, drawing from the full ASCII 95 character set of upper and lowercase letters, numbers, and symbols, (e.g. CY\u4"=t{rV%;N9S), there is a 1 in 4.4*10³¹ chance of someone guessing it.
The chance of someone guessing your private key is 1 in 1.158*10⁷⁷.

The chance of someone correctly guessing your password, your 2FA code, your credit card number, and the key to your house simultaneously is 4.4*10⁶¹, which is still around 2 thousand trillion times more likely than them guessing your private key.

[btcb3g1nn3r]

That's a "funny" quote and looks like  a "q.e.d"
The chances are increased when one is not targeting a particular address but any, the higher number of BTC users (valid keys) the higher chance someone will still have a hit, however the chances are still very low as the maths/probability can demonstrate.

I got hacked twice so far but still I don't know if it was due to poor password (which was not the case according to the specific tools around) or just a typical cpanel vulnerability that the hosting did not bother to patch or there was no patch by that time.
For an IT guy this kind of things are very frustrating when they happen

[o_e_l_e_o]

The chances are increased when one is not targeting a particular address but any

Given that we have only used around 700 million bitcoin addresses in total, then the search space reduction when moving from "a specific private key" to "any used private key" is only from 1.158*10⁷⁷ to 1.654*10⁶⁸, which is still astronomical and completely outside the realm of possibilities. Note as well that this is "any used private key" and not "any private key which is currently storing some coins", which would be a far smaller number.

I got hacked twice so far but still I don't know if it was due to poor password (which was not the case according to the specific tools around) or just a typical cpanel vulnerability that the hosting did not bother to patch or there was no patch by that time.

It sounds like you are storing your coins on an exchange or web wallet. These are notoriously insecure and infamous for users frequently having coins lost or stolen through a variety of means, anything from hacks and phishing through to scams and shut downs. The next thing you should spend some time learning about is how to download and run your own wallet so you (and only you) are in control of your private keys and your coins.

[btcb3g1nn3r]

not at all, my side comment was linked to a website I own hosted by a company that offered me cpanel access and I found under my account weird files (scripts) that were not mine, still no change on my pages.

I did not make the step to buy any crypto yet, I'm still in the learning phase, see my starter thread here: https://bitcointalk.org/index.php?topic=5301688.0

[o_e_l_e_o]

not at all, my side comment was linked to a website I own hosted by a company that offered me cpanel access and I found under my account weird files (scripts) that were not mine, still no change on my pages.

Ahh I see, I thought you were referring to bitcoin when talking about being hacked, not just in general. If you are planning on day trading as you suggest in your other thread, then unfortunately you simply have to store your coins with a third party centralized exchange, and accept all the risks that come with doing so - hacks, phishing, scams, insolvency, KYC, locked accounts, frozen funds, exchange down time, refusal of service, and so on. All the other options for buying and selling cryptocurrency take too long - from minutes to days - which is unacceptable when you are trying to day trade.

If you decide against day trading, or any funds/profits you are not using for day trading, should be withdrawn from the exchange immediately and stored in your own wallet to reduce the risk of hacks or thefts. Provided you have used a good open source wallet and generated your keys securely (even better if you have used an offline cold storage set up), then the chance of your coins being stolen by a random private key or address collision are essentially zero.

[btcb3g1nn3r]

Do you have by chance some maths/probability calculation for one attacker attempting to hit a 12 words seed for Electrum wallet? I guess the possibilities are higher than using random private key of 32 characters as brute force can be done using a dictionary?
I see a thread about an Electrum wallet hacked while its seed was on paper (of course no details under which conditions that seed was created).

[ranochigo]

Do you have by chance some maths/probability calculation for one attacker attempting to hit a 12 words seed for Electrum wallet? I guess the possibilities are higher than using random private key of 32 characters as brute force can be done using a dictionary?
I see a thread about an Electrum wallet hacked while its seed was on paper (of course no details under which conditions that seed was created).

There are 2048 words in a BIP39 English wordlist . Total number of possibility is 2048^12, each word should provide 11 bits of security putting the seed at 132bits of security.

The number of permutations is so astronomically large, I don't expect my seed to be in danger more than my randomly generated ECDSA key.