Cryptography

Cryptography (Winter 2016) is an ancient subject. For millennia, people have wanted to send messages that cannot be intercepted by a snooping third party. At the same time, other people have been interested in reading encoded messages designed to foil them.

For most of its history, cryptography was a linguistic endeavor, and codebreaking involved tactics like counting letter frequencies and looking for repeated sequences. Furthermore, cryptography faced a seemingly insurmountable problem, which goes something like this. Suppose Alice wants to send a message to Bob. They should agree on a mechanism by which the message is to be encrypted, and they should agree to this “privately,” so that no one else knows the encryption mechanism. But how do they do this if they live thousands of miles away, and all their communication has to be public?

This seems impossible, but in the 1970s, several researchers, including Diffie and Hellman, and later Rivest, Shamir, and Adleman (RSA), worked out mechanisms by which Alice and Bob can indeed send secure messages, even though all their communication is done publicly. Their methods are based on the difficulty of solving certain number-theoretic problems, such as factoring large numbers. Thanks to their advances, modern cryptography is an entirely mathematical subject.

In this class, we will study the key topics in modern cryptography, including the Diffie-Hellman and RSA cryptosystems and others, as well as some attacks on them. As part of the process, we will discuss the necessary background in number theory, as well as other branches of mathematics that pop up naturally along the way. For example, we will see why there are some extremely clever ways of factoring numbers!

Cryptography nowadays includes more than just encrypting and decrypting messages. Other topics include digital signatures, in which a recipient can verify the sender of a message, and zero-knowledge proofs, in which I can convince you that I know how to answer a computationally difficult question without giving you any information about how I do it. We will discuss these topics as well.