# Public-key cryptography security given NSA resources

I was wondering how secure public private key encryption methods are.

If two individuals were sending emails back and forth forever, where each person would encrypt the body of the email they were sending with the other person's public key, would anyone be able to decrypt the body of those emails after a while?

I'm assuming that each person creates their own private-public key pair and then if you wanted to send someone an email you would grab their public key and encrypt your message before sending it to them. They would then decrypt it with their own private key.

Wikipedia (http://en.wikipedia.org/wiki/Public-key_cryptography) claims that its effectively impossible to decrypt email if all you know is the public key. But is this really true? What if you had the resources of the NSA, are they not able to brute force the decryption?

• You may be interested in reading about perfect forward secrecy, in which a unique session key is derived for each round of communication. In the event that the master key is compromised, the session keys remain uncompromised (and vice versa). Commented Jun 15, 2013 at 1:06
• Related: Crypto.SE's How big an RSA key is considered secure today?, as well as Security.SE's How to estimate the time needed to crack RSA encryption?. Commented Jun 15, 2013 at 1:31
• It's best to always assume that a Wikipedia article is incorrect until proven otherwise by a reliable source. :) Commented Jun 15, 2013 at 9:44
• So, is perfect forward secrecy a way to thwart man in the middle attacks? As long as the man in the middle doesn't have the private keys then this ensures authentication. Is that correct? Commented Jun 18, 2013 at 3:34

The entire internet security is based on the presumption that factoring prime numbers is NP-hard, as it has yet to be proven mathematically that it is (But centuries of looking indicate its not trivial). If the NSA has figured out a way to do it more efficiently, then RSA is broken.

If the NSA (or anyone else) have broken RSA - they unlikely to use the exploit on you, as the value of people not knowing they have the ability far exceeds any value you as an individual hold (Read the stories of the allies in WWII letting the Germans 'win some' - at the cost of lives, so as not to tip them off that Enigma was cracked). If they do use the exploit, they will manufacture a plausible story as to how the information was "cracked" by something like guessing the key, exploiting a flaw in the implementation etc This is where the statistics come into play - if the NSA gets lucky a "statistically significant" number of times, it will be noticed, so they need to get lucky just enough not to get noticed.

Other exploits (a gun to your head, a big bag of cash etc) are cheaper and as effective. The NSA is more likely to "persuade" your co conspirator to just give them any info they want....

In summary - If the NSA is interested, you can't be certain you can stop them, and can not be certain that you have succeeded. If you have an unlucky streak, maybe it was the NSA.... Best and only practical bet is not to upset the NSA and end up on their radar....

Even for the NSA, brute forcing an algorithm like RSA isn't feasible. There's always the very, very remote possibility the NSA/CIA/etc has discovered an exploit in RSA and managed to keep it a secret (See relevant xkcd comic) but it's much more likely that if the RSA needed to obtain a private key they would try to get it through a man-in-the-middle attack, social engineering, or infecting a computer where the private key is stored (Microsoft and others give the NSA information on unpatched exploits) rather than trying to break the encryption itself.

Modern public-key cryptography is impossible to brute-force. And since that's a rather vague claim, let's be specific: If you had a computer that was so advanced that it had hit the upper bounds of physical possibility and there was no room for improvement left in Moore's Law, you could give it the task of brute-force cracking a message encrypted with 256-bit encryption, and it wouldn't be anywhere even close to finishing before the sun burned out. 2^256 is a very, very large number.

This doesn't mean that it's impossible to read encrypted messages. You just need to have a better way of doing it than that. The two main possibilities are to attack it using a mathematical flaw in the cryptography, which would make the cryptanalysis process much faster than brute force, or to find some way (such as with a virus) to get ahold of the sender's private key.

Everyone is able to brute force the decryption, it's just a matter of how long.

The question/concern you should have is if the NSA (or whomever) has done something to change the algorithmic complexity of the encryption itself (either by finding a mathematical shortcut or something like quantum computing that circumvents usual limitations or of course, attacking the security of your private key).

• No one is able to (successfully) brute force the decryption, because the "matter of how long" is simply too long. Commented Jun 14, 2013 at 22:58
• @MasonWheeler - It's not as though you need to go through the entire keyspace to decrypt the message (unless you're very, very very unlucky). Commented Jun 14, 2013 at 23:01
• No, but on average (by the definition of the word "average") you have to go through half of it. That's too big. Even going through 1% of it is too big. As I said in my answer, 2^256 is a very, very large number. Commented Jun 14, 2013 at 23:06
• And, there are certain accepted assumptions about the hardware and methodology that matter. Task specific hardware that isn't practical or obtainable by anyone but, likely makes a big difference. Commented Jun 15, 2013 at 0:20