alt Hacker NewsTangentially related but regarding RSA and ECC... With RSA can't we just say: "Let's use 16 384 bit keys" and be safe for a long while?
And for ECC, I know many are using the "2 exp 255 - 19" / 25519 for it's unlikely to be backdoored but it's only 256 bits but... Can't we find, say, "2 exp 2047 - 19" (just making that one up) and be safe for a while too?
Basically: for RSA and ECC, is there anything preventing us from using keys 10x bigger?
Replies
Many implementations limit the RSA key size to 8,192 or 16,384 bits (because the maximum bit length determines indirectly how much stack space is required).
for a 10x bigger key the quantum computer needs to be 10x bigger - linear scaling.
the time to run the algorithm has cubic scaling - 1000x more time required.
but it remains exponentially faster, just 1 minute becomes 1 day, 1 day becomes 3 years. still "easily" broken
> for RSA and ECC, is there anything preventing us from using keys 10x bigger?
you can run benchmarks yourself: openssl speed rsa1024 rsa2048
also this (slightly dated) java ex writeup covers this well: https://www.javamex.com/tutorials/cryptography/rsa_key_lengt...
tldr trade off is found between better performance and how many years the data needs to be assumed confidential
> Tangentially related but regarding RSA and ECC... With RSA can't we just say: "Let's use 16 384 bit keys" and be safe for a long while?
That's correct. The quantum computer needs to be "sufficiently larger" than your RSA key.
> Basically: for RSA and ECC, is there anything preventing us from using keys 10x bigger?
For RSA things get very unwieldy (but not technically infeasible) beyond 8192 bits. For ECC there are different challenges, some of which have nothing to do with the underlying cryptography itself: one good example is how the OpenSSH team still haven't bothered supporting Ed448, because they consider it unnecessary.