Do RSA powers of two modulus always have MSB set to one and so when DER encoded have 0x00 prefix?

Question

Looking at https://crypto.stackexchange.com/a/30616/16548 and all the ways I generate RSA keys (code, SSL) the MSB is always 1 and so when DER encoded has 0x00 prefix.

I think it is always so when the RSA key length is a power of two (e.g. 2048 or 4096).

But the question I'm wondering now before going to bed: is it so?

Quoting from the link

We typically select RSA modulus sizes which are powers of two or small multiples thereof (1024, 1536, 2048, 3072, etc), and so this typically happens there.

since I now I'm wondering how to prove or somehow this really is so.

It looks to me the modulus length is set like that and the MSB is set due to modulus construction and these being unsigned integer. So 0x00 will always be there and there is no need to check if MSB is set.

So the answer to the question is in short: yes or no. I am also thinking of a convincing argument that I cannot at the moment produce but if someone has at hand would of course be very interesting.

Answer 1

Yes, it is always so, if just because the key size is actually the size of the modulus for RSA. The sizes of the primes that produce the modulus should be selected so that the key size is between $[2^{len-1}, 2^{len})$. If that is the case then if $len$ is a multiple of 8 then it will have the MSB of each byte set.

This means that the zero byte prefix would also be present for a key size of, e.g. 1792 bits or 1920 bits. These kind of sizes are sometimes used for embedded systems / smart cards as the total response data size is 256 bytes, so a signature or ciphertext would not leave any room for additional data or secure messaging.

Beware that RSA can have any key size, so I would not consider skipping the byte without checking a good defensive programming practice, and normally you would use library functions to perform the conversion to bytes - i.e. most of the time you'd use an ASN.1 component.