Introduction to cryptography

I teach Introduction to cryptography [NDMI100] in the winter semester of 2023/2024. The lecture will cover the basics of both theoretical and practical cryptography, focusing on protocols currently used on the Internet.

Lectures will be on Thursdays from 12:20 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
22. 2. Cryptographic primitives: symmetric and asymmetric ciphers, hash functions, random generators. Protocols and roles. Kerckhoffs principle. Simple protocols: multi-party communication, signatures (symmetric and asymmetric) hybrid ciphers, challenge-response authentication. Designing an auction protocol: padding, nonces, sequence numbers, signatures, session IDs. video
29. 2. Basic types of cryptographic attacks. Security level. Know your enemy. Different kinds of "Birthday attacks". One-time pad and Vernam's cipher. Perfect security and its limits. Secret sharing and threshold schemes (construction with polynomials).
Exercise: How to toss a coin over a phone call? 		video
7. 3. Introduction to symmetric ciphers. Block ciphers: trivial examples, an attempt to define security. General constructions: iterated ciphers, substitution-permutation networks, Feistel networks. DES: history, structure, critique, work-arounds (3-DES). AES a.k.a. Rijndael: history, structure, critique.
Exercise: Why is the security level of 2-DES only 57 bits?
Further reading:: EFF DES cracker, details of AES. 		video
14. 3. How to (mis)use a block cipher: padding, modes ECB, CBC, CTR. Information leaks in CBC and CTR modes. Padding oracle attacks on CTR and CBC. Stream cipher sketches: LFSR-based constructions, eSTREAM project, Trivium.
Further reading: Trivium, ChaCha20, ciphertext stealing.
Illustrations: Block cipher modes (plaintext, ECB, CBC), visual secret sharing (layer 1, layer 2, both layers put together), 		video
21. 3. There will be no lecture.
28. 3. More stream ciphers: RC4, ChaCha20. Hash functions: requirements, Merkle-Damgård construction by iterating compression function, length extension attacks. 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. Practical hash functions: MD5 (broken), SHA1 (broken), SHA2, and SHA3 (sketch). video
4. 4. Sponge hashes: analysis for random permutations, Keccak, SHA3-n, SHAKE-n. Parallel hashing: Merkle trees and Sakura. 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
11. 4. 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
18. 4. 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, note on Agarwal's deterministic test. Generating large primes. Multiplicative group is cyclic, discrete logarithms, how to find a generator. Discrete square roots, Euler's criterion. video
25. 4. Plan: RSA cipher: Definition, acceleration tricks. Properties of RSA: swapping roles of keys, 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, effects of computation errors. Semantic security: RSA preserves Jacobi symbol, but determining the lowest-significant bit or the half of the interval is hard. RSA padding and a note on Bleichenbacher attack. RSA versus factoring.

Sources

This page is maintained by Martin Mareš