Can NSA Crack Public Key Encryption?

Much ink has been expended over the past few months over the Administration's floated idea of requiring encryption back doors in new technology implementions -- an idea that, for now, the Administration has put to rest. But the whole issue is only relevant in the first instance if, in fact, current public key encryption techniques are uncrackable by brute force or other analytic decryption methods. That background fact is one that I have assumed to be true -- not based on my own mathematical analysis of course but based in part on the confident word I have had from a number of good cryptographers. But what if they are wrong? What if, in fact, certain common implementations of public key encryption techniques are not as robust as we think they are? What if, in truth, the decrypters have found a way to break strong large-prime number encyrption?

The question is not as theoretical as it seems. At the Association for Computing Machinery conference the other day, several cryptographers presented a paper in which they claimed that some implementations of Diffie-Hellman keys (which are at the core of most HTTPS and VPN systems) can be cracked. If they are right, perhaps as much as 30-50% of current traffic can, with very large effort, be decrypted. And that, itself, would be a revalation. There is, to be sure, very complex math behind this discussion, but for those who want a layman's summary, this blog is well worth reading.