Why do public keys for RSASSA-PKCS1-v1_5 follow a normal distribution?

I converted ~1000 public keys generated from chrome's RSASSA-PKCS1-v1_5 implementation, converted them to decimal, prepended a "0." to them, and sorted them.

This is the graph that I got:

It puzzled me a little bit because it looks like an inverse normal distribution. I expected a uniform distribution (i.e. straight line). what gives?

the datapoints are the actual values of the keys, you could say normalized 0 to max, sorted, and then plotted by index in the sorted array.

• A public key consists of a public exponent, a modulus and of course a specific encoding. What is it that you actually sorted? Could you update the question for that? – Maarten Bodewes Oct 3 '17 at 9:59
• Note also that RSA public keys are independent to the PKCS#1 padding method used, even if the API does make the distinction between padding methods during key pair generation. – Maarten Bodewes Oct 3 '17 at 9:59

It's not perfectly clear what your graph is actually displaying.

However, if you expect that $k$-bit RSA keys are equidistributed between $2^{k-1}$ and $2^k$, well, that's not likely (unless the key generator goes out of its way to try to ensure that).

Remember, an RSA key is (usually) produced by independently selecting two primes from a range of $[c2^{k/2}, 2^{k/2}]$ (where common values of $c$ are $0.75$ and $\sqrt{1/2} \approx 0.7071$; it varies between implementations; I don't know what Chrome uses).

Each prime might be approximately equidistributed, but the product of two such primes will be somewhat closer to a normal distribution, with intermediate values being of higher probability; however note that it won't really be that close to normal.

• makes more sense if I mention that those are the sorted keys maybe. It's not exactly normal. calculated mean: 0.72473151, std: 0.101483162, but it doesn't fit exactly; the keys are a little flatter. thank you for the insight! – guest Oct 2 '17 at 15:44
• I understand the keys were sorted, but what does the graph actually show? Something like 'percentage of keys with initial digits less than the value given on the x-axis'? That doesn't jive with the values shown, but I can't think of anything more likely... – poncho Oct 2 '17 at 15:47
• the datapoints are the actual values of the keys, you could say normalized 0 to max – guest Oct 2 '17 at 15:51
• @guest: got it; so this shows 'the number of keys (out of 1000)' (x-axis) that have a value > $y2^k$ (where values of $y$ given on the y-axis). Yes, it would appear that my explanation turns out to be the appropriate one; the right and left edges of the graph are near vertical as there are relatively few keys with $y$ values that high/low – poncho Oct 2 '17 at 15:57
• @guest: BTW; we can deduce from your graph that Chrome uses $c = \sqrt{1/2}$; if it used $c = 0.75$, we'd never see a key with a $y$ value smaller than 0.5625... – poncho Oct 2 '17 at 16:02