# Computational complexity of RSA

What's the computational complexity or RSA? One can assume it's O(prime length^2) it you consider multiplication by column, but speed tests slightly differ on slow operations with private key and differ a lot on public key. Why?

> openssl speed rsa1024 rsa2048 rsa4096

sign    verify    sign/s verify/s
rsa 1024 bits 0.002544s 0.000124s    393.1   8049.2
rsa 2048 bits 0.017023s 0.000467s     58.7   2140.7
rsa 4096 bits 0.121189s 0.001824s      8.3    548.2

• Hint: when multiplying two $n$-digit numbers by hand, how many times do you use an elementary single-digit multiplication? About how many for manually reducing the result modulo another $n$-digit number (slightly larger than the two ones multiplied)? How many such modular multiplications are needed for the textbook RSA operation $x\to x^e\bmod N$ with $e=2^k+1$ and small $k$? For $x\to x^d\bmod N$ with $d$ a corresponding private exponent? – fgrieu Apr 17 '18 at 5:38
• I don't see the thing you're hinting at; the private key ops (sign) clearly differ more than the public key ops (verify). – Maarten Bodewes Apr 17 '18 at 22:53

A more concrete answer for the data observed from OpenSSL:

• naive bignum multiplication is $$O(n^2)$$ and so is modular multiplication (which is what is actually needed here). However OpenSSL (for these sizes) uses Karatsuba multiplication which lowers this to roughly $$O(n^{1.6})$$ (thanks frgieu) and also Montgomery reduction which is only a constant factor.

• for publickey the number of multiplications is fixed (and small) so the total operation is the same big-O as one multiplication.

• for privatekey the number of multiplications also scales with $$n$$ giving a total roughly $$O(n^{2.6})$$ . OpenSSL also uses CRT which halves the size of the multiplications and doubles their number (plus wrap-up and sanity check), and windowing which reduces the number of multiplications by about 1/3, but those are both constant factors and ignored for big-O.

OpenSSL doesn't 1.1.1 does implement the imprecisely named 'multi-prime' form of PKCS1, which changes the privatekey benefit from CRT, but to get speed results for it you must specify -primes N and a sufficiently large (total) size.

• Montgomery reduction does not change the exponent in big-O. Karatsuba does, and goes from $O(n^2)$ to $O(n^{\log_23})$, that is $O(n^{\approx1.585})$. – fgrieu Apr 17 '18 at 11:43
• @fgrieu so the reason for the difference for private key operations should be Karatsuba multiplication? – Smit Johnth Apr 17 '18 at 20:58
• Montgomery multiplication doesn't change the asymptotic growth curve, but it makes a big concrete difference for the private-key operation! Does it help for the public-key operation? For $e = 2$ as in Rabin–Williams, it is a waste, but everything else is qualitatively different; for $e = 3$ its benefit is negligible; for $e = 2^{16} + 1$ or more it will help nonnegligibly. This is another reason why the answer is not usefully summed up as some big-O of polylog in $n$. You could pull out Fürer's multiplier, $O(\log n\log\log n\cdot2^{O(\log^*n)})$, but only a fool would use it to compute RSA. – Squeamish Ossifrage Apr 17 '18 at 21:30
• @Smit Johnth: the difference between private key and public key operations is not Karatsuba multiplication; it is mostly related to the size of the exponent (constant and small for public key, almost the modulus/moduli for private); and possibility to use the CRT for a constant speedup (factor approaching 4 for two-factors RSA in private key operation only, sizably less when combined with Karatsuba). – fgrieu Apr 18 '18 at 5:00
• @Squeamish Ossifrage: I challenge that Montgomery multiplication makes a big concrete difference in term of speed. A carefully coded classical $O(n^2)$ mulmod uses essentially the same number of multiply-and-add , and memory accesses, as the Montgomery counterpart (the difference vanishes when operand size increases). Montgomery 1) eases the pesky choice of a dividend word 2) thus suppress some sources of timing dependencies 3) eases performing a one-pass multiply-and-reduce step, a speed saving on memory access compared to multiply-then-reduce. – fgrieu Apr 18 '18 at 5:05

Fix an RSA modulus $$n = \prod_{i = 1}^k p_i$$ for primes $$p_i$$. (Conventionally, $$k = 2$$ in the case $$n = p q$$, but there are applications of multi-prime RSA, and not just goofy ones like post-quantum RSA with terabit moduli.) What does it cost to compute RSA public-key and private-key operations?

We will separately count

• multiplications modulo $$n$$,
• squarings modulo $$n$$,
• multiplications modulo the $$p_i$$, and
• squarings modulo the $$p_i$$,

because they all cost different magnitudes of bit operations.

The RSA permutation, forward or reverse, is modular exponentiation modulo $$n$$: given an integer $$0 \leq x < n$$ and an exponent $$0 \leq e < \lambda(n) = \operatorname{lcm}\{p_i - 1\}_i$$, compute $$x^e \bmod n$$. The standard naive algorithm is square-and-multiply, based on recursive application of the relations $$x^{e + 1} = x^{e} \cdot x, \quad x^{2e} = (x^2)^e.$$ The naive application of this costs $$\lfloor\log_2 e\rfloor$$ squarings modulo $$n$$ and $$H(e) - 1$$ multiplications modulo $$n$$, where $$H(e)$$ is the Hamming weight of $$e$$. But we can do better.

