MT466 Public key cryptography (Term 2: Dr S D Galbraith)

Prerequisites: MT282, MT362

Teaching: 33hr lectures

Assessment: 2hr written examination

Aims

• To introduce some of the mathematical ideas essential for an understanding of public key cryptography, such as discrete logarithms, integer factorisation, lattices and elliptic curves;
• To introduce several important public key cryptosystems, such as RSA, Rabin, El Gamal, Diffie-Hellman, DSA, ECIES, ECDSA;
• To discuss modern notions of security and attack models for public key cryptosystems.

Learning outcomes

On completion of the course, students should:

• be familiar with the RSA and Rabin cryptosystems, the hard problems on which their security relies and certain attacks on them;
• have a basic knowledge of finite fields and elliptic curves over finite fields, and the discrete logarithm problem in these groups;
• be familiar with cryptosystems based on discrete logarithms, and some algorithms for solving the discrete logarithm problem;
• know the definition of a lattice and be familiar with the LLL algorithm and some applications of lattices in cryptography and cryptanalysis;
• be able to define security notions and attack models relevant for modern theoretical cryptography, such as indistinguishability and adaptive chosen-ciphertext attack.

Content

Background: Integers modulo n; Chinese remainder theorem; finite fields; fast exponentiation; RSA; discrete logarithms; public key cryptography and security; complexity theory; primality testing and certificates.

RSA/Rabin: Key generation; implementation; encryption and signatures with OAEP; the RSA problem and relationship with factoring; square roots modulo a prime; Hastad attack; Wiener attack and continued fractions; smooth numbers; survey of integer factorisation methods such as method and index calculus.

Discrete logarithms: Diffie-Hellman; El Gamal encryption and signatures; Schnorr and DSA signatures; Diffie-Hellman problem and decision Diffie-Hellman; methods to solve discrete logarithms such as baby-step-giant-step, Pollard rho and lambda, index calculus.

Lattices: Definition of a lattice; CGH cryptosystem; LLL algorithm; lattice attacks on RSA with small public or private exponents.

Elliptic curves: Group law; Hasse bound; group structure; ECC protocols; elliptic curve factorisation and primality certificates; Maurer equivalence of DH and DL.

Indicative Texts

Cryptography: an introduction – Nigel Smart (McGraw Hill) Library Ref. 001.5436 SMA

Cryptography theory and practice – Doug Stinson (CRC press, 2nd ed.) Library Ref. 001.5436 STI