The Performance of RSA Encryption

When encryption takes up a more of your round trip time than servicing the request itself, it's time to look at optimizing it.

I'm using a home-compiled version of OpenJDK that's running code that looks like this:

import static javax.crypto.Cipher.ENCRYPT_MODE;
        
        KeyPair             keyPair             = keyPairGenerator.genKeyPair();
        PrivateKey          privateKey          = keyPair.getPrivate();
        PublicKey           publicKey           = keyPair.getPublic();
        Cipher              cipher              = Cipher.getInstance(algorithm);
        
        // Note that privateKey is of type sun.security.rsa.RSAPrivateCrtKeyImpl
        
        cipher.init(ENCRYPT_MODE, privateKey);
        byte[] input = "hello world".getBytes();
        byte[] output = cipher.doFinal(input);

Stepping through the code

Thread [main] (Suspended)
RSACore.rsa(byte[], RSAPrivateKey) line: 101
RSACipher.doFinal() line: 352
RSACipher.engineDoFinal(byte[], int, int) line: 389
Cipher.doFinal(byte[]) line: 2121
.
.

I come to this in sun.security.rsa.RSACore:

    public static byte[] rsa(byte[] msg, RSAPrivateKey key)

            throws BadPaddingException {

        if (key instanceof RSAPrivateCrtKey) {

            return crtCrypt(msg, (RSAPrivateCrtKey)key);

        } else {

            return crypt(msg, key.getModulus(), key.getPrivateExponent());

        }

    }

If I wanted the other branch to be taken, I could do something like this:

    RSAPrivateKey       rsaPrivateKey   = (RSAPrivateKey)privateKey;

    RSAPrivateKeySpec   keySpec         = new RSAPrivateKeySpec(

        rsaPrivateKey.getModulus(), 

        rsaPrivateKey.getPrivateExponent());

    PrivateKey          slowPrivateKey  =

        KeyFactory.getInstance("RSA").generatePrivate(keySpec);

and call a Cipher that has been initialized with a private key of class sun.security.rsa.RSAPrivateKeyImpl rather than RSAPrivateCrtKeyImpl. Then when we get to the crypt method, we see this:

        BigInteger c = m.modPow(exp, n);

The BigInteger method modPow is very expensive since exp and n are enormous numbers. In fact, as I run jstack against my JVM, I see half a dozen threads in this code.

Conclusion

Because RSAPrivateCrtKey carries much more information than the interface RSAPrivateKey demands, less expensive calculations appear to be needed. Therefore, encryption is considerably faster using keys of this class than RSAPrivateKeyImpl.

When I benchmarked the two on a small string ("hello world") using JMH I found RSAPrivateCrtKey over three times faster when encrypting.