My question is basically as follows:

How to generate two cases of 2048 bit RSA key so that their unsigned big endian modulus requires prefix with 0x00 and another one not when doing ASN.1 DER encoding?

I have the snippets of code and explanation what I try to do in the following. So, the rational why I try to do so and the method I use.

I give this as a context, since I have a problem generating such a pair and it may be I have misunderstood something. It may also be the that case the requirement for the 0x00 prefix is so rare I have not managed to do it with random generation (I don't think so, but I'm not sure how to calculate/estimate it nor I've found online examples of such).

So, I was thinking about ASN.1 DER encoding a 2048 bit RSA modulus. In .NET (and many other frameworks) the sequence is encoded as unsigned big endian byte array.

A practical consequence of this seem to be that if the first byte of the modulus is between 0x00 (decimal: 0) and 0x7F (decimal: 127) then after DER "header" there will not be added zero byte. Otherwise a 0x00 byte is added. This done because in ASN.1 DER encoding happens with signed integers and the byte would otherwise be interpreted as negative (and the modulus is an unsigned big endian integer).

There are some great explanations about this logic in general at

https://crypto.stackexchange.com/questions/1795/how-can-i-convert-a-der-ecdsa-signature-to-asn-1

and at

what is the format of RSA public key modulus and exponent in .net?

Fudging a bit with dumpasn1/asn1playground, taking the example presented at crypto.stackexchange and modifying the explanation from ECDSA to RSA here, I gather the sequence for a case for modulus with prefix 0x00 is as follows:

1. Start of sequence: 0x30
2. Length of sequence: 0x82 0x01 0x0a
3. Integer tag: 0x02
4. The modulus integer length: 0x82 0x01 0x01
5. Integer leading zero for modulus: 0x00
6. [insert the RSA modulus bytes]
7. Some other DER encoding bytes to end the sequence

And here point 5. is the crucial one. It is only added if the MSB of the unsigned modulus array is set.

Or, in code terms this is what it looks to me

var key = RSA.Create(2048);
var parameters = key.ExportParameters(includePrivateParameters: false);
var modulus = parameters.Modulus!;

// See this check here assuming MSB is in first byte in the array and this checks if the MSB bit is set.
bool isModulusMsbSet = (modulus[0] & 0x80) != 0;

// See here choosing the first version of the same array and concatenating a leading 0x00
// if the MSB is set on unsigned, big endian modulus.
var prefix = isModulusMsbSet ? new byte[] { 0x30, 0x82, 0x01, 0xa, 0x02, 0x82, 0x01, 0x01 }.Concat(new byte[] { 0x0 }).ToArray() : new byte[] { 0x30, 0x82, 0x1, 0xa, 0x2, 0x82, 0x1, 0x1 };

And to get closer to the reason of my question and the problem, the code I try to generate the non-padding case:

RSA? key = null;
do
{
   var testKey = RSA.Create(2048);
   var parameters = testKey.ExportParameters(includePrivateParameters: false);
   var modulusBytes = parameters.Modulus!;

   // See here the checking of MSB is inverted from != to ==.
   // I.e. accept this key only if 0x00 padding is not needed.   
   if((modulusBytes[0] & 0x80) == 0)
   {
      key = testKey;
   }

} while(key == null);

But this loop never stops! Which to me seem to indicate the MSB is always set! But shouldn't RSA.Create(2048); create an acceptable key even once in a while? Is there another good case to generate test material for the padding case?

I'm also partially asking since I'm not exactly sure if the conditional 0x00 should be accounted for or not in the ASN.1 DER encoding prolog sequence or not.

CodePudding user response：

It is unclear what problem you are trying to solve. To me it it looks like you are trying to solve an XY problem.

I'm not the best in explaining these things, I will try to explain:

Which to me seem to indicate the MSB is always set!

it is expected. RSA public key sizes divide by 8 without reminder (e.g. 512, 1024, 2048, etc.). As the result, modulus will consume KeySizeInBits / 8 bytes and all bits in this integer represent the modulus. Since leading zeros are ignored for integers (like in decimal, 1 and 001 represent the same number 1), the first bit (or MSB) of modulus must be 1. Otherwise it is ignored and then your modulus will not be of 2048 bits, it will be 2047 or even less up to 2040 bits long. These are invalid lengths (that don't divide by 8 without reminder) for RSA public key modulus. Think about RSA modulus like a long bit string where length counting starts from the first bit which is set to 1.

Just a very illustrative example. How many bits this bit string takes?

0 1 0 1 0 1 0 1

The answer is 7, leading zero bit is ignored and count begins from the first bit with 1. And 7 does not divide by 8 without reminder. And this:

1 0 0 0 0 0 0 0

is exactly 8 bits. In ASN.1, integers are two-complement values and when first bit in a byte is 0, then the integer is positive, otherwise it is negative. Since MSB in RSA modulus is 1 and the number is meant to be positive, it is padded with zero byte in front as part of encoding. However, this zero byte is not part of public key, it is part of encoding.

Moreover, modulus is the product of two prime numbers: N = p*q. And the product is odd number always. This means that the last bit of RSA modulus will end with 1 too. So for RSA public key, first and last bits in the modulus are set to 1.