Number Theory and Cryptography (Coursera)

Without it, nobody would be able to make secure payments over the internet, or even log in securely to e-mail and other personal services. In this short course, we will make the whole journey from the foundation to RSA in 4 weeks. By the end, you will be able to apply the basics of the number theory to encrypt and decrypt messages, and to break the code if one applies RSA carelessly. You will even pass a cryptographic quest! As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.

Course 4 of 5 in the Introduction to Discrete Mathematics for Computer Science Specialization

Syllabus

WEEK 1

Modular Arithmetic

In this week we will discuss integer numbers and standard operations on them: addition, subtraction, multiplication and division. The latter operation is the most interesting one and creates a complicated structure on integer numbers. We will discuss division with a remainder and introduce an arithmetic on the remainders. This mathematical set-up will allow us to created non-trivial computational and cryptographic constructions in further weeks.

WEEK 2

Euclid's Algorithm

This week we'll study Euclid's algorithm and its applications. This fundamental algorithm is the main stepping-stone for understanding much of modern cryptography! Not only does this algorithm find the greatest common divisor of two numbers (which is an incredibly important problem by itself), but its extended version also gives an efficient way to solve Diophantine equations and compute modular inverses.

WEEK 3

Building Blocks for Cryptography

Cryptography studies ways to share secrets securely, so that even eavesdroppers can't extract any information from what they hear or network traffic they intercept. One of the most popular cryptographic algorithms called RSA is based on unique integer factorization, Chinese Remainder Theorem and fast modular exponentiation. In this module, we are going to study these properties and algorithms which are the building blocks for RSA. In the next module we will use these building blocks to implement RSA and also to implement some clever attacks against RSA and decypher some secret codes.

WEEK 4

Cryptography

Modern cryptography has developed the most during the World War I and World War II, because everybody was spying on everybody. You will hear this story and see why simple cyphers didn't work anymore. You will learn that shared secret key must be changed for every communication if one wants it to be secure. This is problematic when the demand for secure communication is skyrocketing, and the communicating parties can be on different continents. You will then study the RSA cryptosystem which allows parties to exchange secret keys such that no eavesdropper is able to decipher these secret keys in any reasonable time. After that, you will study and later implement a few attacks against incorrectly implemented RSA, and thus decipher a few secret codes and even pass a small cryptographic quest!