February 14, 2014 | 3 minute read

Faster RSA in Java with GMP

A new java library that wraps libgmp

At Square, we care a lot about seller experience, and part of that is making sure our services run as fast as possible. One service I’ve had the chance to help build is our seller session service. The session service essentially does two things:

Creates sessions in response to authentications. When a seller logs in, the session service verifies their username and password, and produces a session ID. The session ID is stored on the client and allows the client to make authenticated calls to Square.
Validates sessions. Once a seller is logged in, every authenticated request they make has to pass through our session service. We validate the session ID and resolve it back to the seller it was generated for. This happens for practically every logged-in request we process, so it needs to be really fast — any latency would affect all of Square’s services.

Here’s where session validation gets a little complicated. As a payments processing company, we take the security and integrity of our data very seriously, and we care about things like security proofs. It was important to us to design a strong user authentication model that could go deep into our software stack.

Our solution was to have the session service produce a user certificate with every request. This certificate is a small piece of data cryptographically signed by the session service using RSA. As the request makes its way from service to service, each recipient uses a well-known public key to verify the authenticity of the certificate, which proves that the request is on behalf of a particular logged-in user. The verification is fast and doesn’t require calling back to the session service.

Unfortunately, generating the certificate was slower than I expected. RSA signing is computationally expensive; performing a 2048-bit private key operation takes several solid milliseconds on a modern CPU. The operation can’t be parallelized either, so while adding CPU power enables us to sign hundreds of requests per second, additional CPUs can’t make an individual operation run any faster. I needed a faster implementation.

The critical operation in RSA is modular exponentiation, that is, (base ^ exponent % modulus). The Java implementation of java.math.BigInteger.modPow() is pretty fast, but it turns out that the one in libgmp (the GNU Multiple Precision Arithmetic Library) is a lot faster…

Announcing jnagmp

I’m happy to announce that today we’re open sourcing a small Java library that wraps libgmp. The only feature we’re launching with is modPow, the key operation in RSA. It’s significantly faster than the native Java version. Here’s a benchmark on my MacBook Pro:

Testing 1000 2048-bit private RSA's Java
1000 2048-bit private RSA's in 7.994s
7.99 ms/op, 125.09 ops/s

Testing 1000 2048-bit private RSA's NativeSecure
1000 2048-bit private RSA's in 1.707s
1.71 ms/op, 585.82 ops/s

As you can see, the native version is more than 4x faster than the Java version. We found similar performance gains on our production boxes, where we were able to chop the latency of our session service in half.

Using the library is simple, just add maven dependency on com.squareup.jnagmp:jnagmp and then:

Gmp**.**modPowSecure**(**base**,** exponent**,** modulus**)**

where the arguments are all BigInteger. (The “secure” version is hardened against timing attacks. There’s also an insecure version, which is faster, but vulnerable to timing attacks. For private key cryptography, you’d definitely want to use the secure version.)

The code we’re releasing today uses the excellent JNA library to talk to libgmp. We originally used plain JNI with some C++ glue to talk to libgmp. The code itself wasn’t bad, but the extra native compile step was really annoying. So we rewrote it using JNA, and the result is much nicer. We’ll be able to add additional features and expose more libgmp methods just by writing more Java.

The maven artifacts contain pre-built libgmp binaries for Mac and 64-bit Linux, but your can build your own binary, or use one installed on your system.

An example: bouncycastle-rsa with GMP

To demonstrate one way to use jnagmp, we’re also releasing a second module, com.squareup.jnagmp:bouncycastle-rsa, a reimplementation of Bouncy Castle’s org.bouncycastle.crypto.engines.RSAEngine using native modPow. You can use it as a drop-in replacement for RSAEngine.

What’s next?

So far we’ve only implemented modPow, but there are many other functions in libgmp we could expose. (We welcome contributions.) We only have a few pre-built libgmp binaries, so it would be nice to get binaries for a broader variety of platforms, including Windows.

On the crypto side, it would be awesome if someone knowledgeable about java.security wants to figure out the magic we’d need to register native RSA as a security provider.