Thoughts on Stanford's CS255 Intro to Cryptography
I’ve always been interested in Cryptography – the field is a really compelling marriage of beautiful mathematics with critical real-world applications. Much of the modern internet would not be possible without the clever math behind asymmetric encryption.
This Winter quarter I took Stanford CS255: Introduction to Cryptography. To be honest, it was quite challenging as I was still working full time as a software engineer on Chrome, and I was never that strong in the math department. However, I got a ton out of this course and solidly recommend it to anyone interested. The professor – Dan Boneh – was amazing and made the complex topics approachable. He publishes the textbook for the course for free here. Here are some interesting things I picked up from the course that I want to take with me.
Real-world cryptography engineering is hard. Cryptography primitives like AES are extremely powerful and extremely difficult to use correctly. It’s not a good idea to implement real-world cryptography yourself, unless you are an expert in the subject. For example, a common refrain during the course was “if you’re typing the letters ‘AES’ into your text editor, you’re doing it wrong.” This is in reference to doing encryption without authentication, or encrypting things in a way that makes it possible for someone to switch the encrypted message with another one without your knowledge.
On top of that, there are so many aspects of the implementation that could become side-channel attacks if you’re not careful. The overall advice was to always use a high-level high-quality cryptography library to ensure you’re doing things right.
All of the the cryptography we use today rests on the assumption that
P≠NP. The famous P vs. NP problem in computer science asserts that
that the set of problems which can be solved quickly (in polynomial time P
)
is smaller than the set of problems that can be verified quickly (in
nondeterministic-polynomial time NP
). Much of modern cryptography is based
on “hard” problems that we believe to be in NP
like prime factorization.
Proving that P=NP
would immediately destroy the security guarantees of these
cryptosystems.
Overall, a main challenge in cryptography is finding good, “hard” math problems
in NP
that are hard on average, not only in some cases.
Quantum computing is a threat to some, but not all crypto algorithms. In general, the advice was that anything with 128 bits or less of security is in danger. Anything that relies on prime factorization or the discrete logarithm problem, like RSA and Diffie-Hellman respectively, are toast. Key exchange algorithms have moved on to elliptic-curve cryptography because it adds additional security for the same key lengths, however it is still not completely safe from quantum attacks.
AES256, the workhorse of modern symmetric cryptography, is not currently thought to be in danger at the moment. NIST is currently working on cryptography standards for the post-quantum world.
Elliptic curve cryptography is one of the most beautiful applications of mathematics. Elliptic curves were discovered in ancient Egypt as a purely mathematical curiosity with no real applications, rescued in scrolls from the burning library of Alexandria, forgotten for hundreds of years, and then re-discovered in the 1980s by modern mathematicians Koblitz and Miller as something that would improve the security of asymmetric cryptography. Elliptic curve cryptography combines all three major fields of math: algebra, geometry, and analysis, and underpins much of the HTTPS communication we do every day.