Speeding Up RSA Signature Verification

In some scenarios that emerge in data centers, one signed certificate is verified a very large number of times. This makes the performance of signature verification a significant target for optimization. With this motivation we show how to speed up RSA verification in the globally deployed cryptographic library OpenSSL. RSA verification time is dominated by the time for computing \(X^e \pmod N\) where e is the public exponent. The default choice is \(e= 65537 = 2^{16} + 1\) , but obviously, signing with \(e=3\) leads to a faster verification. In both cases e has the form of \(e = 2^k +1\) for some k, namely \(k=1\) or \(k=16\) . We speed up the computation of \(X^e \pmod N\) by replacing OpenSSL’s call to its modular exponentiation function with a dedicated sequence of Montgomery Multiplication (MM) calls. We also show an algorithm that uses only \(k+2\) MM calls instead of \(k+3\) , i.e., 3 instead of 4 for \(e=3\) (and 18 instead of 19 for \(e= 65537\) ). Integrating our method into OpenSSL (version 3.0) and measuring RSA2048 on a “Skylake” processor shows speedups of \(1.56x\) for \(e=3\) and \(1.21x\) for \(e= 65537\) .