Bitcoin Forum
August 13, 2020, 03:10:55 AM *
News: Latest Bitcoin Core release: 0.20.0 [Torrent]
   Home   Help Search Login Register More  
Pages: [1]
Author Topic: Isn't doing % N while generating a random key a flaw?  (Read 166 times)
Coding Enthusiast
Offline Offline

Activity: 812
Merit: 1567

Bitcoin and C♯ Enthusiast

View Profile WWW
September 26, 2018, 04:23:37 PM
Merited by suchmoon (4), HeRetiK (1)

I have been going around and reading a lot of ECC code lately, and recently I realized some of them do something that at first sight seems harmless but I think can potentially cause some bugs. But I am not sure!

Basically when generating a new key they generate a new 256 bit number (byte[32]) then they calculate I256 % n (I being the 256 bit number equivalent) to make sure it falls within range of curve values.

Here is the problem. A 256 bit number can be as big as
While the order of the curve (for example secp256k1 that bitcoin uses):
So the difference would be:
(Which is 17 bytes by the way).

So technically you can end up with a number that is between n and 2256 and eventually because of that mod end up with a key with little entropy. For example if I256 is n+1 you will end up with private key 1 while the byte[32] was random and big enough.

I guess my question is whether this chance is too small that it doesn't matter or is it in fact a flaw in this type of implementation?

Projects List+Suggestion box
Donate: 1Q9s or bc1q
Hero Member
Offline Offline

Posts: 1597288255

View Profile Personal Message (Offline)

Reply with quote  #2

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

Activity: 2940
Merit: 1626

View Profile
September 26, 2018, 05:21:12 PM
Last edit: September 26, 2018, 05:32:37 PM by odolvlobo

A random number generator will occasionally give you a value of 1, so the fact that I256 % n can be 1 does not make it not random. If I256 is generated randomly, then I256 % n is also random regardless of what the resulting value is, though you could say the result is very slightly less random in this case because the distribution is not uniform.

Buy stuff on Amazon with BTC or convert Amazon points to BTC here:
Join an anti-signature campaign: Click ignore on the members of signature campaigns.
Sr. Member
Offline Offline

Activity: 490
Merit: 329

Do not trust the government

View Profile
September 26, 2018, 06:28:25 PM

It isn't a big issue.

This just means that those 432420386565659656852420866394968145598 first numbers are twice more likely to occur in the generator then they would naturally.

If you pick a random number between 0 and 2256, there is 1 in 2120 chance that it will be in the range between 0 and 2136. Due to this suboptimal behaviour, it will be 1 in 2119, so not a big difference when it comes to security.

So as an attacker, you would likely want to start by searching that keyspace first at the beginning, although the key will be there only once in 2119 keys that you try to break, but it is still a bit more likely to be there then any other range of same size in that keyspace, so it is a nice optimization technique if you are braking a lot of keys.

Technically it is a flaw, since using this for an attack is slightly better then brute force, but I assume many brute force implementations would have this optimization by an accident, simply because it makes sense to start at the beginning, perhaps, if the numbers are random.
Offline Offline

Activity: 2086
Merit: 2466

Use SegWit and enjoy lower fees.

View Profile WWW
September 26, 2018, 06:56:39 PM

Since the biggest valid value of the secp256k1 is known, the code simply shouldn't use invalid key created from out-of-range value. But some implementation automatically check whether the value is bigger than biggest valid value, so IMO you don't need to worry about it.

Offline Offline

Activity: 3150
Merit: 4169

View Profile
September 27, 2018, 12:27:56 AM
Merited by Foxpup (4), suchmoon (4), ETFbitcoin (1), HeRetiK (1), Coding Enthusiast (1)

Using a 256 bit number mod N will result in a key with less entropy but not in the way you think.

Imagine you had an random number generator that generated a key perfectly uniformly.  It could possibly generate a small value. That small value doen't have "less entropy"  all values out of it have the same entropy (just under 256 bits).

256-bits Mod N results in less entropy because it makes small values more likely: It could generate a small value directly, or by wrapping a big value.  But a big value can only be found directly.

But for secp256k1 N is so ridiculously close to 2^256, relative to the size the amount of bias created is very tiny. Other than with a broken RNG, a wrapping event will probably never happen to anyone ever much less enough of them to account for a meaningful bias.    For some other curves, however, N is not near a power of 2, and wrapping may result in enough bias to actually matter.

The normal way to avoid this problem is to use rejection sampling:  If your random ceil(log2(N)) bit number is greater than N, throw it out and generate a new random number. This eliminates the bias completely but at an expense of making the operation variable time and using more randomness.  Another approach is to generate a much bigger number, like one with several times the number of bits as N, and reduce that mod N.  This will make the bias much smaller.

I prefer to get rid of the bias when I can, but for secp256k1's N it really shouldn't be a problem practically anywhere.
Pages: [1]
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!