MAS345 Codes and Cryptography
Note: Information for future academic years is provisional. Timetable information and teaching staff are especially likely to change, but other details may also be altered, some courses may not run at all, and other courses may be added.
| Semester 2, 2022/23 | 10 Credits | ||||
| Lecturer: | Prof Neil Dummigan | Timetable | Reading List | ||
| Aims | Outcomes | Teaching Methods | Assessment | Full Syllabus | |
The word `code' is used in two different ways. The ISBN code of a book is designed in such a way that simple errors in recording it will not produce the ISBN of a different book. This is an example of an `error-correcting code' (more accurately, an error-detecting code). On the other hand, we speak of codes that encrypt information - a topic of vital importance to the transmission of sensitive financial information across the internet. These two ideas, here labelled `Codes' and `Cryptography', each depend on elegant pure mathematical ideas: codes on linear algebra and cryptography on number theory. This course explores these topics, including the real-life applications and the mathematics behind them.
Prerequisites: MAS220 (Algebra); MAS330 (Topics in Number Theory) desirable
No other modules have this module as a prerequisite.
Outline syllabus
- Codes and linear codes
- Hamming distance
- Examples of error-correcting/error-detecting codes
- Classical methods of cryptography
- Results from number theory
- Public key methods of cryptography
Aims
- To introduce the basic ideas connected with error detection and error correction, and various examples of useful codes
- To demonstrate the importance of the simple concepts of Hamming distance and the minimum distance of a code in the theory of error detection and error correction
- To illustrate how linear algebra can be used to good effect in the theory of linear codes
- To give an overview of cryptography from the most basic examples to modern public key systems
- To introduce the number-theoretic concepts used in public-key cryptosystems and to show how these are applied in practical examples
Learning outcomes
- To understand the mathematical ideas underlying the theory of error- detection and error-correction using linear codes.
- To apply the theory of error-detecting and error-correcting codes.
- To understand the mathematical ideas underlying the theory of cryptography.
- To apply the theory of cryptography.
Teaching methods
Lectures, problem solving
20 lectures, no tutorials
Assessment
One formal written examination.
Full syllabus
0. Modular arithmetic and linear algebra
Reminders from previous modules. Addition, multiplication and
subtraction modulo n. Zp is a field. Powers in
Zp, Fermat's Little Theorem. Linear algebra over
F=Zp: reduced row echelon form, elementary row
operations, transpose, subspaces of Fn, spanning sets,
null spaces, bases, dimension, rank, the Rank-Nullity Theorem.
Codes and linear codes, codewords, encoding, decoding, error detection and error correction. Examples to include the ASCII code, the ISBN-10 and ISBN-13 codes and the Sheffield University Registration number code. Hamming distance, minimum distance and weights. Nearest neighbour-decoding is maximum liklihood decoding. The Hamming sphere, error-correcting index. The Sphere-packing bound, perfect codes. Generator matrices and parity check matrices. The dual of a linear code. The special Hamming codes. 2. Classical Methods of Cryptography
Substitution ciphers as permutations of alphabets. Caesar, Vigenere and affine encryption. One-time keys. 3. Modern Methods of Cryptography
The problems of cryptography: key distribution. One-way functions. Application to passwords. The discrete logarithm. The contrast between raising to a power in modular arithmetic and computing discrete logarithms. Key exchange and Diffie-Hellman. The ElGamal public key cryptosystem. Introduction to elliptic curves and their use in cryptography.
Reading list
| Type | Author(s) | Title | Library | Blackwells | Amazon |
|---|---|---|---|---|---|
| C | Hill | A first course in coding theory | 003.54 (H) | Blackwells | Amazon |
| C | Koblitz | A course in number theory and cryptography | 512.81 (K) | Blackwells | Amazon |
| C | Singh | The code book | Blackwells | Amazon | |
| C | Welsh | Codes and cryptography | 003.54 (W) | Blackwells | Amazon |
| C | Young | Mathematical ciphers: from Caesar to RSA | Blackwells | Amazon |
(A = essential, B = recommended, C = background.)
Most books on reading lists should also be available from the Blackwells shop at Jessop West.