## 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. **Z**_{p} is a field. Powers in
**Z**_{p}, Fermat's Little Theorem. Linear algebra over
**F**=**Z**_{p}: reduced row echelon form, elementary row
operations, transpose, subspaces of **F**^{n}, 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.