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, 2020/21 10 Credits
Lecturer: Prof Neil Dummigan 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: 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 2.5 hour written examination. Format: 4 compulsory questions, two on Codes and two on Cryptography.

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.

1. Codes
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.
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.