Bitcoin Forum
November 22, 2017, 11:59:05 AM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: How to generate a private key?  (Read 3136 times)
Dabs
Staff
Legendary
*
Offline Offline

Activity: 1876



View Profile
April 02, 2013, 07:25:41 AM
 #1

Hi,

According to the wiki:

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.

So, how would one go about generating a random private key? I just use some random number generator or a hash of some text (in the case of brain wallet keys), make sure that it fits in the range, and if it does, it's good. If not, make a new random one, or if it's a hash, increment a nonce for that hash. Then check to make sure that it fits in the range. Repeat until you get a good private key.

For the randomly generated keys, I understand that using regular PRNGs are not a good idea, but used together with SHA256, along with other inputs (time? mouse movements? keyboard timing entries, or even what is actually typed, external files that you are sure no one else has, or external files that are randomly generated by a trusted PRNG), it might be "acceptable".

I could also use OpenSSL RNG, but that might be more difficult.

From there, it's a matter of following the logic to create the WIF private key, the public key, and to make them with the compressed flag.

As a personal project, I'd like to create a program that does this in basic (visual basic or power basic) for Windows. I know and I've seen there are C versions for Linux and pre-compiled binaries for Windows (vanitygen) and even java (bitaddress, brainwallet).

Escrow Service (Services) - GPG ID: 32AD7565, OTC ID: Dabs
All messages concerning escrow or with bitcoin addresses are GPG signed. Please verify.
CompTIA A+, Microsoft Certified Professional, MCSA: Windows 10; Windows Server 2012, MCSE: Cloud Platform and Infrastructure; Productivity; Messaging
1511351945
Hero Member
*
Offline Offline

Posts: 1511351945

View Profile Personal Message (Offline)

Ignore
1511351945
Reply with quote  #2

1511351945
Report to moderator
1511351945
Hero Member
*
Offline Offline

Posts: 1511351945

View Profile Personal Message (Offline)

Ignore
1511351945
Reply with quote  #2

1511351945
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1511351945
Hero Member
*
Offline Offline

Posts: 1511351945

View Profile Personal Message (Offline)

Ignore
1511351945
Reply with quote  #2

1511351945
Report to moderator
1511351945
Hero Member
*
Offline Offline

Posts: 1511351945

View Profile Personal Message (Offline)

Ignore
1511351945
Reply with quote  #2

1511351945
Report to moderator
wumpus
Hero Member
*****
qt
Offline Offline

Activity: 812

No Maps for These Territories


View Profile
April 02, 2013, 07:29:03 AM
 #2

Use a cryptographically secure random number generator. For example, that of OpenSSL, or the /dev/random equivalent of your OS.

I recommend heavily against trying to roll anything yourself.

Bitcoin Core developer [PGP] Warning: For most, coin loss is a larger risk than coin theft. A disk can die any time. Regularly back up your wallet through FileBackup Wallet to an external storage or the (encrypted!) cloud. Use a separate offline wallet for storing larger amounts.
Wolf0
Legendary
*
Offline Offline

Activity: 1750


Miner Developer


View Profile
April 02, 2013, 09:02:59 PM
 #3

If you're on Windows, CryptGenRandom will do. PM me or reply if you want help with deriving the public key from the private key, and getting the corresponding Bitcoin address and all that.

Code:
Donations: BTC: 1WoLFdwcfNEg64fTYsX1P25KUzzSjtEZC -- XMR: 45SLUTzk7UXYHmzJ7bFN6FPfzTusdUVAZjPRgmEDw7G3SeimWM2kCdnDQXwDBYGUWaBtZNgjYtEYA22aMQT4t8KfU3vHLHG
Dabs
Staff
Legendary
*
Offline Offline

Activity: 1876



View Profile
April 03, 2013, 01:28:12 AM
 #4

I will do it in both Visual Basic (classic, or version 6) and maybe Power Basic for Windows. I can probably read C source code and do the translation to basic.

The most secure is to of course use CryptGenRandom, but I remember doing that a few years ago, and it takes awhile to get started. I don't know if subsequent calls to that function is faster. I want my little program to generate keys a little bit faster than java based generators (like bitaddress) and if possible, as fast as, or faster than vanitygen.

