Why would an RSA library tell me that the public key must be at least 512 bits in size? 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 (?!?!)
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.