Bitcoin Forum

Bitcoin => Bitcoin Discussion => Topic started by: remotemass on March 23, 2013, 10:56:39 AM



Title: Indeed, almost any 256-bit number can be a private key
Post by: remotemass on March 23, 2013, 10:56:39 AM
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.

Doing the math:
99.99999999999999999999999999999999999962655446549599% of the 256-bit numbers can be used as private keys.

http://www.wolframalpha.com/input/?i=115792089237316195423570985008687907852837564279074904382605163141518161494337%2F115792089237316195423570985008687907853269984665640564039457584007913129639935 (http://www.wolframalpha.com/input/?i=115792089237316195423570985008687907852837564279074904382605163141518161494337%2F115792089237316195423570985008687907853269984665640564039457584007913129639935)


Title: Re: Indeed, almost any 256-bit number can be a private key
Post by: markm on March 23, 2013, 11:04:17 AM
I didn't know there were any that cannot be used. Hmm now you have me wondering why some cannot be used.

-MarkM-


Title: Re: Indeed, almost any 256-bit number can be a private key
Post by: prezbo on March 23, 2013, 11:12:10 AM
I didn't know there were any that cannot be used. Hmm now you have me wondering why some cannot be used.

-MarkM-

There really is no reason why they coulnd't be used. Yes, the group order is less than 2^256, but even a larger number would work - it just wouldn't be very efficient.


Title: Re: Indeed, almost any 256-bit number can be a private key
Post by: remotemass on March 23, 2013, 11:17:14 AM
I didn't know there were any that cannot be used. Hmm now you have me wondering why some cannot be used.

I don't know enough about elliptic curves to make you more clear on that.
But note that the public key is made of 65 bytes. The first byte is always 0x04, I think, and the next pair of 32 bytes correspond to the (x,y) coordinates of a point in the curve.
So the reason must be that because not all points (x,y) can be used, so that not all public keys can be used and therefore not all private keys.
Just my thoughts about it. I actually have not much clues about Elliptic Curves stuff. This is as much as I get of it.


Title: Re: Indeed, almost any 256-bit number can be a private key
Post by: prezbo on March 23, 2013, 11:24:45 AM
I didn't know there were any that cannot be used. Hmm now you have me wondering why some cannot be used.

I don't know enough about elliptic curves to make you more clear on that.
But note that the public key is made of 65 bytes. The first byte is always 0x04, I think, and the next pair of 32 bytes correspond to the (x,y) coordinates of a point in the curve.
So the reason must be that because not all points (x,y) can be used, so that not all public keys can be used and therefore not all private keys.
Just my thoughts about it. I actually have not much clues about Elliptic Curves stuff. This is as much as I get of it.

Elliptic curves form a group under addition. The private key is an integer, while the public key is a point on the group, so if n is a private key, and G is the "base" point, then n*G = G+G+...+G would be the public key corresponding to n. There is no bound on how large n can be, since a group is closed under it's operator.

Having said that, even though every number *can* be used as a private key, the set of numbers {n, n+R, n+2R, ...} will have the same corresponding public keys, where R is the order of the base element G (and usually also the order of the group itself).


Title: Re: Indeed, almost any 256-bit number can be a private key
Post by: remotemass on March 23, 2013, 11:42:42 AM
Elliptic curves form a group under addition. The private key is an integer, while the public key is a point on the group, so if n is a private key, and G is the "base" point, then n*G = G+G+...+G would be the public key corresponding to n. There is no bound on how large n can be, since a group is closed under it's operator.

Can the G that you mention, the "base" point, be expressed with (X,Y) coordinates?

I barely understand Elliptic Curves with real numbers, but I suppose ECDSA uses Elliptic Curves over Finite Fileds (or is it over Prime Field?!).

I'm still trying to figure if we use a curve or a set of curves.

Can you, give me an idea of how secp256k1 curve and its relevant points look like in a cartesian way? Or it does not work like that at all?!  ??? ::)


Title: Re: Indeed, almost any 256-bit number can be a private key
Post by: kokjo on March 23, 2013, 11:50:04 AM
I didn't know there were any that cannot be used. Hmm now you have me wondering why some cannot be used.

-MarkM-

its because the prime number chosen for secp256k1 is just a little less then 2^256

0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141 is that prime number in hexadecimal.


Title: Re: Indeed, almost any 256-bit number can be a private key
Post by: prezbo on March 23, 2013, 11:51:41 AM
Elliptic curves form a group under addition. The private key is an integer, while the public key is a point on the group, so if n is a private key, and G is the "base" point, then n*G = G+G+...+G would be the public key corresponding to n. There is no bound on how large n can be, since a group is closed under it's operator.

Can the G that you mention, the "base" point, be expressed with (X,Y) coordinates?

I barely understand Elliptic Curves with real numbers, but I suppose ECDSA uses Elliptic Curves over Finite Fileds (or is it over Prime Field?!).

I'm still trying to figure if we use a curve or a set of curves.

Can you, give me an idea of how secp256k1 curve and its relevant points look like in a cartesian way? Or it does not work like that at all?!  ??? ::)


Certainly. secp256k1 is defined over one, predefined elliptic curve. The base point is also predetermined, usually a group generator (http://mathworld.wolfram.com/GroupGenerators.html). The group operator (+) is defined in a purely geometric way as shown in this picture
http://voltage.typepad.com/.a/6a00e55375ef1c88330153903eca0c970b-320wi,
here P1+P2 = P3.

You can find some more information on secp256k1 in this pdf (http://www.secg.org/collateral/sec2_final.pdf). Note that the order of base point G is exactly the number you specified in your OP.


Title: Re: Indeed, almost any 256-bit number can be a private key
Post by: remotemass on March 23, 2013, 11:57:26 AM

what is u and v, in that image?
I am so glad I am learning this stuff  :D


Title: Re: Indeed, almost any 256-bit number can be a private key
Post by: prezbo on March 23, 2013, 12:09:41 PM
what is u and v, in that image?
I am so glad I am learning this stuff  :D
Probably just line identifiers. This was the best picture I could find quickly :)


Title: Re: Indeed, almost any 256-bit number can be a private key
Post by: remotemass on March 23, 2013, 12:17:24 PM
How many points does secp256k1 curve actually have?
And what is this (+), as defined, used for? (regarding them)

The image you provide is very good to understand the (+) operation but still gives me with no clue of how secp256k1 curve and its points look like  :(