Perhaps ideally, I would want a simple command line tool, so I'm also thinking of just doing it completely in C.

Since this is a learning process for me, I will attempt to derive the public key using the steps as explained in the wiki. Or, maybe I could just dig in to the actual source code of the reference client; I haven't tried doing that, I don't know if I can make sense of it.

Escrow Service (Services) - GPG ID: 32AD7565, OTC ID: Dabs
All messages concerning escrow or with bitcoin addresses are GPG signed. Please verify.
CompTIA A+, Microsoft Certified Professional, MCSA: Windows 10; Windows Server 2012, MCSE: Cloud Platform and Infrastructure; Productivity; Messaging
Wolf0
Legendary
*
Offline Offline

Activity: 1750


Miner Developer


View Profile
April 03, 2013, 03:14:22 AM
 #5

I will do it in both Visual Basic (classic, or version 6) and maybe Power Basic for Windows. I can probably read C source code and do the translation to basic.

The most secure is to of course use CryptGenRandom, but I remember doing that a few years ago, and it takes awhile to get started. I don't know if subsequent calls to that function is faster. I want my little program to generate keys a little bit faster than java based generators (like bitaddress) and if possible, as fast as, or faster than vanitygen.

Perhaps ideally, I would want a simple command line tool, so I'm also thinking of just doing it completely in C.

Since this is a learning process for me, I will attempt to derive the public key using the steps as explained in the wiki. Or, maybe I could just dig in to the actual source code of the reference client; I haven't tried doing that, I don't know if I can make sense of it.

I wrote a utility that does this, you might find it easier to study my C code.

Code:
Donations: BTC: 1WoLFdwcfNEg64fTYsX1P25KUzzSjtEZC -- XMR: 45SLUTzk7UXYHmzJ7bFN6FPfzTusdUVAZjPRgmEDw7G3SeimWM2kCdnDQXwDBYGUWaBtZNgjYtEYA22aMQT4t8KfU3vHLHG
wumpus
Hero Member
*****
qt
Offline Offline

Activity: 812

No Maps for These Territories


View Profile
April 03, 2013, 03:57:13 AM
 #6

The most secure is to of course use CryptGenRandom, but I remember doing that a few years ago, and it takes awhile to get started.
It's slower because it takes all kinds of precautions to be secure. Secure PRNGs are usually more computationally expensive than simple, insecure ones, and it for example has to make sure there is enough entropy available in the pool.

If it's only for a learning experiment it doesn't matter. But if you intend to integrate this into a public service or program whatsoever, please make sure it is secure. Otherwise someone on the world figuring out a statistic flaw can plunder all the coins from the generated private keys.

Bitcoin Core developer [PGP] Warning: For most, coin loss is a larger risk than coin theft. A disk can die any time. Regularly back up your wallet through FileBackup Wallet to an external storage or the (encrypted!) cloud. Use a separate offline wallet for storing larger amounts.
proff
Jr. Member
*
Offline Offline

Activity: 46


View Profile
April 03, 2013, 12:09:35 PM
 #7

I am glad to see you are taking randomness seriously Smiley

How many random bits do you need? Unless you are generating many, many keys, the PRNG should not be a bottleneck. There are also hardware-based RNGs.

The order of the base point of secp256k1 is not quite 2^256, as you noticed, but it is so close that generating 256 random bits and throwing away out-of-range values (on the remote chance you ever get one) is not a problem, and that way (after doing all the arithmetic) you will end up with a point uniformly distributed on the curve.

Want to learn more? Consulting / tutoring / distance learning available. PM me !
Support open-access research! Please donate: 123456hi6ofP4zAEbddqiN4Dn5m8gdXXdU
Shevek
Sr. Member
****
Offline Offline

Activity: 252



View Profile
April 03, 2013, 02:33:51 PM
 #8

There is two approaches on the web to solve the problem: the isotope decay and the radioelectric noise.

The first is used by hotbits: http://fourmilab.ch/hotbits/ And the second is used by random.org: http://random.org

If you can't build this machinery, you can download a certain amount of bits (say ~1000) from each source (via the secure server) and concatenate with the result of your /dev/random device. Hash the result and you've got it.

