John
The reason I asked: updating a few certs at office recently I nuked an older F5 LTM device by installing a 4096 bit key/cert pair - the load on the appliance (Linux based) shot up from less than 1 to about 30 and became so excruciatingly slow it was nearly impossible to back the change out (web GUI and ssh were both nearly non-responsive)..
Multiplying two n-bit numbers naively costs O(n^2) operations (one can do better with Karatsuba and related tricks), and exponentiation costs O(n) multiplications (so O(n^3) in total). So assuming the device is using something like Montgomery multiplication you'd expect about 8x increased load. 30x sounds like there *could* be some other issue with the implementation, but a significant slowdown is not unexpected.
On modern hardware, including modern F5s, this problem doesn't exist... but from what reading I've done it seems 4096 buys you very little anyway ?
Depends who you ask. https://www.keylength.com/ - NSA Suite B recommends at least 3072 bits. - BSI says 2048 bits for now, but 3072 bits for 2017 and beyond. - ANSSI and NIST both say 2048 bits should be fine through 2030. All of the above recommendations seem to assume the adversary is classical rather than quantum.
With a theoretical quantum computer attacking is there any significant gain with the bigger key size?
Shor's algorithm runs in time O(n^2) and requires O(n) qubits to factor an n-bit number. The first doesn't offer much help: you're only increasing the time by 4x going from 2048 to 4096 bits. I'm not qualified to comment on how much the second helps because it's not at all clear to me how the expense/difficulty of building a quantum computer scales with the number of qubits. But if you're worried about defending against general-purpose quantum computers, there are other weak points you should be shoring up (no pun intended): 256-bit symmetric ciphers, preferably with 256-bit blocks (so Rijndael-256 rather than AES-256); and ephemeral key exchanges that don't rely on Diffie-Hellman (Google is deploying RLWE and LWE schemes in the next coupld years; supersingular isogeny D-H also looks promising, but there's a recent attack that suggests caution). In sum: it's a strange and scary new world once general-purpose quantum computers arrive. In the next few years we're going to see the rollout of new post-quantum ciphersuites. For now, maybe we should learn to stop worrying and love the qubit :) -=rsw