# 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 :) –  William Hird Nov 14 '11 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)$. –  Samuel Neves Nov 14 '11 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). –  Samuel Neves Nov 16 '11 at 15:39
@Samuel: Thank you for taking the time to run the numbers! –  William Hird Nov 16 '11 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 a 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 in average the half of that 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 in regions which are similar to brute-forcing DES (and I'm not sure how much of this is parallelizable).

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? –  William Hird Nov 14 '11 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. –  Thomas Pornin Nov 14 '11 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. –  Paŭlo Ebermann Nov 14 '11 at 15:57
@ThomasPornin: One out of $\log n$ numbers close to $n$ is prime, so using Miller-Rabin it takes about $(\log n)^4$ operations to find a prime number close to $n$. You surely know this, but I think this complexity should be stated somewhere explicitly. Using Schönhage-Strassen for multiplication (see en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm) one can do multipliations in slightly more than $\log n \cdot \log\log n$ operations instead of $(\log n)^2$, cutting the cost of exponentiation/key generations accordingly. –  j.p. Nov 14 '11 at 16:50
@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). –  Thomas Pornin Nov 14 '11 at 17:34