For the public-key operation, we can safely make it faster by choosing the minimum option $$e = 3$$, for which $$x^e$$ can be computed by $$x^2 \cdot x$$ costing exactly one squaring and exactly one multiplication modulo $$n$$. Out of post-traumatic stress from the possibility that the modulus might be used in a horrifically broken protocol with horrifically broken software, arising from the abuse of cryptography in the dark ages of the 1990s, some people reflexively choose $$e = 2^{16} + 1$$, for which $$x^e$$ can be computed by $$\underbrace{((x^2)\cdots)^2}_\text{16 times} \cdot x$$ at about an order of magnitude above the cost of $$e = 3$$.

For the private-key operation with knowledge of the secret factors $$p_i$$, and where the exponent is traditionally called $$d$$, we can separately compute $$y_i = x^{d_i} \bmod p_i$$, where $$d_i = d \bmod{\lambda(p_i)} = d \bmod{(p_i - 1)}$$, and solve the Chinese remainder theorem system of equations $$y \equiv y_i \pmod{p_i}$$ with an additional $$k$$ multiplications. This costs only $$\lfloor\log_2 d_i\rfloor$$ squarings and $$H(d_i) - 1$$ multiplications modulo $$p_i$$ for each factor, though to avoid leaking bits of the secret through timing side channels we round that up to $$\lfloor\log_2 (p_i - 1)\rfloor$$ multiplications and squarings modulo $$p_i$$.

Thus, knowledge of the secret factors enables faster exponentiation modulo $$n$$ for arbitrary exponents—but it still requires thousands of multiplications as opposed to the handful that $$e = 3$$ or $$e = 2^{16} + 1$$ requires, so the private-key operation is much slower than the public-key operation.

The naive square-and-multiply algorithm is not the only option. For any particular exponent that you plan to compute many exponentiations by, you could compute a near-optimal Lucas chain for it—but if the exponent is supposed to be secret, the choice of Lucas chain leak can information through timing. So implementors typically don't bother with that, and instead just pick small public exponent $$e$$ with low Hamming weight. Picking small private exponent $$d$$ doesn't work to speed up the private-key operation, though, because it is vulnerable to Wiener's attack.

What about the asymptotic growth curves of the cost in bit operations? The cost of naive schoolbook multiplication of two $$N$$-bit integers grows with $$O(N^2)$$ bit operations, and, with $$O(N^2)$$ bit operations precomputation, the cost of one $$N$$-bit Barrett reduction grows with only $$O(N)$$ bit operations, so the cost of multiplication modulo $$n$$ grows with $$O(N^2)$$ if $$N = \log_2 n$$.

For fixed public exponent $$e$$, the cost of the public-key operation grows with $$O(N^2)$$ bit operations under schoolbook multiplication. If $$n$$ has $$k$$ distinct $$P$$-bit prime factors, then the cost of the private-key operation grows with $$O(k P^3)$$ bit operations, which is $$O(N^3)$$ in the typical two-prime case.

But this oversimplified asymptotic story tells you nothing about how the choice of $$e$$ affects public-key performance, or how the Chinese remainder theorem affects private-key performance, or how Montgomery form can affect performance of either operation, and if taken literally might mislead you into thinking that a fancy algorithm like Fürer's will improve your RSA performance.

• Exercise. Estimate the concrete number of bit operations needed to compute multiplications or squarings modulo $$n$$ or the $$p_i$$ with different standard algorithms, such as Karatsuba multiplication or Toom–Cook multiplication. How many multiplications must one perform for it to be worthwhile to perform the computation in Montgomery form?

• Exercise. Estimate the number of bit operations needed to compute additions modulo $$n$$ or the $$p_i$$. Count the number of additions in the above computation, particularly the Chinese remainder theorem solution, and see how much this changes the estimated number of bit operations to compute the RSA public-key or private-key operations.

• Exercise. Suppose you pick $$e$$ uniformly at random from all possibilities. How does this affect the concrete performance vs. $$e = 3$$ or $$e = 2^{16} + 1$$? The asymptotic performance? Security? (This isn't usually done, but there are fun reasons why one might want to do something like this!)

• Excuse me, where is the answer to the question asked? – Smit Johnth Apr 17 '18 at 15:35
• @SmitJohnth ‘The standard naive square-and-multiply algorithm…costs $\lfloor\log_2 e\rfloor$ multiplications modulo $n$ and $H(e)$ squarings modulo $n$.…[T]he private-key operation…costs $\lfloor\log_2 d_i\rfloor$ squarings and $H(d_i)$ multiplications modulo $p_i$ for each factor, though to avoid leaking bits of the secret through timing information we round that up to $\lfloor\log_2 (p_i - 1)\rfloor$ multiplications modulo $p_i$.’ – Squeamish Ossifrage Apr 17 '18 at 19:15
• @SmitJohnth If you want to know the cost in bit operations, it depends on what algorithm you use to compute multiplications modulo $n$ and $p_i$. There are several standard algorithms. I could quote their asymptotic growth curves, but that isn't helpful here because the constant factors are more important when the size of the inputs is fixed—and after all, you already have measurements of the concrete performance in front of you! For example, the cost of Toom–Cook multiplication has an asymptotically impressive growth curve, but it's not worth doing for RSA-size inputs. – Squeamish Ossifrage Apr 17 '18 at 19:20