MAS345 Codes and Cryptography

Semester 2, 2017/18 10 Credits
Lecturer: Dr Jayanta Manoharmayum uses MOLE 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.


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

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.