# 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",
"",


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 (?!?!)

• You got 32 hexadecimal symbols as keylength, which is 128 bit. Therefore, your library is telling you exactly what you did wrong. And as mikeazo said, 512 as lower limit is outdated and not secure any more. Anything less than 1024 is considered questionable, and 1280 are recommended as lower limit. – tylo Sep 15 '14 at 16:55
• 229110545576645850236522690668306544921 = 13118050575083334077 * 17465289088900344973 so this looks like a plausible modulus, albeit very weak. 13082845549543033994073971762152947067 = 37 * 1128586338367 * 313303828194079496938273 It's quite unusual to use a large e, typically we use small primes with low hamming weight like 3 or 65537. – CodesInChaos Sep 16 '14 at 9:37

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.

• Obviously, you can't use a 512 bit RSA key for generating sha512withRSAEncryption signatures. The restriction on key size might have to with more than just best practices. – Henrick Hellström Sep 15 '14 at 19:54

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.

• You should replace the "any kind of asymmetric encryption ... at least 2048 bits" part. This size recommendation if appropriate for RSA or finite field Diffie-Hellman based encryption. There are other algorithms which need much smaller (e.g. 224 bits with ECC) or much larger (~1 Mbit for McEliece) keys for a similar security level. – CodesInChaos Sep 16 '14 at 9:06
• I also want to note that keys used for confidentiality effectively never time out, since the attacker can store the ciphertext forever. – CodesInChaos Sep 16 '14 at 9:08
• The difficulty to implement RSA in a side-channel resistant way does not depend on the key size. – j.p. Sep 17 '14 at 12:20