Skip to main content
Information Security

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

7
  • Your last paragraph is interesting. Could you give some (naturally) rough idea of how very very long the public keys likely should be (in a certain near future)? Commented Sep 14, 2016 at 10:13
  • I am not by any means an expert in this, so please don't take what I say as an authoritative source. When using Grover's search a number of q-bits necessary to attack RSA key it linearly related to key length. I believe there are engineering challenges operating quantum computer with more than few q-bits. If today we had megabytes-long RSA keys and a proven and working quantum gate, such long RSA key would likely be safe for foreseeable future. Since relationship is linear, this is not a trapdoor function. Commented Sep 14, 2016 at 13:24
  • 1
    @KirillSinitski - Your advice is bad. If there's a breakthrough in QC that makes having ~1000 coherent qubits usable for computation, it may not take long to extend to ~10000/100000 coherent qubits. Decrypting with a b-bit private RSA key (on a classical computer) scales as O(b^3). Breaking a b-bit RSA modulus on a QC (with O(b) qubits) also scales as O(b^3). Say your computer takes 4 millisecond to encrypt with 4096 bit RSA key (benchmarking on my computer with openssl speed rsa gives 7 ms) ; it would take about a billion years to do a single decryption with a 1 MB modulus. Commented Sep 16, 2016 at 16:11
  • 1
    @KirillSinitski Yes, nothing's proven quantum resistant, but there's also no public key algorithm/trapdoor function that's proven to be resistant to classical computers in fast polynomial time. It's generally very hard to prove that some new algorithm no one has conceived of (utilizing properties not thought of) can't solve a problem. Quantum computers aren't magic machines that can do everything faster; they can just do certain operations very well like the quantum Fourier transform that can be exploited to find periods in discrete groups used to factor numbers or solve discrete logs. Commented Sep 19, 2016 at 17:14
  • 1
    Also your alternative is not feasible -- massively parallel supercomputers with custom ASICs are not close to being fast enough to generate or use megabyte (8388608 bit) sized RSA keys. Humans have only found about 50 primes in our history that are 4194304 bits or larger (and all have very special form like Mersenne primes). (Using one of these 50 large known primes in a key would be extraordinarily weak as you could factor by dividing the modulus against the 50 known large primes). There's no reason to think post-quantum algorithms should be susceptible to quantum computation. Commented Sep 19, 2016 at 18:22