課程大綱：數論與密碼學培訓
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!
加入高級會員獲得助教答疑
