RSA modulus is $N = pq$ where $p$ and $q$ are prime numbers. I read from somewhere that the time it takes to decrypt the RSA encryption increases exponentially as key length increases, which depends on the value of $N$, which in turn, depends on $p$ and $q$. Are there any mathematical proof to explain this phenomenon?

  • $\begingroup$ Do you want the proof for legitimate holder of the private key, or do you want proof for the adversary? $\endgroup$ – DannyNiu Jun 14 '19 at 6:29
  • $\begingroup$ Regular decryption is just a modular exponentiation with the exponent having almost the same size as the modulus. Thus, using square and multiply, the decryption scales linear to the bitlength in the number of modular multiplications. But keep in mind, those also depend on the bit length. Maybe specify if you mean regular decryption or breaking it. The claim as stated seems wrong. $\endgroup$ – tylo Jun 14 '19 at 13:26

In RSA with modulus $n$, the legitimate user's cost to encrypt a message is $(\log_2 n) (\log_2 \log_2 n)^{1 + o(1)}$ bit operations, with the best public exponent $e = 3$; and to decrypt a message (if you know the secret exponent) is $(\log_2 n) (\log_2 \log_2 n)^{2 + o(1)}$ bit operations. This is most assuredly not exponential in $n$ or even in the size $\log_2 n$ of $n$, and it is quite fast in concrete terms—to measure how fast it is, you can run openssl speed rsa4096 in the privacy of your own living room! You can also consult the SUPERCOP benchmarks for measurements on a wide variety of computers to see the concrete speeds.

What about the attacker's cost to decrypt in RSA without knowing the private key?

If $n = pq$ for $p < q$, the cost of the elliptic curve method of factorization (ECM) is $L^{\sqrt{2} + o(1)}$ where $L = e^{(\log p)^{1/2} (\log \log p)^{1/2}}$. This is the best-known classical method of factoring that depends on the size of a factor, so the factors must be chosen large enough to put this out of reach. This is neither a polynomial function, nor an exponential function, but somewhere in the middle: $e^{(\log p)^\alpha (\log \log p)^{1 - \alpha}}$ is polynomial in $\log p$ when $\alpha = 0$ and exponential in $\log p$ when $\alpha = 1$, but here $\alpha = 1/2$. But, of course, what is really interesting is not the asymptotic growth curves of attack costs, but the concrete attack costs for specific parameter sizes. Based on experimental evidence of ECM performance[1], to make sure that the cost is near $2^{128}$ we can set $p \approx 2^{1024}$ for a ‘128-bit security level’.

There are other methods of factoring:

  • The number field sieve (NFS) costs about $L^{1.704\dots + o(1)}$ per key in a large batch attack[2], where $L = e^{(\log n)^{1/3} (\log \log n)^{2/3}}$. Note that this cost depends on the size of $n$ rather than on the size of its factor $p$. For a 128-bit security level, we need to set $n \approx 3584$.

If we had a large quantum computer:

  • Shor's algorithm costs about $(\log_2 n)^{2 + o(1)}$ qubit operations. If large quantum computers ever became feasible, then for a >100-bit security level, we would need $n \approx 2^{2^{43}}$, i.e. a terabyte modulus[3].

  • Grover-optimized ECM costs about $L^{1 + o(1)}$ where $L = e^{(\log p)^{1/2} (\log \log p)^{1/2}}$, which requires us to use somewhat larger primes. If large quantum computers ever became feasible, then for a >100-bit security level, we would need $p \approx 2^{2048}$, though cryptographers recommend $p \approx 2^{4096}$ until quantum computing is better understood[3].

(Combining the attack costs of Shor and Grover-ECM, it is cheapest for the legitimate user if we use multi-prime RSA with $n = p_1 p_2 \cdots p_\ell$ where $p_i \approx 2^{4096}$ and $\ell \approx 2^{32}$, i.e. four billion factors.)


Why is prime number size important for RSA security?

If the prime numbers are too small it's possible for an adversary to factor $N$ (where $N = p \times q$). If the adversary has $p$ and $q$ he has all the information needed to recreate your private key.

Mathematical proof for the exponential increase of difficulty?

I'm unsure if there exists a mathematical proof of this phenomenon, but actually I think that it's rather simple to explain why this appears to be the fact.

For this example we take the simplest factoring algorithm which would be trial division.

If we know that a number $N$ is a semi-prime number, then we have to try all the numbers from $1$ up to $\sqrt N$.

  • Single digits: $7 \times 5$

    $N = 35$ we would have to check all numbers from $1$ to $5$, because $\sqrt{35} \approx 5.9\ldots$ You would find out very quickly that one factor of $35$ is $5$.

  • Double digits: $53 \times 61$

    $N = 3233$ and now we would have to check all the numbers from $1$ to $56$ until we find a factor.

  • Triple digits: $349 \times 941$

    $N = 328409$, now the limit is already up to $573$.

As you can see from this example the number increases exponentially from $5$ to $56$ to $573$ but all we did was increase the numbers of $p$ and $q$ by one digit. Increasing the factors by a factor of $10$ also increases the possible factors by a factor of $10$.

Generating large prime numbers is very easy but finding the prime factors of a large number can be very difficult, especially in the case of RSA where $N$ is a semi-prime number.

The example above uses the simplest algorithm known and is also very inefficient. There are some algorithms that can factor numbers a lot faster but all of these algorithms still don't suffice if you chose a large enough semi-prime number, i.e. a 2048-bit RSA number.

  • 1
    $\begingroup$ The cost of factorization is LESS than exponential in $\log_2(N)$. The earliest sub-exponential factoring method was probably continued fraction, which predates digital computers. $\endgroup$ – fgrieu Jun 14 '19 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.