Pages:
Author

Topic: Isn't the output of SHA256 *slightly* too big to use for a private key? - page 2. (Read 4437 times)

hero member
Activity: 560
Merit: 517
Quote
but is this what the default Bitcoin behavior is?
What do you mean by "default Bitcoin"?  You mean Bitcoin-QT?  Bitcoin-QT picks a random integer in the appropriate range; it doesn't use SHA-256.  So, it doesn't have this problem.  Brainwallets use SHA-256.  HD wallets use HMAC_SHA512.  Are you referring to any of those in particular?

The correct response, if using SHA-256 to generate a key, is to reject the key and try again.

As pointed out though, it's all moot when writing an application.  When writing a standard you'd want to get details like this right.  But during implementation this isn't important, because the code you write to check for it will never trigger.
legendary
Activity: 2646
Merit: 1137
All paid signature campaigns should be banned.
The probability to hash above n is 1/2^128, so it should be considered practically impossible to achieve.

Actually (2256 - n) / 2256 = 1 - n / 2256, which is very close to zero.
legendary
Activity: 1008
Merit: 1000
So, do brainwallet.org or any of the other brainwallet sites reject pass phrases that happen to hash above n?

The probability to hash above n is 1/2^128, so it should be considered practically impossible to achieve.


I realize that this is very improbable... but for my own understanding of how Bitcoin works, I am interested to know what happens if you generate a private key integer that is greater than n...

I actually implemented my own (very inefficient) version of the ECDSA algorithm, so I know that you can pick a private key outside of the range and the algorithm could still function just fine (by wrapping around)... but is this what the default Bitcoin behavior is?

hero member
Activity: 555
Merit: 654
So, do brainwallet.org or any of the other brainwallet sites reject pass phrases that happen to hash above n?

The probability to hash above n is 1/2^128, so it should be considered practically impossible to achieve.
legendary
Activity: 2646
Merit: 1137
All paid signature campaigns should be banned.
So, do brainwallet.org or any of the other brainwallet sites reject pass phrases that happen to hash above n?
newbie
Activity: 12
Merit: 0
If the output of the SHA256 is greater than n it will just "wrap around" and work.

Although, now that I think about it, if the output of your SHA256 was exactly n that would probably cause a problem.

But then, the probablity of the output of the SHA256 being exactly n is 1 / 2256

You should not "wrap around" or reduce your integer modulo n.

If your integer is == 0 or or >= n, then you should discard it completely and generate a new private key using a new secret. Otherwise you would be introducing a bias towards lower-valued private keys.
newbie
Activity: 12
Merit: 0
If the order of the elliptic curve in Bitcoin is some number slightly less than 2^256, then why is it OK to use the SHA256 hash of some input as a private key? My (steadily growing) understanding of ECDSA is that the private key must be some integer between 1 and the order of the curve, which is :

Code:
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Sorry if this has been asked 1000 times already...

Valid private keys are integers between 1 and n-1. If you get an integer >= n when hashing some secret, then that integer is an invalid private key. It would be a mistake to reduce that integer modulo n as it would introduce a bias towards lower values. The probability of that happening is relatively low however.
legendary
Activity: 2646
Merit: 1137
All paid signature campaigns should be banned.
If the output of the SHA256 is greater than n it will just "wrap around" and work.

Although, now that I think about it, if the output of your SHA256 was exactly n that would probably cause a problem.

But then, the probablity of the output of the SHA256 being exactly n is 1 / 2256
legendary
Activity: 1008
Merit: 1000
If the order of the elliptic curve in Bitcoin is some number slightly less than 2^256, then why is it OK to use the SHA256 hash of some input as a private key? My (steadily growing) understanding of ECDSA is that the private key must be some integer between 1 and the order of the curve, which is :

Code:
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Sorry if this has been asked 1000 times already...
Pages:
Jump to: