Department of Computer Science and Technology

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.).