Are EC public key values evenly distributed? At my Day Job(tm) we've encountered a bug wherein if the leading digit of the X or Y value of a public key are zero, "shit happens" (this bug is in our code - I'm not suggesting there's some problem with EC itself. It's just an encoding thing and it's not particularly interesting for this question).

Naively, this suggests that we should expect 1 out of 128 keys to trigger the bug, but that assumes that the X and Y values are evenly distributed. Are they?

If it matters, the curve is secp256r1.
Yes, the coordinates are more or less evenly distributed, between 0 and the order of the curve (exclusive). The Certicom curves such as secp256r1 generally have an order very near the maximum of the bit size, e.g. the secp256r1 curve has the following order $n$:

FFFFFFFF 00000000 FFFFFFFF FFFFFFFF BCE6FAAD A7179E84 F3B9CAC2 FC632551


So that means that there is about one in 256 chances that the first byte is completely zero for each coordinate.

This is slightly different for e.g. Brainpool curves as the order is randomly chosen (for the correct bit size, of course) and thus lower, brainpoolP256r1 has for instance the following prime order $q$ (same thing, different name):

A9FB57DB A1EEA9BC 3E660A90 9D838D71 8C397AA3 B561A6F7 901E0E82 974856A7


so the chances are slightly higher for brainpool curves that the first byte is fully zero (slightly lower than one in A9 of course, so about 1 in 169).



It gets even more "funny", as I've seen implementations fix this by making sure that the leftmost byte is set to 00 if it is missing, in case constant size X and Y coordinates are required. Of course, that fails if the first two bytes are set to zero, with a much smaller but non-negligible chance. The chance of it starting with 16 bytes of zero are of course negligible, but otherwise you'd better make sure.

A donkey doesn't stumble over the same stone twice, as we say in the Netherlands (A fox is not caught twice in the same snare.)



You can have the same fun with EC private keys or RSA private keys, by the way. The RSA specification lists how to create constant size, unsigned, big endian values that you require in the definition of the I2OSP (Integer to Octet String Primitive) definition.

Note that that definition is a rather mathematical way of saying that you need to prefix enough zero bytes. I've seen a crypto professor implement it using big integer arithmetic. This is definitely not required. It is just a formal description how it commonly looks in computer memory if you encode the value correctly. For more info, see my answers here on crypto and the implemention on SO for Java (shameless plugs, sorry 'bout that).



P.S. The chance of either coordinate starting with a zero byte is about $1 - {({255 \over 256})^2}$. That's ever so slightly lower than $1 \over 128$, but $1 \over 128$ is a good ballpark figure I guess.