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

This page is maintained by Martin Mareš