Introduction to cryptography

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

Lectures are scheduled on Wednesdays from 14:00 in S8.

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
9. 10. 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, session IDs, signatures. Know your enemy. Basic types of cryptographic attacks. Security level. Puzzle: How to toss a coin over a phone call?
16. 10. 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). Commitment using hash functions.
23. 10. 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, key schedule, critique, work-arounds (3-DES). Similarly for AES a.k.a. Rijndael. Puzzle: Why is the security level of 2-DES only 57 bits?
30. 10. How to (mis)use a block cipher: padding, modes ECB, CBC, OFB, and CTR; ciphertext stealing. Information leaks in CBC and OFB/CTR. Padding oracle attacks on CBC. Stream ciphers: LFSR-based constructions, Trivium.
6. 11. Stream ciphers: RC4, ChaCha20. Hash functions: requirements, Merkle-Damgård construction by iterating compression function. How to obtain a compression function: Davies-Meyer construction from a block cipher, MD5, SHA-1, SHA-2. Sponge functions: principle and analysis for random permutations.
13. 11. Sponge functions: Keccak, SHA-3, SHAKE-n and others. Birthday attacks on hash functions. Parallel hashing: Merkle trees, Sakura. Symmetric signatures (MACs): construction from hash functions (KMAC and HMAC), different ways of combining a MAC with a cipher. CBC-MAC.
20. 11. Information-theoretic MAC from 2-independent linear functions or from polynomials; practical applications: GCM mode, Poly1305. 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.
27. 11. 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. Chinese remainder theorem and its constructive version. Computing Euler's function. Factoring vs. primality testing. Fermat and Rabin-Miller tests, Carmichael numbers, a note on Agarwal's deterministic test. Generating large primes.
4. 12. More number theory: Multiplicative group is cyclic, discrete logarithms, how to find a generator. Discrete square roots, Legendre and Jacobi symbols. RSA cipher: Definition, acceleration tricks, effects of computational errors. Properties of RSA: commutativity, key swap, 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, one message encrypted by multiple keys.
11. 12. Semantic security: RSA preserves Jacobi symbol, but determining the lowest-significant bit or the half of the interval is hard. RSA padding and Bleichenbacher attack. Diffie-Hellman key exchange, signing the result/protocol, quadratic residues and (non)uniformity, problems with subgroups, DH in general groups. ElGamal cryptosystem and its derivation from DH. Remarks on ElGamal signatures, DSA, consequences of weak random numbers, deterministic DSA, and elliptic curves.
18. 12. Implementation issues: how to not develop software, various kinds of side channels, storing and destroying secrets. Handling passwords: hashing, salting, key derivation functions (PBKDF2). Interactive authentication: the SCRAM protocol. DNSSEC: introduction.
8. 1. Due to my illness, the lecture was cancelled. If you understand Czech, please view the video recording from previous year. Otherwise please ask for study materials. DNSSEC: details. Kerberos. Verifying identity: directory services, certification authorities, trust on first use, web of trust. The SSL/TLS protocol: cipher suites, record protocol, handshake protocol, alert protocol, types of key exchange, session resume, re-negotiation, and a collection of attacks. The Internet PKI: X.509, certification authorities and their behavior.

Exams

Exam dates are listed in SIS, please sign up there. If no date suits you, let me know and we can arrange another one. If you want to consult anything before the exam, feel free to ask.

You are expected to know the theory presented at the lecture (constructions, theorems, and proofs) and use it to analyse (i.e., break) simple protocols.

Sources

This page is maintained by Martin Mareš