I'm going to take a 10,000 foot view of this. While the scale and speed of the problem has grown immensely, we're still dealing with the same basic sorts of issues that lead to someone wrapping their cigars in a secret order in 1862 and losing the Battle of Antietam. The details have changed, but the basics remain the same.
And I'm going to speak about what I know as an IT professional and amateur historian. I can't usefully talk about what's actually going on inside the military and governments.
Finally, I talk a lot here about cryptographic hash algorithms, not asymmetric encryption, because that's what I know about in detail. The same principles apply.
Modern encryption is generally considered mathematically impossible to break
...and then nobody ever broke encryption again! Except they did. All the time. So let's deal with that.
When an algorithm is declared "mathematically impossible to break" that really means it would take an infeasible amount of time using YOUR SIDE'S current understanding of computing hardware and techniques to brute force all possibilities. This is like declaring your armor "impenetrable" because none of YOUR SIDE'S guns will go through it in YOUR SIDE'S testing. The enemy might have other ideas.
For example, cryptographers are currently having to deal with the sudden rise of cheap parallel computing in the form of GPUs (ie. graphics cards). For $10,000 you too can have a supercomputer dedicated to cracking encryption.
And what was good enough last year might not be good enough next year. Or five years. Or twenty. Organizations are often very slow to upgrade their security, especially when it "works" where "works" means they haven't had a major break in. That they know about (or more importantly, that their users know about). Yet.
As an example, Jon Callas, PGP's CTO said this...
It's time for us all to migrate away from SHA-1.
Luckily, there are alternatives. The National Institute of Standards and Technology already has standards for longer -- and harder to break -- hash functions: SHA-224, SHA-256, SHA-384, and SHA-512. They're already government standards, and can already be used.
He said that in 2005. 10 years later, certificate authorities were still issuing SHA-1 based SSL certificates. After several high profile SSL attacks, it was the major browsers, not the certificate providers, that banned SSL certificates which still used SHA-1. This pattern of authorities dragging their feet and using outdated security measures is very common.
It also assumes that everyone is following correct procedure, and there are no flaws in the algorithm. People inevitably fail to follow correct procedure, and there are usually flaws in the algorithm. The result is cryptographers can use these flaws in procedure and algorithm to whittle away at the number of possibilities carving off orders of magnitude at a stroke.
This is why, for example, current civilian encryption algorithms are made public and undergo years of public review by cryptographers before being accepted as standard. This allows many people with many different ideas to study and attack the algorithm and try to find the flaws before everyone starts using it. For example, SHA-3 came out of the public NIST Hash Function Competition which pitted dozens of algorithms against each other for years of review. Dozens were found to be flawed.
Finally, why break the encryption if you don't have to? Encryption is just one piece of the security puzzle, and amateurs rely on it far too heavily. Often you can get the unencrypted message by some other means. Steal it off their hard drive. Or find a point in the communications link when the message is sent in the clear or using a weaker algorithm. For example, Operation Ivy Bells where US submarines regularly tapped an unencrypted undersea communications cable.
Finally, there is the increasingly sophisticated Side-channel Attacks wherein you extract information from the act of encryption itself. Like how much power or memory is used, or precisely how long it takes, or otherwise innocuous leaks of electromagnetic radiation. If you can monitor these often unsecured things, and watch enough encryption happen, and know something about what's being encrypted, you can extract the key.
Everything from Engima to SHA-1 have fallen to these basic problems with "mathematically impossible to break" algorithms.
Note: there is one actually mathematically impossible to break algorithm, the one-time pad. Assuming the pads are truly random, and only ever used once, and the bad guys never get a hold of them. But they are symmetrical.
How did this change espionage?
I can answer this real quick: at a basic level, not much.
The encryption game hasn't changed much since WWII. Its mathematicians looking for weaknesses in the algorithms, banks of computers to exploit those weaknesses, and everyone else finding a way around the encryption.
Before WWII, cryptanalysis was considered a puzzle, so they figured people good at puzzles would be good at decryption. This made sense since the algorithms were quite simple and quite flawed and the number of possibilities were quite low.
WWII changed all that with Engima. Suddenly its machines could churn out encrypted messages far faster and far more robust than ever before. Crossword fanciers weren't going to cut it, so increasingly powerful machines were built to exploit the subtle flaws in Engima leading to general purpose computers.
That's about as far as I'll go on opinion, I can't usefully speak to what's actually going on in detail.
This is all the different ways you can remotely add or extract information from an environment. For example, 30 years ago this was your phone line and that's about it. And you only got whatever conversation you were having at that moment. About the most sophisticated thing you could do as an attack is call people up and pretend you're someone else.
Now it's your smart phone, computer, laptop, tablet, Wi-Fi, TV, TV app box, car, thermostat, refrigerator, social media accounts, bank accounts, credit cards, utility meters, etc... all of these are potential vectors for attack. All of these contain a multitude of information about you. Even the settings on your thermostat can give an attacker information about when you're not at home.
Governments and militaries are the same way. They're all interlinked with each other with massive databases of information available to that network. Break into the troop net of an armored unit and you might be able to see everything they're doing in real time.
All these new attack surfaces mean increased opportunities for the users to use the wrong procedure, or for a flaw to be found in your algorithm, or a spot which is poorly secured (many Internet appliances have no encryption).