2

From what I can see, Microsoft's RSA CSP always generates identical bitlength pseudo prime numbers. So if the key size is 1024, the P and Q values seem to be (?) guaranteed to be 512 bits each? Does anyone know for sure if this, in fact, is the case?

I'm building an interoperability module between my own RSA implementation and Microsoft's. In my case I have built in a small random variance between P & Q values so for 1024 bit key I could end up with one value being 506 bits and the other 518. On purely experimental basis, if I lock the variance to 0 (i.e. the P & Q values are equal in size) -- Things work the way they should, I soon as I make the size variable Microsoft RSA object responds with "Bad Data" during import process.

I'm looking for a confirmation that Microsoft enforces equal key sizes, so if anyone has any information on it, please post

Before someone has a chance to ask why I had to implement my own RSA provider : CryptoAPI doesn't play nice in a multithreaded environment, it locks the machine keystore on CryptoServiceProvider calls; which means "File not found" (rather cryptic) errors if accessed from multiple threads

For those that care, take a look here: http://blogs.msdn.com/b/alejacma/archive/2007/12/03/rsacryptoserviceprovider-fails-when-used-with-asp-net.aspx

Raj
  • 1,113
  • 1
  • 17
  • 34
arthur
  • 138
  • 7
  • A quick update on this: I have ran a number of iterations to generate the keys via RSACryptoServiceProvider -- every iteration resulted in equal key size. – arthur Oct 19 '11 at 17:14
  • yep, MS will 0-pad if required and will never use **a bit** more (pun intended) than what's required, i.e. you'll always have bit size/2 for P and Q. – poupou Oct 19 '11 at 17:23
  • I could swear I saw aproximately the same size in some RSA paper. You are right though, that also explains why they have a predefined set of "legal key sizes" defined. – arthur Oct 20 '11 at 02:54

2 Answers2

1

Microsoft's RSA CSP generates and uses private keys which it can export and import in the format described on this page, and looks like this:

BLOBHEADER blobheader;
RSAPUBKEY rsapubkey;
BYTE modulus[rsapubkey.bitlen/8];
BYTE prime1[rsapubkey.bitlen/16];
BYTE prime2[rsapubkey.bitlen/16];
BYTE exponent1[rsapubkey.bitlen/16];
BYTE exponent2[rsapubkey.bitlen/16];
BYTE coefficient[rsapubkey.bitlen/16];
BYTE privateExponent[rsapubkey.bitlen/8];

So private keys that the CSP can handle (and in particular generate) must have the following properties:

  • The modulus length, in bits, must be a multiple of 16.
  • The length of each prime factor must be no more than half the length of the modulus.
  • The private exponent must not be longer than the modulus.
  • The private exponent, reduced modulo p-1 (resp. q-1) must be no longer than half the modulus.

Technically, there are infinitely many possible values for the private exponent d, and similarly for exponent1 and exponent2 because all that mathematically matters are the value of d modulo p-1 and q-1; it has been suggested to accept slightly longer private exponent parts if they end up with a lower Hamming weight, because this would lead to some performance benefits. Bottom-line: the format described above will not let you do that.

Other characteristics that the key must have to be acceptable to Microsoft's code (but not directly reported in the description above):

  • The numerical value of the first prime (p, aka prime1) must be greater than the numerical value of the second prime (q, aka prime2).
  • The public exponent (here encoded within the rsapubkey field) must fit in a 32-bit integer (unsigned).

Therefore there are many RSA key pairs which are nominally valid as per the RSA standard, but which cannot be handled by Microsoft RSA CSP code. Noteworthy is the last constraint, on the public exponent size: this means that the constraint is more general than just the CSP; if you setup a SSL server where the server's public key (in its certificate) has a public exponent which does not fit in 32 bits, then Internet Explorer will not be able to connect to it.

So, in practice, if you generate RSA key pairs, you will have to make sure that they comply with the rules above. Do not worry: to the best of our knowledge, these rules do not lower security.

Thomas Pornin
  • 72,986
  • 14
  • 147
  • 189
  • Good post -- I'll put the rules in and see what is going to happen. – arthur Oct 21 '11 at 03:30
  • Good catch with P > Q requirement -- do you know where it came from? As for E -- I have it locked down to 65537 which is the lowest hamming weight possible (well, other than 1) for exponention by squaring performance. That drives a bit longer prime search since it became: do { p = generatePrime(bitsize/2); } while ((p % e) ==1) – arthur Oct 21 '11 at 04:19
  • When you apply the CRT, you first compute m1 = m^d1 mod p and m2 = m^d2 mod q (the exponentiations modulo p and q). Then you take m2 modulo p as the initial step for the CRT. If p < q then an extra modular reduction may be needed here, and Microsoft's code does not have it. I think the "p > q" requirement used to be part of PKCS#1 (I have a comment in my own code which says so) but I do not find it in the current standard version. – Thomas Pornin Oct 21 '11 at 12:09
0

My own work/experimentations, doing Mono's (managed) RSA implementation and unit tests, shows that Microsoft implementation requires specific byte[] size when importing RSA parameter values.

It's also a common interoperability issue (there are some SO questions about it) when people using BigInteger to convert their parameters since they often are a bit smaller (e.g. 1 byte less) than what MS expect and needs to be 0-padded.

So I'm pretty sure you can pad your smaller value to make MS accept it, but you'll likely not be able to make it accept a larger value.

poupou
  • 43,413
  • 6
  • 77
  • 174
  • Thanks, for the answer -- I'm not using big integer , rather (very!) heavily optimized and modified version of IntX class (http://intx.codeplex.com/). The largest interoperability issues I encountered were around Big/Little Endian, Microsoft does some strange things in terms of reversing byte order in, rather, unpredictable places. I was trying to figure out exactly what MSFT was doing in regard to minimum size / skip size (My implementation will give you 2 bytes if you have a 9 bit key -- some implementations will give you 4 bytes) what MSFT expects ... who knows. – arthur Oct 19 '11 at 17:09
  • A lot of what MS expect can be traced back to CryptoAPI (look at theAPI, structures...). Also have a look at Mono's unit tests. You'll find a lot of corner cases that your implement ion should cover if you want the maximum interoperability between your implementation and MS one. – poupou Oct 19 '11 at 17:21