Cryptography

Over the past few weeks I've been looking into cryptography, an area of computer science I've not had the chance to explore much before. I decided to start by taking a Coursera specialization on Introduction to Applied Cryptography, which turned out to be a high-quality program, rather to my surprise¹.

The specialization comprises 4 courses:

• Classical Cryptosystems and Core Concepts
• Mathematical Foundations of Cryptography
• Symmetric Cryptography
• Asymmetric Cryptography

In particular, the first two courses, taught by Prof. William Bahn, are both comprehensive and rigorous. The latter two courses, taught by Prof. Sang-Yoon Chang, are noticeably less so. Nonetheless, the overall program is a very worthwhile introduction to a broad and exciting field.

In the first course we learn about the history of cryptography, both cryptology, the study of hiding information, and cryptanalysis, the study of how to decode it. Together, the two comprise cryptography. From the scytale of ancient Greece to the Caesar cipher used by the famed Roman general to the Vigenère cipher of early Renaissance that was considered unbreakable for 300 yrs., we see that humans have sought clever ways to hide information since time immemorial. We also see how to break these codes using frequency analysis, how polyalphabetic ciphers hinder frequency analysis by hiding the distribution of letters, and how the only truly unbreakable cipher is the one-time pad, which relies on pure randomness.

In the second course, probably my favorite, we launch into the mathematics behind cryptography. Modular arithmetic and primes are introduced as the foundations for important results like Euler's Theorem. The Chinese Remainder Theorem is presented as a different way of representing numbers, which is a mind-opening insight. Finally, probabilistic primality testing² via Fermat's little theorem and the Miller-Rabin test are covered.

In the third course, we delve into symmetric cryptography, in which encryption and decryption use the same key, a secret that is shared between sender and receiver. The differences between block ciphers (which encrypt a fixed number of bits at a time) and stream ciphers (which encrypt a stream of data byte by byte) are presented. An ideal block cipher is shown to be one that randomly (but reversibly) maps inputs and outputs³. The Feistel cipher, an approximation of an ideal block cipher, and DES, the widely used standard based on the Feistel cipher, are covered, as is the later replacement AES.

Finally, in the fourth course, asymmetric cryptography is presented. For millenia it was widely assumed that cryptography had to be symmetric. This made secret distribution a major weak point, allowing only the largest organizations, like nation-states, to use cryptography. Asymmetric cryptography changed this by allowing two parties to establish secure communication by sending each other non-secret information. This is the idea behind RSA, which relies on the difficulty of prime factorization to allow parties to authenticate each other and send confidential information, and Diffie-Hellman key exchange, which relies on the hardness of the discrete log problem to allow two parties to end up with a shared secret.

Cryptography is at the heart of cybersecurity, a field that is exploding in importance as more activity goes digital. Its foundation is mathematics, which gives it a beauty, elegance, and intellectual challenge that many of its practitioners find intoxicating. I've only scratched the surface here, and will eagerly look for opportunities to learn more in the future.