Course pages 2018–19
Cryptography
Principal lecturer: Dr Markus Kuhn
Taken by: Part II CST 50%, Part II CST 75%
No. of lectures: 16
Suggested hours of supervisions: 3-4
Prerequisite courses: Mathematical Methods I from the NST Mathematics
course, Discrete Mathematics, Complexity Theory
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(2n), 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, ElGamal
signatures, DSA, RSA signatures, 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 & Hall/CRC (2nd ed.).