# Are there practical upper limits of RSA key lengths?

Suppose one wanted to use RSA encryption for the sole purpose of sending key bits for use in symmetric crypto systems, a dedicated key exchange system so to speak. And say you didn't think that the presently used RSA key lengths were going to be secure in ten or fifteen years.

What would be some of the technical difficulties (hardware and or software) of of using an RSA key length of say a million bits?

Assume that you are designing this from scratch and you have a clean slate as to your hardware-software design options. Also assume that you don't care if it takes 24 hours or so to encrypt or decrypt the information.

Computational cost of RSA with keys of length $$n$$ bits is roughly $$O(n^2)$$ for public key operations (encryption, signature verification), and $$O(n^3)$$ for private key operations (decryption, signature generation). So RSA with a million-bit key will be roughly one billion times slower than RSA with 1024-bit keys (for the private key operations); the latter takes about 1ms on a common PC, so you're in for a fortnight of computation with your million-bit key.

Memory space is not a hard constraint, because RSA computations require only to keep a few values of the size of the key; a one-million-bit integer is 128 kB; you can have thousands of those in RAM. You will, however, exceed level 1 cache (that's 32 or 64 kB on a common PC) so you can expect some slowdown (with Montgomery's multiplication, data access is sequential, so this effect should be limited).

• Thank you for the reply, although I don't get the connection between scientific inquiry and demonstrations of manhood :) Nov 14, 2011 at 14:34
• To be fair to RSA, 1 million bits is well over the FFT range. Encryption is closer to $O(n \log n \log \log n)$, and decryption $O(n^2 \log n \log \log n)$. Nov 14, 2011 at 18:13
• An an addendum, I actually made the experiment. Generated 3 $2^{20}$-bit numbers $a$, $b$ and $m$, and performed various arithmetic operations (using GMP): $a·b \bmod m$: 0.08s; $a^{65537} \bmod m$: 1.16s; $a^b \bmod m$: 107873.130s (~29 hours). Nov 16, 2011 at 15:39
• @Samuel: Thank you for taking the time to run the numbers! Nov 16, 2011 at 21:55

I see two main points of complication:

• We need to find primes of appropriate size. For your "million bits" key, the primes $$p$$ and $$q$$ would have to have around 500000 bits. I suppose primality tests in this size are quite harder than for our usual 2048 bit primes (though I didn't find numbers in a quick search).

Also, you would need much more entropy as input for your prime searching algorithm, otherwise this can be attacked from the randomness side.

• For each decryption, you need one modular exponentiation with modulus $$n$$ and exponent $$d$$, where $$d$$ has almost the same number of bits as $$n$$.

The simple square-and-multiply algorithm takes $$\log_2 n$$ squarings and on average $$\frac 12 \log_2 n$$ multiplications (depending on how many one bits there are). Each squaring/multiplication itself uses a $$\log_2 n$$-bit number, i.e. takes itself around $$\log_2 n$$ additions of such $$\log_2 n$$-bit numbers (if implemented as double-and-add). That would be $$(\log_2 n)^3$$ single-bit operations, which would be for your million-bit ($$2^{20}$$ bits) number $$(2^{20})^3 = 2^{60}$$ bit-operations (with some small factor). Now we come into regions which are similar to brute-forcing DES (and I'm not sure how much of this can be parallelized).

There are some faster exponentiation and multiplication algorithms, but if I understand right, they change only a constant factor, not the actual complexity.

• Thank you, I was thinking that primality testing would be difficult for such large primes. Can you recommend any literature that explores this avenue of research? Nov 14, 2011 at 14:39
• @Paŭlo: it is $(\log n)^2$ operations for a modular multiplication, and there are $\log n$ of them in an exponentiation, so $(\log n)^3$. I do not know where your exponent $4$ comes from. For primality testing, a basic Miller-Rabin test is $O((\log p)^3)$ and you will need to do about 200000 of these (on average), if you select candidates for $p$ and $q$ with some care; so that's roughly the cost of 25000 private key operations. But at least key pair generation can be distributed over several cores / nodes. Nov 14, 2011 at 15:52
• @Thomas: Seems like I wrongly counted the $\log_2 n$ factors in my paragraph to come to this exponent of 4. Correcting now. Nov 14, 2011 at 15:57
• @jug: Karatsuba, Schönage-Strassen and their ilk, are for multiplication of plain integers; for RSA, we need modular multiplications. Even if we optimize the "multiplication" part with a sub-quadratic algorithm, the modular reduction is still quadratic. I am not aware of any modular exponentiation algorithm which goes below $O((\log n)^3)$ complexity. Edit: it seems such algorithms actually exist, see this presentation. Nov 14, 2011 at 17:30
• @Paŭlo: for a 500k-bit prime, you can arrange for generation of candidates which are not multiple of 2, 3, 5, 7, 11... up to, say, 23. This can divide the number of calls to Miller-Rabin by 3 or 4, hence my estimate of 100000 tests (200000 in total, for $p$ and $q$). Miller-Rabin rules out a non-prime with probability at least $3/4$, so the average number of invocations is bounded by $4/3$ (actually much closer to 1, because the $3/4$ probability is a worst case). Nov 14, 2011 at 17:34

Somewhat off-topic and not with practical considerations as the other answers, but a well written paper (recently, compared to the question) that benchmarks actual limitations:

The authors provide a chapter on RSA scalability (Chapter 3) and a nice overview/benchmarks (Table 4.1) for different key sizes. (E.g. 1 GB key --> 654s encryption)

https://eprint.iacr.org/2017/351

Background: There was a (perhaps not so serious) contribution to the NIST post-quantum competition, that suggested scaling RSA to read 128 bits of post-quantum security. (Note that this is possible due to the square-root overhead of breaking RSA with Shor's algorithm vs encryption/ decryption). In particular the authors suggest to chain many $$(2^{31})$$ 4096-bit primes resulting in a 1-terabyte key to reach 128-bits of security.