Why would an RSA library tell me that the public key must be at least 512 bits in size?

Question

I'm trying to interoperate with a web service by reverse-engineering it. Currently, when sending a POST request, it encrypts the form data one-by-one with a 'RSA' function. But it's rather weird as everywhere else i've tried to use these values have given me errors. It's using this library: https://code.google.com/p/pajhome/source/browse/trunk/crypt/md5/rsa/RSA.js?r=133 Like this:

var crypto = new RSAKeyPair(
    "9d7aa162117a8a9610ed2ddea713d7b",
    "",
    "c9869917572adbb60a2c30ddec2551f")

I know just a little bit of RSA, but if i'm right, this should be the public key with (e,m). But when trying to work it in Java I get the error saying that the RSA public key must be at least 512 bits in size. Where is my mistake happening here?

BigInteger e = new BigInteger("3855b21eba4eb9a8a88117878e1fda49", 16);
BigInteger m = new BigInteger("ac5d160611804794d3e0240f2042b919", 16);

RSAPublicKeySpec spec = new RSAPublicKeySpec(e, m);
KeyFactory keyFact = KeyFactory.getInstance("RSA");
PublicKey publicKey = keyFact.generatePublic(spec);

On my setup, (e,m) are being (13082845549543033994073971762152947067, 229110545576645850236522690668306544921) in decimal (?!?!)

Answer 1

Your javascript library linked to has no restrictions on key size. Many libraries out there that implement RSA will have a restriction on the key size. This is to make sure developers are following best practices as if the key size is too small, the security of the cipher is completely blown. It looks like the Java library you are using won't let you use key sizes of less than 512 bits (which is still too small, even 1024 bits for RSA is no longer recommended for long term security).

If you remove the check for 512 bits, that should take care of the error.

Final Thoughts
I think it should be noted again that 512 bit RSA keys are way too small. Since you will be interoperating with something that is not secure, you'll need to think about what that means when it comes to the security of your system. You won't be able to change what the web service is doing, but you still need to think about how it affects the security of your system.

Answer 2

Because RSA with 512 bits is considered insecure for a fair amount of time yet, and 512 bit RSA primes are already breakable on an average new desktop computer in several weeks.

For any kind of asymmetric encryption that is supposed to be secure, I would suggest a key size of at least 2048 bits, better 4096. Only for keys like session keys that time out frequently 1024 bits are acceptable.

Note: going beyon 4096 bits doesn't necessarily improve security, as it becomes increasingly difficult to implement such RSA ciphers that aren't succeptible to side channel attacks with increased key length, plus such keys are increasingly difficult to find good primes for, because at these sizes Miller-Rabin-style primality testing becomes too slow to perform enough checks.