How to generate a private key?

[Dabs]

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).

[wumpus]

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.

[Dabs]

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.

[wumpus]

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.

[proff]

I am glad to see you are taking randomness seriously

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.

[Shevek]

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.

[kjj]

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

[Dabs]

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:

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.

[proff]

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.

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??

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:

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...

[Dabs]

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.

[proff]

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.

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.

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?

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.

[Dabs]

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.

[Shevek]

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

• http://www.random.org/bytes/
• https://www.fourmilab.ch/hotbits/secure_generate.html

[bitfreak!]

Quantum randomness is the best randomness.

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

EDIT: here's a description from the website, very interesting stuff:

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.

[r.willis]

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).

[Dabs]

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.

[Zeilap]

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.