數論與密碼學培訓

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!