The Mathematics of Data Encryption

Today's world of electronic credit card payments, email, and commerce over the World Wide Web would not be possible without secure methods of transferring information. These methods use data encryption schemes that are based on mathematics.

One of the most common schemes is called the RSA cryptosystem, which gets its name from the last-name initials of its inventors, Ron Rivest, Adi Shamir, and Len Adelman, who came up with the idea in the 1970s. Since that time, researchers have probed the vulnerability of RSA in an effort to understand how secure the system really is.

The February 1999 issue of the Notices of the AMS published an article by Dan Boneh entitled "Twenty Years of Attacks on the RSA Cryptosystem". The article surveys a number of ways in researchers which have tried to expose weaknesses in the RSA system. These efforts range from easily avoidable attacks that seize upon misuses of the RSA system, to more sophisticated ones that exploit some deep results in mathematics, to ones based on observations of the time it takes to perform calculations needed for RSA. Boneh's conclusion is that, although some insightful attacks have been found, "At the moment it appears that proper implementations [of RSA] can be trusted to provide security in the digital world."

The RSA system uses the fact that an efficient method for factoring numbers into their prime factors has not been discovered---in fact, it is widely believed that no such method exists. An important open question in this area of research is whether cracking the RSA cryptosystem is as hard as factoring. The article mentions a recent result by Boneh and his co-author, R. Venkatesan, which provides evidence that, in certain cases, the answer to this question may be no.