# Cryptography

**Principal lecturer:** Dr Martin Kleppmann

**Taken by:** Part II CST 50%, Part II CST 75%

**Term:** Lent

**Hours:** 16

**Format:** In-person lectures

**Suggested hours of supervisions:** 4

**Prerequisites:** Complexity Theory, Discrete Mathematics.
Mathematical Methods I from the NST Mathematics course

**Exam:** Paper 8 Question 3; Paper 9 Question 4

**Past exam questions, timetable**

## Aims

This course provides an overview of basic modern cryptographic techniques and covers essential concepts that users of cryptographic standards need to understand to achieve their intended security goals.

## Lectures

**Cryptography.**Overview, private vs. public-key ciphers, MACs vs. signatures, certificates, capabilities of adversary, Kerckhoffs’ principle.**Classic ciphers.**Attacks on substitution and transposition ciphers, Vigenére. Perfect secrecy: one-time pads.**Private-key encryption.**Stream ciphers, pseudo-random generators, attacking linear-congruential RNGs and LFSRs. Semantic security definitions, oracle queries, advantage, computational security, concrete-security proofs.**Block ciphers.**Pseudo-random functions and permutations. Birthday problem, random mappings. Feistel/Luby-Rackoff structure, DES, TDES, AES.**Chosen-plaintext attack security.**Security with multiple encryptions, randomized encryption. Modes of operation: ECB, CBC, OFB, CNT.**Message authenticity.**Malleability, MACs, existential unforgeability, CBC-MAC, ECBC-MAC, CMAC, birthday attacks, Carter-Wegman one-time MAC.**Authenticated encryption.**Chosen-ciphertext attack security, ciphertext integrity, encrypt-and-authenticate, authenticate-then-encrypt, encrypt-then-authenticate, padding oracle example, GCM.**Secure hash functions.**One-way functions, collision resistance, padding, Merkle-Damgård construction, sponge function, duplex construct, entropy pool, SHA standards.**Applications of secure hash functions.**HMAC, stream authentication, Merkle tree, commitment protocols, block chains, Bitcoin.**Key distribution problem.**Needham-Schroeder protocol, Kerberos, hardware-security modules, public-key encryption schemes, CPA and CCA security for asymmetric encryption.**Number theory, finite groups and fields.**Modular arithmetic, Euclid’s algorithm, inversion, groups, rings, fields, GF(2^{n}), subgroup order, cyclic groups, Euler’s theorem, Chinese remainder theorem, modular roots, quadratic residues, modular exponentiation, easy and difficult problems. [2 lectures]**Discrete logarithm problem.**Baby-step-giant-step algorithm, computational and decision Diffie-Hellman problem, DH key exchange, ElGamal encryption, hybrid cryptography, Schnorr groups, elliptic-curve systems, key sizes. [2 lectures]**Trapdoor permutations.**Security definition, turning one into a public-key encryption scheme, RSA, attacks on “textbook” RSA, RSA as a trapdoor permutation, optimal asymmetric encryption padding, common factor attacks.**Digital signatures.**One-time signatures, RSA signatures, Schnorr identification scheme, ElGamal signatures, DSA, PS3 hack, certificates, PKI.

## Objectives

By the end of the course students should

- be familiar with commonly used standardized cryptographic building blocks;
- be able to match application requirements with concrete security definitions and identify their absence in naive schemes;
- understand various adversarial capabilities and basic attack algorithms and how they affect key sizes;
- understand and compare the finite groups most commonly used with discrete-logarithm schemes;
- understand the basic number theory underlying the most common public-key schemes, and some efficient implementation techniques.

## Recommended reading

Katz, J., Lindell, Y. (2015). *Introduction to modern
cryptography*. Chapman and Hall/CRC (2nd ed.).