MA7010 - Number Theory for Cryptography (2023/24)
| Module specification | Module approved to run in 2023/24 | ||||||||||||||||
| Module title | Number Theory for Cryptography | ||||||||||||||||
| Module level | Masters (07) | ||||||||||||||||
| Credit rating for module | 20 | ||||||||||||||||
| School | School of Computing and Digital Media | ||||||||||||||||
| Total study hours | 200 | ||||||||||||||||
|
|||||||||||||||||
| Assessment components |
|
||||||||||||||||
| Running in 2023/24(Please note that module timeslots are subject to change) |
|
Module summary
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.
Prior learning requirements
Standard Entry Requirements for Masters Courses in SCDM
Syllabus
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. The Agrawal-Kayal-Saxena primality test
Discrete logarithms and methods for their calculation (baby step-giant step and Pohlig-Hellman algorithms).
Congruence equations: applications of the Chinese Remainder Theorem to cryptography, quadratic residues and their properties. Gauss’ quadratic reciprocity theorem and techniques for solving congruence problems. Legendre and Jacobi symbols and their use in primality testing.
Introduction to integer factorisation: methods covered will be selected from basic sieving algorithms, Fermat factorisation, Pollard’s rho method.
Advanced methods for integer factorisation: quadratic sieve and number field sieve algorithms, factorisation using elliptic curves; continued fractions, and their use in integer factorisation.
Complexity: polynomial and exponential time for algorithms; NP complete problems. Examples, e.g. knapsack problem.
Random and pseudo random numbers.
Balance of independent study and scheduled teaching activity
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.
Learning outcomes
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.
Assessment strategy
Students will evidence satisfactory completion of an opensource online programme such as Python Essentials (https://edube.org/study/pe1). 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/electronic calculation or to examples that can be analysed using electronic calculators/computer algebra systems.