2
$\begingroup$

Shor's algorithm has already been implemented to factor 15 into 3*5 on a simple quantum computer. Is technology to the point that we should consider RSA deprecated?

$\endgroup$
7
$\begingroup$

I don't think so. We are still an incredibly long way away from quantum computers being built that can deal with RSA (if they ever happen). It's certainly a good idea to get ready and have alternatives in hand. If you are really paranoid then you can start encrypting things today that still need to be secret in 10-20 years using a combination of RSA and lattice-based encryption. Otherwise, I would just wait.

$\endgroup$
  • 2
    $\begingroup$ you need 3661 qubits for RSA 1024. the issues with quantum computers are mostly entanglement related due to manufacturing. i only saw a 6 qubit span entangle consistently. we stopped looking at the problems when He3 hit 10k per litre. just too rich for academics $\endgroup$ – b degnan Jun 25 '17 at 17:49
  • $\begingroup$ Never thought about mixing known-good RSA with questionably-good quantum-resistant crypto. I like that idea a lot! $\endgroup$ – Daffy Oct 17 '18 at 20:50
3
$\begingroup$

I agree with Yehuda, but I'd like to add that if even if you decided that RSA is rendered obsolete by quantum computing, what algorithm would you move to that itself isn't obsolete due to quantum computing?

While work is ongoing in this area, the simple fact is that we don't have widely accepted algorithms that are quantum resistance. In fact, NIST recently made a call for submissions, not for quantum resistant algorithms, but for the criteria needed to evaluate quantum resistant algorithms.

So for the time being use RSA, a 2048 bit prime size is considered relatively safe, but if you're paranoid move to 3072 and accept the performance hit that will come with such a move. Or use EC, but it's not immune to QC either.

$\endgroup$
  • 1
    $\begingroup$ If you don't trust RSA you could use face to face meetings for key distribution (of a OTP). My current understanding is that good quantum computing could really hurt RSA but only sort of hurts AES. $\endgroup$ – daniel Jun 26 '17 at 8:14
  • $\begingroup$ Agreed. Sufficiently large QC would kill 2048 or even 3072 bit RSA, but not AES. The current guidance for AES is just to move to 256 if you're worried about QC. $\endgroup$ – Swashbuckler Jun 27 '17 at 1:17
3
$\begingroup$

It depends by what you mean by “phase out“, which depend about your use case, as detailed below.

Use case 1: sending secrets now, secure for 10–20 years

This case corresponds to the answers of Yehuda and Swashbuckler

If you worry about using RSA today, as said in the other answers, RSA is probably good enough for secrets which should last for on or two decades, specially since there is no post-quantum alternative yet offering the same things as RSA (public key crypto, cheap, widely understood security claims).

Indeed, a quantum computer able to factor RSA key is probably decades away from now; and the other quantum-safe alternatives are either much more expensive (face to face key exchange, quantum cryptography) and/or much less understood yet (post-quantum cryptography algorithm.)

Use case 2: long term security: secrets which should be safe by more than two decades

If you want security which is guaranteed to last more than decades, then you have to be careful with RSA (or ECC or Diffie Hellman). No one can guarantee that state-level adversary will not have access to big enough quantum computers by then (nor can anyone guarantee they will have access to them: future is hard to predict). The problem is that all the alternatives available now are not drop-in replacements for RSA...

Note that this use case include the scenario where you deploy today an infrastructure which will be used 15 years from now, with secrets supposing to last for 5 years. (see this 2015 talk by Michele Mosca [abstract/slides/video]. A “solution” in this case would be to ensure your infrastructure could be updated when reasonable quantum-safe alternatives to RSA emerge, but it is much easier said than done :

  • MD5 is still widely used while cryptographically broken for a long time, and easy replacements performing the same function are available
  • it is not clear if RSA replacements will perform the same functions, or “only” similar ones

Use case 3: defining cryptographic protocols/standards for the decades to come

In this case, you should definitely consider investigating alternatives to RSA, as the NIST is doing now

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.