MAS345 Codes and Cryptography
|Semester 2, 2017/18||10 Credits|
|Lecturer:||Dr Jayanta Manoharmayum||uses MOLE||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 which 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: MAS211 (Advanced Calculus and Linear Algebra); MAS330 (Topics in Number Theory)
No other modules have this module as a prerequisite.
- 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
- 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
- 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.
Lectures, problem solving
20 lectures, no tutorials
One formal 2.5 hour written examination. Format: 4 compulsory questions, two on Codes and two on Cryptography.
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 cyphers as permutations of alphabets. One time keys. Enigma: simplified examples. 3. Modern Methods of Cryptography
The problems of cryptography: key distribution. Reminder of RSA algorithm. Importance of primality testing and factorisation. Fermat pseudoprimes and Carmichael numbers. The Miller-Rabin test. Contrast simplicity of multiplication and the difficulty of factorisation. 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.
|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.