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