Proposals for improving bitcoin are like asses: everybody has one
1SheveKuPHpzpLqSvPSavik9wnC51voBa
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
April 03, 2013, 02:38:20 PM
 #9

New-ish Intel CPUs have the RDRAND opcode that appears to be suitable for generating high quality random bits.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
Dabs
Staff
Legendary
*
Offline Offline

Activity: 1876



View Profile
April 04, 2013, 03:53:40 AM
 #10

Actually, I've had this idea of using frequently changing websites, including the random number websites, however, they are all still on the internet. No matter what anyone says, even if it were through a secure session (SSL, TLS) it still came from somewhere else.

Random numbers can be generated from hashes of all of those, and then include local (specific to the computer you are using) unpredictable numbers, such as mouse input, keyboard input, hard drive input, operating system input, pictures of lava lamps, pictures of the sky or the ocean or your aquarium. But these are all already provided for by CryptGenRandom or /dev/random.

How about, I use a fast PRNG together with the slow CryptGenRandom as the seed? Or I do something like this:

1. Get a 256-bit number seed from CryptGenRandom.
2. Hash this number with SHA256
3. add 1 to the original number
4. Hash this next number with SHA256.
5. Rinse, Repeat.

Basically use CryptGenRandom as the basis for the next bunch of operations, which can be a hash, or blum blum shub or mersenne or something.

According to some other internet something I read somewhere:
Quote
One good trick for generating very good non-random-but-nearly-random bits is to use /dev/random's entropy to seed a fast symmetric stream cipher, and redirect it's output to the application that needs it.

I could also use AES in some sort of counter mode.

For purposes of discussion, can I safely assume that CryptGenRandom on Windows is equivalent to /dev/random on Linux ?

For truly secure purposes, I am guessing that I will have to call CryptGenRandom for each brand new private key I want to generate.

Escrow Service (Services) - GPG ID: 32AD7565, OTC ID: Dabs
All messages concerning escrow or with bitcoin addresses are GPG signed. Please verify.
CompTIA A+, Microsoft Certified Professional, MCSA: Windows 10; Windows Server 2012, MCSE: Cloud Platform and Infrastructure; Productivity; Messaging
proff
Jr. Member
*
Offline Offline

Activity: 46


View Profile
April 04, 2013, 10:50:49 AM
 #11

Actually, I've had this idea of using frequently changing websites, including the random number websites, however, they are all still on the internet. No matter what anyone says, even if it were through a secure session (SSL, TLS) it still came from somewhere else.
Whether you are just generating a couple of keys for your personal experimental use or running a commercial site that needs a secure wallet, the poster did not mean you need to or should rely on external web sites to get random numbers. The point is that you can obtain data from multiple sources (web sites, stock prices, your own hardware/software) and then "distill" the resulting entropy.

Quote
Random numbers can be generated from hashes of all of those, and then include local (specific to the computer you are using) unpredictable numbers, such as mouse input, keyboard input, hard drive input, operating system input, pictures of lava lamps, pictures of the sky or the ocean or your aquarium. But these are all already provided for by CryptGenRandom or /dev/random.
So the issue is that you do not trust the PRNG provided by the operating system (/dev/random, CryptGenRandom) even with a truly random entropy source seeding it??

Quote
How about, I use a fast PRNG together with the slow CryptGenRandom as the seed? Or I do something like this:

1. Get a 256-bit number seed from CryptGenRandom.
2. Hash this number with SHA256
3. add 1 to the original number
4. Hash this next number with SHA256.
5. Rinse, Repeat.

Basically use CryptGenRandom as the basis for the next bunch of operations, which can be a hash, or blum blum shub or mersenne or something.

According to some other internet something I read somewhere:
Quote
One good trick for generating very good non-random-but-nearly-random bits is to use /dev/random's entropy to seed a fast symmetric stream cipher, and redirect it's output to the application that needs it.

I could also use AES in some sort of counter mode.

For purposes of discussion, can I safely assume that CryptGenRandom on Windows is equivalent to /dev/random on Linux ?

For truly secure purposes, I am guessing that I will have to call CryptGenRandom for each brand new private key I want to generate.
One can use SHA or AES-CBC-MAC or whatever to distill/condition entropy, but... so you do trust the OS-provided CryptGenRandom or /dev/random to gather entropy from electronic thermal noise, OS latency, pictures of lava lamps, but do not trust their conditioning or PRNG? Why use it at all then?

