Minimum key length of RSA

Question

When I implemented a license key mechanism in C# using RSA, I came across the RSACryptoServiceProvider class, which is limited to a minimum of 384 bit key size. This key length has direct impact on the signature (==license key) which I created.

Is 384 bits a technical limit of RSA in general or might it be possible to implement RSA successfully with even shorter key sizes?

Reading the (German) Wikipedia article which explains RSA, they use very small prime numbers in their mathematics calculation example. That seems to work, so I would expect the key size to be shorter than 20 bits... Note: I absolutely don't care about security at the moment. That's another discussion. I'll just want to get the technical limits right.

I know Stackoverflow should not be used to ask for tools, but if you know a .NET RSA library which has a lower limit, maybe you just want to mention that as a side note.

Answer 1

If you do not care about security then Yes, you can implement a RSA with key size < 384 bits. It is not recommended as insecure but it works.

In this slide Dan Boneh takes an example with a private key on ~128 bits. (the rest of his courses worth having look too).

Answer 2

Not a real technical limit but a drawback is that with decreasing private key size (and therefore decreasing modulus) the block size also decreases.

Therefore if your data to be signed/encrypted is larger as the block length you would have to use a block chaining mode which is rather uncommon in combination with RSA.

Answer 3

From a security standpoint, 384 bit RSA can be cracked in a few hours, and 512 bit RSA in a week or two. If you are concerned about signature size, ECDSA with a 160 bit key will generate a 40 byte signature. BLS can do half that, but there aren't good libraries for it.

From a "technical limitations" standpoint, your RSA key must have a little more than twice as many bits as the value you want to sign. Normally you sign a hash of your data rather than signing the data directly.