Computational complexity of RSA

Question

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

Answer 1

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.

Answer 2

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!)