Why is prime number size important for RSA security? 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?
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 &lt; 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.)