I've thought for a long time that this explains why the NSA is recording so much encrypted data. When QCs are available they will be able to decrypt all the things. Imagine what they'll learn.

That’s a bit conspiracy-theorist-ish but unfortunately in the present climate and given that has transpired from the Snowden leaks not at all implausible.

Either they have made a breakthrough in number theory that allows factorisation over finite fields, or they have a quantum computer already, or they are banking on having one soon. In any case, storage is so cheap that it makes sense to just record the traffic (which is useful for sigint anyway) and refer back to it “if and when”.

Of course, much of what we consider “public-key encrypted” traffic is actually encrypted with a symmetric cipher whose encryption is impervious to Shor’s Algorithm… it is the key-exchange process that really uses the textbook public-key encryption algorithms. So much of the traffic is technically impervious to whatever advances they have made, but of course once you have captured the key-exchange “handshake” that sets up the session and exchanges the symmetric cipher keys, you’re all set to retrieve the plaintext from the intercept.

There are public-key algorithms (particularly those based on lattices) that we currently hold to be secure against attack by quantum computers. I am surprised these are not seeing more adoption amongst the “enlightened paranoid cypherpunk elite”. Here is a primer on such “post-quantum cryptography” approaches, courtesy of the good folks at Wikipedia: https://en.wikipedia.org/wiki/Post-quantum_cryptography

In the process they'd get key exchanges too and it's easy to correlate traffic.

I thought it was a really straightforward obvious idea. I'd do it if I were them and had such deep pockets.

QC is clearly coming. Lots of news lately.

I was agreeing with you, of course if they have intercepted all traffic they have both public-key encryption key exchange and the resulting symmetrically encrypted traffic and that they could correlate it... I’m sorry if I was a bit longwinded and pedantic in my reply, I didn’t realise I was talking to virtual Hacker News nobility (with ten times the karma I do!).

Hacker News nobility is a dubious title haha.

Btw on post quantum crypto: the problem is that most of it has not yet had enough conventional cryptanalysis. Makes no sense to use an algorithm immune to quantum speedup if it's conventionally vulnerable.

Yeah I know, I’m no expert, but I studied applied mathematics.

What would be nice book / video / web link that will give a decent intro to a novice like me?

citation? A theoretical understanding of bits in quantum superposition would support the notion of traversing all combinatorially related possibilities however that is not the case for any realizable quantum computer. Realizable machines are based on specific quantum logic gates. otherwise you would have to design at the electron level, a new processor for every problem.

Here's the citation: https://en.wikipedia.org/wiki/Shor%27s_algorithm

You do need to update yourself. There are standard gates, complete computation theories, and algorithms for lots of interesting problems. Those aren't even new.

aes isn't broken by factorization of composites of prime. if the op had said rsa, sure, but they said aes (it was changed you can tell because there was never such a thing as 128bit rsa), but thanks for telling me about that "new" shor's algorithm devised in 1994.

Yes, comment edition sometimes leads to misunderstanding. But there was 128bit RSA, it was in use up to the middle of the 00's.