Let's say that I have an RSA key pair that has been generated in a keystore using the keytool utility.

I am now accessing this key pair through some java code (using the Keystore class) and I want to encrypt/decrypt data using this public/private key.
In order to encrypt/decrypt arbitray length data, I need to know the maximum block size that I can encrypt/decrypt.
Based upon my experiment, this block size seems to be the size of the key divided by 8 and minus 11.

But how can I determine all that programatically when the only thing that I have is the keystore?
I did not find a way to figure out the size of the key from the keystore (unless it can be computed from the RSA exponent or modulus, but this is where my knowledged of RSA keys stops) and I did not find a way to figure out where this "magic" number 11 is coming from.

I can always encrypt 1 byte of data and look at the size of the result. This will give me the blocksize and the key size by multiplying it by 8. But it means that I always need the public key around to compute this size (I cannot do it if I have only the private key).
And this is not helping much on the number 11 side.

Am I missing something obvious?

Thanks.

 

 

Ok, some answers to my own questions....

It appears that the RSA key size is the size of the modulus (that can be obtained with getModulus() on the RSAKey object).

getModulus returns a BigInteger and calling bitLength on this BigInteger provides the key size, or almost. It seems that the bitLength operation is not always returning the exact key size. It is either the key size or the key size minus one (randomly for each newly generated RSA key). Not sure why that is, but probably close enough to figure out the key size.

Last step is to figure out this number 11. I can just hardcode this number as it seem to be consistent whatever the key and its size, but I will fill more comfortable if I understand where it is coming from.

Thomas

 

 

Ok, I found the answer of the magic number 11: http://forums.java.sun.com/thread.jspa?threadID=678310

Sorry for this post and answers to my own questions. I should have spend more time searching before posting.....

Still you probably need to be a PKCS#1 expert to figure out this 11 bytes used for the padding.

So really, only one question left: why the getModulus().bitLength() operation is not always returning the exact key size? Would be nice just to be able to get it easily, wouldn't it?

Thomas

 

 

It is returning the exact keysize, it just happens that it's not a multiple of 8 bits.

 

 

I am running the following code:

KeyPairGenerator keyGenerator = null;
keyGenerator = KeyPairGenerator.getInstance("RSA");
keyGenerator.initialize(512);

for (int i = 0; i < 100; i++) {
KeyPair ks = keyGenerator.generateKeyPair();
System.out.println("Public: " ((RSAKey)ks.getPublic()).getModulus().bitLength());
System.out.println("Private: " ((RSAKey)ks.getPrivate()).getModulus().bitLength());
}

Using the Sun JRE 1.4.2, I get consistently 512 for the public and private key modulus bit length, which is what I expected.

Using the IBM JRE 1.4.2 that is delivered with WebSphere 6.0, I am sometime getting 512, sometime 511. A bug in the IBM JRE?

Thomas

 

 

It is probably a bug. A naive implementation of RSA key generation that would exhibit this bug would work as follows (I'm ignoring the encrypt and decrypt exponents intentionally):

input: an rsa modulus bit size k, k is even:
output: the rsa modulus n.

k is even, so let k=2*l
step1: generate an l bit prime p, 2^l(-1) < p < 2^l
step2: generate another l bit prime q, 2^l(-1) < q < 2^l
step3: output n = p*q

Now the above might seem reasonable, but when you multiply the inequalities you get
2^(2*l -2) < n < 2^(2l)
That lower bound means that n can be 1 bit smaller than you expect.. The correct smallest lower bound for generating the primes p and q is (2^l) / sqrt(2), rounded up to the nearest integer.

I'll bet the IBM code implements something like the first algorithm.

 

 

Thanks again for the answer.
Very impressive support from you in this forum :-)
It is greatly appreciated.

 

 

Just as a general hint; normally you do not encrypt data with an RSA key, mostly due to the slowness of the algorithm. Instead, you encrypt (wrap) a random secret key, and in turn encrypt the data with the secret key. Since current secret key sizes range from 128 bit to 256 bit, you can be pretty sure you can wrap them using an RSA key (which should be 1024-30k in size).

Note that the private exponent can have a slightly smaller bitsize than the modulus in some implementations.