Isn't doing % N while generating a random key a flaw?

[Coding Enthusiast]

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 I₂₅₆ % 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
115792089237316195423570985008687907853269984665640564039457584007913129639935
While the order of the curve (for example secp256k1 that bitcoin uses):
115792089237316195423570985008687907852837564279074904382605163141518161494337
So the difference would be:
432420386565659656852420866394968145598
(Which is 17 bytes by the way).

So technically you can end up with a number that is between n and 2²⁵⁶ and eventually because of that mod end up with a key with little entropy. For example if I₂₅₆ 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?

[1715181259]

1715181259

[1715181259]

1715181259

[1715181259]

1715181259

[odolvlobo]

A random number generator will occasionally give you a value of 1, so the fact that I₂₅₆ % n can be 1 does not make it not random. If I₂₅₆ is generated randomly, then I₂₅₆ % 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.

[aleksej996]

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 2²⁵⁶, there is 1 in 2¹²⁰ chance that it will be in the range between 0 and 2¹³⁶. Due to this suboptimal behaviour, it will be 1 in 2¹¹⁹, 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 2¹¹⁹ 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.

[gmaxwell]

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.