Number Theory and Cryptography

Overview

A prominent expert in the number theory Godfrey Hardy described it in the beginning of 20th century as one of the most obviously useless branches of Pure Mathematics”. Just 30 years after his death, an algorithm for encryption of secret messages was developed using achievements of number theory. It was called RSA after the names of its authors, and its implementation is probably the most frequently used computer program in the world nowadays. 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 course we will start with the basics of the number theory and get to cryptographic protocols based on it. 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.

Syllabus

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.

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.

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.

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!