Isn't the output of SHA256 *slightly* too big to use for a private key? - page 2.

fpgaminer

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.

BurtW

legendary

Activity: 2646

Merit: 1138

All paid signature campaigns should be banned.

Quote from: Sergio_Demian_Lerner on October 09, 2013, 02:24:05 PM

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

Actually (2²⁵⁶ - n) / 2²⁵⁶ = 1 - n / 2²⁵⁶, which is very close to zero.

chriswilmer

legendary

Activity: 1008

Merit: 1000

Quote from: Sergio_Demian_Lerner on October 09, 2013, 02:24:05 PM

Quote from: BurtW on October 09, 2013, 02:17:51 PM

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?

Sergio_Demian_Lerner

hero member

Activity: 555

Merit: 654

Quote from: BurtW on October 09, 2013, 02:17:51 PM

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.

BurtW

legendary

Activity: 2646

Merit: 1138

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?

plaprade

newbie

Activity: 12

Merit: 0

Quote from: BurtW on October 09, 2013, 02:05:34 PM

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 / 2²⁵⁶.

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.

plaprade

newbie

Activity: 12

Merit: 0

Quote from: chriswilmer on October 09, 2013, 02:02:01 PM

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.

BurtW

legendary

Activity: 2646

Merit: 1138

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 / 2²⁵⁶.

chriswilmer

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

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

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