Breaking public-key crypto would have to be the biggest coup in SIGINT in the history of ever. Much bigger than cracking the Enigma. Just thinking about the sheer volume of internet traffic at every level and in every country that relies on the security of encryption makes the possibility of it being fundamentally broken a literal nightmare.
I don't think it has happened. But if it had, that would be the kind of secret that would go in the President's book of secrets right along with the existence of National Treasure or the Men in Black. :P Snowden would never have a clue.
And, as a corrolary of this, you presently won't have much to fear if this break has happened, simply because the NSA would only use it _very_ sparingly, like how the allies used the Enigma break during WW2.
Of course, if the cat ever gets out of the bag, that situation would change.
Carrying on from that thought, the various mathematician-employing agencies have now had over 60 years to study the problem of "how much can we use this critical information-revealing tool without exposing its existence?" If they can identify an upper bound on "sparingly", that's immensely valuable.
During WW2, the Allies would crack messages to locate submarines.
Now killing a submarine once you know where it is, is pretty easy. The problem is finding the submarine, and explaining how you were found. To handle that, the Allies used a form of parallel construction. They would send a spotting plane over the area, to spot the sub and give a plausible reason to have located the submarine.
That just moves the problem. Now the Germans start wondering how the spotting planes seem to be so damn good at being in the right place at the right time.
NSA's statement wasn't "we've got an RSA-breaking machine" or anything like that; the highlights are 0) folks are using RSA-1024, which public sources only ascribe 80 bits' worth of security to, smaller than the usual margin; 1) RSA gets slow with long keys: according to public sources, 256-bit security requires RSA-3072, which is 64x slower than the equivalent ECC-512; 2) RSA-breaking implementations keep getting gradually better over time, whereas ECC's effort-to-break has basically stood still.
Their own ("Suite B") guidelines for use of public algorithms to protect classified data tell the US government to use ECC, not RSA. (AES-256 is fine, though.) They licensed patents for particular implementation techniques:
http://en.wikipedia.org/wiki/NSA_Suite_B_Cryptography
Bruce Schneier, reacting to Bamford's statement about a cryptographic breakthrough, said: "Another option is that the NSA has built dedicated hardware capable of factoring 1024-bit numbers. There's quite a lot of RSA-1024 out there, so that would be a fruitful project. So, maybe."
(There's a lot of RSA-1024 out there partly because old 1024-bit SSL certs die hard, and people are lazy about switching to bigger keys if, for example, it would make establishing SSL sessions more expensive.)
Finally, perhaps not related to public-key crypto but really interesting, the XKeyScore deck had the bullet point "Show me all the VPN startups in country X, and give me the data so I can decrypt and discover the users" as one of the things you can tell the system to do. That could just refer to one of those protocols that everyone knows is broken but is still in use (MS-CHAP/PPTP) or to either a protocol/implementation break or something else affecting VPNs we currently think are secure.
Maybe the best argument against a crypto breakthrough is that it's clearly extremely hard (none of the brilliant mathematicians working in the open are close) whereas attacks on implementations and protocols are relatively easy. If you have a big bag of 0-days, have stolen some certificates (as Stuxnet seemed to indicate), and are inside a bunch of service providers, it seems almost redundant to put a lot of effort into factoring big numbers, unless some big technical improvement basically falls in your lap.
The Snowden comment about VPN startups has intrigued me for a while. My theory is that the NSA have filter boxes placed at the exit points of these VPNs. They sit and wait to see what pops out (at the VPN unencrypted endpoint) and then vacuum it all up. Most VPN endpoints are at major networking points. I.e London, New York, Frankfurt, etc.
It is then a simple matter of waiting for a user to leak personable identifiable information. A visit to Facebook or an email account, etc whilst connected to the VPN is all it takes, and then you can group and map browser headers (roughly) to VPN users.
Maybe they can break small key length SSL when they really need to. If there is TLS traffic of interest popping out from the VPN exit, then they store it and process it later, probably in some massive AWS compute intensive cloud service even.
VPN users have to remember that their traffic is protected from your machine as far as the VPN exit node. After that exit point onwards to the requested web server, you are as naked as before. Worse is that it lulls users into a false sense of security.
Not that NSA probably has the resources to do, and are probably doing all of it at the same time. Having smart thinkers spending time trying to come up with analytical solutions isn't that costly in comparison to a lot of other venues of attacks.
Well, it would be a very well guarded secret. But even then the question is how public key crypto is broken. If they can easily generate exploits for implementations, because they know a essential implementation detail everybody else is missing, then it would be fundamentally different from being able to break RSA directly, or if they have a constructive prove of P=NP.
Remember that factoring primes isn't know to be NP Hard. There is no complexity breakthrough required, we just don't know how to do it quickly. So we don't get P=NP from any factoring breakthrough.
Depends on the breakthrough, we know that multiplication is in P and therefore factorization in NP. So a P?=NP breakthrough may or may not have consequences for integer factorization. ( Actually since I did write that, I wonder if P=NP would invalidate any public key crypto, since efficient encryption should be in P.)
Wouldn't they start moving important web sites off of SSL then? Surely they couldn't be the only ones able to exploit if they found it. Or at least, if they found it, others could theoretically as well.
I don't think it has happened. But if it had, that would be the kind of secret that would go in the President's book of secrets right along with the existence of National Treasure or the Men in Black. :P Snowden would never have a clue.