Revenge of the Mathematicians

computerIf the mathematicians have their way, the days are numbered for two stalwarts of secure data exchange on the Internet: RSA encryption and the Diffie-Hellman algorithm. This article reports that industry experts predict that Diffie-Hellman will be compromised in a few years and RSA a few years after that.

This is a very big deal. Diffie-Hellman is used to enable two parties engaged in a conversation to exchange a secret encryption key using information that is publicly available. Once they have calculated this secret key, then can then exchange information confidentially. The remarkable thing about the Diffie-Hellman algorithm is that it enables the two sides to agree on a key that, practically speaking, only the two of them share, even though they started the calculation using information everybody in the world could know.

RSA is also critically important to electronic communication. RSA is used to help encrypt communications between a web site and its visitors. Specifically, when a user visits a site, her browser downloads a public-key certificate from the site’s web server. That public-key certificate is simply an electronic document that contains the server’s identify and its public key. Where there is a public key, there must be a matching private key, and so is the case for the web server: it keeps a private key for itself on hand, beyond the public’s reach.

Here’s where RSA comes in. When the user receives the public-key certificate through his browser. he extracts the public key of the server from it. He uses that public key to encrypt a randomly generated value he has produced. This randomly generated value will be the secret shared key he and the server will use to encrypt their communications. So, he encrypts the secret shared key with the server’s public key, and he sends that encrypted packet to the server. When the server receives the encrypted packet, it uses its corresponding private key (remember, public and private keys appear in pairs, and one unlocks the other) to decrypt the secret shared key it received. Now both the user and the server know what the secret key is, and they can use it to exchange data that should remain private, such as credit card numbers.

So, Diffie-Hellman and RSA are critical security functions. They both enable keys to be exchanged between two communicating parties. Both depend on a mathematical function called the discrete logarithm. Solving discrete logarithms is even more difficult than it sounds, and no one has been able to come up with an approach that can solve such equations easily. When someone does, then Diffie-Hellman and RSA will be broken.

Recent advances in mathematics suggest that solving the discrete logarithm problem isn’t just a desirable. Rather, it is quickly becoming a reality, thanks to new algorithms and new approaches. That is very bad news for Diffie-Hellman and RSA and has prompted a number of security experts and, indeed, nations to require using a different algorithm that does not depend on solving the discrete logarithm problem: elliptic curve cryptography, Elliptic curve cryptography, or ECC, is likewise used for key exchanges, but it depends on solving equations that describe the shape of ellipse. No algorithms have yet been devised which solve such equations efficiently, and that is why ECC is growing in popularity as a more secure alternative to RSA and Diffie-Hellman.

It is interesting to see how intertwined mathematics and computer science are. Indeed, the entirety of information security depends on the work of mathematicians. Without their contributions, there would be no confidentiality, no authentication, and no verification that a message wasn’t manipulated in transit. In other words, there would be no such thing as secure communication on the Internet.

Change occurs due to a variety of forces. In this case, mathematics is both driving the change and providing the response. The next time a Computer Science student asks me why he has to study so much math, I’ll show him this article.


About Ray Klump

Associate Dean, College of Aviation, Science, and Technology at Lewis University Director, Master of Science in Information Security Lewis University,, You can find him on Google+.

Leave a Reply

Your email address will not be published. Required fields are marked *