24

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.

William Hird
  • 501
  • 1
  • 5
  • 18

3 Answers3

23

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

Of course, security is not only about resisting attacks; it is also about having confidence in being able to resist attacks. My confidence in a system which uses RSA with one-million-bit keys would be near zero... because it makes no sense. RSA is secure because big integers are hard to factor. The best known algorithms with the best available hardware fail at about 1024 bits; 2048 bits are more than enough. Going beyond is making a wild and totally unsubstantiated guess about what not-yet-discovered algorithms may look like, which is speculation on rumours of legends about mythical glimpses of the future. When someone talks to me about having an oversized RSA key, like a 8192-bit key "just to be safe", I see it as if he was talking about buying a SUV to demonstrate his manhood (in your case, you are advocating buying an aircraft carrier).

Thomas Pornin
  • 86,974
  • 16
  • 242
  • 314
  • 1
    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
  • 3
    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
  • 9
    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
  • Shouldn't we be considering the actual use case of the encryption? Specifically, how long do we need this data to be secured? I think it is common to assume that there is someone waiting to receive encrypted data and immediately decrypt it, but that isn't always the case. Signed files (like software binaries) could be published and available for 10+ years. After that amount of time has passed the CPU power needed for factoring will likely be trivial, and the files in question could still contain proprietary information. – ubiquibacon Jan 01 '23 at 01:26
7

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.

Paŭlo Ebermann
  • 22,656
  • 7
  • 79
  • 117
  • 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
  • 1
    @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 http://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
  • @jug: But do we need to run the full Miller-Rabin on each candidate, or can we in most cases stop earlier? – Paŭlo Ebermann Nov 14 '11 at 17:16
  • 2
    @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. – Thomas Pornin Nov 14 '11 at 17:30
  • 2
    @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
  • @R1w thanks for your edit suggestion, but I've declined it because they actually removed some of the meaning which I wanted to convey (counting the operations). I've done another edit of my own, please check whether it now is better. – Paŭlo Ebermann Feb 16 '21 at 23:48
1

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.

Fleeep
  • 512
  • 2
  • 12