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