Computational Number Theory

The cryptographers at Microsoft Research hope that someday, cryptography applications such as e-commerce and secure email will be an ordinary part of everyone’s experience with computers. But for these applications to become widely used, cryptography itself must be invisible to the user. If it’s a hassle, people won’t use it.

With this practical concern in mind, they’re engaged in serious study of computational number theory: thinking of new ways, new mathematical tricks to speed up the processes of encryption, decryption, and key generation and make them more secure and more efficient.

Cryptography is based on arithmetic and algebra – the commonly-used Rivest-Shamir-Adleman (RSA) method of encryption is based on a series of operations involving very large integers: whole numbers usually at least 300 digits long. Fortunately, fast mathematical calculation is what computers do best. It is only in the last 10 years, as processor speeds have increased dramatically, that widespread use of cryptography has become possible. An ordinary RSA 1024-bit decryption involves about 3,000 multiplications and divisions with 310-digit numbers, something that could take months with pencil and paper. Today’s ordinary computer can do it in a fraction of a second, but on the Internet, even this can be too slow.

One of the most useful tricks is called Montgomery Multiplication – a technique for performing division, which we all remember from math class as the most difficult of arithmetical operations, by means of multiplication. Its inventor, the famous mathematician Peter L. Montgomery, is a member of the Cryptography Group.

These days, Montgomery is most interested in different methods of factoring large integers, because the difficulty of factoring these large numbers is the foundation of cryptography. Montgomery was a member of the team that recently succeeded in factoring a number of 155 digits – it took them four months with a roomful of powerful computers. This experiment showed that keys on the old 512-bit model (155 digits) were insufficient, and that the doubling of the size of the keys to 1024 bits (310 digits) was appropriate. This increase makes the numbers about a million times harder to factor – even with the best techniques available today.

The security of cryptography seems immune to the development of bigger, faster computers on the silicon chip model, although if anyone ever succeeds in building a quantum computer – one that functions on the subatomic level – the rules of the game could change. A more immediate threat lies in the possibility that someone will come up with an improved algorithm, a different factoring method, and Montgomery is trying to find it first. “If someone could come up with a way to factor large numbers easily, public key cryptography would no longer work,” he says. He’s trying to solve this problem, or at least get an idea of how hard it is, “because we don’t want to leave it to others. We want to know ourselves, because we’re basing a lot on it.”