Java: Why does a 512-bit RSA KeyPairGenerator return 65 byte keys?

Question

Hello, this is somewhat a newbie question probably. I'm generating keypairs with Java:

KeyPairGenerator keyGen = KeyPairGenerator.getInstance("RSA");
SecureRandom random = SecureRandom.getInstance("SHA1PRNG", "SUN");
keyGen.initialize(512, random);

KeyPair keyPair = keyGen.genKeyPair();

RSAPrivateKey privateKey = (RSAPrivateKey)keyPair.getPrivate();

Now I always thought that privateKey.getModulus() and privateKey.getPrivateExponent() form the "private key" and that they are as big as the keysize (512 bits) passed to the Key Generator.

However, privateKey.getPrivateExponent().toByteArray() returns sometimes a 64 byte (as I expected), sometimes a 65 byte array.

Why sometimes 65 bytes? Am I missing something here?

Answer 1

8 * 64 = 512 ?

Edit: My bad, didn't see the deal between 64 and 65, indeed, good question.

Answer 2

getPrivateExponent() returns a BigInteger and the toByteArray() method returns a byte array, which always includes a sign bit. If the most significant bit in the 512 bit exponent is set, BigInteger will add an extra 513th 0 bit to specify that the number is positive and not a 511 bit negative number with the 512nd bit set to 1. For 513 bits, 65 bytes are required for the encoding.

If you look into the content of the returned byte array, the first byte will always be 0 if you get a 65 element array.

Answer 3

Here a little story on RSA that explains that key length is not always what you think, i.e., it is calculated from its most significant bit onwards. However, it should not exceed 512 bits, because that's the maximum length of the key. The story is about the perceived key length, not necessarily the key length in implementations.

getPrivateExponent returns a BigInteger. getPrivateExponent().toByteArray() returns the two's complement representation of the BigInteger. A BigInteger is signed. The 512 bits (64 bytes) are not signed. That means: if the most significant bit is set (the sign bit) to make it unsigned, the BigInteger needs to pad with one byte to make it conforming. If you look at the bytes, you'll find that the added byte is always zero.