I re-iterate what was said about not "rolling your own", but if you want to implement the PRNG yourself then look up e.g. the Fortuna algorithm in Practical Cryptography. Add a couple of lava lamps and you will be good to go...

Want to learn more? Consulting / tutoring / distance learning available. PM me !
Support open-access research! Please donate: 123456hi6ofP4zAEbddqiN4Dn5m8gdXXdU
Dabs
Staff
Legendary
*
Offline Offline

Activity: 1876



View Profile
April 05, 2013, 01:50:03 AM
 #12

I do trust /dev/random or CryptGenRandom. The question is, what is the harm in adding additional bits of entropy from other sources?

If you get any of them compromised (for whatever reason), the additional bits might help, won't it?

I read that one password generating program uses the high performance counter or high resolution timer. Specifically PWGen uses these two (in order of descending priority):

1. Time stamp counter (RDTSC instruction): The RDTSC processor instruction returns the number (64-bit) of cycles since reset.
2. QueryPerformanceCounter (Windows API function): According to the Windows SDK, this function returns the current value (64-bit) of the high-performance counter. This is probably just a wrapper for the time stamp counter on most systems, but the return value may be different on multicore computers. Calling this function is slower than executing RDTSC.

I mean, maybe there is no reason for me to use anything else aside from CryptGenRandom, and possibly add one or two readings of the high resolution timer.

All I want to do is generate a 256 bit number, then check if that is a valid private key, and go from there.

Escrow Service (Services) - GPG ID: 32AD7565, OTC ID: Dabs
All messages concerning escrow or with bitcoin addresses are GPG signed. Please verify.
CompTIA A+, Microsoft Certified Professional, MCSA: Windows 10; Windows Server 2012, MCSE: Cloud Platform and Infrastructure; Productivity; Messaging
proff
Jr. Member
*
Offline Offline

Activity: 46


View Profile
April 05, 2013, 09:29:39 AM
 #13

I do trust /dev/random or CryptGenRandom. The question is, what is the harm in adding additional bits of entropy from other sources?
No harm; on some (most?) systems you can write data to /dev/random for this purpose.

Quote
If you get any of them compromised (for whatever reason), the additional bits might help, won't it?
Yes, entropy is supposed to be gathered from multiple independent sources and processed to reseed the generator. As long as there is at least one source that is unpredictable to the attacker you should be OK. Did you read the chapter on the implementation of Fortuna?

Note, if your entire system is compromised, you have other things to worry about than the random-number generator. What a cryptographic PRNG is designed to deal with are cryptographic attacks, like reconstructing its internal state, though I am not sure which attack scenario you are envisioning where you have to worry about such attacks on your RNG but your system isn't otherwise completely owned anyway.

Quote
I read that one password generating program uses the high performance counter or high resolution timer. Specifically PWGen uses these two (in order of descending priority):

1. Time stamp counter (RDTSC instruction): The RDTSC processor instruction returns the number (64-bit) of cycles since reset.
2. QueryPerformanceCounter (Windows API function): According to the Windows SDK, this function returns the current value (64-bit) of the high-performance counter. This is probably just a wrapper for the time stamp counter on most systems, but the return value may be different on multicore computers. Calling this function is slower than executing RDTSC.
That's it? No keystrokes, mouse movement, etc?

Quote
I mean, maybe there is no reason for me to use anything else aside from CryptGenRandom, and possibly add one or two readings of the high resolution timer.

All I want to do is generate a 256 bit number, then check if that is a valid private key, and go from there.
Just use CryptGenRandom. Or, if you do not trust Microsoft, a different OS/implementation; I gave you at least one reference.

Want to learn more? Consulting / tutoring / distance learning available. PM me !
Support open-access research! Please donate: 123456hi6ofP4zAEbddqiN4Dn5m8gdXXdU
Dabs
Staff
Legendary
*
Offline Offline

Activity: 1876



View Profile
April 05, 2013, 01:56:30 PM
 #14

That's it? No keystrokes, mouse movement, etc?

It times the difference between keystrokes and mouse movements, according to the manual. I have not yet checked the source code, but I'm pretty sure it does that and then some.

