20 credits / 30 lectures
Cryptography is the mathematics behind information security: that is, keeping digital information secret or ensuring it can't be changed without detection. In this course we first cover the two kinds of secret key cryptosystems (block ciphers and stream ciphers), along with cryptographic hash functions. We then learn some computational number theory, before studying the public key cryptosystems and signature schemes (RSA and ElGamal) based on the factoring and discrete log problems, and elliptic curve cryptosystems. Emphasis throughout is on how all these systems can be attacked mathematically! Finally we'll have one lecture on Bitcoin, just for fun because it uses hash functions, signatures and elliptic curves.
What will be covered in the course (we might not do all of this):
- Stream ciphers. We cover the theory of linear feedback shift registers, correlation generators, filter generators, correlation attacks and algebraic attacks.
- Block ciphers. We cover Feistel and SPN ciphers, and modes of operation of block ciphers. Depending on time we might cover differential cryptanalysis briefly.
- Hash functions. We do all the background probability including the birthday paradox, and cover some generic attacks on Merkle-Damgard hash functions, including multi-collision attacks and the long message attack.
- Elementary number theory. We study the integers modulo n. Emphasis is on computation, i.e., how to do computations on integers modulo n.
- Public key encryption and digital signatures. We explain the concept of a one-way function and cover Diffie-Hellman key exchange and the RSA and ElGamal cryptosystems and signature schemes.
- The factoring problem. We cover the p-1 method, Pollard's Rho method, and the factoring methods from Fermat onwards leading to the quadratic sieve. We explain how the same logic underlies most of the different factoring methods. We also do some primility testing.
- The discrete log problem. We cover the baby-step giant-step algorithm, Pollard's Rho method, and the Index Calculus method.
- Elliptic curves. We cover the basics of how an elliptic curve group works and how it is used in cryptography. We describe supersingular elliptic curves and how they can be used to build identity-based cryptosystems.
- Bitcoin. We explain briefly how hash functions and elliptic curve signatures are used to enable Bitcoin.
- The course is geared towards honours students in either Maths or Computer Science, but it is a mathematics module and there is no programming in it.
- Having done 2IA and 2LA or 3DM would be an advantage, but is not necessary. We assume some familiarity with matrices, but we will cover all the number theory and probability theory you need in the course.
Tel: +27 21 650 3191
University Avenue North
University of Cape Town
Private Bag X3, Rondebosch 7701