[_phred]

The best publicly known attacks on RSA reduce the attack time by a few orders of magnitude at best. A functional quantum CPU could reduce that by a few more orders. Your 4096-bit RSA key is still 2^3072 times harder to break, so even with reductions we're still talking about "heat death of the universe" amounts of time to brute force.

RSA has issues but as of yet hasn't yielded entirely to cryptanalysis.

As the article says, it's easier to attack the system and try to get the plaintext, or coerce you into giving up your key through legal means.

Edit: adding a link to Wikipedia's article on post-quantum crypto, it's a good place to start understanding how to answer these type of questions:

http://en.wikipedia.org/wiki/Post-quantum_cryptography

[pja]

"Your 4096-bit RSA key is still 2^3072 times harder to break,"

No, because the difficulty of breaking RSA keys doesn't scale in the same way as symmetric encryption. Integer factorisation is much easier than a brute force search of the keyspace. A 1024-bit RSA key is believed to be roughly equivalent to an 80-bit symmetric key. A 3072 bit key is about as hard to brute force as an 128-bit symmetric key.

(Source: http://www.keylength.com/en/4/ )

[_phred]

Ah shoot, you're right. I'm an armchair crypto geek at best.

In any case, you can choose a public key exponent large enough to still make it a hard problem to crack in a reasonable amount of time. Barring some huge vulnerability in RSA that hasn't been discovered in 30 years of public scrutiny, of course.

[Dylan16807]

Are you sure about that? As far as I understand it, generic quantum computation would cut that '3072' in half, and using quantum computers specifically for factoring reduces problems to a low polynomial time.

[Filligree]

Correct. Shor's algorithm renders any use of RSA... pointless.

And while there are limits to the applicability of Grover's algorithm, you're correct that it effectively cuts the number of bits in any cryptosystem it applies to in half. Which, to my nonexpert eyes, looks to be most of them.

[_phred]

Hmm, yes, I think I conflated the asymmetric vs symmetric cases.

Shor's algorithm is very tasty, but when the real world demonstrations at top research facilities are saying, "yes, we factored 21 into 7x3, but WITH ENTANGLEMENT"[1] it makes me think that scaling to RSA-size prime factors is still a good way off.

Listen, the US government is powerful, but building a full scale quantum crypto decoder ring in complete secrecy _decades_ ahead of everyone else? I just don't think so. Maybe I'm a sheep for not wanting to believe the government so powerful and corrupt, but the whole thing sounds like a tin foil fantasy.

I don't doubt they would if they could, though. And they've done as much as they can with present day tech: supercomputers, mass data collection, penetration of target systems, exploiting SSL's many weaknesses, tapping undersea lines, and legally strong-arming perceived threats into giving up their encryption keys. I just don't think we need to get science fiction involved.

[1] http://www.nature.com/nphoton/journal/vaop/ncurrent/full/nph...

See http://en.m.wikipedia.org/wiki/Shor's_algorithm

[Filligree]

Hey, I wasn't claiming practical quantum computers existed. Just that, at whatever point running Shor's algorithm becomes practical, RSA will be pointless.

[Achshar]

But what if they have some vulnerability in the crypto itself? thus skipping the need to brute force.