Escrow Service (Services) - GPG ID: 32AD7565, OTC ID: Dabs
All messages concerning escrow or with bitcoin addresses are GPG signed. Please verify.
CompTIA A+, Microsoft Certified Professional, MCSA: Windows 10; Windows Server 2012, MCSE: Cloud Platform and Infrastructure; Productivity; Messaging
Shevek
Sr. Member
****
Offline Offline

Activity: 252



View Profile
April 05, 2013, 02:37:04 PM
 #15

Again: don't miss the free entropy servers on the web:


Proposals for improving bitcoin are like asses: everybody has one
1SheveKuPHpzpLqSvPSavik9wnC51voBa
bitfreak!
Legendary
*
Offline Offline

Activity: 1535


electronic [r]evolution


View Profile WWW
April 05, 2013, 04:00:11 PM
 #16

Quantum randomness is the best randomness.

https://qrng.anu.edu.au/

EDIT: here's a description from the website, very interesting stuff:
Quote
This website offers true random numbers to anyone on the internet. The random numbers are generated in real-time in our lab by measuring the quantum fluctuations of the vacuum. The vacuum is described very differently in the quantum mechanical context than in the classical context. Traditionally, a vacuum is considered as a space that is empty of matter or photons. Quantum mechanically, however, that same space resembles a sea of virtual particles appearing and disappearing all the time. This result is due to the fact that the vacuum still possesses a zero-point energy. Consequently, the electromagnetic field of the vacuum exhibits random fluctuations in phase and amplitude at all frequencies. By carefully measuring these fluctuations, we are able to generate ultra-high bandwidth random numbers.

XCN: CYsvPpb2YuyAib5ay9GJXU8j3nwohbttTz | BTC: 18MWPVJA9mFLPFT3zht5twuNQmZBDzHoWF
Cryptonite - 1st mini-blockchain altcoin | BitShop - digital shop script
Web Developer - PHP, SQL, JS, AJAX, JSON, XML, RSS, HTML, CSS
r.willis
Jr. Member
*
Offline Offline

Activity: 42


View Profile
April 06, 2013, 09:10:46 PM
 #17

Quote
base point of secp256k1 is not quite 2^256
You meant curve order, do you? Base point is G, and it's point on curve.
Dabs, if you want to implement Elliptic curve cryptography, you absolutely need bignum support (at least, for secp256k1 curve, as it uses prime order field).
Then you need to implement field arithmetic: addition, subtraction, negation, multiplication and inversion.
After that, you'll implement EC arithmetic: addition, subtraction, negation, doubiling and, finally, point multiplication.
Once you got p. mul., it's easy to generate public key from private: it's point multiplication of private key and G, base point of the curve (followed with some really simple encoding).
I actually implemented this today in erlang (minus encoding part, that's for tomorrow).

1GVmS56pvVL7YZA7YqMBXmaDedCoputKuJ BitEN - Bitcoin Erlang Node
Dabs
Staff
Legendary
*
Offline Offline

Activity: 1876



View Profile
April 07, 2013, 05:47:14 AM
 #18

There's got to be a simple way to get the public key from the private key. Generating the private key is easy. Just make a random number, then check for proper range of values.

Then to convert the new private key into wallet import format (base58check) is also easy, I think. A few lines of code.


Escrow Service (Services) - GPG ID: 32AD7565, OTC ID: Dabs
All messages concerning escrow or with bitcoin addresses are GPG signed. Please verify.
CompTIA A+, Microsoft Certified Professional, MCSA: Windows 10; Windows Server 2012, MCSE: Cloud Platform and Infrastructure; Productivity; Messaging
Zeilap
Full Member
***
Offline Offline

Activity: 154


View Profile
April 07, 2013, 05:53:15 AM
 #19

There's got to be a simple way to get the public key from the private key. Generating the private key is easy. Just make a random number, then check for proper range of values.

Then to convert the new private key into wallet import format (base58check) is also easy, I think. A few lines of code.



Yes, once you have your elliptic curve code, you just multiply your private key by the generator point of the elliptic curve. The public key is then simply 0x04 followed by the x and y coordinates, 32 bytes for each.

1GLeSqooAPe8PfWbJecnL3AteDac2B3cqj
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!