1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Really good extra explanation. Thank you. (Went actually down to constructing proofs, but I think for now cease and try to do something else. :)) $\endgroup$
    – Veksi
    May 15, 2022 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.