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

Veksi

9/14/23, 9:36 PM

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.

0 + 0

rsa

asn.1

encoding

Score:1

Crypto

Maarten Bodewes

9/15/23, 2:56 PM

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.

0 + 0

Veksi

9/15/23, 7:18 PM

Really good extra explanation. Thank you. (Went actually down to constructing proofs, but I think for now cease and try to do something else. :))

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

TH: พลัง RSA ของสองโมดูลัสตั้งค่า MSB เป็นหนึ่งเสมอ ดังนั้นเมื่อเข้ารหัส DER จะมีคำนำหน้า 0x00 หรือไม่

RO: Puterile RSA de două module au întotdeauna MSB setat la unul și astfel, atunci când DER este codificat, au prefixul 0x00?

RU: Всегда ли RSA с двумя модулями имеет MSB, равный единице, и поэтому, когда DER закодирован, имеет префикс 0x00?

VI: Các quyền hạn RSA của hai mô-đun luôn có MSB được đặt thành một và vì vậy khi DER được mã hóa có tiền tố 0x00?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.