Introduction to cryptography
I teach Introduction to cryptography [NDMI100] in the winter semester of 2021/2022. The lecture will cover the basics of both theoretical and practical cryptography, focusing on protocols currently used on the Internet.
We will meet on Wednesdays 9:00 in S4.
If you want to consult anything, please write an e-mail to mares+kry@kam.mff.cuni.cz and we will discuss possibilities.
date | topics | recording |
---|---|---|
29. 9. | Cryptographic primitives: symmetric and asymmetric ciphers, hash functions, random generators. Protocols and roles. Kerckhoffs principle. Simple protocols: multi-party communication, signatures, message authentication codes, hybrid ciphers, challenge-response authentication. Designing an auction protocol: padding, nonces, sequence numbers, signatures, session IDs. | |
6. 10. | Know your enemy. Basic types of cryptographic attacks. Security level. Different kinds of "birthday attacks". One-time pad a.k.a. Vernam's cipher. Perfect security and its limits. Secret sharing. | video (sorry for low quality) |
13. 10. |
Secret sharing and threshold schemes (construction with polynomials).
Introduction to symmetric ciphers.
Block ciphers: trivial examples, an attempt to define security, ideal block ciphers.
General constructions: iterated ciphers, substitution-permutation networks, Feistel networks.
DES: history, structure, critique, work-arounds (3-DES).
Puzzle: Why is the security level of 2-DES only 57 bits? | video |
20. 10. | AES a.k.a. Rijndael: history, structure, critique. How to (mis)use a block cipher: padding, modes ECB, CBC, CTR, and OFB. Information leaks in CBC and CTR modes. | video |
27. 10. |
Block ciphers: Padding oracle attacks on CBC. Ciphertext stealing.
Stream ciphers (briefly): LFSR-based constructions, eSTREAM project, Trivium, RC4, ChaCha20.
Hash functions: requirements, Merkle-Damgård construction by iterating compression function,
length extension attacks.
Illustrations: Block cipher modes (plaintext, ECB, CBC), visual secret sharing (layer 1, layer 2, combined), Trivium, ChaCha20. Puzzle: How to toss a coin over a phone call? | Sorry, no recording today. |
3. 11. | Commitment using hash functions. Birthday attacks on hash functions: the tortoise, the hare, and the turtle. How to obtain a compression function: Davies-Meyer construction from a block cipher. Examples: MD5, SHA-1, SHA-2. Sponge functions: principle and analysis for random permutations. Keccak, SHA-3, SHAKE-n. | video |
10. 11. | Parallel hashing: Merkle trees. Symmetric signatures (MACs): construction from hash functions (KMAC and HMAC), different ways of combining a MAC with a cipher. CBC-MAC. Information-theoretic MAC from 2-independent linear functions or from polynomials. Practical polynomial MACs: GCM mode, Poly1305 (sketch). | video |
17. 11. | No lecture today due to holiday. | |
24. 11. | Generating random bits: pseudo-random generators from symmetric ciphers, physical randomness (LavaRand, circular oscillators, …), combining both – Fortuna, RDRAND, /dev/random. Putting all symmetric cryptography together: a secure channel. Basics of algorithmic number theory: Complexity of arithmetics. Euclid's algorithm and Bézout's coefficients. Multiplicative group modulo N. Little Fermat's and Euler's theorem. Lagrange's theorem on subgroups (without proof). | video |
1. 12. | Plan: More number theory: Chinese remainder theorem and its constructive version. Computing Euler's function. Factoring vs. primality testing. Fermat and Rabin-Miller tests (R-M without proof), Carmichael numbers, mention of Agarwal's deterministic test. Generating large primes. Multiplicative group is cyclic, discrete logarithms, how to find a generator. Discrete square roots, Legendre symbol. RSA cipher: Definition, acceleration tricks. Properties of RSA: commutativity, homomorphism with respect to multiplication (application: blind signatures). Attacks: short messages, small secret exponent, meet in the middle, similar primes, similar messages, multiple keys with the same modulus. |
Sources
- Web page of the previous run of this lecture including video recordings
- Web page of the first run of this lecture (in Czech, includes video recordings).
- My notes (in Czech)
- Niels Ferguson, Bruce Schneier: Practical Cryptography. Wiley Publishing, 2003.
- Jonathan Katz, Yehuda Lindell: Introduction to Modern Cryptography, 2nd Edition. CRC Press, 2015.
- Douglas Stinson, Maura Paterson: Cryptography – Theory and Practice. CRC Press, 2018.
- Dan Boneh, Victor Shoup: A Graduate Course in Applied Cryptography.
- Mike Rosulek: The Joy of Cryptography.
- Ross Anderson: Security Engineering, Wiley Publishing, 2008.
- Martin Mareš: Algoritmy okolo teorie čísel (in Czech).
- Ivan Ristić: Bulletproof SSL and TLS, Feisty Duck Publishing, 2017.