MATH3401 Cryptography and Codes III
This course deals with two very concrete applications in data transfer which heavily involve very abstract mathematics. The first one is about error-correcting codes. In particular they are used in compact discs to cope with scratches. But error-correcting codes are also used more widely, e.g., for data transmission over noisy channels.
The next application is cryptography. Nowadays it is not only used by spies and secret agents. It makes internet browsing and in particular internet banking secure. Cryptography also prevents unauthorized people from capturing and listening to your mobile phone talks.
In term 1, we start with the basics of error-correcting codes, working with vectors and matrices with coefficients in ℤp (p prime) or more generally over a general finite field, and discuss the error-detection and error-correction capabilities of various codes, such as the Hamming, Golay, cyclic and Reed-Solomon codes.
In term 2, we start with the notion of trapdoor function which is in the essence of the whole area of open key cryptography. We consider several number theoretical problems (i.e. factorization and discrete logarithm problem) which provide us with examples of trapdoor functions. Then we go through Diffie-Hellman key exchange scheme and RSA cryptosystem. We end up with elliptic curves and the modification of Diffie-Hellman based on it.
Material from Linear Algebra I and Elementary Number theory II will be heavily used in this course. Algebra II may also help.
Outline of Course
- Introduction to codes: Hamming distance, error detection and error correction: procedures, capabilities, probabilities. Equivalence of codes.
- Revision of linear algebra over 𝔽p.
- Linear codes: rank, generator and check matrices. Equivalence. Dual codes. Decoding methods: standard array, syndromes.
- Hamming codes, sphere-packing bound and perfect codes. Decoding with a Hamming code. Golay Codes.
- Finite fields 𝔽pr. Linear codes over such fields. Cyclic codes and Reed-Solomon codes.
- Introduction to open-key cryptography, the notion of "trapdoor function". The factorization and the discrete logarithm problems.
- Diffie-Hellman key exchange scheme.
- RSA cryptosystem and possible attacks on it. Various factorization methods and conditions on the parameters on RSA.
- Elliptic curves over rational numbers and over finite fields.
- Elliptic curve Diffie-Hellman scheme.
- Lenstra factoring algorithm.
For details of prerequisites, corequisites, excluded combinations, teaching methods, and assessment details, please see the Faculty Handbook.
Please see the Library Catalogue for the MATH3401 reading list.