module specification

Aims of the module: what key skills and knowledge will it enable students to develop?

This module, together with MA7009, Discrete Mathematical Structures provides the essential grounding needed to complement the algorithms and techniques encountered in spring semester modules in cryptography and information security.  It aims to describe relevant topics in the theory of the natural numbers that underpin much of 21st century cryptographic security. It is designed to complement, in particular, MA7011 -Applications in Cryptography and Cryptanalysis and can be taken either before or after this module depending on a student’s start point without disadvantaging them.

Additionally, this module will support a series of mini investigations designed to develop students’ ability to take the ideas they encounter, apply them with realistic datasets and draw appropriate conclusions. These will principally be delivered via procedures written in the mathematical programming language MAPLE in which students will be supported as they gain fluency but the module will also encourage students to use other languages such as Python where these are applicable to the problems being investigated. 

The module will principally introduce topics in number theory but their application to cryptography will be stressed as they are introduced and in the initial weeks the module will also provide a brief overview of the subject of cryptography and its historical context.

Fundamental skills in mathematical programming through MAPLE and Python.

Introduction/Recap of key terms and concepts in cryptography: symmetric and asymmetric cryptography. Example of classical ciphers (affine, Playfair, Vigenere) and the use of frequency analysis in cryptanalysis.

Introduction to number theory: early history, prime numbers and their distribution. The infinity of primes and the prime number theorem.

Prime testing: Fermat’s Little Theorem; probabilistic methods, Miller Rabin Test and other Monte Carlo methods. Carmichael numbers and Korselt’s criterion.

Introduction to integer factorisation: methods covered will be selected from basic sieving algorithms, Pollard’s rho method. Advanced methods for integer factorisation: fermat factorisation, quadratic sieve and number field sieve algorithms, continued fractions and their use in integer factorisation    

Euler totient function, primitive elements and the Euler Fermat Theorem. Discrete logarithms and methods for their calculation (index calculus, baby step-giant step algorithms).

Congruence equations: the Chinese Remainder Theorem, quadratic residues and their properties. Gauss’ quadratic reciprocity theorem and techniques for solving congruence problems.

Complexity: polynomial and exponential time for algorithms; NP complete problems. Examples, e.g. knapsack problem.
 
Random and pseudo random numbers.

The module has 200 learning hours. 4 hours per week contact is divided approximately equally between lectures covering background, theory and examples and workshops in PC Labs which involve discussion of the ideas and an opportunity for students to practice the mathematical techniques and to develop proficiency in programming in Maple and Python and investigating realistic data sets. The remaining hours of private study will allow students to follow the self study python guide, complete background reading, work on exercises and prepare for assessment.

This module aims to enable students to:
LO1:    Acquire and consolidate skills in programming languages needed to support cryptographic investigation and to engage in self reflection to identify and address any other areas of skills deficiency that may affect performance on the course.
LO2:   Assimilate key concepts in number theory and demonstrate understanding of the properties of the natural numbers appropriate to cryptography;
LO3:    Understand and apply key theorems that prove the properties needed to demonstrate cryptographic security;
LO4:    Describe how the concepts in number theory encountered in the module find application in the modern technological world.

The online python tutorial is a pass/fail component that students will work on in the early weeks of the module, submitting evidence of completion to the Module Leader.

The investigations will be carried out in using python or an appropriate computer algebra system such as MAPLE enabling students to analyse and apply the theory to large examples.

A final exam will assess understanding of the theory and its application to hand calculation or to examples that can be analysed using electronic calculators

https://rl.talis.com/3/londonmet/lists/27B8AAC4-A274-827C-C3A1-95145C7132E7.html?lang=en-US&login=1

Recommended Texts: 
Koblitz, N. A Course in Number Theory and Cryptography Springer 2nd Edition (2012). ISBN: 9780387942933
Holt, J and Jones, J Discovering Number Theory WH Freeman 2001
Katz, J and Lindell, Y Introduction to Modern Cryptography CRC Press 2014